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 local clone. Page wiki View or edit the community-maintained wiki page associated with this page.

std.allocator

License:
Boost License 1.0.

Authors:
Andrei Alexandrescu

Source:
std/allocator.d

This module implements untyped composable memory allocators. They are untyped because they deal exclusively in void[] and have no notion of what type the memory allocated would be destined for. They are composable because the included allocators are building blocks that can be assembled in complex nontrivial allocators.

Unlike the allocators for the C and C++ programming languages, which manage the allocated size internally, these allocators require that the client maintains (or knows a priori) the allocation size for each piece of memory allocated. Put simply, the client must pass the allocated size upon deallocation. Storing the size in the allocator has significant negative performance implications, and is virtually always redundant because client code needs knowledge of the allocated size in order to avoid buffer overruns. (See more discussion in a proposal for sized deallocation in C++.) For this reason, allocators herein traffic in void[] as opposed to void*.

In order to be usable as an allocator, a type should implement the following methods with their respective semantics. Only alignment and allocate are required. If any of the other methods is missing, the allocator is assumed to not have that capability (for example some allocators do not offer manual deallocation of memory).

Method name Semantics
uint alignment;
Post: result > 0
Returns the minimum alignment of all data returned by the allocator. An allocator may implement alignment as a statically-known enum value only. Applications that need dynamically-chosen alignment values should use the alignedAllocate and alignedReallocate APIs.
size_t goodAllocSize(size_t n);
Post: result >= n
Allocators customarily allocate memory in discretely-sized chunks. Therefore, a request for n bytes may result in a larger allocation. The extra memory allocated goes unused and adds to the so-called internal fragmentation. The function goodAllocSize(n) returns the actual number of bytes that would be allocated upon a request for n bytes. This module defines a default implementation that returns n rounded up to a multiple of the allocator's alignment.
void[] allocate(size_t s);
Post: result is null || result.length == s
If s == 0, the call may return any empty slice (including null). Otherwise, the call allocates s bytes of memory and returns the allocated block, or null if the request could not be satisfied.
void[] alignedAllocate(size_t s, uint a);
Post: result is null || result.length == s
Similar to allocate, with the additional guarantee that the memory returned is aligned to at least a bytes. a must be a power of 2.
void[] allocateAll(); Offers all of allocator's memory to the caller, so it's usually defined by fixed-size allocators. If the allocator is currently NOT managing any memory, then allocateAll() shall allocate and return all memory available to the allocator, and subsequent calls to all allocation primitives should not succeed (e..g allocate shall return null etc). Otherwise, allocateAll only works on a best-effort basis, and the allocator is allowed to return null even if does have available memory. Memory allocated with allocateAll is not otherwise special (e.g. can be reallocated or deallocated with the usual primitives, if defined).
bool expand(ref void[] b, size_t delta);
Post: !result || b.length == old(b).length + delta
Expands b by delta bytes. If delta == 0, succeeds without changing b. If b is null, the call evaluates b = allocate(delta) and returns b !is null. Otherwise, b must be a buffer previously allocated with the same allocator. If expansion was successful, expand changes b's length to b.length + delta and returns true. Upon failure, the call effects no change upon the allocator object, leaves b unchanged, and returns false.
bool reallocate(ref void[] b, size_t s);
Post: !result || b.length == s
Reallocates b to size s, possibly moving memory around. b must be null or a buffer allocated with the same allocator. If reallocation was successful, reallocate changes b appropriately and returns true. Upon failure, the call effects no change upon the allocator object, leaves b unchanged, and returns false. An allocator should implement reallocate if it can derive some advantage from doing so; otherwise, this module defines a reallocate free function implemented in terms of expand, allocate, and deallocate.
bool alignedReallocate(ref void[] b,
size_t s, uint a);

Post: !result || b.length == s
Similar to reallocate, but guarantees the reallocated memory is aligned at a bytes. The buffer must have been originated with a call to alignedAllocate. a must be a power of 2 greater than (void*).sizeof. An allocator should implement alignedReallocate if it can derive some advantage from doing so; otherwise, this module defines a alignedReallocate free function implemented in terms of expand, alignedAllocate, and deallocate.
bool owns(void[] b); Returns true if b has been allocated with this allocator. An allocator should define this method only if it can decide on ownership precisely and fast (in constant time, logarithmic time, or linear time with a low multiplication factor). Traditional allocators such as the C heap do not define such functionality. If b is null, the allocator shall return false, i.e. no allocator owns the null slice.
void[] resolveInternalPointer(void* p); If p is a pointer somewhere inside a block allocated with this allocator, returns a pointer to the beginning of the allocated block. Otherwise, returns null. If the pointer points immediately after an allocated block, the result is implementation defined.
void deallocate(void[] b); If b is null, does nothing. Otherwise, deallocates memory previously allocated with this allocator.
void deallocateAll();
Post: empty
Deallocates all memory allocated with this allocator. If an allocator implements this method, it must specify whether its destructor calls it, too.
bool empty(); Returns true if and only if the allocator holds no memory (i.e. no allocation has occurred, or all allocations have been deallocated).
bool zeroesAllocations; Enumerated value indicating whether the allocator zeroes newly allocated memory automatically. If not defined, it is assumed the allocator does not zero allocated memory.
static Allocator it;
Post: it is a valid Allocator object
Some allocators are monostate, i.e. have only an instance and hold only global state. (Notable examples are C's own malloc-based allocator and D's garbage-collected heap.) Such allocators must define a static it instance that serves as the symbolic placeholder for the global instance of the allocator. An allocator should not hold state and define it simultaneously. Depending on whether the allocator is thread-safe or not, this instance may be shared.
void markAllAsUnused();
Post: empty
This routine is meant as an aid for garbage collectors. It is similar to deallocateAll, with an important distinction: if there's no intervening call to allocate, a subsequent call markAsUsed(b) (see below) for any block b that had been allocated prior to calling markAllAsUnused is guaranteed to restore the allocation status of b. markAllAsUnused must not affect memory managed by the allocator at all. This is unlike deallocateAll, which is allowed to alter managed memory in any way. The primitive resolveInternalPointer must continue working unaffected following a call to markAllAsUnused.
bool markAsUsed(void[] b); This routine is meant as an aid for garbage collectors. Following a call to markAllAsUnused, calling markAsUsed(b) restores b's status as an allocated block. Just like markAllAsUnused, markAsUsed(b) is not supposed to affect b or any other memory managed by the allocator. The function returns false if the block had already been marked by a previous call to markAsUsed, true otherwise.
void doneMarking(); This routine is meant as an aid for garbage collectors. This call allows the allocator to clear state following a call to markAllAsUnused and a series of calls to markAsUsed.

The example below features an allocator modeled after jemalloc, which uses a battery of free-list allocators spaced so as to keep internal fragmentation to a minimum. The FList definitions specify no bounds for the freelist because the Segregator does all size selection in advance.

