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 pointer to the array's data.
  84      *
  85      * Use with care, the data belongs to the array and you should not
  86      * realloc() or free() it, you should only use it a as a read-only chunk of
  87      * memory.
  88      */
  89     T* ptr()
  90     {
  91         return this._data;
  92     }
  93
  94     /**
  95      * Access an element by index.
  96      *
  97      * A pointer is returned so the real element can be modified in place.
  98      */
  99     T* opIndex(size_t i)
 100     {
 101         assert (i < this._size);
 102         return this._data + i;
 103     }
 104
 105     /**
 106      * Append a copy of the element x at the end of the array.
 107      *
 108      * This can trigger an allocation if the array is not big enough.
 109      *
 110      * Returns true if the append was successful, false otherwise (i.e. an
 111      * allocation was triggered but the allocation failed) in which case the
 112      * internal state is not changed.
 113      */
 114     T* append(in T x)
 115     {
 116         if (this._size == this._capacity)
 117             if (!this.resize())
 118                 return null;
 119         this._data[this._size] = x;
 120         this._size++;
 121         return this._data + this._size - 1;
 122     }
 123
 124     /**
 125      * Append a copy of the element x at the end of the array.
 126      *
 127      * This can trigger an allocation if the array is not big enough.
 128      *
 129      * Returns true if the append was successful, false otherwise (i.e. an
 130      * allocation was triggered but the allocation failed) in which case the
 131      * internal state is not changed.
 132      */
 133     T* insert_sorted(in T x)
 134     {
 135         size_t i = 0;
 136         for (; i < this._size; i++) {
 137             if (this._data[i] < x)
 138                 continue;
 139             break;
 140         }
 141         if (this._size == this._capacity)
 142             if (!this.resize())
 143                 return null;
 144         memmove(this._data + i + 1, this._data + i,
 145                 (this._size - i) * T.sizeof);
 146         this._data[i] = x;
 147         this._size++;
 148         return this._data + i;
 149     }
 150
 151     /**
 152      * Remove the element at position pos.
 153      */
 154     void remove_at(size_t pos)
 155     {
 156         this._size--;
 157         // move the rest of the items one place to the front
 158         memmove(this._data + pos, this._data + pos + 1,
 159                 (this._size - pos) * T.sizeof);
 160     }
 161
 162     /**
 163      * Remove the first occurrence of the element x from the array.
 164      */
 165     bool remove(in T x)
 166     {
 167         for (size_t i = 0; i < this._size; i++) {
 168             if (this._data[i] == x) {
 169                 this.remove_at(i);
 170                 return true;
 171             }
 172         }
 173         return false;
 174     }
 175
 176     /**
 177      * Change the current capacity of the array to new_capacity.
 178      *
 179      * This can enlarge or shrink the array, depending on the current capacity.
 180      * If new_capacity is 0, the array is enlarged to hold double the current
 181      * size. If new_capacity is less than the current size, the current size is
 182      * truncated, and the (size - new_capacity) elements at the end are lost.
 183      *
 184      * Returns true if the resize was successful, false otherwise (and the
 185      * internal state is not changed).
 186      */
 187     bool resize(in size_t new_capacity=0)
 188     {
 189         // adjust new_capacity if necessary
 190         if (new_capacity == 0)
 191             new_capacity = this._size * 2;
 192             if (new_capacity == 0)
 193                 new_capacity = 16;
 194         // reallocate the memory with the new_capacity
 195         T* new_data = cast(T*) realloc(this._data, new_capacity * T.sizeof);
 196         if (new_data is null)
 197             return false;
 198         this._data = new_data;
 199         this._capacity = new_capacity;
 200         // truncate the size if necessary
 201         if (this._size > this._capacity)
 202             this._size = this._capacity;
 203         return true;
 204     }
 205
 206     /**
 207      * Remove all the elements of the array and set the capacity to 0.
 208      */
 209     void free()
 210     {
 211         this._data = cast(T*) realloc(this._data, 0);
 212         assert (this._data is null);
 213         this._size = 0;
 214         this._capacity = 0;
 215     }
 216
 217 }
 218
 219
 220 unittest // DynArray
 221 {
 222     DynArray!(int) array;
 223     assert (array.length == 0);
 224     assert (array.capacity == 0);
 225     assert (array.ptr is null);
 226     assert (array.append(5));
 227     assert (array.length == 1);
 228     assert (array.capacity >= 1);
 229     assert (array.ptr !is null);
 230     for (auto i = 0; i < array.length; i++)
 231         assert (*array[i] == 5);
 232     assert (array.append(6));
 233     assert (array.length == 2);
 234     assert (array.capacity >= 2);
 235     assert (array.ptr !is null);
 236     int j = 0;
 237     while (j < array.length)
 238         assert (*array[j] == (5 + j++));
 239     assert (j == 2);
 240     array.remove(5);
 241     assert (array.length == 1);
 242     assert (array.capacity >= 1);
 243     assert (array.ptr !is null);
 244     for (auto i = 0; i < array.length; i++)
 245         assert (*array[i] == 6);
 246     assert (array.resize(100));
 247     assert (array.length == 1);
 248     assert (array.capacity >= 100);
 249     assert (array.ptr !is null);
 250     array.free();
 251     assert (array.length == 0);
 252     assert (array.capacity == 0);
 253     assert (array.ptr is null);
 254 }
 255
 256
 257 // vim: set et sw=4 sts=4 :