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.
- 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.
- enum uint alignment;
- The FreeTree is word aligned.
- size_t goodAllocSize(size_t s);
- Returns parent.goodAllocSize(max(Node.sizeof, s)).
- void allocate(size_t n);
- 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).