Sizes through 3584 bytes are handled via freelists of staggered sizes. Sizes from 3585 bytes through 4072 KB are handled by a HeapBlock with a block size of 4 KB. Sizes above that are passed direct to the Mallocator.

    alias FList = Freelist!(GCAllocator, 0, unbounded);
    alias A = Segregator!(
        8, Freelist!(GCAllocator, 0, 8),
        128, Bucketizer!(FList, 1, 128, 16),
        256, Bucketizer!(FList, 129, 256, 32),
        512, Bucketizer!(FList, 257, 512, 64),
        1024, Bucketizer!(FList, 513, 1024, 128),
        2048, Bucketizer!(FList, 1025, 2048, 256),
        3584, Bucketizer!(FList, 2049, 3584, 512),
        4072 * 1024, CascadingAllocator!(
            () => HeapBlock!(GCAllocator, 4096)(4072 * 1024)),
        GCAllocator
    );
    A tuMalloc;
    auto b = tuMalloc.allocate(500);
    assert(b.length == 500);
    auto c = tuMalloc.allocate(113);
    assert(c.length == 113);
    assert(tuMalloc.expand(c, 14));
    tuMalloc.deallocate(b);
    tuMalloc.deallocate(c);

Allocating memory for sharing across threads

One allocation pattern used in multithreaded applications is to share memory across threads, and to deallocate blocks in a different thread than the one that allocated it.

All allocators in this module accept and return void[] (as opposed to shared void[]). This is because at the time of allocation, deallocation, or reallocation, the memory is effectively not shared (if it were, it would reveal a bug at the application level).

The issue remains of calling a.deallocate(b) from a different thread than the one that allocated b. It follows that both threads must have access to the same instance a of the respective allocator type. By definition of D, this is possible only if a has the shared qualifier. It follows that the allocator type must implement allocate and deallocate as shared methods. That way, the allocator commits to allowing usable shared instances.

Conversely, allocating memory with one non-shared allocator, passing it across threads (by casting the obtained buffer to shared), and later deallocating it in a different thread (either with a different allocator object or with the same allocator object after casting it to shared) is illegal.

Synopsis of predefined allocator building blocks
Allocator Description
NullAllocator Very good at doing absolutely nothing. A good starting point for defining other allocators or for studying the API.
GCAllocator The system-provided garbage-collector allocator. This should be the default fallback allocator tapping into system memory. It offers manual free and dutifully collects litter.
Mallocator The C heap allocator, a.k.a. malloc/realloc/free. Use sparingly and only for code that is unlikely to leak.
AlignedMallocator Interface to OS-specific allocators that support specifying alignment: posix_memalign on Posix and _aligned_xxx on Windows.
AffixAllocator Allocator that allows and manages allocating extra prefix and/or a suffix bytes for each block allocated.
HeapBlock Organizes one contiguous chunk of memory in equal-size blocks and tracks allocation status at the cost of one bit per block.
FallbackAllocator Allocator that combines two other allocators - primary and fallback. Allocation requests are first tried with primary, and upon failure are passed to the fallback. Useful for small and fast allocators fronting general-purpose ones.
Freelist Allocator that implements a free list on top of any other allocator. The preferred size, tolerance, and maximum elements are configurable at compile- and run time.
SharedFreelist Same features as Freelist, but packaged as a shared structure that is accessible to several threads.
SimpleBlocklist A simple structure on top of a contiguous block of storage, organizing it as a singly-linked list of blocks. Each block has a word-sized header consisting of its length massaged with a bit indicating whether the block is occupied.
Blocklist An enhanced block-list style of allocator building on top of SimpleBlocklist. Each block in the list stores the block size at the end of the block as well (similarly to the way dlmalloc does), which makes it possible to iterate the block list backward as well as forward. This makes for better coalescing properties.
Region Region allocator organizes a chunk of memory as a simple bump-the-pointer allocator.
InSituRegion Region holding its own allocation, most often on the stack. Has statically-determined size.
SbrkRegion Region using sbrk for allocating memory.
MmapAllocator Allocator using mmap directly.
AllocatorWithStats Collect statistics about any other allocator.
CascadingAllocator Given an allocator factory, lazily creates as many allocators as needed to satisfy allocation requests. The allocators are stored in a linked list. Requests for allocation are satisfied by searching the list in a linear manner.
Segregator Segregates allocation requests by size and dispatches them to distinct allocators.
Bucketizer Divides allocation sizes in discrete buckets and uses an array of allocators, one per bucket, to satisfy requests.
InternalPointersTree Adds support for resolving internal pointers on top of another allocator.

template stateSize(T)
Returns the size in bytes of the state that needs to be allocated to hold an object of type T. stateSize!T is zero for structs that are not nested and have no nonstatic member variables.

ulong chooseAtRuntime;
chooseAtRuntime is a compile-time constant of type size_t that several parameterized structures in this module recognize to mean deferral to runtime of the exact value. For example, HeapBlock!(Allocator, 4096) (described in detail below) defines a block allocator with block size of 4096 bytes, whereas HeapBlock!(Allocator, chooseAtRuntime) defines a block allocator that has a field storing the block size, initialized by the user.

ulong unbounded;
unbounded is a compile-time constant of type size_t that several parameterized structures in this module recognize to mean "infinite" bounds for the parameter. For example, Freelist (described in detail below) accepts a maxNodes parameter limiting the number of freelist items. If unbounded is passed for maxNodes, then there is no limit and no checking for the number of nodes.

uint platformAlignment;
The alignment that is guaranteed to accommodate any D object allocation on the current platform.

size_t goodAllocSize(A)(auto ref A a, size_t n);
The default good size allocation is deduced as n rounded up to the allocator's alignment.

bool reallocate(Allocator)(ref Allocator a, ref void[] b, size_t s);
The default reallocate function first attempts to use expand. If Allocator.expand is not defined or returns false, reallocate allocates a new block of memory of appropriate size and copies data from the old block to the new block. Finally, if Allocator defines deallocate, reallocate uses it to free the old memory block.

reallocate does not attempt to use Allocator.reallocate even if defined. This is deliberate so allocators may use it internally within their own implementation of reallocate.

bool alignedReallocate(Allocator)(ref Allocator alloc, ref void[] b, size_t s, uint a);
The default alignedReallocate function first attempts to use expand. If Allocator.expand is not defined or returns false, alignedReallocate allocates a new block of memory of appropriate size and copies data from the old block to the new block. Finally, if Allocator defines deallocate, alignedReallocate uses it to free the old memory block.

alignedReallocate does not attempt to use Allocator.reallocate even if defined. This is deliberate so allocators may use it internally within their own implementation of reallocate.

struct NullAllocator;
NullAllocator is an emphatically empty implementation of the allocator interface. Although it has no direct use, it is useful as a "terminator" in composite allocators.

