gapbuffer

A gap buffer is a simple, array-based data structure used to store and edit text in many text editors. It represents the document as a single contiguous array with a reserved, unused region called the gap at the current cursor position. The text before the gap and the text after the gap together comprise the document content, while the gap holds characters that have not yet been inserted. The gap is defined by two indices: gap_start and gap_end, marking the beginning and end of the unused space.

Edits occur by moving the gap to the desired position and then filling or enlarging it. Moving the gap involves shifting characters across the gap so that the gap sits at the new cursor location; this cost is proportional to the distance the gap must travel. Insertion is cheap when there is space in the gap: a character is written into the gap and the gap’s size decreases by one. Deletion simply increases the gap’s size by removing a character near the gap. If the gap becomes full, the underlying array is resized to make a larger gap, and the existing text is copied accordingly to maintain the invariant.

Complexity in a gap buffer depends on the operation. Insertion and deletion near the gap are O(1) amortized, while moving the gap across a long distance costs O(distance). The approach is memory-efficient and offers good cache locality, but performance can degrade for edits far from the current cursor or for very large documents, where alternatives like ropes or piece tables may perform better.

Gap buffers are a classical technique used in several editors, including Emacs in its early implementations, and remain a core, uncomplicated option for localized text editing.