Storing Text — Buffers of Lines

The emulator half of the course is done: you can put a device in raw mode, decode what comes in, and control what goes out. The remaining lessons build the thing that lives inside the terminal: a text editor. And an editor's first decision — the one everything else leans on — is how to store the text being edited.

The design space (worth ten minutes of your life)

One flat buffer. The file as a single char*. Reading is trivial; inserting a character at position k means shifting everything after k. Type at the top of a 10 MB file and every keystroke is a 10 MB memmove. Fine for a config-file editor, embarrassing beyond that.

A gap buffer. One flat buffer with a hole at the cursor: insertions fill the hole (O(1)); moving the cursor moves the hole. Elegant, cache-friendly, and famously what Emacs uses. Weakness: edits far from the gap pay to relocate it, and multi-cursor / multi-view scenarios fight over where the hole lives.

A rope / piece table. Trees of text chunks; edits touch O(log n) nodes. This is what heavyweights use (VS Code: piece table; xi: rope) because it stays fast at gigabyte scale and makes undo nearly free (old pieces are the history). The price is real complexity — balancing, iterators, invariants.

An array of lines. The file as struct line* — each line its own heap string. Inserting a character shifts one line's bytes, not the file's. Inserting a line shifts an array of pointers (8 bytes each), not text. Newline handling becomes structural instead of textual. This is what vi's family and kilo use, it matches how an editor renders (by lines!), and its worst case — one pathological million-character line — is a case real editors handle badly too.

We take the array of lines. It's the sweet spot of simplicity-to-capability, and its failure modes are honest.

struct line {
    char *text;   /* heap-allocated, NUL-terminated       */
    int   len;    /* strlen(text) — cached, kept in sync  */
};

struct editor {
    struct line *lines;   /* growable array                */
    int nlines;
    int cap;              /* allocated slots               */
    /* cursor, viewport, file state ... (coming lessons)  */
};

We keep lines NUL-terminated and cache len. The NUL keeps every str* function and %s format usable; the cached length avoids strlen in every loop. The cost is one invariant to maintain: whoever edits text fixes len. Centralize edits in a few functions and the invariant holds itself.

The four structural edits

Everything an editor does to text decomposes into four operations. (Notice each is "memmove + bookkeeping" — the craft is in the bookkeeping.)

Insert a char into a line at column c: grow the allocation by one, shift the tail right (len - c + 1 bytes — the +1 drags the NUL along), drop the char in, bump len.

Delete a char from a line at column c: shift the tail left, shrink len. (Shrinking the allocation is optional; nobody does.)

Split a line at column c — the Enter key: the text right of c becomes a brand-new line inserted below; the current line truncates to c. Inserting into the middle of the lines array is the same shift-right dance one level up, on struct line values.

Join two lines — Backspace at column 0, or Delete at end-of-line: append line n+1's text onto line n, then remove slot n+1 from the array (shift-left) and free the removed line's text — this is the classic use-after-free / double-free hazard of the whole structure. Join is where editor memory bugs go to be born; write it once, carefully, and test it hard.

Delete-vs-Backspace, precisely, because every editor user's fingers know the difference even if they've never said it aloud:

• Delete removes the character at the cursor; the cursor does not move. At end of line, it joins the next line up into this one.
• Backspace removes the character before the cursor; the cursor moves left. At column 0, it joins this line onto the previous one — and the cursor lands at the join seam (the old end of the previous line).

Growth and the amortized array, reprised

The lines array grows like your abuf: double cap when full, realloc through a temporary. One subtlety unique to this struct: realloc may move the array, so never cache a struct line* pointer across an insertion. (The bug this footnote prevents costs an afternoon. Cheap at the price.)

Run the numbers to see why doubling matters here too: loading a 100,000-line file line-by-line with grow-by-one does ~5 billion element-copies (N²/2); with doubling, ~200,000 (the geometric series sums to about 2N). That's the difference between "instant" and "why is my editor frozen".