Gap buffer
From Wikipedia, the free encyclopedia
A gap buffer is a data structure used to store long arrays compactly, while still allowing efficient insertion and deletion operations, provided that the operations are clustered near the same location. Gap buffers are especially common in text editors, where most changes to the text occur at or near the current location of the cursor. The text is stored in a large buffer in two contiguous segments, with a gap between them for inserting new text. Moving the cursor involves copying text from one side of the gap to the other (sometimes copying is delayed until the next operation that changes the text). Insertion adds new text at the end of the first segment. Deletion increases the size of the gap.
The advantage of using a gap buffer over more sophisticated data structures (such as linked lists) is that the text is represented simply as two literal strings, which take very little extra space and which can be searched and displayed very quickly.
The disadvantage is that operations at different locations in the text and ones that fill the gap (requiring a new gap to be created) require re-copying most of the text, which is especially inefficient for large files. The use of gap buffers is based on the assumption that such recopying occurs rarely enough that its cost can be amortized over the more common cheap operations.
A gap buffer is used in most Emacs editors.
[edit] Example
Below are some examples of operations with buffer gaps. The gap is represented pictorially by the empty space between the square brackets. This representation is a bit misleading: in a typical implementation, the endpoints of the gap are tracked using pointers, and the contents of the gap are ignored; this allows, for example, deletions to be done by adjusting a pointer without changing the text in the buffer.
Initial state:
This is the way [ ]out.
User inserts some new text:
This is the way the world started [ ]out.
User moves the cursor before "started"; system moves "started " from the first buffer to the second buffer.
This is the way the world [ ]started out.
User adds text filling the gap; system creates new gap:
This is the way the world as we know it [ ]started out.
