From e22e481ad2881b43acdc16fd6061bee9d68270f7 Mon Sep 17 00:00:00 2001
From: Leandro Lucarella <llucax@gmail.com>
Date: Wed, 30 Jun 2010 10:57:18 -0300
Subject: [PATCH] Use a custom dynamic array to store roots and ranges

---
 rt/gc/cdgc/dynarray.d | 257 ++++++++++++++++++++++++++++++++++++++++++
 rt/gc/cdgc/gc.d       | 167 ++++++---------------------
 2 files changed, 294 insertions(+), 130 deletions(-)
 create mode 100644 rt/gc/cdgc/dynarray.d

diff --git a/rt/gc/cdgc/dynarray.d b/rt/gc/cdgc/dynarray.d
new file mode 100644
index 0000000..2a36d93
--- /dev/null
+++ b/rt/gc/cdgc/dynarray.d
@@ -0,0 +1,257 @@
+/**
+ * Dynamic array.
+ *
+ * This module contains a simple dynamic array implementation for use in the
+ * Naive Garbage Collector. Standard D dynamic arrays can't be used because
+ * they rely on the GC itself.
+ *
+ * See_Also:  gc module
+ * Copyright: Public Domain
+ * License:   Public Domain
+ * Authors:   Leandro Lucarella <llucax@gmail.com>
+ */
+
+module rt.gc.cdgc.dynarray;
+
+import tango.stdc.stdlib: realloc;
+import tango.stdc.string: memmove;
+
+
+private void Invariant(T)(DynArray!(T)* a)
+{
+        assert ((a._data && a._capacity)
+                    || ((a._data is null) && (a._capacity == 0)));
+        assert (a._capacity >= a._size);
+}
+
+
+package:
+
+/**
+ * Dynamic array.
+ *
+ * This is a simple dynamic array implementation. D dynamic arrays can't be
+ * used because they rely on the GC, and we are implementing the GC.
+ */
+struct DynArray(T)
+{
+
+private:
+
+    /// Memory block to hold the array.
+    T* _data = null;
+
+    /// Total array capacity, in number of elements.
+    size_t _capacity = 0;
+
+    /// Current array size, in number of elements.
+    size_t _size = 0;
+
+
+public:
+
+    invariant()
+    {
+        .Invariant(this);
+    }
+
+    /**
+     * Check the structure invariant.
+     */
+    void Invariant()
+    {
+        .Invariant(this);
+    }
+
+    /**
+     * Get the array size.
+     */
+    size_t length()
+    {
+        return this._size;
+    }
+
+    /**
+     * Get the array capacity.
+     */
+    size_t capacity()
+    {
+        return this._capacity;
+    }
+
+    /**
+     * Get the pointer to the array's data.
+     *
+     * Use with care, the data belongs to the array and you should not
+     * realloc() or free() it, you should only use it a as a read-only chunk of
+     * memory.
+     */
+    T* ptr()
+    {
+        return this._data;
+    }
+
+    /**
+     * Access an element by index.
+     *
+     * A pointer is returned so the real element can be modified in place.
+     */
+    T* opIndex(size_t i)
+    {
+        assert (i < this._size);
+        return this._data + i;
+    }
+
+    /**
+     * Append a copy of the element x at the end of the array.
+     *
+     * This can trigger an allocation if the array is not big enough.
+     *
+     * Returns true if the append was successful, false otherwise (i.e. an
+     * allocation was triggered but the allocation failed) in which case the
+     * internal state is not changed.
+     */
+    T* append(in T x)
+    {
+        if (this._size == this._capacity)
+            if (!this.resize())
+                return null;
+        this._data[this._size] = x;
+        this._size++;
+        return this._data + this._size - 1;
+    }
+
+    /**
+     * Append a copy of the element x at the end of the array.
+     *
+     * This can trigger an allocation if the array is not big enough.
+     *
+     * Returns true if the append was successful, false otherwise (i.e. an
+     * allocation was triggered but the allocation failed) in which case the
+     * internal state is not changed.
+     */
+    T* insert_sorted(in T x)
+    {
+        size_t i = 0;
+        for (; i < this._size; i++) {
+            if (this._data[i] < x)
+                continue;
+            break;
+        }
+        if (this._size == this._capacity)
+            if (!this.resize())
+                return null;
+        memmove(this._data + i + 1, this._data + i,
+                (this._size - i) * T.sizeof);
+        this._data[i] = x;
+        this._size++;
+        return this._data + i;
+    }
+
+    /**
+     * Remove the element at position pos.
+     */
+    void remove_at(size_t pos)
+    {
+        this._size--;
+        // move the rest of the items one place to the front
+        memmove(this._data + pos, this._data + pos + 1,
+                (this._size - pos) * T.sizeof);
+    }
+
+    /**
+     * Remove the first occurrence of the element x from the array.
+     */
+    bool remove(in T x)
+    {
+        for (size_t i = 0; i < this._size; i++) {
+            if (this._data[i] == x) {
+                this.remove_at(i);
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Change the current capacity of the array to new_capacity.
+     *
+     * This can enlarge or shrink the array, depending on the current capacity.
+     * If new_capacity is 0, the array is enlarged to hold double the current
+     * size. If new_capacity is less than the current size, the current size is
+     * truncated, and the (size - new_capacity) elements at the end are lost.
+     *
+     * Returns true if the resize was successful, false otherwise (and the
+     * internal state is not changed).
+     */
+    bool resize(in size_t new_capacity=0)
+    {
+        // adjust new_capacity if necessary
+        if (new_capacity == 0)
+            new_capacity = this._size * 2;
+            if (new_capacity == 0)
+                new_capacity = 4;
+        // reallocate the memory with the new_capacity
+        T* new_data = cast(T*) realloc(this._data, new_capacity * T.sizeof);
+        if (new_data is null)
+            return false;
+        this._data = new_data;
+        this._capacity = new_capacity;
+        // truncate the size if necessary
+        if (this._size > this._capacity)
+            this._size = this._capacity;
+        return true;
+    }
+
+    /**
+     * Remove all the elements of the array and set the capacity to 0.
+     */
+    void free()
+    {
+        this._data = cast(T*) realloc(this._data, 0);
+        assert (this._data is null);
+        this._size = 0;
+        this._capacity = 0;
+    }
+
+}
+
+
+unittest // DynArray
+{
+    DynArray!(int) array;
+    assert (array.length == 0);
+    assert (array.capacity == 0);
+    assert (array.ptr is null);
+    assert (array.append(5));
+    assert (array.length == 1);
+    assert (array.capacity >= 1);
+    assert (array.ptr !is null);
+    for (auto i = 0; i < array.length; i++)
+        assert (*array[i] == 5);
+    assert (array.append(6));
+    assert (array.length == 2);
+    assert (array.capacity >= 2);
+    assert (array.ptr !is null);
+    int j = 0;
+    while (j < array.length)
+        assert (*array[j] == (5 + j++));
+    assert (j == 2);
+    array.remove(5);
+    assert (array.length == 1);
+    assert (array.capacity >= 1);
+    assert (array.ptr !is null);
+    for (auto i = 0; i < array.length; i++)
+        assert (*array[i] == 6);
+    assert (array.resize(100));
+    assert (array.length == 1);
+    assert (array.capacity >= 100);
+    assert (array.ptr !is null);
+    array.free();
+    assert (array.length == 0);
+    assert (array.capacity == 0);
+    assert (array.ptr is null);
+}
+
+
+// vim: set et sw=4 sts=4 :
diff --git a/rt/gc/cdgc/gc.d b/rt/gc/cdgc/gc.d
index 6ed0b1d..14d323b 100644
--- a/rt/gc/cdgc/gc.d
+++ b/rt/gc/cdgc/gc.d
@@ -47,6 +47,7 @@ version = STACKGROWSDOWN;       // growing the stack means subtracting from the
 import rt.gc.cdgc.bits: GCBits;
 import rt.gc.cdgc.stats: GCStats;
 import alloc = rt.gc.cdgc.alloc;
+import rt.gc.cdgc.dynarray: DynArray;
 
 import cstdlib = tango.stdc.stdlib;
 import cstring = tango.stdc.string;
@@ -989,11 +990,13 @@ class GC
 
         if (!thread_needLock())
         {
-            gcx.addRoot(p);
+            if (roots.append(p) is null)
+                onOutOfMemoryError();
         }
         else synchronized (gcLock)
         {
-            gcx.addRoot(p);
+            if (roots.append(p) is null)
+                onOutOfMemoryError();
         }
     }
 
@@ -1008,14 +1011,16 @@ class GC
             return;
         }
 
+        bool r;
         if (!thread_needLock())
         {
-            gcx.removeRoot(p);
+            r = roots.remove(p);
         }
         else synchronized (gcLock)
         {
-            gcx.removeRoot(p);
+            r = roots.remove(p);
         }
+        assert (r);
     }
 
 
