その１ Boundary Tagアルゴリズム
～ 不定長メモリブロックをリスト化 ～
Boundary Tagアルゴリズムは主に長さがバラバラのメモリブロックを一列に並べてリスト化する簡単な方法です。出典元は「D.
E. Knuth. The art of computer programming. Volume 1: Fundamental algorithms.
sec. cd. (Addison-Wesley. Reading, Mass. 1973) section 2.5.」という本…ですが、すいません、こんな歴史のある本は持ってません(-_-;。以下はあちこちのWebサイトから集めた情報を元にしています。
① お隣さんへジャンプするには？
例えば、あるメモリブロックを次のように区切ったとしましょう：
この時、例えばB3とB2の境界線にいる人がB3のサイズを知るにはどうしたら良いでしょうか？これは簡単で、B3の先頭にB3のサイズを書きこんでおくと、境界線にいる人はそのままそのサイズを読むことができます：
先程のメモリブロックの頭にサイズ部分を差し込んだ状態で、その分だけブロックサイズは増えています。こうすると、いわゆる「単方向リスト」を再現できます。例えば、B1の先頭に人がいるとして、まずそこにあるサイズを読みます（8byteとか）。サイズ記入部分が4byteとすると、B1ブロックは全部で12byteある事になります。そこで、B2にジャンプするには、今いる位置から12byte先へ飛べば良いんです：
つまり、管理ブロックの頭にサイズを入れておけば、単方向リストのようにある一方方向へぴょんぴょん飛んで読み込みができるわけです。では、B2とB3の境界にいる人が「B2の先頭に戻る」にはどうしたら良いでしょうか？
上の図で考えてみてください。B2のB3の境界線に立っている人がB2方向にちょっとずつ戻って行くことはできます。でも、B1とB2の境界線に気付くのは難しいです。なぜなら、境界線となるマークがちゃんと存在しているわけではないからです。では、そういうマークを付けるでしょうか？これは「否」です。マークに辿りつくまでに牛歩の如く歩かないといけないわけで、あまりにも効率が悪い検索方法です。
そこで、次のようにブロックの終端にブロックサイズを記載してしまいます：
黄色い部分が終端に付けた各ブロックの全サイズです。例えばB1は元々が8byteでしたが前後にサイズ部(4byte)があるので全部で16byteとなります。こうすると、B2-B3境界線に立っていた人はすぐ後ろを見ればB2の先頭（境界線）まで飛ぶべきサイズ(12byte)がありますから、そのサイズに従ってピョンとB2へジャンプすることができるようになります。
このように、管理したいメモリブロックの前後にジャンプするためのサイズを記載する事で双方向リストと同じような動き方をする事が可能になります。これがBoundary Tagアルゴリズムです。図の前後についたサイズ部は「タグ」と呼ばれています。
② ブロックのマージ
Boundary Tagアルゴリズムのもう一つの利点はブロックのマージが簡単だという事です。ブロックのマージ、つまりお隣さん同士をくっつけて一つのブロックにしてしまうには、くっつけた両端の境界線にあるサイズ部の値を変更するだけです。例えばB2とB3をマージしてみましょう：
B2の先頭にいた場合、自分の隣に確実にジャンプできるためその場でB3へアクセスしてそのサイズを得るのは非常に簡単です。右側のブロックとマージする場合は、自分のサイズ4byteに「自分の後端タグサイズ＋隣の前方タグサイズ＋隣の管理メモリサイズ」を加えた物がマージ後のメモリサイズ(4+4+4+10 = 22byte)となります。後は前後タグに新規のサイズを書きこむだけです。自分の左ブロックとマージする場合もほぼ同様の作業を行えばOKです。
③ ブロックの分割
マージができるならば分割もできます。ただし、分割する場合は新規に発生するタグサイズに注意する必要があります。上のB2-B3マージブロックに対して6byteの新規ブロックを作るとしましょう。この場合、管理メモリサイズ6byteにさらに後端タグサイズ(4byte)と右側の前方タグサイズ(4byte)、合わせて14byteが占有されます。つまり、マージ前の管理メモリがこのサイズ以上でないと分割ができないわけです：
分割した時の右側の新規管理メモリサイズは、
右ブロック管理サイズ = 元の管理メモリサイズ - 左ブロックの管理サイズ - 後端タグサイズ - 前方タグサイズ
で計算できます。これがマイナスだと分割不可です。
④ メモリアロケータ等で活躍！
一続きのメモリ領域に並んだメモリブロック群を付け加えたりマージしたり分割したり、こういう事を頻繁に行うのは「メモリアロケータ」です。Boundary Tagアルゴリズムだけでも簡単なメモリアロケータを作る事が出来ます。例えば32byteのメモリ領域を確保する場合は、メモリブロックリストの後端にそのサイズ分の新しいブロックを作ればいいんです。そのブロックを使用中なのか解放中（フリーブロック）かは前方タグにフラグを追加で設けて区別します。もちろん、これだけですと非常に非効率なメモリアロケータです。実際はこれを基本に効率を高めるための色々な工夫をします。
別の応用方法としては、バイナリファイル内に連続した文字列を並べる時などに便利です。もっともその場合は単方向リストで大抵は良いので後端タグはいりません。C言語スタイルのように文字列の後ろに\0をくっつけると、文字列後端の検索が必要になるため、1バイトずつ読む必要があり非効率になります。
⑤ クラス化とPlacement new
さて、理屈はわりと簡単なBoundary Tagアルゴリズムですが、これをクラス化する時にはちょっと工夫が必要になります。メモリブロックは管理メモリ部が不定長です。つまり、宣言時にサイズが固定されているクラスでは厳密に管理しきれません。ではどうするか？「誰にも邪魔されないメモリブロックを確保できている」という大前提を敷きます。メモリブロックを管理するクラスをBlockとします。例えば32byteの管理メモリを保持する場合、最初に「Blockサイズ+管理メモリサイズ+後端タグサイズ」分のメモリを確保してしまいます。次に、そのメモリの頭にBlockオブジェクトを置きます。ちょっとプログラムで書いてみましょう：
char memoryBlock[1024]; // メモリブロックをがっつり確保
unsigned lastPos = 0; // メモリ後端位置
// 32バイトの管理メモリを保持するBlockオブジェクトをmemoryBlockの先頭に作る
Block *newBlock = new(memoryBlock) Block(32);
// 後端位置を更新
lastPos += newBlock->getBlockSize();
太文字の部分に注目です。これは「Placement new」と呼ばれる特殊なnewで、引数に渡したポインタ位置にオブジェクトを作ってくれます。この手の不定長のメモリを管理するプログラムにPlacement newは必須です。
Blockクラスの中には前方タグがあります。またその他の付加情報（フラグ等）も入れ込む事ができます。実際に管理するメモリは自分のすぐ後ろに続き、その一番最後に後端タグがくっつきます：
次にメモリを確保する場合に備えて後端位置をどこかに保存しておいても良いですね。普通は管理クラスを設けて、その中でメモリのやり取りをします。
