Struct std.experimental.allocator.building_blocks.free_tree.FreeTree
The Free Tree allocator, stackable on top of any other allocator, bears similarity with the free list allocator. Instead of a singly-linked list of previously freed blocks, it maintains a binary search tree. This allows the Free Tree allocator to manage blocks of arbitrary lengths and search them efficiently.
struct FreeTree(ParentAllocator)
;
Common uses of FreeTree include:
- Adding
deallocatecapability to an allocator that lacks it (such as simple regions). - Getting the benefits of multiple adaptable freelists that do not need to be tuned for one specific size but insted automatically adapts itself to frequently used sizes.
The free tree has special handling of duplicates (a singly-linked list per
node) in anticipation of large number of duplicates. Allocation time from the
free tree is expected to be Ο(log n) where n is the number of
distinct sizes (not total nodes) kept in the free tree.
Allocation requests first search the tree for a buffer of suitable size
deallocated in the past. If a match is found, the node is removed from the tree
and the memory is returned. Otherwise, the allocation is directed to ParentAllocator. If at this point ParentAllocator also fails to allocate,
FreeTree frees everything and then tries the parent allocator again.
Upon deallocation, the deallocated block is inserted in the internally maintained free tree (not returned to the parent). The free tree is not kept balanced. Instead, it has a last-in-first-out flavor because newly inserted blocks are rotated to the root of the tree. That way allocations are cache friendly and also frequently used sizes are more likely to be found quickly, whereas seldom used sizes migrate to the leaves of the tree.
FreeTree rounds up small allocations to at least 4 * size_t,
which on 64-bit system is one cache line size. If very small objects need to
be efficiently allocated, the FreeTree should be fronted with an
appropriate small object allocator.
The following methods are defined if ParentAllocator defines them, and forward to it: allocateAll, expand, owns, reallocate.
Methods
| Name | Description |
|---|---|
allocate
|
Allocates n bytes of memory. First consults the free tree, and returns
from it if a suitably sized block is found. Otherwise, the parent allocator
is tried. If allocation from the parent succeeds, the allocated block is
returned. Otherwise, the free tree tries an alternate strategy: If ParentAllocator defines deallocate, FreeTree releases all of its
contents and tries again.
|
clear
|
Defined if ParentAllocator exists, and returns to it
all memory held in the free tree.
|
deallocate
|
Places b into the free tree.
|
deallocateAll
|
Defined if ParentAllocator exists, and forwards to it.
Also nullifies the free tree (it's assumed the parent frees all memory
stil managed by the free tree).
|
goodAllocSize
|
Returns parent.
|