SmallVector

smallvector.d

struct SmallVector(T, size_t SIZE)
{
    private T[SIZE] small_buffer;
    private T* begin_ptr;
    private size_t size;
    private size_t capacity = SIZE;

    invariant
    {
        assert(capacity >= size);
    }

    @disable this(this);

    ~this()
    {
        import core.stdc.stdlib : free;

        if (begin_ptr)
        {
            free(begin_ptr);
        }
    }

    private inout(T)* data() inout nothrow pure
    {
        return begin_ptr ? begin_ptr : small_buffer.ptr;
    }

    private inout(T)* begin() inout nothrow pure
    {
        return data();
    }

    private inout(T)* end() inout nothrow pure
    {
        return data() + size;
    }

    private void reserve(size_t count)
    {
        assert(capacity >= size);
        assert(capacity >= SIZE);
        if (count + size > capacity)
        {
            import core.stdc.stdlib : malloc, realloc;
            import core.stdc.string : memcpy;

            if (capacity == SIZE)
            {
                capacity = size + count;
                begin_ptr = cast(T*) malloc(capacity * T.sizeof);
                memcpy(begin_ptr, small_buffer.ptr, size * T.sizeof);
            }
            else
            {
                capacity = size + count;
                begin_ptr = cast(T*) realloc(begin_ptr, capacity * T.sizeof);
            }
        }
    }

    private void internalAppend(const(T)* ptr, size_t data_size)
    {
        import core.stdc.string : memcpy;

        reserve(data_size);
        memcpy(end, ptr, data_size * T.sizeof);
        size += data_size;
    }

    bool isSmall() const nothrow pure
    {
        return begin_ptr is null;
    }

    size_t opDollar(size_t dim : 0)() const pure nothrow
    {
        return size;
    }

    size_t length() const nothrow pure
    {
        return size;
    }

    bool empty() const nothrow pure
    {
        return size == 0;
    }

    ref inout(T) front() inout nothrow pure
    {
        assert(size > 0);
        return begin[0];
    }

    ref inout(T) back() inout nothrow pure
    {
        assert(size > 0);
        return end[-1];
    }

    ref inout(T) opIndex(size_t i) inout nothrow pure
    {
        assert(i <= size);
        return begin[i];
    }

    inout(T)[] opSlice() inout nothrow pure
    {
        return begin[0 .. size];
    }

    inout(T)[] opSlice(size_t a, size_t b) inout nothrow pure
    {
        assert(a <= b && b <= size);
        return begin[a .. b];
    }

    void length(size_t length)
    {
        if (length > size)
        {
            reserve(length - size);
            begin[size .. length][] = T.init;
        }
        size = length;
    }

    void opOpAssign(string op : "~", U)(U item) if (is(U : T))
    {
        internalAppend(&item, 1);
    }

    void opOpAssign(string op : "~", U)(U[] item) if (is(U : T))
    {
        internalAppend(item.ptr, item.length);
    }

    void opOpAssign(string op : "~", size_t N)(ref const SmallVector!(T, N) other)
    {
        internalAppend(other.begin, other.size);
    }

    void opAssign(U)(U item) if (is(U : T))
    {
        size = 0;
        this ~= item;
    }

    void opAssign(U)(U[] items) if (is(U : T))
    {
        size = 0;
        this ~= items;
    }

    void opAssign(size_t N)(ref const SmallVector!(T, N) other)
    {
        size = 0;
        this ~= other;
    }
}

unittest
{
    auto vector = SmallVector!(int, 1)();
    assert(vector.empty);
    assert(vector.length == 0);
    vector ~= 1;
    assert(!vector.empty);
    assert(vector.length == 1);
    assert(vector.isSmall);
    vector.front = 1;
    assert(vector.front == 1);
    assert(vector.back == 1);
    vector ~= 5;
    assert(!vector.empty);
    assert(vector.length == 2);
    assert(!vector.isSmall);
    assert(vector.front == 1);
    assert(vector.back == 5);
}

// Test expanding leads default value.
unittest
{
    struct M
    {
        int data = 123;
    }

    auto vector = SmallVector!(M, 1)();
    vector.length = 1;
    assert(vector.length == 1);
    assert(vector[] == [M.init]);
}

// Test append array.
unittest
{
    auto vector = SmallVector!(int, 2)();
    vector ~= [1, 2, 3];
    assert(!vector.isSmall);
    assert(vector.length == 3);
    assert(vector.capacity == 3);
    assert(vector[] == [1, 2, 3]);
    assert(vector.front == 1);
    assert(vector.back == 3);
}

// Test set array.
unittest
{
    auto vector = SmallVector!(int, 2)();
    assert(vector.length == 0);
    vector = [1, 2];
    assert(vector.length == 2);
    assert(vector[] == [1, 2]);
    assert(vector.isSmall);
    vector = [1, 2, 3];
    assert(vector.length == 3);
    assert(vector[] == [1, 2, 3]);
    assert(!vector.isSmall);
}

// Test set from other.
unittest
{
    auto one = SmallVector!(int, 2)();
    auto two = SmallVector!(int, 3)();
    two = [1, 2, 3];
    one = two;
    assert(one[] == [1, 2, 3]);
}

// Test append to self.
unittest
{
    auto one = SmallVector!(int, 2)();
    // Appending empty.
    one ~= one;
    assert(one.isSmall);
    // Filling and appending again.
    one = [1, 2];
    assert(one.isSmall);
    one ~= one;
    assert(one[] == [1, 2, 1, 2]);
    assert(!one.isSmall);
}

// Test append other.
unittest
{
    auto one = SmallVector!(int, 2)();
    auto two = SmallVector!(int, 3)();
    two = [1, 2, 3];
    one ~= two;
    assert(one[] == [1, 2, 3]);
}