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
deallocatecapability to an allocator that lacks it (such as simple regions).
log n) where
nis the number of distinct sizes (not total nodes) kept in the free tree.
ParentAllocator. If at this point
ParentAllocatoralso fails to allocate,
FreeTreefrees everything and then tries the parent allocator again.
FreeTreerounds 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
FreeTreeshould be fronted with an appropriate small object allocator.
ParentAllocatordefines them, and forward to it:
FreeTree is word aligned.
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
FreeTree releases all of its contents and tries again.
ParentAllocatordoes not defined
b into the free tree.
ParentAllocator.deallocate exists, and returns to it all memory held in the free tree.
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.