3 ms·

I've been doing the same thing (implementing a text editor for fun) and settled on a data structure which is a hybrid rope+2-3 tree+B+tree+gap buffer. I don't k

I've been doing the same thing (implementing a text editor for fun) and settled on a data structure which is a hybrid rope+2-3 tree+B+tree+gap buffer. I don't know what to call it but maybe someone here has seen it before. Basically the idea is, the inner nodes are a 2-3 tree which track the size of each child like a rope does. The leaves are gap buffers of a fixed size (a few cache lines), which, when full, split into two like leaves of a B+tree. So you get the dense-ish packing of a gap buffer with the O(log n) performance guarantee of a 2-3 tree, while avoiding the potential linear copies associated with ropes and gap buffers. (I know this is overkill for a toy text editor but it wouldn't be a side project if it weren't!)

audidude 9y ago
I did something like this recently too. A b+tree w/ linked leaves containing piecetables in the leaf nodes. To avoid the memmove() costs it uses the right-edge of the leaf to keep a sorting queue so the operations are still O(1) inside the leaf. I still need to finish up deletions, but early performance numbers are showing similar/better than the RBTree approach while being much more cacheline/allocation friendly. Ultimately, I want to use this in a replacement for GtkTextBuffer/GtkTextView in gtk 4.x. https://github.com/chergert/pieceplustree https://github.com/chergert/pieceplustree