Most of my career I’ve been working on a text editor product in either a hobby or professional capacity. Years ago I had an idea to combine a B+Tree with a PieceTable and put together a quick prototype. However, it didn’t do the nasty part which was removal and compaction of the B+Tree (so just another unfinished side-project).
Now that we’re between GNOME cycles, I had the chance to catch up on that data structure and finish it off.
Just for a bit of background, a B+Tree is a B-Tree (N-ary tree) where you link the leaves (and often the branches) in a doubly-linked list from left-to-right. This is handy when you need to do in-order/reverse-order table-scans as you don’t need to traverse the internal nodes of the tree. Unsurprisingly, editors do this a lot. Since B+Trees only grow from the root, maintaining these linked-lists is pretty easy.
And a PieceTable is essentially an array of tuples where each tuple tells you the length of a run of text, what buffer it came from (read-only original buffer or append-only change buffer), and the offset in that buffer. They are very handy but can become expensive to manage as you gain a lot of changes over time. They are fantastic when you want to support infinite undo as you can keep an append-only file for individual changes along with one for the transaction log. You can use that for crash recovery as well.
This augmented B+Tree works by storing pointers to children branch-or-leaves along with their combined run-length. This is handy because as you mutate runs in the leaves, you only need to adjust lengths as you traverse back up the tree.
Another bit of fun trickery when writing B-trees of various forms is to break your branches-or-leaves into two sections. One section is for the items to be inserted. On the other, you have a fixed array of integers. After you insert an item into a free slot, you update a linked list of integers (as opposed to pointers) on the other end. Doing so allows you to do most inserts/removals in O(1) once you know the proper slot and avoid a whole series of memmove()s. Scanning requires traversing the integer linked-list instead of your typical for (i=0; i<n_items; i++) scenario. Easily resolved with a FOREACH macro.
Anyway, here it is, and it seems to work. Finally I can move on from having that bit of data-structure on my mind.