Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page.
Requires a signed-in GitHub account. This works well for small changes.
If you'd like to make larger changes you may want to consider using
a local clone.
std.experimental.allocator.building_blocks.free_tree
- struct
FreeTree
(ParentAllocator); - 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:- Adding deallocate capability 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.
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.sizeof, which on 64-bit system is one cache line size. If very small objects need to be efficiently allocated, theFreeTree
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.- enum uint
alignment
; - The FreeTree is word aligned.
- size_t
goodAllocSize
(size_ts
); - Returns parent.goodAllocSize(max(Node.sizeof, s)).
- void[]
allocate
(size_tn
); - 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.TODO Splitting and coalescing should be implemented if ParentAllocator does not defined deallocate.
- bool
deallocate
(void[]b
); - Places
b
into the free tree. - void
clear
(); - Defined if ParentAllocator.deallocate exists, and returns to it all memory held in the free tree.
- bool
deallocateAll
(); - 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).
Copyright © 1999-2022 by the D Language Foundation | Page generated by
Ddoc on (no date time)