dynarray.d

   1 /**
   2  * This module contains a minimal garbage collector implementation according to
   3  * Tango requirements.  This library is mostly intended to serve as an example,
   4  * but it is usable in applications which do not rely on a garbage collector
   5  * to clean up memory (ie. when dynamic array resizing is not used, and all
   6  * memory allocated with 'new' is freed deterministically with 'delete').
   7  *
   8  * Please note that block attribute data must be tracked, or at a minimum, the
   9  * FINALIZE bit must be tracked for any allocated memory block because calling
  10  * rt_finalize on a non-object block can result in an access violation.  In the
  11  * allocator below, this tracking is done via a leading uint bitmask.  A real
  12  * allocator may do better to store this data separately, similar to the basic
  13  * GC normally used by Tango.
  14  *
  15  * Copyright: Public Domain
  16  * License:   BOLA
  17  * Authors:   Leandro Lucarella
  18  */
  19
  20 module dynarray;
  21
  22 private import tango.stdc.stdlib: realloc;
  23 private import tango.stdc.string: memmove;
  24 private extern (C) void onOutOfMemoryError();
  25
  26 package:
  27
  28 struct DynArray(T)
  29 {
  30
  31     T* data = null;
  32
  33     size_t capacity = 0;
  34
  35     size_t size = 0;
  36
  37     invariant
  38     {
  39         assert (this.data);
  40         assert (this.capacity >= this.size);
  41     }
  42
  43     void append(T x)
  44     {
  45         if (this.size == this.capacity)
  46             this.expand();
  47         this.data[this.size] = x;
  48         this.size++;
  49     }
  50
  51     void remove(T x)
  52     {
  53         for (size_t i = 0; i < this.size; i++) {
  54             if (this.data[i] == x) {
  55                 this.size--;
  56                 memmove(this.data + i, this.data + i + T.sizeof,
  57                                 (this.size - i) * T.sizeof);
  58                 return;
  59             }
  60         }
  61     }
  62
  63     void expand(size_t new_capacity=0)
  64     {
  65         if (new_capacity == 0)
  66             new_capacity = this.size * 2;
  67             if (new_capacity == 0)
  68                 new_capacity = 4;
  69         T* new_data = cast(T*) realloc(this.data, new_capacity);
  70         if (new_data is null)
  71             onOutOfMemoryError();
  72         this.data = new_data;
  73         this.capacity = new_capacity;
  74     }
  75
  76     int opApply(int delegate(ref T) dg)
  77     {
  78         int result = 0;
  79         for (size_t i = 0; i < this.size; i++) {
  80             result = dg(this.data[i]);
  81             if (result)
  82                 break;
  83         }
  84         return result;
  85     }
  86
  87 }
  88
  89 // vim: set et sw=4 sts=4 :