uint alignment;
NullAllocator advertises a relatively large alignment equal to 64 KB. This is because NullAllocator never actually needs to honor this alignment and because composite allocators using NullAllocator shouldn't be unnecessarily constrained.

shared void[] allocate(size_t);
Always returns null.

shared void[] alignedAllocate(size_t, uint);
Always returns null.

shared void[] allocateAll();
Always returns null.

shared bool expand(ref void[] b, size_t);
shared bool reallocate(ref void[] b, size_t);
shared bool alignedReallocate(ref void[] b, size_t, uint);
These methods return false.

Precondition:
b is null. This is because there is no other possible legitimate input.

shared bool owns(void[] b);
Returns b is null.

shared void[] resolveInternalPointer(void*);
Returns null.

shared void deallocate(void[] b);
No-op.

Precondition:
b is null

shared void deallocateAll();
No-op.

shared bool empty();
Returns true.

static NullAllocator it;
Returns the shared global instance of the NullAllocator.

shared void markAllAsUnused();
No-op

shared bool markAsUsed(void[]);
Returns false.

shared void doneMarking();
No-op

struct GCAllocator;
D's built-in garbage-collected allocator.

Examples:
auto buffer = GCAllocator.it.allocate(1024 * 1024 * 4);
scope(exit) GCAllocator.it.deallocate(buffer); // or leave it to collection
//...

uint alignment;
The alignment is a static constant equal to platformAlignment, which ensures proper alignment for any D data type.

shared @trusted void[] allocate(size_t bytes);
shared @trusted bool expand(ref void[] b, size_t delta);
shared @system bool reallocate(ref void[] b, size_t newSize);
shared void[] resolveInternalPointer(void* p);
shared @system void deallocate(void[] b);
Standard allocator methods per the semantics defined above. The deallocate and reallocate methods are @system because they may move memory around, leaving dangling pointers in user code.

static GCAllocator it;
Returns the global instance of this allocator type. The garbage collected allocator is thread-safe, therefore all of its methods and it itself are shared.

struct Mallocator;
The C heap allocator.

Examples:
auto buffer = Mallocator.it.allocate(1024 * 1024 * 4);
scope(exit) Mallocator.it.deallocate(buffer);
//...

uint alignment;
The alignment is a static constant equal to platformAlignment, which ensures proper alignment for any D data type.

shared @trusted void[] allocate(size_t bytes);
shared @system void deallocate(void[] b);
shared @system bool reallocate(ref void[] b, size_t s);
Standard allocator methods per the semantics defined above. The deallocate and reallocate methods are @system because they may move memory around, leaving dangling pointers in user code. Somewhat paradoxically, malloc is @safe but that's only useful to safe programs that can afford to leak memory allocated.

static Mallocator it;
Returns the global instance of this allocator type. The C heap allocator is thread-safe, therefore all of its methods and it itself are shared.

struct AlignedMallocator;
Aligned allocator using OS-specific primitives, under a uniform API.

Examples:
auto buffer = AlignedMallocator.it.alignedAllocate(1024 * 1024 * 4, 128);
scope(exit) AlignedMallocator.it.deallocate(buffer);
//...

uint alignment;
The default alignment is platformAlignment.

shared @trusted void[] allocate(size_t bytes);
Forwards to alignedAllocate(bytes, platformAlignment).

shared @trusted void[] alignedAllocate(size_t bytes, uint a);
Uses posix_memalign on Posix and _aligned_malloc on Windows.

shared @system void deallocate(void[] b);
Calls free(b.ptr) on Posix and _aligned_free(b.ptr) on Windows.

shared @system bool reallocate(ref void[] b, size_t newSize);
On Posix, forwards to realloc. On Windows, forwards to alignedReallocate(b, newSize, platformAlignment).

static AlignedMallocator it;
Returns the global instance of this allocator type. The C heap allocator is thread-safe, therefore all of its methods and it itself are shared.

struct AffixAllocator(Allocator, Prefix, Suffix = void);
Allocator that adds some extra data before (of type Prefix) and/or after (of type Suffix) any allocation made with its parent allocator. This is useful for uses where additional allocation-related information is needed, such as mutexes, reference counts, or walls for debugging memory corruption errors.

If Prefix is not void, Allocator must guarantee an alignment at least as large as Prefix.alignof.

Suffixes are slower to get at because of alignment rounding, so prefixes should be preferred. However, small prefixes blunt the alignment so if a large alignment with a small affix is needed, suffixes should be chosen.

Examples:
// One word before and after each allocation.
alias A = AffixAllocator!(Mallocator, size_t, size_t);
auto b = A.it.allocate(11);
A.it.prefix(b) = 0xCAFE_BABE;
A.it.suffix(b) = 0xDEAD_BEEF;
assert(A.it.prefix(b) == 0xCAFE_BABE && A.it.suffix(b) == 0xDEAD_BEEF);

uint alignment;
If Prefix is void, the alignment is that of the parent. Otherwise, the alignment is the same as the Prefix's alignment.

Allocator parent;
If the parent allocator Allocator is stateful, an instance of it is stored as a member. Otherwise, AffixAllocator uses Allocator.it. In either case, the name parent is uniformly used for accessing the parent allocator.

size_t goodAllocSize(size_t);
void[] allocate(size_t);
bool owns(void[]);
bool expand(ref void[] b, size_t delta);
bool reallocate(ref void[] b, size_t s);
void deallocate(void[] b);
void deallocateAll();
bool empty();
bool zeroesAllocations;
void markAllAsUnused();
bool markAsUsed(void[] b);
void doneMarking();
Standard allocator methods. Each is defined if and only if the parent allocator defines the homonym method (except for goodAllocSize, which may use the global default). Also, the methods will be shared if the parent allocator defines them as such.

AffixAllocator it;
The it singleton is defined if and only if the parent allocator has no state and defines its own it object.

Prefix prefix(void[] b);
Suffix suffix(void[] b);
Affix access functions offering mutable references to the affixes of a block previously allocated with this allocator. b may not be null. They are defined if and only if the corresponding affix is not void.

Precondition:
b !is null

struct HeapBlock(size_t theBlockSize, uint theAlignment = platformAlignment);
HeapBlock implements a simple heap consisting of one contiguous area of memory organized in blocks, each of size theBlockSize. A block is a unit of allocation. A bitmap serves as bookkeeping data, more precisely one bit per block indicating whether that block is currently allocated or not.

There are advantages to storing bookkeeping data separated from the payload (as opposed to e.g. AffixAllocator). The layout is more compact, searching for a free block during allocation enjoys better cache locality, and deallocation does not touch memory around the payload being deallocated (which is often cold).

