libphobos/libdruntime/rt/util/container/array.d

/**
 * Array container for internal usage.
 *
 * Copyright: Copyright Martin Nowak 2013.
 * License:   $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
 * Authors:   Martin Nowak
 */
module rt.util.container.array;

static import common = rt.util.container.common;

import core.exception : onOutOfMemoryErrorNoGC;

struct Array(T)
{
nothrow:
    @disable this(this);

    ~this()
    {
        reset();
    }

    void reset()
    {
        length = 0;
    }

    @property size_t length() const
    {
        return _length;
    }

    @property void length(size_t nlength)
    {
        import core.checkedint : mulu;

        bool overflow = false;
        size_t reqsize = mulu(T.sizeof, nlength, overflow);
        if (!overflow)
        {
            if (nlength < _length)
                foreach (ref val; _ptr[nlength .. _length]) common.destroy(val);
            _ptr = cast(T*)common.xrealloc(_ptr, reqsize);
            if (nlength > _length)
                foreach (ref val; _ptr[_length .. nlength]) common.initialize(val);
            _length = nlength;
        }
        else
            onOutOfMemoryErrorNoGC();

    }

    @property bool empty() const
    {
        return !length;
    }

    @property ref inout(T) front() inout
    in { assert(!empty); }
    body
    {
        return _ptr[0];
    }

    @property ref inout(T) back() inout
    in { assert(!empty); }
    body
    {
        return _ptr[_length - 1];
    }

    ref inout(T) opIndex(size_t idx) inout
    in { assert(idx < length); }
    body
    {
        return _ptr[idx];
    }

    inout(T)[] opSlice() inout
    {
        return _ptr[0 .. _length];
    }

    inout(T)[] opSlice(size_t a, size_t b) inout
    in { assert(a < b && b <= length); }
    body
    {
        return _ptr[a .. b];
    }

    alias length opDollar;

    void insertBack()(auto ref T val)
    {
        import core.checkedint : addu;

        bool overflow = false;
        size_t newlength = addu(length, 1, overflow);
        if (!overflow)
        {
            length = newlength;
            back = val;
        }
        else
            onOutOfMemoryErrorNoGC();
    }

    void popBack()
    {
        length = length - 1;
    }

    void remove(size_t idx)
    in { assert(idx < length); }
    body
    {
        foreach (i; idx .. length - 1)
            _ptr[i] = _ptr[i+1];
        popBack();
    }

    void swap(ref Array other)
    {
        auto ptr = _ptr;
        _ptr = other._ptr;
        other._ptr = ptr;
        immutable len = _length;
        _length = other._length;
        other._length = len;
    }

    invariant
    {
        assert(!_ptr == !_length);
    }

private:
    T* _ptr;
    size_t _length;
}

unittest
{
    Array!size_t ary;

    assert(ary[] == []);
    ary.insertBack(5);
    assert(ary[] == [5]);
    assert(ary[$-1] == 5);
    ary.popBack();
    assert(ary[] == []);
    ary.insertBack(0);
    ary.insertBack(1);
    assert(ary[] == [0, 1]);
    assert(ary[0 .. 1] == [0]);
    assert(ary[1 .. 2] == [1]);
    assert(ary[$ - 2 .. $] == [0, 1]);
    size_t idx;
    foreach (val; ary) assert(idx++ == val);
    foreach_reverse (val; ary) assert(--idx == val);
    foreach (i, val; ary) assert(i == val);
    foreach_reverse (i, val; ary) assert(i == val);

    ary.insertBack(2);
    ary.remove(1);
    assert(ary[] == [0, 2]);

    assert(!ary.empty);
    ary.reset();
    assert(ary.empty);
    ary.insertBack(0);
    assert(!ary.empty);
    destroy(ary);
    assert(ary.empty);

    // not copyable
    static assert(!__traits(compiles, { Array!size_t ary2 = ary; }));
    Array!size_t ary2;
    static assert(!__traits(compiles, ary = ary2));
    static void foo(Array!size_t copy) {}
    static assert(!__traits(compiles, foo(ary)));

    ary2.insertBack(0);
    assert(ary.empty);
    assert(ary2[] == [0]);
    ary.swap(ary2);
    assert(ary[] == [0]);
    assert(ary2.empty);
}

unittest
{
    alias RC = common.RC!();
    Array!RC ary;

    size_t cnt;
    assert(cnt == 0);
    ary.insertBack(RC(&cnt));
    assert(cnt == 1);
    ary.insertBack(RC(&cnt));
    assert(cnt == 2);
    ary.back = ary.front;
    assert(cnt == 2);
    ary.popBack();
    assert(cnt == 1);
    ary.popBack();
    assert(cnt == 0);
}

unittest
{
    import core.exception;
    try
    {
        // Overflow ary.length.
        auto ary = Array!size_t(cast(size_t*)0xdeadbeef, -1);
        ary.insertBack(0);
    }
    catch (OutOfMemoryError)
    {
    }
    try
    {
        // Overflow requested memory size for common.xrealloc().
        auto ary = Array!size_t(cast(size_t*)0xdeadbeef, -2);
        ary.insertBack(0);
    }
    catch (OutOfMemoryError)
    {
    }
}