Comment by audidude
9 years 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.
No comments yet
Contribute on Hacker News ↗