std.experimental.allocator.building_blocks.free_tree

struct FreeTree(ParentAllocator);

フリー・ツリー・アロケータは、他のアロケータの上にスタック可能で、フリー・リスト・アロケータと似ている。 フリー・リスト・アロケータと似ている。以前に解放されたブロックのシングルリンクリストの代わりに 代わりに、バイナリー・サーチツリーを保持する。これにより これにより、フリーツリーアロケータは任意の長さのブロックを管理し、効率的に検索することができる。 を効率的に行うことができる。

一般的な FreeTreeには以下のようなものがある:

• 単純なリージョンなどの)アロケータにdeallocate 機能を追加する。
• 複数の適応可能なフリーリストの利点を得る。 複数の適応可能なフリーリストの利点を得る。 よく使われるサイズに自動的に適応する。

自由木は、重複が大量に発生することを想定して、重複の特別な処理(ノードごとに単一リンクリスト)を持っている。 )を持つ。フリーツリーからの割り当て時間は 自由木からの割り当て時間はΟ(log n)であると予想される。n は、自由木に保持されている別個のサイズ(ノードの総数ではない)の数である。 ここで、 は、フリーツリーに保持される個別のサイズ(ノードの総数ではない)の数である。

割り当てリクエストは、まずツリーを検索して、過去に割り当て解除された適切なサイズのバッファを探す。 を検索する。一致するノードが見つかれば、そのノードはツリーから削除され、メモリが返却される。 メモリが返される。そうでない場合、割り当てはParentAllocator 。この時点でParentAllocator も割り当てに失敗している、 FreeTreeはすべてを解放し、親アロケータを再度試す。

割り当てが解除されると、解除されたブロックは内部で管理されているフリーツリーに挿入される。 に挿入される(親には戻されない)。空きツリーは バランスは保たれない。その代わり、新しく挿入されたブロックはツリーのルートにローテートされるため、先入れ先出しの性質を持つ。 ブロックはツリーのルートにローテーションされるからだ。こうすることで、割り当てがキャッシュ フレンドリーになり、頻繁に使用されるサイズはすぐに見つかる可能性が高くなる、 一方、あまり使用されないサイズはツリーの葉に移動する。

FreeTreeは小さなアロケーションを少なくとも4 * size_t.sizeof 、 これは64ビットシステムでは1キャッシュ・ライン・サイズである。非常に小さなオブジェクトを効率的に割り当てる必要がある場合 を効率的に割り当てる必要がある場合 FreeTreeを使用する必要がある。 適切なスモール・オブジェクト・アロケータを使用する必要がある。

以下のメソッドは、ParentAllocator が定義している場合に定義され、それにフォワードする:allocateAll expand,owns,reallocate 。

enum uint alignment;

FreeTree はワードアラインされている。

size_t goodAllocSize(size_t s);

parent.goodAllocSize(max(Node.sizeof, s)) を返す。

void[] allocate(size_t n);

バイトのメモリを割り当てる。 nバイトのメモリを確保する。最初にフリーツリーを参照し、適切なサイズのブロックが見つかればそこから 適切なサイズのブロックが見つかれば、そこから戻る。そうでない場合は、親アロケータ が試される。親からの割り当てが成功すると、割り当てられたブロックが返される。 が返される。そうでない場合、フリーツリーは別の戦略を試す: ParentAllocator がdeallocate を定義した場合、FreeTree はその内容をすべて解放し、再度試行する。 を定義している場合、その内容をすべて解放して再試行する。

TODO ParentAllocator がdeallocate を定義していない場合、分割と合体を実装すべきである。

bool deallocate(void[] b);

自由ツリーに bを自由木に置く。

void clear();

ParentAllocator.deallocate が存在する場合に定義される。 フリーツリーに保持されているすべてのメモリをフリーツリーに戻す。

bool deallocateAll();

が存在する場合に定義される。 ParentAllocator.deallocateAllが存在する場合に定義され、それに転送する。 また、フリー・ツリーを無効にする(親がフリー・ツリーで管理されているすべてのメモリを解放すると仮定される)。 を解放すると仮定される)。