@@ -1031,11 +1036,13 @@ class GC
 
         if (!thread_needLock())
         {
-            gcx.addRange(p, p + sz);
+            if (ranges.append(Range(p, p+sz)) is null)
+                onOutOfMemoryError();
         }
         else synchronized (gcLock)
         {
-            gcx.addRange(p, p + sz);
+            if (ranges.append(Range(p, p+sz)) is null)
+                onOutOfMemoryError();
         }
     }
 
@@ -1050,14 +1057,16 @@ class GC
             return;
         }
 
+        bool r;
         if (!thread_needLock())
         {
-            gcx.removeRange(p);
+            r = ranges.remove(Range(p, null));
         }
         else synchronized (gcLock)
         {
-            gcx.removeRange(p);
+            r = ranges.remove(Range(p, null));
         }
+        assert (r);
     }
 
 
@@ -1307,6 +1316,13 @@ struct Range
 {
     void *pbot;
     void *ptop;
+    int opCmp(in Range other)
+    {
+        if (pbot < other.pbot)
+            return -1;
+        else
+        return cast(int)(pbot > other.pbot);
+    }
 }
 
 
@@ -1314,6 +1330,9 @@ const uint binsize[B_MAX] = [ 16,32,64,128,256,512,1024,2048,4096 ];
 const uint notbinsize[B_MAX] = [ ~(16u-1),~(32u-1),~(64u-1),~(128u-1),~(256u-1),
                                 ~(512u-1),~(1024u-1),~(2048u-1),~(4096u-1) ];
 
