gap · 光标就位 · 扩容

gap buffer：跟着光标走的洞

朴素字符串的问题是空闲空间在文档末尾，而编辑发生在光标处。要把 $n/2$ 个字符往后挪一格，本质上是在把末尾那点空位一路运到光标附近。

gap buffer 的想法是：既然空位每次都要运过来，那就让它一直待在那儿。

1 · 洞

定义 1.1（gap buffer） 一块长度为 $c$ 的连续内存，被分成三段： $[0, g_s)$ 是正文的前半， $[g_s, g_e)$ 是gap（不属于正文的空闲区）， $[g_e, c)$ 是正文的后半。文档长度为 $c - (g_e - g_s)$ ，逻辑下标 $i$ 对应的物理槽是 $i < g_s$ 时的 $i$ ，否则是 $i + (g_e - g_s)$ 。

在 $g_s$ 处插入一个字符：写进 buf[gs]，gs 加一。既有内容一个字符也不动。删除 $g_s$ 之后的一个字符：ge 加一，洞往右吞掉一格，同样什么都不用搬。

前提是光标恰好在 $g_s$ 。这就是全部的代价所在。

2 · 光标移动

把洞从 $g_s$ 挪到 $p$ ，要把这两点之间的内容跨过洞搬到另一侧：向左移动 $k$ 格搬 $k$ 个字符，向右同理。搬移用一次 copyWithin 完成，是连续内存上最便宜的操作形式，但字符数摆在那里。

图 2-1 · gap buffer 的底层数组与洞的位置。可移动光标、插入删除，观察洞跨过内容时留在原处的残字，以及右上角累计搬移量的变化。

搬移之后，被跨过的那段内容在原处留着一份副本。洞里的这些残字不属于正文，toString() 只拼 $[0, g_s)$ 与 $[g_e, c)$ 两段。把 abcdefgh 的洞从末尾挪到下标 2，底层内容变成 abcdefcdefgh：中间的 cdef 就是刚被跨过的那四个字符留下的影子。Emacs 的实现同样不清洗 gap，写文件时按两段拼。

一次编辑会话里的光标移动次数远多于插入次数，但绝大多数移动只有几格。真正伤人的是「跳到文件开头」「跳到匹配的括号」这类大跳，它们各要一次全长搬移。

3 · 扩容

洞用完了就要换一块更大的内存。策略与动态数组一样：新容量取当前容量的两倍与「正文长度加所需空间加最小洞」的较大者，把前后两段正文各复制一次到新块的两端。

一次扩容搬走全部正文，摊还到之后的插入上是常数。1 MB 文档正中连续插入 1000 个字符的总搬移量是 1572880，拆成三笔看得更清楚：

阶段	搬移字符数	说明
第 1 次插入	524288	洞从文档末尾就位到正中
第 2 至 16 次	0	初始洞有 16 格，白拿
第 17 至 1000 次	1048592	洞用完，整体重排一次，之后再无搬移

这三笔的结构值得留意：真正与插入次数相关的那一项是 0。gap buffer 在单光标顺序输入下的边际代价确实是常数，全部开销都是一次性的就位与扩容。

建议 · 初始洞开多大是个纯工程取舍。开得小则扩容频繁，每次扩容搬全文；开得大则空文档也占一大块内存。Emacs 的默认值是 2000 字节量级，理由是它比一次连续输入的长度大一个数量级，而对整个进程的内存无关紧要。本系列引擎的默认值取 16，是为了让扩容在 lab 里几步就能看到。

4 · 两种光标轨迹

同一串 1000 次插入，只改光标轨迹，搬移量相差三个数量级。

图 4-1 · 四种光标轨迹下 gap buffer 的累计搬移量。可切换轨迹与文档规模，观察多光标轨迹的曲线是一条斜率恒定的直线。

1 MB 文档上的实测：

光标轨迹	搬移字符数	gap 搬移次数
单光标顺序输入	1572880	1
四处多光标轮流	446957421	1000
两端反复跳	1008181544	1000
随机位置	342887016	1000

两端反复跳的 10.08 亿已经与朴素字符串的 10.49 亿在同一量级。gap buffer 在这种负载下没有优势可言，它只是把「每次插入搬半篇」换成了「每次移动光标搬大半篇」。

多光标那一行尤其值得注意，因为它不是构造出来的极端情形。四个光标同时输入是现代编辑器的常规操作，而 gap buffer 只有一个洞，每次轮换都要把洞整个拖过去。要支持多光标只能开多个洞，那就退化成了 piece 列表的雏形。

警示 · 墙钟在这一页会说谎。本系列引擎最初把底层数组写成 string[]，200 次两端交替插入要跑 1897 毫秒；换成 Uint16Array 加 copyWithin 之后同一段是 14.9 毫秒，而搬移量一个字没变，仍是 202415160。快了 127 倍的是表示法，不是算法。这也是本系列一律用搬移量而非墙钟做横向对照的原因。

5 · gap buffer 的适用边界

回到评价维度那张表（见一个字符串不够用：编辑的代价账 §4），gap buffer 的得分是这样的：

随机访问是满分。逻辑下标到物理槽只差一次比较和一次加法，charAt 恒为一次访存，substring 至多跨洞取两段。这一点上它和朴素字符串一样好，而 piece table 与 rope 都要下降一棵树。

内存开销也很低。除了洞本身，没有任何每字符的额外结构；洞的大小是可控的常数。相比之下 rope 的每 64 个字符要挂一个结点。

行号查询是零分。缓冲里没有任何行的信息，lineStart(k) 只能从头扫。1 MB 文档单次查询平均扫 51 万个字符。真实的 gap buffer 实现都在旁边挂一张行表，而那张表在每次编辑后要维护，代价与本页讨论的东西不再是同一件事。

撤销也是零分。缓冲被原地改写，历史版本不留痕。Emacs 的 undo 靠一条独立的操作日志，那条日志与缓冲结构无关。

结论是 gap buffer 押注一件事：编辑高度集中在一处。这个假设在 1970 年代的编辑器里成立，在今天的多光标、多协作者、大文件场景里成立得越来越少。而下一页的 piece table 换了个押注方向。

6 · 参考文献

Finseth, C. A. (1991). The Craft of Text Editing: Emacs for the Modern World. Springer-Verlag.
Free Software Foundation. GNU Emacs Lisp Reference Manual, §Buffer Gap. gnu.org/software/emacs/manual.
Crowley, C. (1998). Data structures for text sequences, §5 (Gap Method). University of New Mexico, Technical Report.