ギャップバッファ

初めて見た構造なのでメモです。

http://www.kmonos.net/wlog/39.php#_2322040527
http://aiwww.main.eng.hokudai.ac.jp/~takty/program.html

なるほどなるほど。
現在編集しているあたりを差分として、線形配列の最後のほうに固めておいて、編集カーソルが移動したら書き戻す構造ですか。…という解釈でいいですか？
線形配列は一般的に言えば挿入、削除が遅いですが、数個移動させるだけでいい最後のほうはそうでもないので、賢い構造と思います。たまたま私が見たのがvectorの後ろを再利用してるだけで、データを前半と後半にわけてその間を編集して、また別の場所を編集する時はそこでわけ直して他をマージ…ってのが正しい解釈のようです。

ちなみにThebeでは、可変サイズのバッファを単方向リンクリストでつないだものを使ってます。最初は連続メモリですが編集が起きた位置で前後に切ってしまうわけです。ある程度(1kbだったか？)よりも細切れになってしまうようなら切らずに直接そこを書き換える方針です。ランダムアクセスでも、ユーザーが編集した地点のうち距離が近いものを除外した数だけリンクをたどれば到達できますので、まあまあじゃないかと思ってますが、Thebeの動作を見てればわかるように巨大なファイルには弱いです。

それとは別に、双方向リンクリストで行とかUTF16化済みデータとか色分けの管理を行っていますので、開くファイルの約3〜5倍強のメモリを消費してしまうのがなんとも。逐次UTF16化するようにすればメモリは節約できるでしょうが、速度が心配です。

CyberXに4MBとかのファイルを開くのが遅いと言われたときはうわーって感じでしたが、10MBぐらいは楽勝で扱えないとバイナリエディタを名乗れないかも…ですね。純テキストエディタのgreenpadと勝負しても仕方ないかもしれませんが、それにしたってthebeは遅すぎる…もっともこれは、むしろ色分けや改行の処理が遅いことがわかってます。肝心なのは、バッファより、そういうのも含めたトータルなデータ構造なんでしょうね…。

混乱を防ぐために書いておきます。
greenpadというのはk.inabaさんの高速なテキストエディタ。データはUTF-16で、ギャップバッファと呼ばれる構造で格納しているらしいです。読み書きに対応した文字コードが多いのが特徴で、私はブラウザのソース表示エディタに使わせていただいています。
thebeというのは私の鈍速なバイナリエディタ。データは無変換で、単方向リンクリストで管理しています。…で、言い訳ですが、テキストエディタ風の表示もできるというかそっちがメインな謎エディタですので、正直かなり無駄の多いことをしています。