1/**
2 * Array container for internal usage.
3 *
4 * Copyright: Copyright Martin Nowak 2013.
5 * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 * Authors:   Martin Nowak
7 */
8module core.internal.container.array;
9
10static import common = core.internal.container.common;
11
12import core.exception : onOutOfMemoryErrorNoGC;
13
14struct Array(T)
15{
16nothrow:
17    @disable this(this);
18
19    ~this()
20    {
21        reset();
22    }
23
24    void reset()
25    {
26        length = 0;
27    }
28
29    @property size_t length() const
30    {
31        return _length;
32    }
33
34    @property void length(size_t nlength)
35    {
36        import core.checkedint : mulu;
37
38        bool overflow = false;
39        size_t reqsize = mulu(T.sizeof, nlength, overflow);
40        if (!overflow)
41        {
42            if (nlength < _length)
43                foreach (ref val; _ptr[nlength .. _length]) common.destroy(val);
44            _ptr = cast(T*)common.xrealloc(_ptr, reqsize);
45            if (nlength > _length)
46                foreach (ref val; _ptr[_length .. nlength]) common.initialize(val);
47            _length = nlength;
48        }
49        else
50            onOutOfMemoryErrorNoGC();
51
52    }
53
54    @property bool empty() const
55    {
56        return !length;
57    }
58
59    @property ref inout(T) front() inout
60    in { assert(!empty); }
61    do
62    {
63        return _ptr[0];
64    }
65
66    @property ref inout(T) back() inout
67    in { assert(!empty); }
68    do
69    {
70        return _ptr[_length - 1];
71    }
72
73    ref inout(T) opIndex(size_t idx) inout
74    in { assert(idx < length); }
75    do
76    {
77        return _ptr[idx];
78    }
79
80    inout(T)[] opSlice() inout
81    {
82        return _ptr[0 .. _length];
83    }
84
85    inout(T)[] opSlice(size_t a, size_t b) inout
86    in { assert(a < b && b <= length); }
87    do
88    {
89        return _ptr[a .. b];
90    }
91
92    alias length opDollar;
93
94    void insertBack()(auto ref T val)
95    {
96        import core.checkedint : addu;
97
98        bool overflow = false;
99        size_t newlength = addu(length, 1, overflow);
100        if (!overflow)
101        {
102            length = newlength;
103            back = val;
104        }
105        else
106            onOutOfMemoryErrorNoGC();
107    }
108
109    void popBack()
110    {
111        length = length - 1;
112    }
113
114    void remove(size_t idx)
115    in { assert(idx < length); }
116    do
117    {
118        foreach (i; idx .. length - 1)
119            _ptr[i] = _ptr[i+1];
120        popBack();
121    }
122
123    void swap(ref Array other)
124    {
125        auto ptr = _ptr;
126        _ptr = other._ptr;
127        other._ptr = ptr;
128        immutable len = _length;
129        _length = other._length;
130        other._length = len;
131    }
132
133    invariant
134    {
135        assert(!_ptr == !_length);
136    }
137
138private:
139    T* _ptr;
140    size_t _length;
141}
142
143unittest
144{
145    Array!size_t ary;
146
147    assert(ary[] == []);
148    ary.insertBack(5);
149    assert(ary[] == [5]);
150    assert(ary[$-1] == 5);
151    ary.popBack();
152    assert(ary[] == []);
153    ary.insertBack(0);
154    ary.insertBack(1);
155    assert(ary[] == [0, 1]);
156    assert(ary[0 .. 1] == [0]);
157    assert(ary[1 .. 2] == [1]);
158    assert(ary[$ - 2 .. $] == [0, 1]);
159    size_t idx;
160    foreach (val; ary) assert(idx++ == val);
161    foreach_reverse (val; ary) assert(--idx == val);
162    foreach (i, val; ary) assert(i == val);
163    foreach_reverse (i, val; ary) assert(i == val);
164
165    ary.insertBack(2);
166    ary.remove(1);
167    assert(ary[] == [0, 2]);
168
169    assert(!ary.empty);
170    ary.reset();
171    assert(ary.empty);
172    ary.insertBack(0);
173    assert(!ary.empty);
174    destroy(ary);
175    assert(ary.empty);
176
177    // not copyable
178    static assert(!__traits(compiles, { Array!size_t ary2 = ary; }));
179    Array!size_t ary2;
180    static assert(!__traits(compiles, ary = ary2));
181    static void foo(Array!size_t copy) {}
182    static assert(!__traits(compiles, foo(ary)));
183
184    ary2.insertBack(0);
185    assert(ary.empty);
186    assert(ary2[] == [0]);
187    ary.swap(ary2);
188    assert(ary[] == [0]);
189    assert(ary2.empty);
190}
191
192unittest
193{
194    alias RC = common.RC!();
195    Array!RC ary;
196
197    size_t cnt;
198    assert(cnt == 0);
199    ary.insertBack(RC(&cnt));
200    assert(cnt == 1);
201    ary.insertBack(RC(&cnt));
202    assert(cnt == 2);
203    ary.back = ary.front;
204    assert(cnt == 2);
205    ary.popBack();
206    assert(cnt == 1);
207    ary.popBack();
208    assert(cnt == 0);
209}
210
211unittest
212{
213    import core.exception;
214    try
215    {
216        // Overflow ary.length.
217        auto ary = Array!size_t(cast(size_t*)0xdeadbeef, -1);
218        ary.insertBack(0);
219    }
220    catch (OutOfMemoryError)
221    {
222    }
223    try
224    {
225        // Overflow requested memory size for common.xrealloc().
226        auto ary = Array!size_t(cast(size_t*)0xdeadbeef, -2);
227        ary.insertBack(0);
228    }
229    catch (OutOfMemoryError)
230    {
231    }
232}
233