Allocation requests are handled on a first-fit basis. Although linear in complexity, allocation is in practice fast because of the compact bookkeeping representation, use of simple and fast bitwise routines, and memoization of the first available block position. A known issue with this general approach is fragmentation, partially mitigated by coalescing. Since HeapBlock does not maintain the allocated size, freeing memory implicitly coalesces free blocks together. Also, tuning blockSize has a considerable impact on both internal and external fragmentation.

The size of each block can be selected either during compilation or at run time. Statically-known block sizes are frequent in practice and yield slightly better performance. To choose a block size statically, pass it as the blockSize parameter as in HeapBlock!(Allocator, 4096). To choose a block size parameter, use HeapBlock!(Allocator, chooseAtRuntime) and pass the block size to the constructor.

TODO:
implement alignedAllocate and alignedReallocate.

Examples:
// Create a block allocator on top of a 10KB stack region.
InSituRegion!(10240, 64) r;
auto a = HeapBlock!(64, 64)(r.allocateAll());
static assert(hasMember!(InSituRegion!(10240, 64), "allocateAll"));
auto b = a.allocate(100);
assert(b.length == 100);

alias blockSize = theBlockSize;
If blockSize == chooseAtRuntime, HeapBlock offers a read/write property blockSize. It must be set to a power of two before any use of the allocator. Otherwise, blockSize is an alias for theBlockSize.

alias alignment = theAlignment;
The alignment offered is user-configurable statically through parameter theAlignment, defaulted to platformAlignment.

this(void[] data);
Constructs a block allocator given a hunk of memory. The layout puts the bitmap at the front followed immediately by the payload.

void[] allocate(const size_t s);
void[] allocateAll();
const bool owns(void[] b);
bool expand(ref void[] b, immutable size_t delta);
bool reallocate(ref void[] b, size_t newSize);
void deallocate(void[] b);
void deallocateAll();
bool empty();
Standard allocator methods per the semantics defined above. The deallocate and reallocate methods are @system because they may move memory around, leaving dangling pointers in user code.

BUGS:
Neither deallocateAll nor the destructor free the original memory block. Either user code or the parent allocator should carry that.

struct HeapBlockWithInternalPointers(size_t theBlockSize, uint theAlignment = platformAlignment);
A HeapBlock with additional structure for supporting resolveInternalPointer. To that end, HeapBlockWithInternalPointers adds a bitmap (one bit per block) that marks object starts. The bitmap itself has variable size and is allocated together with regular allocations.

The time complexity of resolveInternalPointer is Ο(k), where k is the size of the object within which the internal pointer is looked up.

alias alignment = theAlignment;
void[] allocate(size_t bytes);
void[] allocateAll();
bool expand(ref void[] b, size_t bytes);
void deallocate(void[] b);
void[] resolveInternalPointer(void* p);
bool empty();
void markAllAsUnused();
bool markAsUsed(void[] b);
void doneMarking();
Allocator primitives.

struct FallbackAllocator(Primary, Fallback);
FallbackAllocator is the allocator equivalent of an "or" operator in algebra. An allocation request is first attempted with the Primary allocator. If that returns null, the request is forwarded to the Fallback allocator. All other requests are dispatched appropriately to one of the two allocators.

In order to work, FallbackAllocator requires that Primary defines the owns method. This is needed in order to decide which allocator was responsible for a given allocation.

FallbackAllocator is useful for fast, special-purpose allocators backed up by general-purpose allocators. The example below features a stack region backed up by the GCAllocator.

Examples:
FallbackAllocator!(InSituRegion!16384, GCAllocator) a;
// This allocation uses the stack
auto b1 = a.allocate(1024);
assert(b1.length == 1024, text(b1.length));
assert(a.primary.owns(b1));
// This large allocation will go to the Mallocator
auto b2 = a.allocate(1024 * 1024);
assert(!a.primary.owns(b2));
a.deallocate(b1);
a.deallocate(b2);

Primary primary;
The primary allocator.

Fallback fallback;
The fallback allocator.

FallbackAllocator it;
If both Primary and Fallback are stateless, FallbackAllocator defines a static instance it.

uint alignment;
The alignment offered is the minimum of the two allocators' alignment.

void[] allocate(size_t s);
Allocates memory trying the primary allocator first. If it returns null, the fallback allocator is tried.

void[] alignedAllocate(size_t s, uint a);
FallbackAllocator offers alignedAllocate iff at least one of the allocators also offers it. It attempts to allocate using either or both.

bool expand(ref void[] b, size_t delta);
expand is defined if and only if at least one of the allocators defines expand. It works as follows. If primary.owns(b), then the request is forwarded to primary.expand if it is defined, or fails (returning false) otherwise. If primary does not own b, then the request is forwarded to fallback.expand if it is defined, or fails (returning false) otherwise.

bool reallocate(ref void[] b, size_t newSize);
reallocate works as follows. If primary.owns(b), then primary.reallocate(b, newSize) is attempted. If it fails, an attempt is made to move the allocation from primary to fallback.

If primary does not own b, then fallback.reallocate(b, newSize) is attempted. If that fails, an attempt is made to move the allocation from fallback to primary.

bool owns(void[] p);
owns is defined if and only if both allocators define owns. Returns primary.owns(b) || fallback.owns(b).

void[] resolveInternalPointer(void* p);
resolveInternalPointer is defined if and only if both allocators define it.

void deallocate(void[] b);
deallocate is defined if and only if at least one of the allocators define deallocate. It works as follows. If primary.owns(b), then the request is forwarded to primary.deallocate if it is defined, or is a no-op otherwise. If primary does not own b, then the request is forwarded to fallback.deallocate if it is defined, or is a no-op otherwise.

bool empty();
empty is defined if both allocators also define it.

bool zeroesAllocations;
zeroesAllocations is defined if both allocators also define it.

struct Freelist(ParentAllocator, size_t minSize, size_t maxSize = minSize, uint batchCount = 8, size_t maxNodes = unbounded);
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 a program makes many allocations in the interval [minSize, maxSize] and then frees most of them, the freelist may grow large, thus making memory inaccessible to requests of other sizes. To prevent that, the maxNodes parameter allows limiting the size of the free list. Alternatively, deallocateAll cleans the free list.

Freelist attempts to reduce internal fragmentation and improve cache locality by allocating multiple nodes at once, under the control of the batchCount parameter. This makes Freelist an efficient front for small object allocation on top of a large-block allocator. The default value of batchCount is 8, which should amortize freelist management costs to negligible in most cases.

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.

size_t min();
void min(size_t newMinSize);
size_t max();
void max(size_t newMaxSize);
void setBounds(size_t newMin, size_t newMax);
Properties for getting and setting bounds. Setting a bound is only possible if the respective compile-time parameter has been set to chooseAtRuntime. setBounds is defined only if both minSize and maxSize are set to chooseAtRuntime.

