Incremental tri-color GC

gc.hpp

#pragma once
#include <stdlib.h>
#include <stdint.h>
#include <stack>
#include "obj.hpp"
using namespace std;

class GC {

	Obj head;
	stack<Obj*> registered;
	stack<Obj*> gray;
	bool pending_registered;

	void push_gray(Val v) {
		if(IS_PTR(v) && !(((Obj*)v)->black()))
			gray.push((Obj*)v);
	}

	void gray_children(Obj* obj) {
		if(obj->array_like()) {
			Val* p = obj->array_ptr();
			size_t len = obj->len();
			for(size_t i = 0; i < len; i++)
				push_gray(p[i]);
		} else if(obj->hash_like()) {
			ValHash* hash = obj->hash_ptr();
			for(ValHash::iterator i = hash->begin(); i != hash->end(); i++) {
				push_gray((*i).first);
				push_gray((*i).second);
			}
		}
	}

public:

	GC() : pending_registered(true) {
		head.next = NULL;
		head.meta = 0;
	}

	~GC() {
		Obj* p = head.next;
		while(p) {
			free(p);
			p = p->next;
		}
	}

	Obj* gc_malloc(size_t size) {
		if (!pending_registered)
			gc_sweep();
		Obj* p = (Obj*)malloc(size);
		if(p) {
			memset(p, 0, size);
			p->next = head.next;
			head.next = p;
			pending_registered = true;
			return p;
		} else {
			throw "OOM";
		}
	}

	void gc_register(Obj* p) {
		registered.push(p);
	}

	// insert into mutator code between gc_mallocs
	void gc_step() {
		if(pending_registered) {
			pending_registered = false;
			gray = registered; // duplicate
		} else if(gray.empty()) {
			return;
		} else { 
			Obj* p = gray.top();
			gray.pop();
			p->black(true);
			gray_children(p);
		}
	}

	void gc_sweep() {
		while(!gray.empty())
			gc_step();
		Obj* prev = &head;
		Obj* p = prev->next;
		while(p) {
			if(p->black()) {
				p->black(false);
				prev = p;
			} else {
				prev->next = p->next;
				free(p);
			}
			p = prev->next;
		}
	}
};

obj.hpp

#pragma once

#include <tr1/unordered_map>

typedef void* Val;
typedef std::tr1::unordered_map<Val, Val> ValHash;
#define IS_PTR(v) (v && ((((uint64_t)(v)) >> 48) == 0))

struct Obj {
	static const uint64_t BLACK = ((uint64_t)1) << 61;
	static const uint64_t ARRAY = ((uint64_t)1) << 62;
	static const uint64_t HASH = ((uint64_t)1) << 61;
	
	// for gc use
	Obj* next;

	//   1       1          1      9bit  48bit
	// black array_like hash_like         len
	uint64_t meta;

	uint64_t black() {
		return meta & BLACK;
	}
	
	uint64_t black(bool flag) {
		meta &= ~BLACK;
		if (flag) meta |= BLACK;
	}
	
	uint64_t array_like() {
		return meta & ARRAY;
	}
	
	void array_like(bool flag) {
		meta &= ~ARRAY;
		if (flag) meta |= ARRAY;
	}
	
	uint64_t hash_like() {
		return meta & HASH;
	}
	
	void hash_like(bool flag) {
		meta &= ~HASH;
		if (flag) meta |= HASH;
	}
	
	size_t len() {
		return (meta << 16) >> 16;
	}
	
	void len(size_t sz) {
		meta >>= 48;
		meta <<= 48;
		meta |= sz;
	}
	
	ValHash* hash_ptr() {
		return (ValHash*)(void*)(&meta + 1);
	}
	
	Val* array_ptr() {
		return (Val*)(void*)(&meta + 1);
	}
};