The OpenD Programming Language

// 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))());
}