Gap buffers

Tim Bray updated an old piece on binary search this morning — I missed it the first time around, so I was glad that it popped up in my blog reader. Tim’s taking some flak about data abstraction from people who don’t have his experience in high-performance environments, but what got my attention most was his mention of using gaps in a long array to provide efficient updates.

It turns out that this technique, called a gap buffer [wikipedia], is one of the cornerstones of text editors like Gnu Emacs. I’ve been using Emacs for 20 years and have contributed to the main distribution (see derived.el), but never bothered to look at the C code long enough to discover this particular technique. There’s surprisingly little information online — if anyone’s ever bothered to do testing for the optimum gap size, etc., it’s not showing up in Google — but it’s still nice to experience the joy and excitement of a new (to me), simple algorithm that solves a common problem well.

Does anyone have pointers to more detailed research on gap buffers? It seems to me that they’d have applications far beyond text editing, including (perhaps) storing compiled tree data (aka binary xml) on disk.

About David Megginson

Scholar, tech guy, Canuck, open-source/data/information zealot, urban pedestrian, language geek, tea drinker, pater familias, red tory, amateur musician, private pilot.
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

One Response to Gap buffers

  1. You might enjoy Simon Tatham’s “An Efficient Data Structure For A Hex Editor”:
    http://www.chiark.greenend.org.uk/~sgtatham/tweak/btree.html

Comments are closed.