gc/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 gc.dynarray;
  15
  16 // Standard imports
  17 private import tango.stdc.stdlib: realloc;
  18 private import tango.stdc.string: memmove;
  19
  20 // External runtime functions
  21 private extern (C) void onOutOfMemoryError();
  22
  23
  24 package:
  25
  26 /**
  27  * Dynamic array.
  28  *
  29  * This is a simple dynamic array implementation. D dynamic arrays can't be
  30  * used because they rely on the GC, and we are implementing the GC.
  31  */
  32 struct DynArray(T)
  33 {
  34
  35 private:
  36
  37     /// Memory block to hold the array.
  38     T* data = null;
  39
  40     /// Total array capacity, in number of elements.
  41     size_t capacity = 0;
  42
  43     /// Current array size, in number of elements.
  44     size_t size = 0;
  45
  46     invariant()
  47     {
  48         assert ((this.data && this.capacity)
  49                     || ((this.data is null) && (this.capacity == 0)));
  50         assert (this.capacity >= this.size);
  51     }
  52
  53
  54 public:
  55
  56     /**
  57      * Append a copy of the element x at the end of the array.
  58      *
  59      * This can trigger an allocation if the array is not big enough.
  60      */
  61     void append(in T x)
  62     {
  63         if (this.size == this.capacity)
  64             this.expand();
  65         this.data[this.size] = x;
  66         this.size++;
  67     }
  68
  69     /**
  70      * Remove the first element for which predicate(element) is true.
  71      */
  72     void remove_if(bool delegate(ref T) predicate)
  73     {
  74         for (size_t i = 0; i < this.size; i++) {
  75             if (predicate(this.data[i])) {
  76                 this.size--;
  77                 // move the rest of the items one place to the front
  78                 memmove(this.data + i, this.data + i + 1,
  79                             (this.size - i) * T.sizeof);
  80                 return;
  81             }
  82         }
  83     }
  84
  85     /**
  86      * Remove the first occurrence of the element x from the array.
  87      */
  88     void remove(in T x)
  89     {
  90         this.remove_if((ref T e) { return e == x; });
  91     }
  92
  93     /**
  94      * Change the current capacity of the array to new_capacity.
  95      *
  96      * This can enlarge or shrink the array, depending on the current capacity.
  97      * If new_capacity is 0, the array is enlarged to hold double the current
  98      * size. If new_capacity is less than the current size, the current size is
  99      * truncated, and the (size - new_capacity) elements at the end are lost.
 100      */
 101     void expand(in size_t new_capacity=0)
 102     {
 103         // adjust new_capacity if necessary
 104         if (new_capacity == 0)
 105             new_capacity = this.size * 2;
 106             if (new_capacity == 0)
 107                 new_capacity = 4;
 108         // reallocate the memory with the new_capacity
 109         T* new_data = cast(T*) realloc(this.data, new_capacity);
 110         if (new_data is null)
 111             onOutOfMemoryError();
 112         this.data = new_data;
 113         this.capacity = new_capacity;
 114         // truncate the size if necessary
 115         if (this.size > this.capacity)
 116             this.size = this.capacity;
 117     }
 118
 119     /**
 120      * Remove all the elements of the array and set the capacity to 0.
 121      */
 122     void clear()
 123     {
 124         this.data = cast(T*) realloc(this.data, 0);
 125         assert (this.data is null);
 126         this.size = 0;
 127         this.capacity = 0;
 128     }
 129
 130     /**
 131      * Iterate over the array elements.
 132      */
 133     int opApply(int delegate(ref T) dg)
 134     {
 135         int result = 0;
 136         for (size_t i = 0; i < this.size; i++) {
 137             result = dg(this.data[i]);
 138             if (result)
 139                 break;
 140         }
 141         return result;
 142     }
 143
 144 }
 145
 146 debug (UnitTest)
 147 {
 148
 149 private:
 150
 151     unittest // DynArray
 152     {
 153         DynArray!(int) array;
 154         assert (array.size == 0);
 155         assert (array.capacity == 0);
 156         assert (array.data == null);
 157         foreach (x; array)
 158             assert (false, "there should be no elements in the array");
 159         array.append(5);
 160         assert (array.size == 1);
 161         assert (array.capacity >= 1);
 162         assert (array.data);
 163         foreach (x; array)
 164             assert (x == 5);
 165         array.append(6);
 166         assert (array.size == 2);
 167         assert (array.capacity >= 2);
 168         assert (array.data);
 169         int i = 0;
 170         foreach (x; array)
 171             assert (x == 5 + i++);
 172         assert (i == 2);
 173         array.remove(5);
 174         assert (array.size == 1);
 175         assert (array.capacity >= 1);
 176         assert (array.data);
 177         foreach (x; array)
 178             assert (x == 6);
 179         array.expand(100);
 180         assert (array.size == 1);
 181         assert (array.capacity >= 100);
 182         assert (array.data);
 183         foreach (x; array)
 184             assert (x == 6);
 185         array.clear();
 186         assert (array.size == 0);
 187         assert (array.capacity == 0);
 188         assert (array.data == null);
 189         foreach (x; array)
 190             assert (false, "there should be no elements in the array");
 191     }
 192
 193 } // debug (UnitTest)
 194
 195 // vim: set et sw=4 sts=4 :