手抜き Mark & Seep GC for D

Mark & Sweep GCのアルゴリズムを適当にDで書いてみました。
頭で考えてると難しい気がするかもしれませんが、
作ってみるとそうでもないということが分かります。

• 適当な説明

オブジェクトを作るときにobjectの連想配列に突っ込んでおきます。
ルートになるものはrootsに連想配列に突っ込んでおきます。
通常の変数の参照や、参照の削除では特別することはありません。
collectでは一度、markRootsを呼んで、rootから辿れるオブジェクトのmarkedを1にします。
終わったら、sweepを呼んで、objects内のmarkedが0なものをdeleteし、1のものは0に戻します。
最後に、rootsを空にしてcollectすると見事何もなくなります。
しっかり、循環参照している部分は消えてなくなります。
また、collectしない間はdeleteは呼ばれないことが分かると思います。
ここでは、便宜上rootsやobjectsを連想配列にしていますが、実際のGCではスピードが求められるので
ヒープ等を構成してそこから割り当てたり、削除したりといったことが必要になってくるでしょう。

以下ソースです。

class S {
	static S[S] roots;
	static S[S] objects;
	string data;
	int marked;
	S[string] children;

	this(string dt) {
		data = dt;
		printf("new %.*s\n", data);
		objects[this]=this;
	}

	~this() {
		objects.remove(this);
		printf("delete %.*s\n", data);
	}

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

	S opIndex(string i) {
		return children[i];
	}

	static void collect() {
		markRoots();
		sweep();
	}

	static void markRoots() {
		foreach (S s; roots) {
			mark(s);
		}
	}

	static void sweep() {
		foreach (S s; objects) {
			if (s.marked == 0) delete s;
			else s.marked = 0;
		}
	}

	static void mark(S s) {
		if (s.marked == 0) {
			s.marked = 1;
			foreach(S c; s.children) {
				mark(c);
			}
		}
	}
}

void main() {
	S t = new S("root");
	S.roots[t] = t;
	t["a"] = new S("a");
	t["b"] = new S("b");
printf("remove root\n");
	t["a"] = null;
	t["b"] = null;
printf("ok\n");
printf("increment root 2\n");
	t["a"] = new S("c");
	t["a"]["a"] = new S("d");
	t["a"]["a"]["a"] = new S("e");
printf("--\n");
printf("increment root 3\n");
	t["b"] = new S("f");
	t["b"]["a"] = new S("g");
	t["b"]["a"]["a"] = t["b"];
printf("make cycle ref\n");
	t["b"] = null;
printf("collect\n");
	S.collect();
printf("remove root & collect\n");
	S.roots.remove(t);
printf("collect\n");
	S.collect();
}