std.experimental.allocator.building_blocks.free_list

Source: std/experimental/allocator/building_blocks/free_list.d

struct ContiguousFreeList FreeList SharedFreeList

Types 3

structFreeList(ParentAllocator, size_t minSize, size_t maxSize = minSize, Flag!"adaptive" adaptive = No.adaptive)
Free list allocator, stackable on top of

another allocator. Allocation requests between min and max bytes are rounded up to max and served from a singly-linked list of buffers deallocated in the past. All other allocations are directed to ParentAllocator. Due to the simplicity of free list management, allocations from the free list are fast. If adaptive is set to Yes.adaptive, the free list gradually reduces its size if allocations tend to use the parent allocator much more than the lists' available nodes.

One instantiation is of particular interest: FreeList!(0, unbounded) puts every deallocation in the freelist, and subsequently serves any allocation from the freelist (if not empty). There is no checking of size matching, which would be incorrect for a freestanding allocator but is both correct and fast when an owning allocator on top of the free list allocator (such as Segregator) is already in charge of handling size checking.

The following methods are defined if ParentAllocator defines them, and forward to it: expand, owns, reallocate.

Fields
private minSize == 0 && maxSize == unbounded unchecked
private !unchecked && (minSize != maxSize || maxSize == chooseAtRuntime) hasTolerance
private Node * root
Methods
private bool tooSmall(size_t n) const
private bool tooLarge(size_t n) const
private bool freeListEligible(size_t n) const
size_t goodAllocSize(size_t bytes)If maxSize == unbounded, returns `parent.goodAllocSize(bytes)`. Otherwise, returns `max` for sizes in the interval [min, and `parent.goodAllocSize(bytes)` otherwise.
private void[] allocateEligible(string fillMode)(size_t bytes) if (fillMode == "void" || fillMode == "zero")
void[] allocate(size_t n)Allocates memory either off of the free list or from the parent allocator. If `n` is within [min or if the free list is unchecked (minSize == 0 && maxSize == size_t.max), then the free list is cons...
bool deallocate(void[] block)If `block.length` is within [min or if the free list is unchecked (minSize == 0 && maxSize == size_t.max), then inserts the block at the front of the free list. For all others, forwards to parent.d...
Nested Templates
Node
structContiguousFreeList(ParentAllocator, size_t minSize, size_t maxSize = minSize)

Free list built on top of exactly one contiguous block of memory. The block is assumed to have been allocated with ParentAllocator, and is released in ContiguousFreeList's destructor (unless ParentAllocator is NullAllocator).

ContiguousFreeList has most advantages of FreeList but fewer disadvantages. It has better cache locality because items are closer to one another. It imposes less fragmentation on its parent allocator.

The disadvantages of ContiguousFreeList over FreeList are its pay upfront model (as opposed to FreeList's pay-as-you-go approach), and a hard limit on the number of nodes in the list. Thus, a large number of long- lived objects may occupy the entire block, making it unavailable for serving allocations from the free list. However, an absolute cap on the free list size may be beneficial.

The options minSize == unbounded and maxSize == unbounded are not available for ContiguousFreeList.

Fields
minSize == 0 && maxSize == unbounded unchecked
SParent parentThe parent allocator. Depending on whether `ParentAllocator` holds state or not, this is a member variable or an alias for `ParentAllocator.instance`.
FreeList!(NullAllocator, minSize, maxSize) fl
void[] support
size_t allocated
uint alignmentAlignment offered.
Methods
private void initialize(ubyte[] buffer, size_t itemSize = fl.max)
size_t goodAllocSize(size_t n)If `n` is eligible for freelisting, returns `max`. Otherwise, returns `parent.goodAllocSize(n)`.
void[] allocate(size_t n)Allocate `n` bytes of memory. If `n` is eligible for freelist and the freelist is not empty, pops the memory off the free list. In all other cases, uses the parent allocator.
bool deallocate(void[] b)Deallocates `b`. If it's of eligible size, it's put on the free list. Otherwise, it's returned to `parent`.
Ternary empty()Returns `Ternary.yes` if no memory is currently allocated with this allocator, `Ternary.no` otherwise. This method never returns `Ternary.unknown`.
structSharedFreeList(ParentAllocator, size_t minSize, size_t maxSize = minSize, size_t approxMaxNodes = unbounded)

FreeList shared across threads. Allocation and deallocation are lock-free. The parameters have the same semantics as for FreeList.

expand is defined to forward to ParentAllocator.expand (it must be also shared).

Fields
private minSize == 0 && maxSize == unbounded unchecked
private SpinLock lock
private Node * _root
uint alignmentStandard primitives.
Methods
private bool tooSmall(size_t n) const shared
private bool tooLarge(size_t n) const shared
private bool freeListEligible(size_t n) const shared
size_t goodAllocSize(size_t bytes) sharedDitto
void[] allocate(size_t bytes) sharedDitto
private void[] allocateFresh(const size_t bytes) shared
bool deallocate(void[] b) sharedDitto
bool deallocateAll() sharedDitto
Nested Templates
Node