// Written in the D programming language.
/**
Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/segregator.d)
*/
module std.experimental.allocator.building_blocks.segregator;
import std.experimental.allocator.common;
/**
Dispatches allocations (and deallocations) between two allocators ($(D
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 $(D
shared) methods.
*/
struct Segregator(size_t threshold, SmallAllocator, LargeAllocator)
{
import std.algorithm.comparison : min;
import std.traits : hasMember, ReturnType;
import std.typecons : Ternary;
static if (stateSize!SmallAllocator) private SmallAllocator _small;
else private alias _small = SmallAllocator.instance;
static if (stateSize!LargeAllocator) private LargeAllocator _large;
else private alias _large = LargeAllocator.instance;
version (StdDdoc)
{
/**
The alignment offered is the minimum of the two allocators' alignment.
*/
enum uint alignment;
/**
This method is defined only if at least one of the allocators defines
it. The good allocation size is obtained from `SmallAllocator` if $(D
s <= threshold), or `LargeAllocator` otherwise. (If one of the
allocators does not define `goodAllocSize`, the default
implementation in this module applies.)
*/
static size_t goodAllocSize(size_t s);
/**
The memory is obtained from `SmallAllocator` if $(D s <= threshold),
or `LargeAllocator` otherwise.
*/
void[] allocate(size_t);
/**
This method is defined if both allocators define it, and forwards to
`SmallAllocator` or `LargeAllocator` appropriately.
*/
void[] alignedAllocate(size_t, uint);
/**
This method is defined only if at least one of the allocators defines
it. If `SmallAllocator` defines `expand` and $(D b.length +
delta <= threshold), the call is forwarded to `SmallAllocator`. If $(D
LargeAllocator) defines `expand` and $(D b.length > threshold), the
call is forwarded to `LargeAllocator`. Otherwise, the call returns
`false`.
*/
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 `reallocate` and $(D b.length <=
threshold && s <= threshold), the call is forwarded to $(D
SmallAllocator). If `LargeAllocator` defines `expand` and $(D
b.length > threshold && s > threshold), the call is forwarded to $(D
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, and work similarly to `reallocate`.
*/
bool alignedReallocate(ref void[] b, size_t s, uint a);
/**
This method is defined only if both allocators define it. The call is
forwarded to `SmallAllocator` if $(D b.length <= threshold), or $(D
LargeAllocator) otherwise.
*/
Ternary owns(void[] b);
/**
This function is defined only if both allocators define it, and forwards
appropriately depending on `b.length`.
*/
bool deallocate(void[] b);
/**
This function is defined only if both allocators define it, and calls
`deallocateAll` for them in turn.
*/
bool deallocateAll();
/**
This function is defined only if both allocators define it, and returns
the conjunction of `empty` calls for the two.
*/
Ternary empty();
}
/**
Composite allocators involving nested instantiations of `Segregator` make
it difficult to access individual sub-allocators stored within. $(D
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);
----
*/
ref auto allocatorForSize(size_t s)()
{
static if (s <= threshold)
static if (is(SmallAllocator == Segregator!(Args), Args...))
return _small.allocatorForSize!s;
else return _small;
else
static if (is(LargeAllocator == Segregator!(Args), Args...))
return _large.allocatorForSize!s;
else return _large;
}
enum uint alignment = min(SmallAllocator.alignment,
LargeAllocator.alignment);
private template Impl()
{
size_t goodAllocSize(size_t s)
{
return s <= threshold
? _small.goodAllocSize(s)
: _large.goodAllocSize(s);
}
void[] allocate(size_t s)
{
return s <= threshold ? _small.allocate(s) : _large.allocate(s);
}
static if (hasMember!(SmallAllocator, "alignedAllocate")
&& hasMember!(LargeAllocator, "alignedAllocate"))
void[] alignedAllocate(size_t s, uint a)
{
return s <= threshold
? _small.alignedAllocate(s, a)
: _large.alignedAllocate(s, a);
}
static if (hasMember!(SmallAllocator, "expand")
|| hasMember!(LargeAllocator, "expand"))
bool expand(ref void[] b, size_t delta)
{
if (!delta) return true;
if (b.length + delta <= threshold)
{
// Old and new allocations handled by _small
static if (hasMember!(SmallAllocator, "expand"))
return _small.expand(b, delta);
else
return false;
}
if (b.length > threshold)
{
// Old and new allocations handled by _large
static if (hasMember!(LargeAllocator, "expand"))
return _large.expand(b, delta);
else
return false;
}
// Oops, cross-allocator transgression
return false;
}
static if (hasMember!(SmallAllocator, "reallocate")
|| hasMember!(LargeAllocator, "reallocate"))
bool reallocate(ref void[] b, size_t s)
{
static if (hasMember!(SmallAllocator, "reallocate"))
if (b.length <= threshold && s <= threshold)
{
// Old and new allocations handled by _small
return _small.reallocate(b, s);
}
static if (hasMember!(LargeAllocator, "reallocate"))
if (b.length > threshold && s > threshold)
{
// Old and new allocations handled by _large
return _large.reallocate(b, s);
}
// Cross-allocator transgression
return .reallocate(this, b, s);
}
static if (hasMember!(SmallAllocator, "alignedReallocate")
|| hasMember!(LargeAllocator, "alignedReallocate"))
bool alignedReallocate(ref void[] b, size_t s, uint a)
{
static if (hasMember!(SmallAllocator, "alignedReallocate"))
if (b.length <= threshold && s <= threshold)
{
// Old and new allocations handled by _small
return _small.alignedReallocate(b, s, a);
}
static if (hasMember!(LargeAllocator, "alignedReallocate"))
if (b.length > threshold && s > threshold)
{
// Old and new allocations handled by _large
return _large.alignedReallocate(b, s, a);
}
// Cross-allocator transgression
return .alignedReallocate(this, b, s, a);
}
static if (hasMember!(SmallAllocator, "allocateZeroed")
|| hasMember!(LargeAllocator, "allocateZeroed"))
package(std) void[] allocateZeroed()(size_t s)
{
if (s <= threshold)
{
static if (hasMember!(SmallAllocator, "allocateZeroed"))
return _small.allocateZeroed(s);
else
{
auto b = _small.allocate(s);
(() @trusted => (cast(ubyte[]) b)[] = 0)(); // OK even if b is null.
return b;
}
}
else
{
static if (hasMember!(LargeAllocator, "allocateZeroed"))
return _large.allocateZeroed(s);
else
{
auto b = _large.allocate(s);
(() @trusted => (cast(ubyte[]) b)[] = 0)(); // OK even if b is null.
return b;
}
}
}
static if (hasMember!(SmallAllocator, "owns")
&& hasMember!(LargeAllocator, "owns"))
Ternary owns(void[] b)
{
return Ternary(b.length <= threshold
? _small.owns(b) : _large.owns(b));
}
static if (hasMember!(SmallAllocator, "deallocate")
&& hasMember!(LargeAllocator, "deallocate"))
bool deallocate(void[] data)
{
return data.length <= threshold
? _small.deallocate(data)
: _large.deallocate(data);
}
static if (hasMember!(SmallAllocator, "deallocateAll")
&& hasMember!(LargeAllocator, "deallocateAll"))
bool deallocateAll()
{
// Use & insted of && to evaluate both
return _small.deallocateAll() & _large.deallocateAll();
}
static if (hasMember!(SmallAllocator, "empty")
&& hasMember!(LargeAllocator, "empty"))
Ternary empty()
{
return _small.empty & _large.empty;
}
static if (hasMember!(SmallAllocator, "resolveInternalPointer")
&& hasMember!(LargeAllocator, "resolveInternalPointer"))
Ternary resolveInternalPointer(const void* p, ref void[] result)
{
Ternary r = _small.resolveInternalPointer(p, result);
return r == Ternary.no ? _large.resolveInternalPointer(p, result) : r;
}
}
private enum sharedMethods =
!stateSize!SmallAllocator
&& !stateSize!LargeAllocator
&& is(typeof(SmallAllocator.instance) == shared)
&& is(typeof(LargeAllocator.instance) == shared);
static if (sharedMethods)
{
static shared Segregator instance;
shared { mixin Impl!(); }
}
else
{
static if (!stateSize!SmallAllocator && !stateSize!LargeAllocator)
__gshared Segregator instance;
mixin Impl!();
}
}
///
@system unittest
{
import std.experimental.allocator.building_blocks.free_list : FreeList;
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.experimental.allocator.mallocator : Mallocator;
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);
}
/**
A `Segregator` with more than three arguments expands to a composition of
elemental `Segregator`s, 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 $(D n1 + 1) and `n2` bytes (inclusive) are
directed to `A2`; requests between $(D 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.
*/
template Segregator(Args...)
if (Args.length > 3)
{
// Binary search
private enum cutPoint = ((Args.length - 2) / 4) * 2;
static if (cutPoint >= 2)
{
alias Segregator = .Segregator!(
Args[cutPoint],
.Segregator!(Args[0 .. cutPoint], Args[cutPoint + 1]),
.Segregator!(Args[cutPoint + 2 .. $])
);
}
else
{
// Favor small sizes
alias Segregator = .Segregator!(
Args[0],
Args[1],
.Segregator!(Args[2 .. $])
);
}
}
///
@system unittest
{
import std.experimental.allocator.building_blocks.free_list : FreeList;
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.experimental.allocator.mallocator : Mallocator;
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);
}
@system unittest
{
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.experimental.allocator.building_blocks.kernighan_ritchie : KRRegion;
Segregator!(128, GCAllocator, KRRegion!GCAllocator) alloc;
assert((() nothrow @safe @nogc => alloc.goodAllocSize(1))()
== GCAllocator.instance.goodAllocSize(1));
// Note: we infer `shared` from GCAllocator.goodAllocSize so we need a
// shared object in order to be able to use the function
shared Segregator!(128, GCAllocator, GCAllocator) sharedAlloc;
assert((() nothrow @safe @nogc => sharedAlloc.goodAllocSize(1))()
== GCAllocator.instance.goodAllocSize(1));
}
@system unittest
{
import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
import std.typecons : Ternary;
alias A =
Segregator!(
128, BitmappedBlock!(4096),
BitmappedBlock!(4096)
);
A a = A(
BitmappedBlock!(4096)(new ubyte[4096 * 1024]),
BitmappedBlock!(4096)(new ubyte[4096 * 1024])
);
assert(a.empty == Ternary.yes);
auto b = a.allocate(42);
assert(b.length == 42);
assert(a.empty == Ternary.no);
assert(a.alignedReallocate(b, 256, 512));
assert(b.length == 256);
assert(a.alignedReallocate(b, 42, 512));
assert(b.length == 42);
assert((() pure nothrow @safe @nogc => a.owns(b))() == Ternary.yes);
assert((() pure nothrow @safe @nogc => a.owns(null))() == Ternary.no);
// Ensure deallocate inherits from parent allocators
assert((() nothrow @nogc => a.deallocate(b))());
assert(a.empty == Ternary.yes);
// Test that deallocateAll inherits from parents
auto c = a.allocate(42);
assert(c.length == 42);
assert((() pure nothrow @safe @nogc => a.expand(c, 58))());
assert(c.length == 100);
assert(a.empty == Ternary.no);
assert((() nothrow @nogc => a.deallocateAll())());
assert(a.empty == Ternary.yes);
}
@system unittest
{
import std.experimental.allocator.gc_allocator : GCAllocator;
import std.typecons : Ternary;
shared Segregator!(1024 * 4, GCAllocator, GCAllocator) a;
auto b = a.allocate(201);
assert(b.length == 201);
void[] p;
assert((() nothrow @safe @nogc => a.resolveInternalPointer(&b[0], p))() == Ternary.yes);
assert((() nothrow @safe @nogc => a.resolveInternalPointer(null, p))() == Ternary.no);
// Ensure deallocate inherits from parent allocators
assert((() nothrow @nogc => a.deallocate(b))());
}
@system unittest
{
import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlockWithInternalPointers;
import std.typecons : Ternary;
alias A =
Segregator!(
10_240, BitmappedBlockWithInternalPointers!(4096),
BitmappedBlockWithInternalPointers!(4096)
);
A a = A(
BitmappedBlockWithInternalPointers!(4096)(new ubyte[4096 * 1024]),
BitmappedBlockWithInternalPointers!(4096)(new ubyte[4096 * 1024])
);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
auto b = a.allocate(201);
assert(b.length == 201);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.no);
assert((() nothrow @nogc => a.deallocate(b))());
}
// Test that reallocate infers from parent
@system unittest
{
import std.experimental.allocator.mallocator : Mallocator;
alias a = Segregator!(10_240, Mallocator, Mallocator).instance;
auto b = a.allocate(42);
assert(b.length == 42);
assert((() nothrow @nogc => a.reallocate(b, 100))());
assert(b.length == 100);
assert((() nothrow @nogc => a.deallocate(b))());
}
@system unittest
{
import std.experimental.allocator.building_blocks.region : BorrowedRegion;
import std.typecons : Ternary;
auto a = Segregator!(10_240, BorrowedRegion!(), BorrowedRegion!())(
BorrowedRegion!()(new ubyte[4096 * 1024]),
BorrowedRegion!()(new ubyte[4096 * 1024]));
assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
auto b = a.alignedAllocate(42, 8);
assert(b.length == 42);
assert((() nothrow @nogc => a.alignedReallocate(b, 100, 8))());
assert(b.length == 100);
assert((() nothrow @safe @nogc => a.empty)() == Ternary.no);
assert((() nothrow @nogc => a.deallocate(b))());
}