こんにちは。次に書こうと思ってた内容ゆえ、更に横から割り込み^^;

> EmacsもSwingも知らずに尋ねますが、GapBuffer中の位置、ということは、インデックスですよね？
> 各行がインデックスを持っていると、一文字挿入しただけで、移行の行が持っている開始位置情報全てを更新(+1)しないといけなくないですか？

開始位置情報は論理的なインデックスでなくて、物理的なインデックスを持ちます。例えば
[abcd][ギャップが8個][efgh]
という内容の時に文字"f"の位置を指すマーカーは、ギャップも含めた
配列先頭からのインデックス、つまり13で表します。
こうすると、ギャップがfの後ろに移動するような操作をするまでは
位置情報を更新する必要がありません。（YTさんがはてなで書かれてた、
「各細切れ要素へのポインタ＋その細切れ要素内での位置」という構造と要するに同じことだと思います。）

でもって、ギャップが動いたときに位置情報の更新が必要になるマーカーって言うのは
移動時にmemcpyされた要素を指すマーカのみなので、その個数はギャップ移動範囲に比例します。
ので、マーカを加えたせいでギャップバッファの処理の計算量のオーダが
落ちるようなこともありません。

Emacsのソースは読んだことないのですが、swingはそんな感じでした。