Re:Text Showdown: Gap Buffers vs. Ropes
by IshKebab on Tuesday October 10, 2023 @02:18AM
(#37829044)
You can possible use an array of (heap allocated) ring buffers. I heard about that data structure a while ago and it is clever but I have never seen anyone use it.
It means an insertion anywhere just involves M character moves where M is the number of ring buffers.
The data layout won't quite be as nice as a gap buffer (2 chunks), instead you get 2*M chunks. But if you make your ring buffers like 10MB it's probably fine.
Re:Text Showdown: Gap Buffers vs. Ropes
by funcDropShadow on Wednesday October 11, 2023 @07:34AM
(#37843204)
> they wouldn't help with the resizing latency
Could'nt you avoid resizing by massively over allocating in the first place? A decent OS, hint Linux, would only map pages to the allocated memory pages once they are touched.
That is a really cool idea! I actually tried implementing that. However I gave up because the code became quite a bit more complex, but it would totally be possible! That being said, multiple gaps would only help the "move gap" latency, they wouldn't help with the resizing latency. The later is both less predictable and much higher then moving the gap. Also when you need to coalesce the text for searching you would loose all your gaps.