ギャップ・バッファは，テキスト・エディタなどで用いられる，シーケンスを扱うデータ構造です．ここで公開するプログラムはK. Inaba氏の制作されたエディタ，GreenPadにおいて使われているギャップ・バッファをC++言語に含まれるSTLのvectorを使うように改造したものです．また，それをC言語のみで書き直したものも公開しています．両方ともNYSL（ライセンス）とします．
ギャップ・バッファはテキスト・エディタのテキスト・バッファなど，長く連なるデータを保持する際に用いられるシーケンス・コンテナです．局所的な要素の挿入，削除を頻繁にする場合に適したデータ構造です．双方向リスト（C++のlist，JavaのLinkedList）と可変長配列（C++のvector，JavaのArrayList）の両方の利点と欠点を持っています．
可変長配列と異なり，領域の中にギャップ(空白)を保持しています．そして，要素の挿入，削除時に，可変長配列のように対象位置以降の全要素を移動させるのではなく，ギャップの縮小と拡大に置き換えることで，効率化を図ります．なお，以下，各種操作の説明における図では「■」が要素を，「□」がギャップ(空白)を，「|(縦棒)もしくは◆」が操作対象位置を表します．
■や□のサイズ（バイト数）は目的に依存して決定されます．私が参考にしたいくつかのエディタでは，行を表す別のデータ構造のポインタが1つの要素として扱われていたり，1文字1文字が要素として扱われていたりしたようです．
下図のような16の要素があるギャップ・バッファの中央に要素を挿入するとします．
普通の配列なら，対象位置以降を1つ移動する（後ろにずらす）ことになりますが，ここでは，8つ移動します（下図）．こうして出来た空白領域をギャップと呼びます．このときだけはO(n)のコストがかかります．
そうして，出来たギャップの一番先頭に実際に挿入したい要素を入れます．すなわち，ギャップが1つ縮まることになります．挿入後は下図のようになります（ギャップは7つ分）．
下図のようにギャップのすぐ後(前)に要素を挿入するとします．
この場合はギャップの最後に要素を入れます．すなわち，ギャップの範囲が縮まることになります．ギャップを埋めただけなので，要素移動のコストはかかりません．
テキスト・エディタでは局所的に要素（文字）が挿入されることが多いので，多くの場合はこの「ギャップが挿入位置にあるとき」になります．
いままでとは違う位置(下図|の位置)にこれから挿入するとします．
まず，挿入位置にギャップを移動します．このとき，要素を4つ（挿入位置とギャップまでの間）しか移動していないことに注目してください．
実際に要素を挿入します（ギャップを要素で埋めます）．要素移動のコストがギャップを移動するだけなので比較的少なくて済みます．
下図のような15の要素があるギャップ・バッファの中央の要素を削除するとします．
普通のベクタであれば，削除後に出来た空白を埋めるため，削除位置以降を最後まで1つずらします．しかし，ここではそのままにして，出来た空白領域をギャップとします．こうすることで要素移動のコストがかかりません．
下図のようにギャップのすぐ後(前)の要素を削除するとします．
この場合，要素を一つ削除してギャップの範囲を一つ広げると完了します．ギャップを広げるだけなので要素移動のコストがかかりません．
いままでとは違う位置(◆)をこれから削除するとします．
まず，削除位置にギャップを移動します．このとき，移動した要素は2つ（削除位置とギャップまでの間）しかないことに注目してください．
実際に要素を削除して開いた部分をそのままギャップとします．要素移動のコストはギャップを移動する分だけなので比較的少なくて済みます．
以上が，私が2つほどソースを見て判断したギャップ・バッファの仕組みです．実際にアプリケーションに組み込んで期待した動きをしているので，それほど間違ってはいないと思います．しかしながら，ギャップの移動アルゴリズムはいろいろ考えられます．特に，全データを格納するメモリの再確保をどのタイミングで行うのか，それとギャップの確保を関連付けるのかどうか，あたりで方法がいくつかあるでしょう．