Manipulate B-Trees with your NES/Famicom controller. This is basically an implementation of COW-friendly B-Trees in pure 6502 assembly, with a little UI on top of it just to showcase it. ## The "game" The "game" is just a file explorer. Use the arrow keys to go up/down the list, and press A or Start to edit one of the files. There's also the option to create a new file. Press A or Start and it will prompt you to give it a unique name. With that, a file will be created and you will jump into edit mode. You can edit the file currently selected with the following button mapping: - B: change the character. - A: write the character in place. - Arrows: move around the document. - Start: save the file. - Select: go back to the file explorer. ## Internal design ### The data structure The main data structure is a COW-friendly B-tree (just like filesystems like [btrfs](https://btrfs.readthedocs.io/en/latest/)). You can read all about them [here](https://btrfs.readthedocs.io/en/latest/dev/dev-btrfs-design.html). To sum things up, these are B+-trees which: 1. Are updated top-down. 2. Leaf nodes are not chained. 3. Storage management is done via delayed reference counting. Here we have the invariant that a node has between 2 to 5 elements before it gets split or merged. When a modification happens, it's done top-down, and all modified elements are copied in a new location: the update is not done in-place. ### On top of the NES/Famicom The storage is covered via the 8KB battery-backed PRG-RAM that some chips allowed. In particular, here the MMC1 chip is being used just because it's the one that allows for this and it's simple enough. This chip allows for having a swappable bank, and here's where I've written my code, inside of the "LIBTREE" segment and on the `lib.s` file. There is no good reason to have the library into another segment, but it felt like a good way to have separation of concerns. In the context of operating systems, we would be manipulating at the page level. Out of simplicity here the same is done, the size of which will be the one native to the 6502 platform: 256B. Hence, on PRG-RAM we have 32 pages in total. ## But, why? Just for fun :) ## License Released under the [GPLv3+](http://www.gnu.org/licenses/gpl-3.0.txt), Copyright (C) 2026-Ω Miquel Sabaté Solà.