1 /**
2  * Array container for internal usage.
3  *
4  * Copyright: Copyright Martin Nowak 2013.
5  * License:   $(WEB www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6  * Authors:   Martin Nowak
7  */
8 module rt.util.container.array;
9 
10 static import common = rt.util.container.common;
11 
12 import core.exception : onOutOfMemoryErrorNoGC;
13 
Array(T)14 struct Array(T)
15 {
16 nothrow:
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     body
62     {
63         return _ptr[0];
64     }
65 
66     @property ref inout(T) back() inout
67     in { assert(!empty); }
68     body
69     {
70         return _ptr[_length - 1];
71     }
72 
73     ref inout(T) opIndex(size_t idx) inout
74     in { assert(idx < length); }
75     body
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     body
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     body
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 
138 private:
139     T* _ptr;
140     size_t _length;
141 }
142 
143 unittest
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 
192 unittest
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 
211 unittest
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     }
catch(OutOfMemoryError)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     }
catch(OutOfMemoryError)229     catch (OutOfMemoryError)
230     {
231     }
232 }
233