rt/gc/cdgc/dynarray.d

   1 /**
   2  * Dynamic array.
   3  *
   4  * This module contains a simple dynamic array implementation for use in the
   5  * Naive Garbage Collector. Standard D dynamic arrays can't be used because
   6  * they rely on the GC itself.
   7  *
   8  * See_Also:  gc module
   9  * Copyright: Public Domain
  10  * License:   Public Domain
  11  * Authors:   Leandro Lucarella <llucax@gmail.com>
  12  */
  13
  14 module rt.gc.cdgc.dynarray;
  15
  16 import tango.stdc.stdlib: realloc;
  17 import tango.stdc.string: memmove;
  18
  19
  20 private void Invariant(T)(DynArray!(T)* a)
  21 {
  22         assert ((a._data && a._capacity)
  23                     || ((a._data is null) && (a._capacity == 0)));
  24         assert (a._capacity >= a._size);
  25 }
  26
  27
  28 package:
  29
  30 /**
  31  * Dynamic array.
  32  *
  33  * This is a simple dynamic array implementation. D dynamic arrays can't be
  34  * used because they rely on the GC, and we are implementing the GC.
  35  */
  36 struct DynArray(T)
  37 {
  38
  39 private:
  40
  41     /// Memory block to hold the array.
  42     T* _data = null;
  43
  44     /// Total array capacity, in number of elements.
  45     size_t _capacity = 0;
  46
  47     /// Current array size, in number of elements.
  48     size_t _size = 0;
  49
  50
  51 public:
  52
  53     invariant()
  54     {
  55         .Invariant(this);
  56     }
  57
  58     /**
  59      * Check the structure invariant.
  60      */
  61     void Invariant()
  62     {
  63         .Invariant(this);
  64     }
  65
  66     /**
  67      * Get the array size.
  68      */
  69     size_t length()
  70     {
  71         return this._size;
  72     }
  73
  74     /**
  75      * Get the array capacity.
  76      */
  77     size_t capacity()
  78     {
  79         return this._capacity;
  80     }
  81
  82     /**
  83      * Get the total ammount of bytes the elements consumes (capacity included).
  84      */
  85     size_t elements_sizeof()
  86     {
  87         return this._capacity * (T.sizeof + (T*).sizeof);
  88     }
  89
  90     /**
  91      * Get the pointer to the array's data.
  92      *
  93      * Use with care, the data belongs to the array and you should not
  94      * realloc() or free() it, you should only use it a as a read-only chunk of
  95      * memory.
  96      */
  97     T* ptr()
  98     {
  99         return this._data;
 100     }
 101
 102     /**
 103      * Access an element by index.
 104      *
 105      * Bear in mind that a copy of the element is returned. If you need
 106      * a pointer, you can always get it through a.ptr + i (but be careful if
 107      * you use the insert_sorted() method).
 108      */
 109     T opIndex(size_t i)
 110     {
 111         assert (i < this._size);
 112         return this._data[i];
 113     }
 114
 115     /**
 116      * Append a copy of the element x at the end of the array.
 117      *
 118      * This can trigger an allocation if the array is not big enough.
 119      *
 120      * Returns a pointer to the newly appended element if the append was
 121      * successful, null otherwise (i.e. an allocation was triggered but the
 122      * allocation failed) in which case the internal state is not changed.
 123      */
 124     T* append(in T x)
 125     {
 126         if (this._size == this._capacity)
 127             if (!this.resize())
 128                 return null;
 129         this._data[this._size] = x;
 130         this._size++;
 131         return this._data + this._size - 1;
 132     }
 133
 134     /**
 135      * Insert an element preserving the array sorted.
 136      *
 137      * This assumes the array was previously sorted. The "cmp" template
 138      * argument can be used to specify a custom comparison expression as "a"
 139      * string (where a is the element in the array and "b" is the element
 140      * passed as a parameter "x"). Using a template to specify the comparison
 141      * method is a hack to cope with compilers that have trouble inlining
 142      * a delegate (i.e. DMD).
 143      *
 144      * This can trigger an allocation if the array is not big enough and moves
 145      * memory around, so you have to be specially careful if you are taking
 146      * pointers into the array's data.
 147      *
 148      * Returns a pointer to the newly inserted element if the append was
 149      * successful, null otherwise (i.e. an allocation was triggered but the
 150      * allocation failed) in which case the internal state is not changed.
 151      */
 152     T* insert_sorted(char[] cmp = "a < b")(in T x)
 153     {
 154         size_t i = 0;
 155         for (; i < this._size; i++) {
 156             T a = this._data[i];
 157             alias x b;
 158             if (mixin(cmp))
 159                 continue;
 160             break;
 161         }
 162         if ((this._size == this._capacity) && !this.resize())
 163             return null;
 164         memmove(this._data + i + 1, this._data + i,
 165                 (this._size - i) * T.sizeof);
 166         this._data[i] = x;
 167         this._size++;
 168         return this._data + i;
 169     }
 170
 171     /**
 172      * Remove the element at position pos.
 173      */
 174     void remove_at(size_t pos)
 175     {
 176         this._size--;
 177         // move the rest of the items one place to the front
 178         memmove(this._data + pos, this._data + pos + 1,
 179                 (this._size - pos) * T.sizeof);
 180     }
 181
 182     /**
 183      * Remove the first occurrence of the element x from the array.
 184      */
 185     bool remove(in T x)
 186     {
 187         for (size_t i = 0; i < this._size; i++) {
 188             if (this._data[i] == x) {
 189                 this.remove_at(i);
 190                 return true;
 191             }
 192         }
 193         return false;
 194     }
 195
 196     /**
 197      * Change the current capacity of the array to new_capacity.
 198      *
 199      * This can enlarge or shrink the array, depending on the current capacity.
 200      * If new_capacity is 0, the array is enlarged to hold double the current
 201      * size. If new_capacity is less than the current size, the current size is
 202      * truncated, and the (size - new_capacity) elements at the end are lost.
 203      *
 204      * Returns true if the resize was successful, false otherwise (and the
 205      * internal state is not changed).
 206      */
 207     bool resize(in size_t new_capacity=0)
 208     {
 209         // adjust new_capacity if necessary
 210         if (new_capacity == 0)
 211             new_capacity = this._size * 2;
 212             if (new_capacity == 0)
 213                 new_capacity = 16;
 214         // reallocate the memory with the new_capacity
 215         T* new_data = cast(T*) realloc(this._data, new_capacity * T.sizeof);
 216         if (new_data is null)
 217             return false;
 218         this._data = new_data;
 219         this._capacity = new_capacity;
 220         // truncate the size if necessary
 221         if (this._size > this._capacity)
 222             this._size = this._capacity;
 223         return true;
 224     }
 225
 226     /**
 227      * Remove all the elements of the array and set the capacity to 0.
 228      */
 229     void free()
 230     {
 231         this._data = cast(T*) realloc(this._data, 0);
 232         assert (this._data is null);
 233         this._size = 0;
 234         this._capacity = 0;
 235     }
 236
 237 }
 238
 239
 240 unittest // DynArray
 241 {
 242     DynArray!(int) array;
 243     assert (array.length == 0);
 244     assert (array.capacity == 0);
 245     assert (array.ptr is null);
 246     assert (array.append(5));
 247     assert (array.length == 1);
 248     assert (array.capacity >= 1);
 249     assert (array.ptr !is null);
 250     for (auto i = 0; i < array.length; i++)
 251         assert (*array[i] == 5);
 252     assert (array.append(6));
 253     assert (array.length == 2);
 254     assert (array.capacity >= 2);
 255     assert (array.ptr !is null);
 256     int j = 0;
 257     while (j < array.length)
 258         assert (*array[j] == (5 + j++));
 259     assert (j == 2);
 260     array.remove(5);
 261     assert (array.length == 1);
 262     assert (array.capacity >= 1);
 263     assert (array.ptr !is null);
 264     for (auto i = 0; i < array.length; i++)
 265         assert (*array[i] == 6);
 266     assert (array.resize(100));
 267     assert (array.length == 1);
 268     assert (array.capacity >= 100);
 269     assert (array.ptr !is null);
 270     array.free();
 271     assert (array.length == 0);
 272     assert (array.capacity == 0);
 273     assert (array.ptr is null);
 274 }
 275
 276
 277 // vim: set et sw=4 sts=4 :