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.
Common uses of FreeTree
include:
deallocate
capability to an allocator that lacks it (such as simple regions).log n
) where n
is the number of distinct sizes (not total nodes) kept in the free tree. ParentAllocator
. If at this point ParentAllocator
also fails to allocate, FreeTree
frees everything and then tries the parent allocator again. FreeTree
rounds up small allocations to at least 4 * size_t.sizeof
, 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. ParentAllocator
defines them, and forward to it: allocateAll
, expand
, owns
, reallocate
. The FreeTree
is word aligned.
Returns parent.goodAllocSize(max(Node.sizeof, s))
.
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.
ParentAllocator
does not defined deallocate
.Places b
into the free tree.
Defined if ParentAllocator.deallocate
exists, and returns to it all memory held in the free tree.
Defined if ParentAllocator.deallocateAll
exists, and forwards to it. Also nullifies the free tree (it's assumed the parent frees all memory stil managed by the free tree).
© 1999–2019 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_experimental_allocator_building_blocks_free_tree.html