Examples:
Freelist!(Mallocator, chooseAtRuntime, chooseAtRuntime) a;
// Set the maxSize first so setting the minSize doesn't throw
a.max = 128;
a.min = 64;
a.setBounds(64, 128); // equivalent
assert(a.max == 128);
assert(a.min == 64);

ParentAllocator parent;
The parent allocator. Depending on whether ParentAllocator holds state or not, this is a member variable or an alias for ParentAllocator.it.

uint alignment;
Alignment is defined as parent.alignment. However, if parent.alignment > maxSize, objects returned from the freelist will have a smaller alignment, namely maxSize rounded up to the nearest multiple of 2. This allows Freelist to minimize internal fragmentation by allocating several small objects within an allocated block. Also, there is no disruption because no object has smaller size than its alignment.

size_t goodAllocSize(size_t bytes);
Returns max for sizes in the interval [min, max], and parent.goodAllocSize(bytes) otherwise.

void[] allocate(size_t bytes);
Allocates memory either off of the free list or from the parent allocator.

bool owns(void[] b);
Forwards to if implemented.

bool expand(void[] b, size_t s);
bool reallocate(void[] b, size_t s);
Forwards to parent.

void deallocate(void[] block);
Intercepts deallocations and caches those of the appropriate size in the freelist. For all others, forwards to parent.deallocate or does nothing if Parent does not define deallocate.

void deallocateAll();
If ParentAllocator defines deallocateAll, just forwards to it and reset the freelist. Otherwise, walks the list and frees each object in turn.

void markAllAsUnused();
GC helper primitives.

bool markAsUsed(void[] b);
GC helper primitives.

void doneMarking();
GC helper primitives.

struct SharedFreelist(ParentAllocator, size_t minSize, size_t maxSize = minSize, uint batchCount = 8, size_t maxNodes = unbounded);
Freelist shared across threads. Allocation and deallocation are lock-free. The parameters have the same semantics as for Freelist.

size_t min();
void min(size_t newMinSize);
size_t max();
void max(size_t newMaxSize);
void setBounds(size_t newMin, size_t newMax);
Properties for getting (and possibly setting) the bounds. Setting bounds is allowed only once , and before any allocation takes place. Otherwise, the primitives have the same semantics as those of Freelist.

Examples:
Freelist!(Mallocator, chooseAtRuntime, chooseAtRuntime) a;
// Set the maxSize first so setting the minSize doesn't throw
a.max = 128;
a.min = 64;
a.setBounds(64, 128); // equivalent
assert(a.max == 128);
assert(a.min == 64);

ParentAllocator parent;
The parent allocator. Depending on whether ParentAllocator holds state or not, this is a member variable or an alias for ParentAllocator.it.

uint alignment;
shared size_t goodAllocSize(size_t bytes);
shared const bool owns(void[] b);
Standard primitives.

bool expand(void[] b, size_t s);
bool reallocate(void[] b, size_t s);
shared void[] allocate(size_t bytes);
shared void deallocate(void[] b);
shared void deallocateAll();
Forwards to parent, which must also support shared primitives.

struct SimpleBlocklist;
A SimpleBlockList manages a contiguous chunk of memory by embedding a block list onto it. Blocks have variable size, and each is preceded by exactly one word that holds that block's size plus a bit indicating whether the block is occupied.

Initially the list has only one element, which covers the entire chunk of memory. Due to that block's management and a sentinel at the end, the maximum amount that can be allocated is n - 2 * size_t.sizeof, where n is the entire chunk size. The first allocation will adjust the size of the first block and will likely create a new free block right after it. As memory gets allocated and deallocated, the block list will evolve accordingly.

SimpleBlockList is one of the simplest allocators that is also memory efficient. However, the allocation speed is Ο(O(n)), where n is the number of blocks in use. To improve on that, allocations start at the last deallocation point, which may lead to constant-time allocation in certain situations. (Deallocations are O(1)).

Fragmentation is also an issue; the allocator does coalescing but has no special strategy beyond a simple first fit algorithm. Coalescing of blocks is performed during allocation. However, a block can be coalesced only with the block of its right (it is not possible to iterate blocks right to left), which means an allocation may spend more time searching. So SimpleBlockList should be used for simple allocation needs, or for coarse-granular allocations in conjunction with specialized allocators for small objects.

this(void[] b);
Create a SimpleBlocklist managing a chunk of memory. Memory must be larger than two words, word-aligned, and of size multiple of size_t.alignof.

ulong alignment;
void[] allocate(size_t bytes);
void deallocate(void[] b);
void[] allocateAll();
void deallocateAll();
bool owns(void[] b);
Standard allocator primitives.

struct Blocklist;
Blocklist builds additional structure on top of SimpleBlocklist by storing the size of each block not only at the beginning, but also at the end of the block. This allows Blocklist to iterate in both directions, which is used for better coalescing capabilities.

Free block coalescing to the right takes place during allocation, whereas free block coalescing to the left takes place during deallocation. This makes both operations Ο(n) in the number of managed blocks, but improves the chance of finding a good block faster than SimpleBlocklist. After deallocation the (possibly coalesced) freed block will be the starting point of searching for the next allocation.

The allocation overhead is two words per allocated block.

this(void[] b);
Constructs an allocator given a block of memory.

alias alignment = .SimpleBlocklist.alignment;
void[] allocate(size_t bytes);
void deallocate(void[] b);
auto owns(void[] b);
auto deallocateAll();
void markAllAsUnused();
bool markAsUsed(void[] b);
void doneMarking();
Standard allocator primitives.

struct Region(uint minAlign = platformAlignment);
A Region allocator manages one block of memory provided at construction. There is no deallocation, and once the region is full, allocation requests return null. Therefore, Regions are often used in conjunction with freelists, a fallback general-purpose allocator, or both.

The region stores three words corresponding to the start of the store, the current position in the store, and the end of the store. One allocation entails rounding up the allocation size for alignment purposes, bumping the current pointer, and comparing it against the limit.

The minAlign parameter establishes alignment. If minAlign > 1, the sizes of all allocation requests are rounded up to a multiple of minAlign. Applications aiming at maximum speed may want to choose minAlign = 1 and control alignment externally.

Examples:
auto reg = Region!()(Mallocator.it.allocate(1024 * 64));
scope(exit) Mallocator.it.deallocate(reg.relinquish);
auto b = reg.allocate(101);
assert(b.length == 101);

this(void[] buffer);
Constructs a Region object backed by buffer, which must be aligned to minAlign.

uint alignment;
void[] allocate(size_t bytes);
void[] alignedAllocate(size_t bytes, uint a);
const bool owns(void[] b);
void deallocateAll();
Standard primitives.

void[] relinquish();
Nonstandard function that gives away the initial buffer used by the range, and makes the range unavailable for further allocations. This is useful for deallocating the memory assigned to the region.

