アラインメントの大きなメモリ領域を用いて， 高速かつメモリ効率の良い多数の集合を実現する方法

「アラインメントの大きなメモリ領域を確保する方法」では， glibc malloc() がアラインメントの大きなメモリ領域を確保するために使用している方法について解説したが， ここではその領域を使って何をしているかということを， 問題を一般化した形で解説する． 非常に多数の要素 (子) を持つ集合 (親) を実現するデータ構造を考えよう． 例えば次のようなものである． 集合を連結リストで実装する場合， 親はリストヘッダ (またはそれを含む構造体) で，子はリストの要素． 配列で実装する場合，親は配列全体 (を含む構造体)，子は配列要素． 木構造の場合，親は根節点へのポインタ (を含む構造体)， 子は木のすべての節点 (根節点を含む)． 使用するデータ構造はどれでも (これら以外でも) よい． 同じデータ構造で実現された集合が多数あるとして， 一つの子 child のアドレスを知っているとき