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 */ 8 module core.internal.container.array; 9 10 static import common = core.internal.container.common; 11 12 import core.exception : onOutOfMemoryErrorNoGC; 13 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 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 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 } 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 }