struct InSituRegion(size_t size, size_t minAlign = platformAlignment);
InSituRegion is a convenient region that carries its storage within itself (in the form of a statically-sized array).

The first template argument is the size of the region and the second is the needed alignment. Depending on the alignment requested and platform details, the actual available storage may be smaller than the compile-time parameter. To make sure that at least n bytes are available in the region, use InSituRegion!(n + a - 1, a).

Examples:
// 128KB region, allocated to x86's cache line
InSituRegion!(128 * 1024, 64) r1;
auto a1 = r1.allocate(101);
assert(a1.length == 101);

// 128KB region, with fallback to the garbage collector.
FallbackAllocator!(InSituRegion!(128 * 1024), GCAllocator) r2;
auto a2 = r1.allocate(102);
assert(a2.length == 102);

// Reap with GC fallback.
InSituRegion!(128 * 1024, 8) tmp3;
FallbackAllocator!(HeapBlock!(64, 8), GCAllocator) r3;
r3.primary = HeapBlock!(64, 8)(tmp3.allocateAll());
auto a3 = r3.allocate(103);
assert(a3.length == 103);

// Reap/GC with a freelist for small objects up to 16 bytes.
InSituRegion!(128 * 1024, 64) tmp4;
Freelist!(FallbackAllocator!(HeapBlock!(64, 64), GCAllocator), 0, 16) r4;
r4.parent.primary = HeapBlock!(64, 64)(tmp4.allocateAll());
auto a4 = r4.allocate(104);
assert(a4.length == 104);

uint alignment;
An alias for minAlign, which must be a valid alignment (nonzero power of 2). The start of the region and all allocation requests will be rounded up to a multiple of the alignment.

InSituRegion!(4096) a1;
assert(a1.alignment == platformAlignment);
InSituRegion!(4096, 64) a2;
assert(a2.alignment == 64);

void[] allocate(size_t bytes);
Allocates bytes and returns them, or null if the region cannot accommodate the request. For efficiency reasons, if bytes == 0 the function returns an empty non-null slice.

void[] alignedAllocate(size_t bytes, uint a);
As above, but the memory allocated is aligned at a bytes.

const bool owns(void[] b);
Returns true if and only if b is the result of a successful allocation. For efficiency reasons, if b is null the function returns false.

void deallocateAll();
Deallocates all memory allocated with this allocator.

void[] allocateAll();
Allocates all memory available with this allocator.

size_t available();
Nonstandard function that returns the bytes available for allocation.

struct SbrkRegion(uint minAlign = platformAlignment);
Allocator backed by sbrk for Posix systems. Due to the fact that sbrk is not thread-safe by design, SbrkRegion uses a mutex internally. This implies that uncontrolled calls to brk and sbrk may affect the workings of SbrkRegion adversely.

SbrkRegion it;
Instance shared by all callers.

uint alignment;
shared void[] allocate(size_t bytes);
shared void[] alignedAllocate(size_t bytes, uint a);
Standard allocator primitives.

shared bool expand(ref void[] b, size_t delta);
shared bool owns(void[] b);
The expand method may only succeed if the argument is the last block allocated. In that case, expand attempts to push the break pointer to the right.

shared bool deallocate(void[] b);
The deallocate method only works (and returns true) on systems that support reducing the break address (i.e. accept calls to sbrk with negative offsets). OSX does not accept such. In addition the argument must be the last block allocated.

shared bool deallocateAll();
The deallocateAll method only works (and returns true) on systems that support reducing the break address (i.e. accept calls to sbrk with negative offsets). OSX does not accept such.

bool empty();
bool zeroesAllocations;
Standard allocator API.

struct MmapAllocator;
Allocator (currently defined only for Posix) using mmap and munmap directly. There is no additional structure: each call to allocate(s) issues a call to mmap(null, s, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0), and each call to deallocate(b) issues munmap(b.ptr, b.length). So MmapAllocator is usually intended for allocating large chunks to be managed by fine-granular allocators.

static MmapAllocator it;
The one shared instance.

size_t alignment;
Alignment is page-size and hardcoded to 4096 (even though on certain systems it could be larger).

shared void[] allocate(size_t bytes);
shared void deallocate(void[] b);
bool zeroesAllocations;
Allocator API.

enum Options: uint;
Options for AllocatorWithStats defined below. Each enables during compilation one specific counter, statistic, or other piece of information.

numOwns
Counts the number of calls to owns.

numAllocate
Counts the number of calls to allocate. All calls are counted, including requests for zero bytes or failed requests.

numAllocateOK
Counts the number of calls to allocate that succeeded, i.e. they were for more than zero bytes and returned a non-null block.

numExpand
Counts the number of calls to expand, regardless of arguments or result.

numExpandOK
Counts the number of calls to expand that resulted in a successful expansion.

numReallocate
Counts the number of calls to reallocate, regardless of arguments or result.

numReallocateOK
Counts the number of calls to reallocate that succeeded. (Reallocations to zero bytes count as successful.)

numReallocateInPlace
Counts the number of calls to reallocate that resulted in an in-place reallocation (no memory moved). If this number is close to the total number of reallocations, that indicates the allocator finds room at the current block's end in a large fraction of the cases, but also that internal fragmentation may be high (the size of the unit of allocation is large compared to the typical allocation size of the application).

numDeallocate
Counts the number of calls to deallocate.

numDeallocateAll
Counts the number of calls to deallocateAll.

numAll
Chooses all numXxx flags.

bytesAllocated
Tracks total cumulative bytes allocated by means of allocate, expand, and reallocate (when resulting in an expansion). This number always grows and indicates allocation traffic. To compute bytes currently allocated, subtract bytesDeallocated (below) from bytesAllocated.

bytesDeallocated
Tracks total cumulative bytes deallocated by means of deallocate and reallocate (when resulting in a contraction). This number always grows and indicates deallocation traffic.

bytesExpanded
Tracks the sum of all delta values in calls of the form expand(b, delta) that succeed (return true).

bytesContracted
Tracks the sum of all b.length - s with b.length > s in calls of the form realloc(b, s) that succeed (return true).

bytesMoved
Tracks the sum of all bytes moved as a result of calls to realloc that were unable to reallocate in place. A large number (relative to bytesAllocated) indicates that the application should use larger preallocations.

bytesSlack
Measures the sum of extra bytes allocated beyond the bytes requested, i.e. the internal fragmentation. This is the current effective number of slack bytes, and it goes up and down with time.

bytesHighTide
Measures the maximum bytes allocated over the time. This is useful for dimensioning allocators.

bytesAll
Chooses all byteXxx flags.

callerSize
Instructs AllocatorWithStats to store the size asked by the caller for each allocation. All per-allocation data is stored just before the actually allocation (see AffixAllocator).

callerModule
Instructs AllocatorWithStats to store the caller module for each allocation.

callerFile
Instructs AllocatorWithStats to store the caller's file for each allocation.

