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

   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
  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     }
 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 }