[implement grey set as stack rather than judy array
John Meacham <john@repetae.net>**20100327224532
 Ignore-this: 56428458f1f456f6b6d85e1aa61f2155
] hunk ./src/data/rts/jhc_jgc.h 56
-#define FOOF 0xF00DF00FACEBAFFUL
-
-void gc_print_stats(gc_t gc);
-void gc_perform_gc(gc_t gc);
-void *gc_alloc_tag(gc_t gc,unsigned count, unsigned nptrs, int tag);
+static void gc_print_stats(gc_t gc);
+static void gc_perform_gc(gc_t gc);
+static void *gc_alloc_tag(gc_t gc,unsigned count, unsigned nptrs, int tag);
hunk ./src/data/rts/jhc_jgc.h 65
-bool gc_add_root(gc_t gc, void *root);
-bool gc_del_root(gc_t gc, void *root);
hunk ./src/data/rts/jhc_jgc.h 81
-static Pvoid_t gc_roots = NULL;       // extra roots in addition to the stack
-static Pvoid_t gc_allocated = NULL;   // black set of currently allocated memory
-static size_t heap_threshold = 2048;  // threshold at which we want to run a gc rather than malloc more memory
-static size_t mem_inuse;              // amount of memory in use by gc'ed memory
-static unsigned number_gcs;           // number of garbage collections
-static unsigned number_allocs;        // number of allocations since last garbage collection
+static Pvoid_t  gc_roots = NULL;        // extra roots in addition to the stack
+static Pvoid_t  gc_allocated = NULL;    // black set of currently allocated memory
+static size_t   heap_threshold = 2048;  // threshold at which we want to run a gc rather than malloc more memory
+static size_t   mem_inuse;              // amount of memory in use by gc'ed memory
+static unsigned number_gcs;             // number of garbage collections
+static unsigned number_allocs;          // number of allocations since last garbage collection
hunk ./src/data/rts/jhc_jgc.h 106
-        } else 
+        } else
hunk ./src/data/rts/jhc_jgc.h 117
-        } else 
+        } else
hunk ./src/data/rts/jhc_jgc.h 130
+
+struct stack {
+        unsigned size;
+        unsigned ptr;
+        uintptr_t *stack;
+};
+
+#define EMPTY_STACK { 0, 0, NULL }
+
+static void
+stack_check(struct stack *s, unsigned n) {
+        while(s->size - s->ptr <= n) {
+                s->size += 4096;
+                s->stack = realloc(s->stack, sizeof(uintptr_t)*s->size);
+                assert(s->stack);
+                debugf(stderr, "stack:");
+                for(unsigned i = 0; i < s->ptr; i++) {
+                        debugf(stderr, " %p", (void *)s->stack[i]);
+                }
+                debugf(stderr, "\n");
+        }
+}
+
hunk ./src/data/rts/jhc_jgc.h 157
+        number_gcs++;
+
hunk ./src/data/rts/jhc_jgc.h 162
-        unsigned number_whnf = 0;
-        number_gcs++;
+        struct stack stack = EMPTY_STACK;
+
hunk ./src/data/rts/jhc_jgc.h 165
-        Pvoid_t gc_black = NULL;
hunk ./src/data/rts/jhc_jgc.h 166
-        int r;
-        // initialize the grey set with the roots
hunk ./src/data/rts/jhc_jgc.h 167
-        for(ix = 0,(J1F(r,gc_roots,ix)); r; (J1N(r,gc_roots,ix))) {
+        Word_t n_roots;
+        J1C(n_roots,gc_roots,0,-1);
+        stack_check(&stack, n_roots);
+        int r; for(ix = 0,(J1F(r,gc_roots,ix)); r; (J1N(r,gc_roots,ix))) {
hunk ./src/data/rts/jhc_jgc.h 172
+                stack.stack[stack.ptr++] = ix*GC_BASE;
hunk ./src/data/rts/jhc_jgc.h 179
+                stack_check(&stack, gc->nptrs);
hunk ./src/data/rts/jhc_jgc.h 182
-                        //if(IS_LAZY(gc->ptrs[i])) {
-                        //        if(!IS_LAZY(GETHEAD(FROM_SPTR(gc->ptrs[i])))) {
-                        //                number_redirects++;
-                        //                debugf(" *");
-                        //                gc->ptrs[i] = GETHEAD(FROM_SPTR(gc->ptrs[i]));
-                        //                number_whnf++;
-                        //        }
-                        //} else {
-                        //        number_whnf++;
-                        //}
+                        // TODO - short circuit redirects on stack
hunk ./src/data/rts/jhc_jgc.h 191
+                        if(d)
+                                stack.stack[stack.ptr++] = (uintptr_t)e;
hunk ./src/data/rts/jhc_jgc.h 196
-        // trace the grey
-        while(ix = 0,(J1F(r,gc_grey,ix)),r) {
+
+        while(stack.ptr) {
+                uintptr_t ix = stack.stack[--stack.ptr] / GC_BASE;
+                J1T(r,gc_grey,ix);
+                assert(r);
hunk ./src/data/rts/jhc_jgc.h 202
-                J1U(r,gc_grey,ix);
hunk ./src/data/rts/jhc_jgc.h 204
+                        J1U(r,gc_grey,ix);
hunk ./src/data/rts/jhc_jgc.h 209
-                J1S(r,gc_black,ix);
+                //J1S(r,gc_black,ix);
hunk ./src/data/rts/jhc_jgc.h 213
-                for(int i = 0 + offset;i < e->u.v.nptrs + offset; i++) {
+                stack_check(&stack, e->u.v.nptrs);
+                for(int i = offset; i < e->u.v.nptrs + offset; i++) {
hunk ./src/data/rts/jhc_jgc.h 222
-                        entry_t * ptr = e->ptrs[i];
-                        if(SHOULD_FOLLOW(ptr)) {
-                                ptr = FROM_SPTR(ptr);
-                                debugf("Following: %p %p\n",e->ptrs[i], (void *)(ptr - 1));
-                                Word_t p = (Word_t)(ptr - 1) / GC_BASE;
-                                int r;
-                                J1T(r,gc_black,p);
-                                if(__predict_true(!r))
-                                        J1S(r,gc_grey,p);
+                        if(SHOULD_FOLLOW(e->ptrs[i])) {
+                                entry_t * ptr = (entry_t *)(FROM_SPTR(e->ptrs[i])) - 1;
+                                debugf("Following: %p %p\n",e->ptrs[i], (void *)ptr);
+                                Word_t p = (Word_t)ptr / GC_BASE;
+                                int d;
+                                J1S(d,gc_grey,p);
+                                if(d)
+                                        stack.stack[stack.ptr++] = (uintptr_t)ptr;
hunk ./src/data/rts/jhc_jgc.h 231
-
hunk ./src/data/rts/jhc_jgc.h 233
-        assert(gc_grey == NULL);
+        free(stack.stack);
hunk ./src/data/rts/jhc_jgc.h 240
-        gc_allocated = gc_black;
-#if JGC_STATUS
-        fprintf(stderr, "Ss: %5u Ws: %5u Ps: %5u Rs: %5u As: %5u ", number_stack, number_whnf, number_ptr, number_redirects, number_allocs);
+        gc_allocated = gc_grey;
hunk ./src/data/rts/jhc_jgc.h 242
+#if JGC_STATUS
+        fprintf(stderr, "Ss: %5u Ps: %5u Rs: %5u As: %5u ", number_stack, number_ptr, number_redirects, number_allocs);