callerFunction
Instructs AllocatorWithStats to store the caller __FUNCTION__ for each allocation.

callerLine
Instructs AllocatorWithStats to store the caller's line for each allocation.

callerTime
Instructs AllocatorWithStats to store the time of each allocation.

callerAll
Chooses all callerXxx flags.

all
Combines all flags above.

struct AllocatorWithStats(Allocator, uint flags = Options.all);
Allocator that collects extra data about allocations. Since each piece of information adds size and time overhead, statistics can be individually enabled or disabled through compile-time flags.

All stats of the form numXxx record counts of events occurring, such as calls to functions and specific results. The stats of the form bytesXxx collect cumulative sizes.

In addition, the data callerSize, callerModule, callerFile, callerLine, and callerTime is associated with each specific allocation. This data prefixes each allocation.

struct AllocationInfo;
Per-allocation information that can be iterated upon by using byAllocation. This only tracks live allocations and is useful for e.g. tracking memory leaks.

Example:
AllocatorWithStats!(Mallocator, Options.all) a;
auto d1 = a.allocate(10);
auto d2 = a.allocate(11);
a.deallocate(d1);
foreach (ref e; a.byAllocation)
{
    writeln("Allocation module: ", e.callerModule);
}

const size_t callerSize();
const string callerModule();
const string callerFile();
const uint callerLine();
const uint callerFunction();
const const(SysTime) callerTime();
Read-only property defined by the corresponding flag chosen in options.

struct CascadingAllocator(alias make);
Given make as a function that returns fresh allocators, CascadingAllocator creates an allocator that lazily creates as many allocators are needed for satisfying client allocation requests.

The management data of the allocators is stored in memory obtained from the allocators themselves, in a private linked list.

Examples:
// Create an allocator based upon 4MB regions, fetched from the GC heap.
CascadingAllocator!({ return Region!()(new void[1024 * 4096]); }) a;
auto b1 = a.allocate(1024 * 8192);
assert(b1 is null); // can't allocate more than 4MB at a time
b1 = a.allocate(1024 * 10);
assert(b1.length == 1024 * 10);
a.deallocateAll();

alias Allocator = typeof(make());
Alias for typeof(make).

uint alignment;
void[] allocate(size_t s);
Standard primitives.

bool owns(void[] b);
Defined only if Allocator.owns is defined.

void[] resolveInternalPointer(void* p);
Defined only if Allocator.resolveInternalPointer is defined.

bool expand(ref void[] b, size_t delta);
Defined only if Allocator.expand is defined.

bool reallocate(ref void[] b, size_t s);
Allows moving data from one Allocator to another.

void deallocate(void[] b);
Defined only if Allocator.deallocate is defined.

void deallocateAll();
Defined only if Allocator.deallocateAll is defined.

struct Segregator(size_t threshold, SmallAllocator, LargeAllocator);
Dispatches allocations (and deallocations) between two allocators (SmallAllocator and LargeAllocator) depending on the size allocated, as follows. All allocations smaller than or equal to threshold will be dispatched to SmallAllocator. The others will go to LargeAllocator.

If both allocators are shared, the Segregator will also offer shared methods.

Examples:
alias A =
    Segregator!(
        1024 * 4,
        Segregator!(
            128, Freelist!(Mallocator, 0, 128),
            GCAllocator),
        Segregator!(
            1024 * 1024, Mallocator,
            GCAllocator)
        );
A a;
auto b = a.allocate(200);
assert(b.length == 200);
a.deallocate(b);

uint alignment;
The alignment offered is the minimum of the two allocators' alignment.

size_t goodAllocSize(size_t s);
This method is defined only if at least one of the allocators defines it. The good allocation size is obtained from SmallAllocator if s <= threshold, or LargeAllocator otherwise. (If one of the allocators does not define goodAllocSize, the default implementation in this module applies.)

void[] allocate(size_t);
The memory is obtained from SmallAllocator if s <= threshold, or LargeAllocator otherwise.

bool owns(void[] b);
This method is defined only if both allocators define it. The call is forwarded to SmallAllocator if b.length <= threshold, or LargeAllocator otherwise.

bool expand(ref void[] b, size_t delta);
This method is defined only if at least one of the allocators defines it. If SmallAllocator defines expand and b.length + delta <= threshold, the call is forwarded to SmallAllocator. If $( LargeAllocator) defines expand and b.length > threshold, the call is forwarded to LargeAllocator. Otherwise, the call returns false.

bool reallocate(ref void[] b, size_t s);
This method is defined only if at least one of the allocators defines it. If SmallAllocator defines reallocate and b.length <= threshold && s <= threshold, the call is forwarded to SmallAllocator. If LargeAllocator defines expand and b.length > threshold && s > threshold, the call is forwarded to LargeAllocator. Otherwise, the call returns false.

void deallocate(void[] b);
This function is defined only if both allocators define it, and forwards appropriately depending on b.length.

void deallocateAll();
This function is defined only if both allocators define it, and calls deallocateAll for them in turn.

ref auto allocatorForSize(size_t s)();
Composite allocators involving nested instantiations of Segregator make it difficult to access individual sub-allocators stored within. allocatorForSize simplifies the task by supplying the allocator nested inside a Segregator that is responsible for a specific size s.

Example:
alias A = Segregator!(300,
    Segregator!(200, A1, A2),
    A3);
A a;
static assert(typeof(a.allocatorForSize!10) == A1);
static assert(typeof(a.allocatorForSize!250) == A2);
static assert(typeof(a.allocatorForSize!301) == A3);

template Segregator(Args...) if (Args.length > 3)
A Segregator with more than three arguments expands to a composition of elemental Segregators, as illustrated by the following example:

alias A =
    Segregator!(
        n1, A1,
        n2, A2,
        n3, A3,
        A4
    );

With this definition, allocation requests for n1 bytes or less are directed to A1; requests between n1 + 1 and n2 bytes (inclusive) are directed to A2; requests between n2 + 1 and n3 bytes (inclusive) are directed to A3; and requests for more than n3 bytes are directed to A4. If some particular range should not be handled, NullAllocator may be used appropriately.

Examples:
alias A =
    Segregator!(
        128, Freelist!(Mallocator, 0, 128),
        1024 * 4, GCAllocator,
        1024 * 1024, Mallocator,
        GCAllocator
    );
A a;
auto b = a.allocate(201);
assert(b.length == 201);
a.deallocate(b);

struct Bucketizer(Allocator, size_t min, size_t max, size_t step);
A Bucketizer uses distinct allocators for handling allocations of sizes in the intervals [min, min + step - 1], [min + step, min + 2 * step - 1], [min + 2 * step, min + 3 * step - 1], ..., [max - step + 1, max].

Bucketizer holds a fixed-size array of allocators and dispatches calls to them appropriately. The size of the array is (max + 1 - min) / step, which must be an exact division.

