// Written in the D programming language./**Utility and ancillary artifacts of `std.experimental.allocator`. This moduleshouldn't be used directly; its functionality will be migrated into moreappropriate parts of `std`. Authors: $(HTTP erdani.com, Andrei Alexandrescu), Timon Gehr (`Ternary`) Source: $(PHOBOSSRC std/experimental/allocator/common.d)*/module std.experimental.allocator.common;import std.algorithm.comparison, std.traits; /**Is `true` iff `A` is an allocator. */enum isAllocator(A) = (is(typeof(A.allocate(size_t.init)) == void[]) && is(typeof(A.alignment) : size_t)); ///@safe @nogc nothrow pureunittest{    import std.experimental.allocator.building_blocks.null_allocator : NullAllocator;    import std.experimental.allocator.mallocator : Mallocator;    import std.experimental.allocator.gc_allocator : GCAllocator;    import std.experimental.allocator.mmap_allocator : MmapAllocator;    static assert(isAllocator!NullAllocator);    static assert(isAllocator!Mallocator);    static assert(isAllocator!GCAllocator);    static assert(isAllocator!MmapAllocator);    static assert(!isAllocator!int);} /**Returns the size in bytes of the state that needs to be allocated to hold anobject of type `T`. `stateSize!T` is zero for `struct`s that are notnested and have no nonstatic member variables. */template stateSize(T){    static if (is(T == class) || is(T == interface))        enum stateSize = __traits(classInstanceSize, T);    else static if (is(T == struct) || is(T == union))        enum stateSize = Fields!T.length || isNested!T ? T.sizeof : 0;    else static if (is(T == void))        enum size_t stateSize = 0;    else        enum stateSize = T.sizeof;} @safe @nogc nothrow pureunittest{    static assert(stateSize!void == 0);    struct A {}    static assert(stateSize!A == 0);    struct B { int x; }    static assert(stateSize!B == 4);    interface I1 {}    //static assert(stateSize!I1 == 2 * size_t.sizeof);    class C1 {}    static assert(stateSize!C1 == 3 * size_t.sizeof);    class C2 { char c; }    static assert(stateSize!C2 == 4 * size_t.sizeof);    static class C3 { char c; }    static assert(stateSize!C3 == 2 * size_t.sizeof + char.sizeof);} /**State of an allocator `A`. `AllocatorState!(A).sizeof` is zero for `A` being `NullAllocator`, `Mallocator`,`GCAllocator`, and `MMapAllocator` and typically non-zero for the other. */mixin template AllocatorState(A)if (isAllocator!A){    static if (stateSize!A == 0)        alias allocator = A.instance;    else        A allocator;} ///@safe @nogc nothrow pureunittest{    import std.experimental.allocator.building_blocks.null_allocator : NullAllocator;    import std.experimental.allocator.mallocator : Mallocator;    import std.experimental.allocator.gc_allocator : GCAllocator;    import std.experimental.allocator.mmap_allocator : MmapAllocator;    struct S    {        mixin AllocatorState!NullAllocator n;        mixin AllocatorState!GCAllocator g;        mixin AllocatorState!Mallocator m;        mixin AllocatorState!MmapAllocator p;    }    static assert(S.sizeof == 1);} /**Returns `true` if the `Allocator` has the alignment known at compile time;otherwise it returns `false`. */template hasStaticallyKnownAlignment(Allocator){    enum hasStaticallyKnownAlignment = __traits(compiles,                                                {enum x = Allocator.alignment;});} /**`chooseAtRuntime` is a compile-time constant of type `size_t` that severalparameterized structures in this module recognize to mean deferral to runtime ofthe exact value. For example, $(D BitmappedBlock!(Allocator, 4096)) (described indetail below) defines a block allocator with block size of 4096 bytes, whereas$(D BitmappedBlock!(Allocator, chooseAtRuntime)) defines a block allocator that has afield storing the block size, initialized by the user.*/enum chooseAtRuntime = size_t.max - 1; /**`unbounded` is a compile-time constant of type `size_t` that severalparameterized structures in this module recognize to mean "infinite" bounds forthe 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 thenumber of nodes.*/enum unbounded = size_t.max; /**The alignment that is guaranteed to accommodate any D object allocation on thecurrent platform.*/enum uint platformAlignment = std.algorithm.comparison.max(double.alignof, real.alignof); /**The default good size allocation is deduced as `n` rounded up to theallocator's alignment.*/size_t goodAllocSize(A)(auto ref A a, size_t n){    return n.roundUpToMultipleOf(a.alignment);} /*Returns s rounded up to a multiple of base.*/@safe @nogc nothrow purepackage size_t roundUpToMultipleOf(size_t s, uint base){    assert(base);    auto rem = s % base;    return rem ? s + base - rem : s;} @safe @nogc nothrow pureunittest{    assert(10.roundUpToMultipleOf(11) == 11);    assert(11.roundUpToMultipleOf(11) == 11);    assert(12.roundUpToMultipleOf(11) == 22);    assert(118.roundUpToMultipleOf(11) == 121);} /*Returns `n` rounded up to a multiple of alignment, which must be a power of 2.*/@safe @nogc nothrow purepackage size_t roundUpToAlignment(size_t n, uint alignment){    import std.math.traits : isPowerOf2;    assert(alignment.isPowerOf2);    immutable uint slack = cast(uint) n & (alignment - 1);    const result = slack        ? n + alignment - slack        : n;    assert(result >= n);    return result;} @safe @nogc nothrow pureunittest{    assert(10.roundUpToAlignment(4) == 12);    assert(11.roundUpToAlignment(2) == 12);    assert(12.roundUpToAlignment(8) == 16);    assert(118.roundUpToAlignment(64) == 128);} /*Returns `n` rounded down to a multiple of alignment, which must be a power of 2.*/@safe @nogc nothrow purepackage size_t roundDownToAlignment(size_t n, uint alignment){    import std.math.traits : isPowerOf2;    assert(alignment.isPowerOf2);    return n & ~size_t(alignment - 1);} @safe @nogc nothrow pureunittest{    assert(10.roundDownToAlignment(4) == 8);    assert(11.roundDownToAlignment(2) == 10);    assert(12.roundDownToAlignment(8) == 8);    assert(63.roundDownToAlignment(64) == 0);} /*Advances the beginning of `b` to start at alignment `a`. The resulting buffermay therefore be shorter. Returns the adjusted buffer, or null if obtaining anon-empty buffer is impossible.*/@nogc nothrow purepackage void[] roundUpToAlignment(void[] b, uint a){    auto e = b.ptr + b.length;    auto p = cast(void*) roundUpToAlignment(cast(size_t) b.ptr, a);    if (e <= p) return null;    return p[0 .. e - p];} @nogc nothrow pure@system unittest{    void[] empty;    assert(roundUpToAlignment(empty, 4) == null);    char[128] buf;    // At least one pointer inside buf is 128-aligned    assert(roundUpToAlignment(buf, 128) !is null);} /*Like `a / b` but rounds the result up, not down.*/@safe @nogc nothrow purepackage size_t divideRoundUp(size_t a, size_t b){    assert(b);    return (a + b - 1) / b;} /*Returns `s` rounded up to a multiple of `base`.*/@nogc nothrow purepackage void[] roundStartToMultipleOf(void[] s, uint base){    assert(base);    auto p = cast(void*) roundUpToMultipleOf(        cast(size_t) s.ptr, base);    auto end = s.ptr + s.length;    return p[0 .. end - p];} nothrow pure@system unittest{    void[] p;    assert(roundStartToMultipleOf(p, 16) is null);    p = new ulong[10];    assert(roundStartToMultipleOf(p, 16) is p);} /*Returns `s` rounded up to the nearest power of 2.*/@safe @nogc nothrow purepackage size_t roundUpToPowerOf2(size_t s){    import std.meta : AliasSeq;    assert(s <= (size_t.max >> 1) + 1);    --s;    static if (size_t.sizeof == 4)        alias Shifts = AliasSeq!(1, 2, 4, 8, 16);    else        alias Shifts = AliasSeq!(1, 2, 4, 8, 16, 32);    foreach (i; Shifts)    {        s |= s >> i;    }    return s + 1;} @safe @nogc nothrow pureunittest{    assert(0.roundUpToPowerOf2 == 0);    assert(1.roundUpToPowerOf2 == 1);    assert(2.roundUpToPowerOf2 == 2);    assert(3.roundUpToPowerOf2 == 4);    assert(7.roundUpToPowerOf2 == 8);    assert(8.roundUpToPowerOf2 == 8);    assert(10.roundUpToPowerOf2 == 16);    assert(11.roundUpToPowerOf2 == 16);    assert(12.roundUpToPowerOf2 == 16);    assert(118.roundUpToPowerOf2 == 128);    assert((size_t.max >> 1).roundUpToPowerOf2 == (size_t.max >> 1) + 1);    assert(((size_t.max >> 1) + 1).roundUpToPowerOf2 == (size_t.max >> 1) + 1);} /*Returns the number of trailing zeros of `x`.*/@safe @nogc nothrow purepackage uint trailingZeros(ulong x){    import core.bitop : bsf;    return x == 0 ? 64 : bsf(x);} @safe @nogc nothrow pureunittest{    assert(trailingZeros(0) == 64);    assert(trailingZeros(1) == 0);    assert(trailingZeros(2) == 1);    assert(trailingZeros(3) == 0);    assert(trailingZeros(4) == 2);} /*Returns `true` if `ptr` is aligned at `alignment`.*/@nogc nothrow purepackage bool alignedAt(T)(T* ptr, uint alignment){    return cast(size_t) ptr % alignment == 0;} /*Returns the effective alignment of `ptr`, i.e. the largest power of two that isa divisor of `ptr`.*/@nogc nothrow purepackage size_t effectiveAlignment(void* ptr){    return (cast(size_t) 1) << trailingZeros(cast(size_t) ptr);} @nogc nothrow pure@system unittest{    int x;    assert(effectiveAlignment(&x) >= int.alignof);     const max = (cast(size_t) 1) << (size_t.sizeof * 8 - 1);    assert(effectiveAlignment(cast(void*) max) == max);} /*Aligns a pointer down to a specified alignment. The resulting pointer is lessthan or equal to the given pointer.*/@nogc nothrow purepackage void* alignDownTo(return scope void* ptr, uint alignment){    import std.math.traits : isPowerOf2;    assert(alignment.isPowerOf2);    return cast(void*) (cast(size_t) ptr & ~(alignment - 1UL));} /*Aligns a pointer up to a specified alignment. The resulting pointer is greaterthan or equal to the given pointer.*/@nogc nothrow purepackage void* alignUpTo(return scope void* ptr, uint alignment){    import std.math.traits : isPowerOf2;    assert(alignment.isPowerOf2);    immutable uint slack = cast(size_t) ptr & (alignment - 1U);    return slack ? ptr + alignment - slack : ptr;} @safe @nogc nothrow purepackage bool isGoodStaticAlignment(uint x){    import std.math.traits : isPowerOf2;    return x.isPowerOf2;} @safe @nogc nothrow purepackage bool isGoodDynamicAlignment(uint x){    import std.math.traits : isPowerOf2;    return x.isPowerOf2 && x >= (void*).sizeof;} /**The default `reallocate` function first attempts to use `expand`. If $(DAllocator.expand) is not defined or returns `false`, `reallocate`allocates a new block of memory of appropriate size and copies data from the oldblock to the new block. Finally, if `Allocator` defines `deallocate`, $(Dreallocate) uses it to free the old memory block. `reallocate` does not attempt to use `Allocator.reallocate` even ifdefined. This is deliberate so allocators may use it internally within their ownimplementation of `reallocate`. */bool reallocate(Allocator)(ref Allocator a, ref void[] b, size_t s){    if (b.length == s) return true;    static if (hasMember!(Allocator, "expand"))    {        if (b.length <= s && a.expand(b, s - b.length)) return true;    }    auto newB = a.allocate(s);    if (newB.length != s) return false;    if (newB.length <= b.length) newB[] = b[0 .. newB.length];    else newB[0 .. b.length] = b[];    static if (hasMember!(Allocator, "deallocate"))        a.deallocate(b);    b = newB;    return true;} /** The default `alignedReallocate` function first attempts to use `expand`.If `Allocator.expand` is not defined or returns `false`,  $(DalignedReallocate) allocates a new block of memory of appropriate size andcopies data from the old block to the new block. Finally, if `Allocator`defines `deallocate`, `alignedReallocate` uses it to free the old memoryblock. `alignedReallocate` does not attempt to use `Allocator.reallocate` even ifdefined. This is deliberate so allocators may use it internally within their ownimplementation of `reallocate`. */bool alignedReallocate(Allocator)(ref Allocator alloc,        ref void[] b, size_t s, uint a)if (hasMember!(Allocator, "alignedAllocate")){    static if (hasMember!(Allocator, "expand"))    {        if (b.length <= s && b.ptr.alignedAt(a)            && alloc.expand(b, s - b.length)) return true;    }    else    {        if (b.length == s && b.ptr.alignedAt(a)) return true;    }    auto newB = alloc.alignedAllocate(s, a);    if (newB.length != s) return false;    if (newB.length <= b.length) newB[] = b[0 .. newB.length];    else newB[0 .. b.length] = b[];    static if (hasMember!(Allocator, "deallocate"))        alloc.deallocate(b);    b = newB;    return true;} @system unittest{    bool called = false;    struct DummyAllocator    {        void[] alignedAllocate(size_t size, uint alignment)        {            called = true;            return null;        }    }     struct DummyAllocatorExpand    {        void[] alignedAllocate(size_t size, uint alignment)        {            return null;        }         bool expand(ref void[] b, size_t length)        {            called = true;            return true;        }    }     char[128] buf;    uint alignment = 32;    auto alignedPtr = roundUpToMultipleOf(cast(size_t) buf.ptr, alignment);    auto diff = alignedPtr - cast(size_t) buf.ptr;     // Align the buffer to 'alignment'    void[] b = cast(void[]) (buf.ptr + diff)[0 .. buf.length - diff];     DummyAllocator a1;    // Ask for same length and alignment, should not call 'alignedAllocate'    assert(alignedReallocate(a1, b, b.length, alignment));    assert(!called);     // Ask for same length, different alignment    // should call 'alignedAllocate' if not aligned to new value    alignedReallocate(a1, b, b.length, alignment + 1);

Lines 1–500 of 812. Load more