+DynArray!(void*) roots;
+DynArray!(Range) ranges;
+
 /* ============================ Gcx =============================== */
 
 
@@ -1323,14 +1342,6 @@ struct Gcx
     void *p_cache;
     size_t size_cache;
 
-    size_t nroots;
-    size_t rootdim;
-    void **roots;
-
-    size_t nranges;
-    size_t rangedim;
-    Range *ranges;
-
     uint noStack;       // !=0 means don't scan stack
     uint log;           // turn on logging
     uint anychanges;
@@ -1385,23 +1396,14 @@ struct Gcx
                 }
             }
 
-            if (roots)
-            {
-                assert(rootdim != 0);
-                assert(nroots <= rootdim);
-            }
+            roots.Invariant();
+            ranges.Invariant();
 
-            if (ranges)
+            for (i = 0; i < ranges.length; i++)
             {
-                assert(rangedim != 0);
-                assert(nranges <= rangedim);
-
-                for (i = 0; i < nranges; i++)
-                {
-                    assert(ranges[i].pbot);
-                    assert(ranges[i].ptop);
-                    assert(ranges[i].pbot <= ranges[i].ptop);
-                }
+                assert(ranges[i].pbot);
+                assert(ranges[i].ptop);
+                assert(ranges[i].pbot <= ranges[i].ptop);
             }
 
             for (i = 0; i < B_PAGE; i++)
@@ -1414,101 +1416,6 @@ struct Gcx
     }
 
 
-    /**
-     *
-     */
-    void addRoot(void *p)
-    {
-        if (nroots == rootdim)
-        {
-            size_t newdim = rootdim * 2 + 16;
-            void** newroots;
-
-            newroots = cast(void**) cstdlib.malloc(newdim * newroots[0].sizeof);
-            if (!newroots)
-                onOutOfMemoryError();
-            if (roots)
-            {
-                cstring.memcpy(newroots, roots, nroots * newroots[0].sizeof);
-                cstdlib.free(roots);
-            }
-            roots = newroots;
-            rootdim = newdim;
-        }
-        roots[nroots] = p;
-        nroots++;
-    }
-
-
-    /**
-     *
-     */
-    void removeRoot(void *p)
-    {
-        for (size_t i = nroots; i--;)
-        {
-            if (roots[i] == p)
-            {
-                nroots--;
-                cstring.memmove(roots + i, roots + i + 1,
-                        (nroots - i) * roots[0].sizeof);
-                return;
-            }
-        }
-        assert(0);
-    }
-
-
-    /**
-     *
-     */
-    void addRange(void *pbot, void *ptop)
-    {
-        if (nranges == rangedim)
-        {
-            size_t newdim = rangedim * 2 + 16;
-            Range *newranges;
-
-            newranges = cast(Range*) cstdlib.malloc(newdim * Range.sizeof);
-            if (!newranges)
-                onOutOfMemoryError();
-            if (ranges)
-            {
-                cstring.memcpy(newranges, ranges, nranges * Range.sizeof);
-                cstdlib.free(ranges);
-            }
-            ranges = newranges;
-            rangedim = newdim;
-        }
-        ranges[nranges].pbot = pbot;
-        ranges[nranges].ptop = ptop;
-        nranges++;
-    }
-
-
-    /**
-     *
-     */
-    void removeRange(void *pbot)
-    {
-        for (size_t i = nranges; i--;)
-        {
-            if (ranges[i].pbot == pbot)
-            {
-                nranges--;
-                cstring.memmove(ranges + i, ranges + i + 1,
-                        (nranges - i) * ranges[0].sizeof);
-                return;
-            }
-        }
-
-        // This is a fatal error, but ignore it.
-        // The problem is that we can get a Close() call on a thread
-        // other than the one the range was allocated on.
-        //assert(zero);
-    }
-
-
     /**
      * Find Pool that pointer is in.
      * Return null if not in a Pool.
@@ -2179,14 +2086,14 @@ struct Gcx
             thread_scanAll( &mark, stackTop );
         }
 
-        // Scan roots[]
+        // Scan roots
         debug(COLLECT_PRINTF) printf("scan roots[]\n");
-        mark(roots, roots + nroots);
+        mark(roots.ptr, roots.ptr + roots.length);
 
-        // Scan ranges[]
+        // Scan ranges
         debug(COLLECT_PRINTF) printf("scan ranges[]\n");
         //log++;
-        for (n = 0; n < nranges; n++)
+        for (n = 0; n < ranges.length; n++)
         {
             debug(COLLECT_PRINTF) printf("\t%x .. %x\n", ranges[n].pbot, ranges[n].ptop);
             mark(ranges[n].pbot, ranges[n].ptop);
-- 
2.43.0