Allocations for sizes smaller than min or larger than max are illegal for Bucketizer. To handle them separately, Segregator may be of use.

Examples:
Bucketizer!(Freelist!(Mallocator, 0, unbounded),
    65, 512, 64) a;
auto b = a.allocate(400);
assert(b.length == 400, text(b.length));
a.deallocate(b);

Allocator[(max - (min - 1)) / step] buckets;
The array of allocators is publicly available for e.g. initialization

and inspection.

uint alignment;
The alignment offered is the same as Allocator.alignment.

const size_t goodAllocSize(size_t bytes);
Rounds up to the maximum size of the bucket in which bytes falls.

const bool owns(void[] b);
Returns b.length >= min && b.length <= max.

void[] allocate(size_t bytes);
Directs the call to either one of the buckets allocators.

bool expand(ref void[] b, size_t delta);
This method allows expansion within the respective bucket range. It succeeds if both b.length and b.length + delta fall in a range of the form [min + k * step, min + (k + 1) * step - 1].

void deallocate(void[] b);
This method is only defined if Allocator defines deallocate.

void deallocateAll();
This method is only defined if all allocators involved define deallocateAll, and calls it for each bucket in turn.

void[] resolveInternalPointer(void* p);
This method is only defined if all allocators involved define resolveInternalPointer, and tries it for each bucket in turn.

struct ThreadLocal(A);
Stores an allocator object in thread-local storage (i.e. non-shared D global). ThreadLocal!A is a subtype of A so it appears to implement A's allocator primitives.

A must hold state, otherwise ThreadLocal!A refuses instantiation. This means e.g. ThreadLocal!Mallocator does not work because Mallocator's state is not stored as members of Mallocator, but instead is hidden in the C library implementation.

Examples:
static assert(!is(ThreadLocal!Mallocator));
static assert(!is(ThreadLocal!GCAllocator));
alias ThreadLocal!(Freelist!(GCAllocator, 0, 8, 1)) Allocator;
auto b = Allocator.it.allocate(5);
static assert(hasMember!(Allocator, "allocate"));

A it;
The allocator instance.

this();
ThreadLocal disables all constructors. The intended usage is ThreadLocal!A.it.

interface IAllocator;
Dynamic version of an allocator. This should be used wherever a uniform type is required for encapsulating various allocator implementations.

See Also:
ISharedAllocator

abstract @property uint alignment();
Returns the alignment offered.

abstract size_t goodAllocSize(size_t s);
Returns the good allocation size that guarantees zero internal fragmentation.

abstract void[] allocate(size_t);
Allocates memory. The default returns null.

abstract Ternary owns(void[] b);
Returns Ternary.yes if the allocator owns b, Ternary.no if the allocator doesn't own b, and Ternary.unknown if ownership not supported by the allocator.

abstract Ternary expand(ref void[], size_t);
Expands a memory block in place. If expansion not supported by the allocator, returns Ternary.unknown. If implemented, returns Ternary.yes if expansion succeeded, Ternary.no otherwise.

abstract bool reallocate(ref void[], size_t);
Reallocates a memory block.

abstract Ternary deallocate(void[]);
Deallocates a memory block. Returns Ternary.unknown if deallocation is not supported. A simple way to check that an allocator supports deallocation is to call deallocate(null).

abstract Ternary deallocateAll();
Deallocates all memory. Returns Ternary.unknown if deallocation is not supported.

abstract void[] allocateAll();
Allocates and returns all memory available to this allocator.

interface ISharedAllocator;
Shared version of IAllocator.

abstract shared @property uint alignment();
abstract shared size_t goodAllocSize(size_t s);
abstract shared void[] allocate(size_t);
abstract shared Ternary owns(void[] b);
abstract shared Ternary expand(ref void[], size_t);
abstract shared bool reallocate(ref void[], size_t);
abstract shared Ternary deallocate(void[]);
abstract shared Ternary deallocateAll();
abstract shared void[] allocateAll();
These methods prescribe similar semantics to their CAllocator counterparts for shared allocators.

auto allocatorObject(A)(auto ref A a);
Returns a dynamically-typed CAllocator built around a given statically-typed allocator a of type A, as follows.

  • If A has no state, the resulting object is allocated in static shared storage.
  • If A has state and is copyable, the result will store a copy of it within. The result itself is allocated in its own statically-typed allocator.
  • If A has state and is not copyable, the result will move the passed-in argument into the result. The result itself is allocated in its own statically-typed allocator.

class CAllocatorImpl(Allocator): Select!(is(typeof(Allocator.it) == shared), ISharedAllocator, IAllocator);
Implementation of CAllocator using Allocator. This adapts a statically-built allocator type to a uniform dynamic interface (either IAllocator or ISharedAllocator, depending on whether Allocator offers a shared instance it or not) that is directly usable by non-templated code.

Usually CAllocatorImpl is used indirectly by calling allocatorObject.

Examples:
/// Define an allocator bound to the built-in GC.
shared ISharedAllocator alloc = allocatorObject(GCAllocator.it);
auto b = alloc.allocate(42);
assert(b.length == 42);
assert(alloc.deallocate(b) == Ternary.yes);

// Define an elaborate allocator and bind it to the class API.
// Note that the same variable "alloc" is used.
alias FList = Freelist!(GCAllocator, 0, unbounded);
alias A = ThreadLocal!(
    Segregator!(
        8, Freelist!(GCAllocator, 0, 8),
        128, Bucketizer!(FList, 1, 128, 16),
        256, Bucketizer!(FList, 129, 256, 32),
        512, Bucketizer!(FList, 257, 512, 64),
        1024, Bucketizer!(FList, 513, 1024, 128),
        2048, Bucketizer!(FList, 1025, 2048, 256),
        3584, Bucketizer!(FList, 2049, 3584, 512),
        4072 * 1024, CascadingAllocator!(
            () => HeapBlock!(4096)(GCAllocator.it.allocate(4072 * 1024))),
        GCAllocator
    )
);

auto alloc2 = allocatorObject(A.it);
b = alloc.allocate(101);
assert(alloc.deallocate(b) == Ternary.yes);

Allocator impl;
The implementation is available as a public member.

struct InternalPointersTree(Allocator);
InternalPointersTree adds a primitive on top of another allocator: calling resolveInternalPointer(p) returns the block within which the internal pointer p lies. Pointers right after the end of allocated blocks are also considered internal.

The implementation stores three additional words with each allocation (one for the block size and two for search management).

Parent parent;
The implementation is available as a public member.

void[] allocate(size_t bytes);
void deallocate(void[] b);
bool reallocate(ref void[] b, size_t s);
bool owns(void[] b);
bool empty();
Allocator API.

void[] resolveInternalPointer(void* p);
Returns the block inside which p resides, or null if the pointer does not belong.