25年前のテキストエディタの設計技法


テキストエディタなので行の挿入・削除などが頻繁に行われるわけだが、行の挿入や削除によって大きなメモリブロックのコピーをするわけにはいかない。ゆえに、各行を双方向linked listで持っておいて削除・挿入時にメモリブロックのコピーは極力発生しないようにする。


まあ、linked listでなくて、各行へのポインタだけ持ってるような実装でもいいのだが、その場合行削除するときにそのポインタ配列の要素のremoveに伴なうメモリブロックのコピーが発生するのでそれはそれでレスポンスの低下につながるのである。


次に、行を削除した場合だが、その削除した行のデータが存在していたメモリブロックを永久に使わないような実装だともったいないのでここを再利用しなければならない。これは、バックグラウンドで少しずつ前方に詰めていく作業を行う。(次図)



ちょっとこの図ではわかりにくいかも知れないがGCは、1行目から順番にlinked listを辿っていく。行の終端は'\0'で終わっていることは保証されているので、この図で4行目まできたときに、4行目の行頭の1番地手前のメモリが'\0'でなければここは削除された行であることがわかるのでそのさらに手前にある'\0'をスキャンして(これは2行目の最後の'\0'で見つかる)、4行目を中身を2行目の末尾の直後に移動させる。


いま風の言葉で言うと、incremental GCである。とても簡素な実装ではあるが。


25年も昔のプログラムですらこれくらいのことは最低限やっていたのだ。