Synchronous Cycle Collectionの適当な実装

RubyGCをなんとかしてみようハックしてみようと思ってはいるのですが、あまりGCの実装慣れしていないので

GC - GCアルゴリズム詳細解説
http://wiki.livedoor.jp/author_nari/d/GC

この辺を読んで、Cycle CollectionとかいうGCが面白いというか、
参照カウンタ方式の循環参照問題を解決する方法として面白いので実装してみました。
似たようなことは考えてたのですが、偉い効率の悪い方法しか考えられてなかったんですが、
これはすばらしいいいんじゃないかと思います。

元の論文はこれです。
Concurrent Cycle Collection in Reference Counted Systems

http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf

この中の、Fig. 2. Synchronous Cycle Collectionを丸写してstaticなクラスの関数にしました。
以下ソースです。

import std.string;
class S {
	int rc;
	S[string] children;
	byte color;
	byte buffered;
	this() {
		printf("new %d\n", this);
		color = black;
	}
	~this() {
		printf("delete %d\n", this);
	}
	void opIndexAssign( S o, int i) {
		opIndexAssign(o, std.string.toString(i));
	}

	void opIndexAssign( S o, string i) {
		if (i in children)
			decrement(children[i]);
		if (o is null) {
			children.remove(i);
		} else {
			children[i] = o;
			increment(o);
		}
	}

	S opIndex(int i) {
		return children[std.string.toString(i)];
	}
	S opIndex(string i) {
		return children[i];
	}

	enum { black, purple, white, gray };
	static S[S] roots;

	static void increment(S s) {
		s.rc++;
		s.color = black;
	}

	static void decrement(S s) {
		s.rc--;
		if (s.rc == 0) release(s);
		else           possibleRoot(s);
	}

	static void release(S s) {
		foreach (S t; s.children)
			decrement(t);
		s.color = black;
		if(!s.buffered)
			delete s;
	}

	static void possibleRoot(S s) {
		if (s.color != purple) {
			s.color = purple;
			if (!s.buffered) {
				s.buffered = true;
				roots[s] = s;
			}
		}
	}

	static void collectCycles() {
		markRoots();
		scanRoots();
		collectRoots();
	}

	static void markRoots() {
		foreach (S s; roots) {
			if(s.color == purple) {
				markGray(s);
			} else {
				s.buffered = false;
				roots.remove(s);
				if(s.color == black && s.rc == 0)
					delete s;
			}
		}

	}

	static void scanRoots() {
		foreach (S s; roots)
			scan(s);
	}

	static void collectRoots() {
		foreach (S s; roots) {
			s.buffered = false;
			collectWhite(s);
		}
		roots = null;
	}

	static void markGray(S s) {
		if (s.color != gray) {
			s.color = gray;
			foreach (S t; s.children) {
				t.rc--;
				markGray(t);
			}
		}
	}

	static void scan(S s) {
		if (s.color == gray) {
			if (s.rc > 0) {
				scanBlack(s);
			} else {
				s.color = white;
				foreach (S t; s.children)
					scan(t);
			}
		}
	}

	static void scanBlack(S s) {
		s.color = black;
		foreach (S t; s.children) {
			t.rc++;
			if (t.color != black)
				scanBlack(t);
		}
	}

	static void collectWhite(S s) {
		if (s.color == white && !s.buffered) {
			s.color = black;
			foreach (S t; s.children)
				collectWhite(t);
			delete s;
		}

	}

}

void main() {
	S t = new S();
	S.increment(t);

	t[0] = new S();
	t[1] = new S();
printf("remove root\n");
	t[0] = null;
	t[1] = null;
printf("ok\n");
printf("increment root 2\n");
	t[0] = new S();
	t[0][0] = new S();
	t[0][0][0] = new S();
printf("--\n");
printf("increment root 3\n");
	t[1] = new S();
	t[1][0] = new S();
	t[1][0][0] = t[1];
printf("make cycle ref\n");
	t[1] = null;
printf("collect\n");
	S.collectCycles();

printf("remove root\n");
	S.decrement(t);
}