Text Editor Data Structures: Gap Buffers, Ropes, and Piece Tables
A deep dive into how the editors you use every day actually store and manipulate text — and why it's one of the most underrated problems in systems programming.
Introduction: Why This Problem Is Hard
On the surface, a text editor sounds trivial to implement. You have some text, the user types characters, you show it on screen. A first-year CS student might reach for a std::string or a char[] and call it a day.
That works — right up until you try to open a 50 MB log file, or edit a document with 10,000 lines, or implement multi-level undo, or support multiple cursors. Then the cracks appear immediately. The naive array approach requires shifting potentially millions of bytes on every single keystroke. At 60 keystrokes per minute across a large file, that's catastrophic.
So the question becomes: what data structure lets you efficiently insert, delete, and navigate arbitrary positions in a large text document?
This is not a new question. It was a pressing research topic in the 1970s and 1980s when the first serious text editors were being built, and the solutions developed then — the gap buffer, the rope, and the piece table — are still what production editors use today. VS Code, Emacs, Vim, Neovim, and Word all use variants of these structures. Understanding them gives you a window into the design tradeoffs at the heart of systems programming.
This post covers all three in depth: the theory, the implementation in C, the edge cases, and the real-world tradeoffs. By the end you'll understand not just what they are but why they were designed the way they were.
The Naive Approach and Its Problems
Before jumping to the solutions, it's worth spending a moment on why the obvious approach fails. This makes the design decisions of the real structures feel inevitable rather than arbitrary.
The Simple Array
If you store text as a contiguous array of characters, operations look like this:
// Insert character c at position pos in buffer of length len
void naive_insert(char *buf, int *len, int pos, char c) {
// shift everything from pos to the end one slot to the right
memmove(buf + pos + 1, buf + pos, *len - pos);
buf[pos] = c;
(*len)++;
}For a 1 MB file with a cursor in the middle, that memmove is copying 500,000 bytes. Every. Single. Keystroke. At interactive editing speeds this is perceptible lag. At 10 MB it's genuinely painful. At 100 MB it's unusable.
Deletion is symmetrical — you shift everything left. Neither operation is O(1).
The Linked List of Characters
A linked list fixes insert and delete: O(1) once you have a pointer to the right node. But finding that node requires traversing from the head — O(N). And the constant factors are brutal: each character requires a heap allocation with pointer overhead. For a 1 MB file you have ~1 million heap allocations, each of which is probably 32–64 bytes due to allocator metadata. That's 32–64 MB of memory for 1 MB of text, with terrible cache locality because each node is scattered across the heap.
The Linked List of Lines
Many early editors (and Vim/Neovim today) compromise: store text as a linked list of lines, where each line is a small char array. This is much more cache-friendly than per-character nodes, and inter-line navigation is still O(line count). Within a line, inserts and deletes still require shifting, but lines are usually short so the shifts are small.
The weakness appears on pathological inputs: a minified JSON or JavaScript file where the entire content is a single line. That line becomes a huge array and you're back to the naive case.
The three structures we'll study solve these problems in fundamentally different ways.
1. The Gap Buffer
Conceptual Foundation
The gap buffer was developed at Xerox PARC in the 1970s and is one of the oldest purpose-built editor data structures. Its key observation is simple: most editing happens near the cursor. People type characters one after another. They backspace locally. They paste a block of text. They rarely jump from the very beginning of a document to the very end on every other keystroke.
Given that observation, why not design a structure that's extremely fast near the cursor and merely acceptable everywhere else?
The gap buffer does exactly this. It's a single contiguous array with a hole — the gap — sitting right where the cursor is. The gap is reserved empty space. When you type, characters fill the gap from its left edge. When you move the cursor, the gap moves with it by physically shifting text within the array.
Initial state (cursor at position 5):
[ H | e | l | l | o | _ | _ | _ | _ | w | o | r | l | d ]
0 1 2 3 4 5 6 7 8 9 10 11 12 13
^gap_start ^gap_end
(cursor is here)
After typing 'X':
[ H | e | l | l | o | X | _ | _ | _ | w | o | r | l | d ]
^gap_start ^gap_end
(gap shrank by 1)
After typing 'Y':
[ H | e | l | l | o | X | Y | _ | _ | w | o | r | l | d ]
^gap_start ^gap_endMoving the Cursor
Moving the cursor requires moving the gap. If the new cursor position is to the left of the current gap start, we shift text from just before the gap rightward into the gap. If the cursor moves right, we shift text from just after the gap leftward into the gap.
Before cursor move (cursor at 5, moving to 2):
[ H | e | l | l | o | _ | _ | _ | w | o | r | l | d ]
^gs ^ge
After moving cursor to 2 (shift 'llo' to the right):
[ H | e | _ | _ | _ | l | l | o | w | o | r | l | d ]
^gs ^geThis shift is O(distance moved), which is the main cost. For typical editing patterns where the cursor moves a few characters at a time, this is negligible.
Growing the Buffer
When the gap shrinks to zero, you need more space. The standard strategy is to allocate a new buffer of double the size, copy the left part (before the gap) to the start of the new buffer, copy the right part (after the gap) to the end of the new buffer, and place the new (larger) gap in between. This is the same doubling strategy used by dynamic arrays, giving O(1) amortized insert.
Full C Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define INITIAL_GAP 16
#define GROW_FACTOR 2
typedef struct {
char *buf; // the raw storage array
int gap_start; // index of first gap slot
int gap_end; // index one past last gap slot (exclusive)
int capacity; // total allocated bytes
} GapBuffer;
/* ─── helpers ─── */
static inline int gap_size(const GapBuffer *gb) {
return gb->gap_end - gb->gap_start;
}
int gb_length(const GapBuffer *gb) {
return gb->capacity - gap_size(gb);
}
int gb_cursor(const GapBuffer *gb) {
return gb->gap_start; // cursor position == gap start
}
/* ─── create / destroy ─── */
GapBuffer *gb_new(void) {
GapBuffer *gb = malloc(sizeof(GapBuffer));
gb->capacity = INITIAL_GAP;
gb->buf = malloc(gb->capacity);
gb->gap_start = 0;
gb->gap_end = gb->capacity; // whole buffer is the gap
return gb;
}
GapBuffer *gb_from_string(const char *s) {
GapBuffer *gb = gb_new();
// We'll insert the string and then reset cursor to 0
while (*s) {
if (gap_size(gb) == 0) {
// inline grow (see below)
int new_cap = gb->capacity * GROW_FACTOR;
char *nb = malloc(new_cap);
int right = gb->capacity - gb->gap_end;
memcpy(nb, gb->buf, gb->gap_start);
memcpy(nb + new_cap - right, gb->buf + gb->gap_end, right);
free(gb->buf);
gb->buf = nb;
gb->gap_end = new_cap - right;
gb->capacity = new_cap;
}
gb->buf[gb->gap_start++] = *s++;
}
return gb;
}
void gb_free(GapBuffer *gb) {
free(gb->buf);
free(gb);
}
/* ─── grow: double capacity, preserve gap position ─── */
static void gb_grow(GapBuffer *gb) {
int new_cap = gb->capacity * GROW_FACTOR;
char *nb = malloc(new_cap);
// copy text left of gap
memcpy(nb, gb->buf, gb->gap_start);
// copy text right of gap to END of new buffer
int right_len = gb->capacity - gb->gap_end;
memcpy(nb + new_cap - right_len,
gb->buf + gb->gap_end,
right_len);
free(gb->buf);
gb->buf = nb;
gb->gap_end = new_cap - right_len; // gap end moves
gb->capacity = new_cap;
// gap_start unchanged; gap is now bigger
}
/* ─── move cursor to logical position pos ─── */
void gb_set_cursor(GapBuffer *gb, int pos) {
assert(pos >= 0 && pos <= gb_length(gb));
if (pos < gb->gap_start) {
// moving left: shift text[pos .. gap_start) rightward into gap
int delta = gb->gap_start - pos;
memmove(gb->buf + gb->gap_end - delta,
gb->buf + pos,
delta);
gb->gap_start -= delta;
gb->gap_end -= delta;
} else if (pos > gb->gap_start) {
// moving right: shift text[gap_end .. gap_end+delta) leftward into gap
int delta = pos - gb->gap_start;
memmove(gb->buf + gb->gap_start,
gb->buf + gb->gap_end,
delta);
gb->gap_start += delta;
gb->gap_end += delta;
}
}
/* ─── insert character at current cursor position ─── */
void gb_insert_char(GapBuffer *gb, char c) {
if (gap_size(gb) == 0)
gb_grow(gb);
gb->buf[gb->gap_start++] = c;
// gap shrinks by 1; cursor advances by 1
}
/* ─── insert a full string at current cursor ─── */
void gb_insert_str(GapBuffer *gb, const char *s) {
while (*s)
gb_insert_char(gb, *s++);
}
/* ─── backspace: delete character BEFORE cursor ─── */
void gb_delete_before(GapBuffer *gb) {
if (gb->gap_start > 0)
gb->gap_start--; // just expand the gap left
}
/* ─── delete key: delete character AFTER cursor ─── */
void gb_delete_after(GapBuffer *gb) {
if (gb->gap_end < gb->capacity)
gb->gap_end++; // expand the gap right
}
/* ─── random read: get char at logical position i ─── */
char gb_get(const GapBuffer *gb, int i) {
assert(i >= 0 && i < gb_length(gb));
if (i < gb->gap_start)
return gb->buf[i];
else
return gb->buf[gb->gap_end + (i - gb->gap_start)];
}
/* ─── flatten to a heap-allocated string ─── */
char *gb_to_string(const GapBuffer *gb) {
int len = gb_length(gb);
char *out = malloc(len + 1);
memcpy(out, gb->buf, gb->gap_start);
int right = gb->capacity - gb->gap_end;
memcpy(out + gb->gap_start, gb->buf + gb->gap_end, right);
out[len] = '\0';
return out;
}
/* ─── debug: visualise the raw buffer ─── */
void gb_dump(const GapBuffer *gb) {
printf("capacity=%d gap=[%d,%d) len=%d cursor=%d\n [",
gb->capacity, gb->gap_start, gb->gap_end,
gb_length(gb), gb_cursor(gb));
for (int i = 0; i < gb->capacity; i++) {
if (i == gb->gap_start) printf(" |GAP| ");
if (i >= gb->gap_start && i < gb->gap_end) {
printf("_");
} else {
printf("%c", gb->buf[i]);
}
}
printf("]\n");
}
/* ─── demo ─── */
int main(void) {
GapBuffer *gb = gb_from_string("Hello world");
printf("Initial: ");
gb_dump(gb);
// Move cursor to after "Hello" and insert ", beautiful"
gb_set_cursor(gb, 5);
gb_insert_str(gb, ", beautiful");
printf("After insert: ");
gb_dump(gb);
// Move to end and delete "world" (5 chars) via backspace
gb_set_cursor(gb, gb_length(gb));
for (int i = 0; i < 5; i++)
gb_delete_before(gb);
char *s = gb_to_string(gb);
printf("Final: \"%s\"\n", s);
free(s);
gb_free(gb);
return 0;
}Strengths and Weaknesses In Depth
Strengths:
Cache locality. The gap buffer is a single contiguous block of memory. When iterating through text (for rendering, syntax highlighting, searching), the CPU prefetcher can predict access patterns perfectly. This beats a rope or piece table by a wide margin for sequential read-heavy workloads.
Simplicity. The implementation above is about 120 lines of C. It's auditable, debuggable, and easy to reason about. There's no tree rebalancing, no pointer chasing, no memory fragmentation.
Insert/delete at cursor is genuinely O(1) amortized. With a gap of say 64 bytes, you can type 64 characters before needing a reallocation. Even when reallocation happens, the amortized cost is O(1) by the standard doubling argument.
Weaknesses:
Cursor teleportation is O(N). If your editor supports jumping to a search result on the opposite side of a large file, moving the gap across the entire buffer is slow. A 10 MB file with a cursor jump from position 0 to position 5,000,000 involves a
memmoveof 5 million bytes.Multiple cursors are awkward. A single gap buffer naturally models one cursor. Adding multi-cursor support (like VS Code's) requires either multiple gap buffers (one per cursor, which wastes space) or giving up on the gap buffer entirely.
The gap wastes space when empty. A file opened read-only still has a gap sitting somewhere consuming memory and complicating rendering logic.
Real-world use: GNU Emacs has used a gap buffer since Richard Stallman wrote the first version. The code in src/buffer.c is a direct descendant of that original implementation. Emacs proves that a gap buffer is entirely viable for serious, decades-long production use — the tradeoffs just need to be known and accepted.
2. The Rope
Conceptual Foundation
A rope is a binary tree where the leaves hold actual substrings and the internal nodes carry metadata — specifically, the total character count of the left subtree (called the weight). This weight is what makes navigation fast: you can find any character in O(log N) by walking the tree, going left when your target index is less than the current node's weight and right when it's greater.
The name comes from the physical metaphor: just as a thick rope is made by twisting together smaller strands, a rope data structure is built by joining smaller string pieces.
Inserting "Hello, beautiful world" built as a rope:
[weight=13, total=22]
/ \
[weight=7] [weight=9]
"Hello, " "beautiful"
|
[weight=6]
" world"
(weight of internal node = length of left subtree)Core Operations
Index(i): Walk down from root. At each internal node, if i < weight, go left. Otherwise, subtract weight from i and go right. At a leaf, return str[i].
Split(i): Divide the rope into two ropes at position i. Walk down to the split point splitting nodes as you go, collecting left and right fragments to reassemble into two valid ropes.
Concat(r1, r2): Create a new internal node with r1 as left child and r2 as right child. The weight is length(r1). This is O(1) — just pointer manipulation.
Insert(i, s): split(root, i) → create a leaf for s → concat(concat(left, leaf), right).
Delete(start, len): split(root, start) → split(right, len) → discard the middle → concat(left, remaining_right).
Rebalancing
After many splits and concatenations the tree can degenerate into a linked list (every node has one empty child). A degenerate rope has O(N) navigation instead of O(log N).
The standard solution is Fibonacci rebalancing, described in the original rope paper by Boehm, Atkinson, and Plass (1995). The idea: a rope of length N is "balanced" if its depth is no greater than log_φ(N) + 2 where φ is the golden ratio. To rebalance, collect all leaves in left-to-right order and rebuild the tree bottom-up in a balanced fashion. This is O(N) but only runs occasionally.
An alternative used in some implementations is weight-balanced trees, where you track subtree sizes and rotate when one subtree is more than twice the size of the other — similar to AVL or red-black tree rebalancing but based on character counts.
Full C Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/* ─── node types ─── */
typedef enum { ROPE_LEAF, ROPE_NODE } RopeType;
typedef struct Rope {
RopeType type;
// For ROPE_NODE:
struct Rope *left;
struct Rope *right;
int weight; // total chars in left subtree
// For ROPE_LEAF:
char *str;
int len;
} Rope;
/* ─── constructors ─── */
Rope *rope_leaf(const char *s, int len) {
Rope *r = calloc(1, sizeof(Rope));
r->type = ROPE_LEAF;
r->str = malloc(len + 1);
memcpy(r->str, s, len);
r->str[len] = '\0';
r->len = len;
r->weight = len; // leaf weight == its own length
return r;
}
static Rope *rope_internal(Rope *left, Rope *right) {
Rope *r = calloc(1, sizeof(Rope));
r->type = ROPE_NODE;
r->left = left;
r->right = right;
// weight = total characters in left subtree
r->weight = left ? rope_length(left) : 0;
return r;
}
/* forward declarations */
int rope_length(const Rope *r);
void rope_free(Rope *r);
/* ─── length ─── */
int rope_length(const Rope *r) {
if (!r) return 0;
if (r->type == ROPE_LEAF) return r->len;
return rope_length(r->left) + rope_length(r->right);
}
/* ─── free ─── */
void rope_free(Rope *r) {
if (!r) return;
if (r->type == ROPE_LEAF) {
free(r->str);
} else {
rope_free(r->left);
rope_free(r->right);
}
free(r);
}
/* ─── index: character at position i ─── */
char rope_at(const Rope *r, int i) {
assert(i >= 0 && i < rope_length(r));
while (r->type == ROPE_NODE) {
int llen = rope_length(r->left);
if (i < llen) {
r = r->left;
} else {
i -= llen;
r = r->right;
}
}
return r->str[i];
}
/* ─── concat two ropes ─── */
Rope *rope_concat(Rope *left, Rope *right) {
if (!left) return right;
if (!right) return left;
return rope_internal(left, right);
}
/* ─── split: divide rope at position i into (left, right) ─── */
typedef struct { Rope *left; Rope *right; } RopePair;
RopePair rope_split(Rope *r, int i) {
RopePair res = {NULL, NULL};
if (!r) return res;
if (r->type == ROPE_LEAF) {
// split this leaf's string
if (i <= 0) {
res.right = r;
} else if (i >= r->len) {
res.left = r;
} else {
res.left = rope_leaf(r->str, i);
res.right = rope_leaf(r->str + i, r->len - i);
rope_free(r);
}
return res;
}
// ROPE_NODE
int llen = rope_length(r->left);
if (i <= llen) {
// split falls in left subtree
RopePair sub = rope_split(r->left, i);
res.left = sub.left;
res.right = rope_concat(sub.right, r->right);
free(r); // free this node (not its children, they've been reused)
} else {
// split falls in right subtree
RopePair sub = rope_split(r->right, i - llen);
res.left = rope_concat(r->left, sub.left);
res.right = sub.right;
free(r);
}
return res;
}
/* ─── insert string s at position i ─── */
Rope *rope_insert(Rope *r, int i, const char *s) {
RopePair halves = rope_split(r, i);
Rope *mid = rope_leaf(s, strlen(s));
return rope_concat(rope_concat(halves.left, mid), halves.right);
}
/* ─── delete range [start, start+len) ─── */
Rope *rope_delete(Rope *r, int start, int len) {
RopePair first = rope_split(r, start);
RopePair second = rope_split(first.right, len);
rope_free(second.left); // discard deleted region
return rope_concat(first.left, second.right);
}
/* ─── flatten to string ─── */
static void rope_collect(const Rope *r, char *out, int *pos) {
if (!r) return;
if (r->type == ROPE_LEAF) {
memcpy(out + *pos, r->str, r->len);
*pos += r->len;
} else {
rope_collect(r->left, out, pos);
rope_collect(r->right, out, pos);
}
}
char *rope_to_string(const Rope *r) {
int len = rope_length(r);
char *out = malloc(len + 1);
int pos = 0;
rope_collect(r, out, &pos);
out[len] = '\0';
return out;
}
/* ─── debug: print tree structure ─── */
static void rope_print_tree(const Rope *r, int depth) {
if (!r) return;
for (int i = 0; i < depth * 2; i++) printf(" ");
if (r->type == ROPE_LEAF) {
printf("LEAF(%d) \"%s\"\n", r->len, r->str);
} else {
printf("NODE(weight=%d, total=%d)\n", r->weight, rope_length(r));
rope_print_tree(r->left, depth + 1);
rope_print_tree(r->right, depth + 1);
}
}
/* ─── substring extract ─── */
char *rope_substr(const Rope *r, int start, int len) {
// Split off what we need, flatten it, then put the rope back together.
// In production you'd avoid the splits; this is for clarity.
char *out = malloc(len + 1);
int pos = 0;
for (int i = start; i < start + len; i++) {
out[pos++] = rope_at(r, i);
}
out[pos] = '\0';
return out;
}
/* ─── demo ─── */
int main(void) {
Rope *r = rope_leaf("Hello world", 11);
printf("Initial tree:\n");
rope_print_tree(r, 0);
r = rope_insert(r, 5, ", beautiful");
printf("\nAfter inserting ', beautiful' at 5:\n");
rope_print_tree(r, 0);
r = rope_delete(r, 16, 6); // delete " world"
printf("\nAfter deleting ' world':\n");
rope_print_tree(r, 0);
char *s = rope_to_string(r);
printf("\nResult: \"%s\"\n", s);
free(s);
rope_free(r);
return 0;
}Why Ropes Are Used in Zed and xi-editor
The Zed editor (written in Rust) and the xi-editor use a rope as their primary text storage. The Rust ropey crate is the canonical reference implementation. The reasons are instructive:
Immutable sharing. In Rust, you can cheaply clone a reference to a subtree. Two rope states (before and after an edit) can share the unchanged subtrees — this is the same technique used by functional persistent data structures and gives you undo for free.
Parallel rendering. A rope's tree structure naturally partitions the text into independent chunks. Multiple threads can read different subtrees simultaneously without locking.
UTF-8 handling. A rope can store metadata at each node (character count, line count, UTF-8 byte count) making it fast to convert between byte offsets, character offsets, and line/column positions — a real requirement for any Unicode-aware editor.
3. The Piece Table
Conceptual Foundation
The piece table was described by J. Quentin Miller and M. D. Rowe in the 1980s and later popularized by the analysis in Charles Crowley's 1998 survey paper "Data Structures for Text Sequences". Microsoft Word uses a variant of it. VS Code adopted it in 2018 after a detailed analysis by Peng Lyu, whose blog post is worth reading.
The central insight is a reversal of the usual framing. Instead of asking "how do I efficiently mutate a buffer of text?", the piece table asks: "what if I never mutate the text at all?"
Two underlying buffers exist:
- Original buffer: the file's initial content, loaded at open time, never modified.
- Add buffer: a strictly append-only log of every new character ever typed or pasted. Once written, bytes are never changed.
The document's logical content is described by an ordered list of pieces, each being a tuple:
{ buffer: ORIGINAL | ADD, start: int, length: int }To read the document, iterate the piece list and for each piece, read length bytes from buffer starting at start. Concatenating those reads gives you the full document.
File just opened: "Hello world"
Original: [ H e l l o w o r l d ]
Add: [ ]
Pieces: [ {ORIG, 0, 11} ]
→ "Hello world"Now the user moves the cursor to position 5 and types , beautiful:
Original: [ H e l l o w o r l d ] (unchanged)
Add: [ , b e a u t i f u l ] (appended)
Pieces: [ {ORIG, 0, 5} ] → "Hello"
[ {ADD, 0, 11} ] → ", beautiful"
[ {ORIG, 5, 6} ] → " world"Nothing was moved in either buffer. The old piece {ORIG, 0, 11} was split into two pieces {ORIG, 0, 5} and {ORIG, 5, 6}, and the new piece was inserted between them. The modification cost is O(1) in the buffers; O(P) in the piece list where P is the number of pieces (bounded by the number of edits, not the file size).
Deletion in a Piece Table
Deletion never erases bytes from the buffers. It only modifies the piece list by shrinking, splitting, or removing pieces.
To delete the range [start, end):
- Find which piece(s) cover
startandend. - Trim the piece at
start(keep only the part beforestart). - Remove any pieces entirely within the range.
- Trim the piece at
end(keep only the part afterend).
Bytes in the add buffer that were "deleted" this way still sit there forever, orphaned. This is intentional — it enables undo.
Undo is a First-Class Citizen
Because neither buffer is ever mutated, undo is just restoring a previous piece list. After every edit, snapshot the piece list (which is small — typically a few hundred entries even in a long editing session). To undo, swap in the previous snapshot.
This is dramatically simpler than gap buffer undo (which requires recording inverse operations as a stack) or rope undo (which requires maintaining version history through tree operations). The piece table's immutability makes snapshots trivially cheap.
The Piece Tree: How VS Code Does It
The naive piece table stores pieces in a flat array. Inserting in the middle of the piece array requires O(P) shifting. For a long editing session with thousands of edits, P grows and this becomes a bottleneck.
VS Code's implementation (introduced in 2018, authored by Peng Lyu) stores pieces in a red-black tree keyed by character offset. This gives O(log P) insert, delete, and search. Each node in the tree additionally caches the line count of its subtree so that line-column to character-offset conversion is also O(log P).
This is a beautiful layering of data structures: a red-black tree of pieces, each piece pointing into one of two flat character buffers.
Full C Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
/* ─── constants ─── */
#define ORIG_CAP (1024 * 1024) // 1 MB original buffer
#define ADD_CAP (1024 * 1024) // 1 MB add buffer
#define MAX_PIECES 8192
typedef enum { BUF_ORIG, BUF_ADD } BufKind;
typedef struct {
BufKind kind;
int start; // byte offset into the named buffer
int length; // number of bytes
} Piece;
typedef struct {
/* ── the two immutable buffers ── */
char orig[ORIG_CAP];
int orig_len;
char add[ADD_CAP];
int add_len;
/* ── piece list (flat array for clarity) ── */
Piece pieces[MAX_PIECES];
int piece_count;
/* ── simple undo stack (snapshots of piece_count + pieces array) ── */
Piece undo_stack[32][MAX_PIECES];
int undo_counts[32];
int undo_top;
} PieceTable;
/* ─── utility ─── */
static const char *pt_raw(const PieceTable *pt, BufKind k) {
return k == BUF_ORIG ? pt->orig : pt->add;
}
static int pt_total_length(const PieceTable *pt) {
int n = 0;
for (int i = 0; i < pt->piece_count; i++)
n += pt->pieces[i].length;
return n;
}
/* ─── init ─── */
void pt_init(PieceTable *pt, const char *initial_text) {
memset(pt, 0, sizeof(PieceTable));
int len = strlen(initial_text);
assert(len < ORIG_CAP);
memcpy(pt->orig, initial_text, len);
pt->orig_len = len;
if (len > 0) {
pt->pieces[0] = (Piece){ BUF_ORIG, 0, len };
pt->piece_count = 1;
}
pt->undo_top = -1;
}
/* ─── save undo snapshot ─── */
static void pt_push_undo(PieceTable *pt) {
int top = (pt->undo_top + 1) % 32;
memcpy(pt->undo_stack[top], pt->pieces,
pt->piece_count * sizeof(Piece));
pt->undo_counts[top] = pt->piece_count;
pt->undo_top = top;
}
/* ─── pop undo snapshot ─── */
int pt_undo(PieceTable *pt) {
if (pt->undo_top < 0) return 0; // nothing to undo
memcpy(pt->pieces, pt->undo_stack[pt->undo_top],
pt->undo_counts[pt->undo_top] * sizeof(Piece));
pt->piece_count = pt->undo_counts[pt->undo_top];
pt->undo_top--;
return 1;
}
/* ─── append to add buffer, return start offset ─── */
static int pt_add_text(PieceTable *pt, const char *s, int len) {
assert(pt->add_len + len < ADD_CAP);
int start = pt->add_len;
memcpy(pt->add + start, s, len);
pt->add_len += len;
return start;
}
/* ─── find piece index + offset-within-piece for logical pos ─── */
static int pt_locate(const PieceTable *pt, int pos, int *off) {
int remaining = pos;
for (int i = 0; i < pt->piece_count; i++) {
if (remaining < pt->pieces[i].length) {
*off = remaining;
return i;
}
remaining -= pt->pieces[i].length;
}
// pos is at the very end of the last piece
int last = pt->piece_count - 1;
*off = pt->pieces[last].length;
return last;
}
/* ─── shift piece array to make room for `count` new pieces at `at` ─── */
static void pt_make_room(PieceTable *pt, int at, int count) {
assert(pt->piece_count + count <= MAX_PIECES);
memmove(&pt->pieces[at + count],
&pt->pieces[at],
(pt->piece_count - at) * sizeof(Piece));
pt->piece_count += count;
}
/* ─── remove pieces[from..to] (inclusive) ─── */
static void pt_remove_range(PieceTable *pt, int from, int to) {
int remove = to - from + 1;
memmove(&pt->pieces[from],
&pt->pieces[to + 1],
(pt->piece_count - to - 1) * sizeof(Piece));
pt->piece_count -= remove;
}
/* ─── insert string at logical position pos ─── */
void pt_insert(PieceTable *pt, int pos, const char *s) {
pt_push_undo(pt);
int slen = strlen(s);
int add_start = pt_add_text(pt, s, slen);
Piece np = { BUF_ADD, add_start, slen };
if (pt->piece_count == 0) {
pt->pieces[0] = np;
pt->piece_count = 1;
return;
}
int off, idx = pt_locate(pt, pos, &off);
Piece old = pt->pieces[idx];
if (off == 0) {
// insert BEFORE piece[idx]
pt_make_room(pt, idx, 1);
pt->pieces[idx] = np;
} else if (off == old.length) {
// insert AFTER piece[idx]
pt_make_room(pt, idx + 1, 1);
pt->pieces[idx + 1] = np;
} else {
// split piece[idx]: left | new_piece | right
Piece left = { old.kind, old.start, off };
Piece right = { old.kind, old.start + off, old.length - off };
pt_make_room(pt, idx + 1, 2);
pt->pieces[idx] = left;
pt->pieces[idx + 1] = np;
pt->pieces[idx + 2] = right;
}
}
/* ─── delete logical range [pos, pos+len) ─── */
void pt_delete(PieceTable *pt, int pos, int del_len) {
pt_push_undo(pt);
int end = pos + del_len;
int start_off, end_off;
int si = pt_locate(pt, pos, &start_off);
int ei = pt_locate(pt, end, &end_off);
// build replacement pieces for partial start/end pieces
Piece reps[2];
int rep_n = 0;
// left remnant of start piece
if (start_off > 0)
reps[rep_n++] = (Piece){ pt->pieces[si].kind,
pt->pieces[si].start,
start_off };
// right remnant of end piece
if (end_off < pt->pieces[ei].length)
reps[rep_n++] = (Piece){ pt->pieces[ei].kind,
pt->pieces[ei].start + end_off,
pt->pieces[ei].length - end_off };
// replace pieces[si..ei] with our remnants
int span = ei - si + 1;
// shift tail left to cover the removed span
memmove(&pt->pieces[si + rep_n],
&pt->pieces[ei + 1],
(pt->piece_count - ei - 1) * sizeof(Piece));
// copy remnants in
memcpy(&pt->pieces[si], reps, rep_n * sizeof(Piece));
pt->piece_count = pt->piece_count - span + rep_n;
}
/* ─── read character at logical position i ─── */
char pt_get(const PieceTable *pt, int i) {
int off, idx = pt_locate(pt, i, &off);
const Piece *p = &pt->pieces[idx];
return pt_raw(pt, p->kind)[p->start + off];
}
/* ─── flatten to string ─── */
char *pt_to_string(const PieceTable *pt) {
int total = pt_total_length(pt);
char *out = malloc(total + 1);
int pos = 0;
for (int i = 0; i < pt->piece_count; i++) {
const Piece *p = &pt->pieces[i];
const char *src = pt_raw(pt, p->kind) + p->start;
memcpy(out + pos, src, p->length);
pos += p->length;
}
out[total] = '\0';
return out;
}
/* ─── debug: dump piece list ─── */
void pt_dump(const PieceTable *pt) {
printf("Piece table (%d pieces, %d chars total):\n",
pt->piece_count, pt_total_length(pt));
for (int i = 0; i < pt->piece_count; i++) {
const Piece *p = &pt->pieces[i];
const char *src = pt_raw(pt, p->kind) + p->start;
printf(" [%d] %s start=%-4d len=%-4d → \"",
i, p->kind == BUF_ORIG ? "ORIG" : "ADD ",
p->start, p->length);
fwrite(src, 1, p->length, stdout);
printf("\"\n");
}
}
/* ─── demo ─── */
int main(void) {
PieceTable pt;
pt_init(&pt, "Hello world");
printf("=== Initial ===\n");
pt_dump(&pt);
pt_insert(&pt, 5, ", beautiful");
printf("\n=== After insert at 5 ===\n");
pt_dump(&pt);
pt_delete(&pt, 16, 6); // delete " world"
printf("\n=== After delete [16, 22) ===\n");
pt_dump(&pt);
char *s = pt_to_string(&pt);
printf("\nResult: \"%s\"\n\n", s);
free(s);
// demonstrate undo
pt_undo(&pt);
s = pt_to_string(&pt);
printf("After undo: \"%s\"\n", s);
free(s);
pt_undo(&pt);
s = pt_to_string(&pt);
printf("After second undo: \"%s\"\n", s);
free(s);
return 0;
}Expected output:
=== Initial ===
Piece table (1 pieces, 11 chars total):
[0] ORIG start=0 len=11 → "Hello world"
=== After insert at 5 ===
Piece table (3 pieces, 22 chars total):
[0] ORIG start=0 len=5 → "Hello"
[1] ADD start=0 len=11 → ", beautiful"
[2] ORIG start=5 len=6 → " world"
=== After delete [16, 22) ===
Piece table (2 pieces, 16 chars total):
[0] ORIG start=0 len=5 → "Hello"
[1] ADD start=0 len=11 → ", beautiful"
Result: "Hello, beautiful"
After undo: "Hello, beautiful world"
After second undo: "Hello world"Strengths and Weaknesses In Depth
Strengths:
Undo is structurally free. Unlike the gap buffer (which needs an inverse operation stack) or the rope (which needs tree versioning), the piece table only needs to snapshot its piece list. Piece lists are small — a typical editing session might produce at most a few thousand pieces. Snapshotting a few thousand integers is negligible.
Original content is never copied. When you open a 100 MB log file, the piece table reads it into the original buffer once and never touches it again. All edits operate only on the small piece list and the (much smaller) add buffer. Memory usage for the edit metadata is proportional to the number of edits, not the file size.
Clean separation of concerns. The immutable buffers make the structure easy to reason about and verify. There's no aliasing, no in-place mutation, no question of "which version of this byte is current."
Weaknesses:
The add buffer grows forever. Every typed character, including deleted ones, stays in the add buffer. For a very long editing session on a large file with lots of churn, the add buffer can grow significantly. In practice this is rarely a problem — the add buffer is bounded by the total number of characters ever typed, and sessions don't typically generate hundreds of megabytes of keystrokes.
Random access requires traversing the piece list. Getting the character at position
irequires walking pieces until you find which one containsi. With a flat array of pieces this is O(P). With VS Code's red-black tree it's O(log P).Cache behavior is less predictable than a gap buffer. Characters in the document might come from two different memory regions (original and add buffers). For sequential rendering this is fine; for more complex access patterns the two-buffer indirection adds overhead.
4. Neovim's memline: The Pragmatic Oddity
What It Inherited
Neovim's text storage comes directly from Vim, which comes from STEVIE (a portable vi clone from the late 1980s), which itself descended from Stevie by Tim Thompson. This lineage predates widespread knowledge of gap buffers and piece tables in editor engineering circles.
The result is a bespoke structure called memline — a line-oriented storage system that doesn't cleanly map to any of the three textbook structures.
The Architecture
PieceTable / Gap Buffer / Rope: character-granularity
memline: line-granularity
memfile (swap-backed file, for crash recovery)
└── memline (B-tree-like index of data blocks)
├── data block 0: "Hello\nWorld\nFoo\n" [3 lines packed]
├── data block 1: "Bar\nBaz\n" [2 lines packed]
└── ptr block: [index into data blocks]Multiple short lines are packed into data blocks (typically 8 KB each). A separate pointer block acts as an index, storing the first line number of each data block so you can binary-search to any line in O(log N) where N is the number of lines (not characters).
Within a data block, lines are stored contiguously with their lengths, so accessing line k within a block is O(number of lines in block), which is small (usually 10–100 lines per block).
The Scratch Buffer
For character-level edits within a single line, memline.c maintains a small scratch buffer where the current line is copied and edited in place. When the cursor moves to a different line, the scratch buffer is flushed back to its data block. This is conceptually similar to a gap buffer but scoped to a single line rather than the whole document.
The char* Assumption
The deepest architectural issue in Vim/Neovim is that virtually every function that operates on line content receives a char* — a pointer into the data block's memory — and assumes it can access the entire line by reading forward from that pointer.
This works perfectly for normal text. It fails catastrophically for:
- Minified JavaScript/JSON/HTML — entire file on one line → one
char*that's millions of bytes long - Binary files — null bytes terminate the
char*unexpectedly - Very long generated lines — SQL dumps, base64-encoded content, etc.
This is why Neovim (and Vim) can feel sluggish on minified files. The line-based data blocks handle inter-line navigation beautifully but degrade to array-shifting for intra-line edits on huge lines.
What Would a Rewrite Look Like?
A Neovim maintainer answered this directly in GitHub Discussions (issue #25647): a rope would be the natural successor, since the existing block tree structure already resembles a B-tree of chunks. The main obstacle is not the data structure change itself but the thousands of internal APIs that assume char* line semantics.
5. Side-by-Side Comparison
Operational Complexity
| Operation | Gap Buffer | Rope | Piece Table |
|---|---|---|---|
| Insert at cursor | O(1) amortized | O(log N) | O(log P) with tree |
| Insert far away | O(dist) gap move | O(log N) | O(log P) with tree |
| Delete | O(1) near cursor | O(log N) | O(log P) with tree |
| Random char access | O(1) | O(log N) | O(P) naive / O(log P) tree |
| Undo one step | O(op size) extra | O(op size) extra | O(1) snapshot swap |
| Iterate all text | O(N) | O(N) | O(N) |
| Memory overhead | One buffer + gap | Node pointers | Two buffers + piece list |
| Multi-cursor support | Awkward | Natural | Natural |
Qualitative Tradeoffs
| Dimension | Gap Buffer | Rope | Piece Table |
|---|---|---|---|
| Implementation complexity | Low | High | Medium |
| Cache friendliness | Excellent (contiguous) | Poor (pointer chasing) | Medium (two buffers) |
| Large file performance | Poor | Excellent | Excellent |
| Undo friendliness | Poor (needs extra work) | Medium (tree versioning) | Excellent (snapshot free) |
| Suited for | Small/medium files, Emacs-style editing | Huge files, parallel access | General purpose editors |
Real-World Usage
| Editor / Product | Data Structure |
|---|---|
| GNU Emacs | Gap buffer (src/buffer.c) |
| Vim / Neovim | Custom memline (line-based B-tree + scratch) |
| VS Code | Piece tree (red-black tree of pieces) |
| Microsoft Word | Piece table variant |
| Zed | Rope (Rust, using the sum_tree crate) |
| xi-editor | Rope (Rust, xi-rope crate) |
| Sublime Text | Custom (undisclosed, likely rope-like) |
| Helix | Rope (Rust, ropey crate) |
6. Building Your Own: Recommendations
For a Learning Project
Start with the gap buffer. It's small enough to hold completely in your head, it implements in an afternoon, and it teaches you the core tension between insert performance and seek performance. Add a simple undo stack that records (position, character, operation_type) tuples. You'll end up with something that could plausibly power a small terminal editor.
// A complete minimal editor in ~300 lines using a gap buffer
// is a classic systems programming exercise. Try it.For a Practical Editor
Use a piece table with a sorted piece list (or steal VS Code's piece tree). The undo story is so much better than the alternatives that it pays for itself immediately. The flat array implementation above is fine for files up to a few MB and editing sessions up to a few thousand operations. For larger scale, move the piece list into a balanced BST.
For High-Performance or Distributed Editing
Use a rope, ideally in Rust with the ropey crate which handles UTF-8, line indexing, and incremental rendering slices out of the box. The tree structure maps naturally to concurrent read access (different threads can hold references to different subtrees) and to CRDT-style collaborative editing (where operations are reordered and merged, which ropes handle gracefully due to their structural decomposition).
7. Further Reading
If this post gave you an appetite for more, these are the best next steps:
"Data Structures for Text Sequences" — Charles Crowley (1998). This is the canonical academic survey of the field. It covers gap buffers, piece tables, ropes, and several other structures with rigorous analysis. Available as a PDF from the University of New Mexico.
Peng Lyu's VS Code piece tree blog post — "Text Buffer Reimplementation" on the VS Code blog (2018). A practitioner's account of profiling the old line-array approach and redesigning it as a red-black tree of pieces. Excellent engineering writing.
"Ropes: an Alternative to Strings" — Boehm, Atkinson, Plass (1995). The original rope paper. Short and readable. Introduces Fibonacci rebalancing.
xi-ropecrate source —github.com/xi-editor/xi-editor,rust/rope/. Beautifully commented Rust implementation with UTF-8 metric tracking, line counting, and incremental diff support.ropeycrate —github.com/cessen/ropey. The most production-ready Rust rope. Used by Helix and others. The README has an excellent explanation of the B-tree-of-chunks design it uses (a hybrid between a traditional rope and a B-tree).Neovim
memline.c—github.com/neovim/neovim,src/nvim/memline.c. Worth reading if you want to understand how a 40-year-old architecture evolves under modern constraints.Emacs
buffer.c—github.com/emacs-mirror/emacs,src/buffer.c. The production gap buffer. Look for theBEG,GPT,Zmacros that define the buffer start, gap point, and end.
Conclusion
The gap buffer, rope, and piece table aren't just academic curiosities — they are the beating hearts of the editors that power billions of keystrokes every day. Each represents a different answer to the same hard question: how do you make editing feel instant regardless of file size or editing pattern?
The gap buffer bets on locality. The rope bets on tree structure. The piece table bets on immutability. All three bets pay off in their respective niches.
What makes this domain particularly rewarding to study is that the problems are real and the constraints are physical. Cache lines, memory allocation costs, branch misprediction — these aren't abstractions. They're the difference between an editor that feels snappy and one that lags. The data structures here were designed by people who measured, profiled, and iterated until the numbers were right.
If you've read this far, the next step is to write one. A gap buffer in 200 lines of C. A piece table that can load a real file and handle undo. A toy rope that you rebalance by hand. The theory only sticks when you've debugged it at 2am wondering why your cursor is off by one.
Go build something.