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