--- /dev/null
+/**
+ * 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 :
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;
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();
}
}
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);
}
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();
}
}
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);
}
{
void *pbot;
void *ptop;
+ int opCmp(in Range other)
+ {
+ if (pbot < other.pbot)
+ return -1;
+ else
+ return cast(int)(pbot > other.pbot);
+ }
}
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 =============================== */
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;
}
}
- 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++)
}
- /**
- *
- */
- 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.
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);
projects / software / dgc / cdgc.git / commitdiff