Concurrent Cycle Collection Algorithm

昨日の続きです。書きかけ。
多分、インクリメンタルなGCですよ−って事だと思います。

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

Fig. 4. Concurrent Cycle Collection Algorithmの丸写しに近いもの。
以下ソース

import std.string;
enum { black, purple, white, gray, orange, red };

class S {
	int rc;
	int crc;
	S[string] children;
	byte color;
	byte buffered;
	this() {
		printf("new %d\n", this);
		color = black;
		buffered = false;
	}
	~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];
	}

	static S[S] roots;
	static S[] currentCycle;
	static S[][] cycleBuffer;

	static void increment(S s) {
		s.rc++;
		scanBlack(s);
	}

	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) {
		scanBlack(s);
		s.color = purple;
		if (!s.buffered) {
			s.buffered = true;
			roots[s] = s;
		}
	}

	static void processCycles() {
		freeCycles();
		collectCycles();
		sigmaPreparation();
	}

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

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

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

	static void collectRoots() {
		foreach (S s; roots) {
			if (s.color == white) {
				currentCycle = null;
				collectWhite(s);
				cycleBuffer ~= currentCycle;
			} else {
				s.buffered = false;
				roots.remove(s);
			}
		}
	}

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

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

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

	static void collectWhite(S s) {
		if (s.color == white) {
			s.color = orange;
			s.buffered = true;
			currentCycle ~= s;
			foreach (S t; s.children) collectWhite(t);
		}
	}

	static void sigmaPreparation() {
		foreach (S[] c; cycleBuffer) {
			foreach (S n; c) {
				n.color = red;
				n.crc = n.rc;
			}
			foreach (S n; c)
				foreach (S m; n.children)
					if (m.color == red && m.crc > 0)
						m.crc--;
			foreach (S n; c)
				n.color = orange;
		}
	}

	static void freeCycles() {
		int last = cycleBuffer.length - 1;
		for (int i = last; i >= 0; i--) {
			S[] c = cycleBuffer[i];
			if (deltaTest(c) && sigmaTest(c))
				freeCycle(c);
			else
				refurbish(c);
		}
		cycleBuffer = null;
	}

	static bool deltaTest(S[] c) {
		foreach (S n; c) if (n.color != orange) return false;
		return true;
	}

	static bool sigmaTest(S[] c) {
		int externRC = 0;
		foreach (S n; c) externRC += n.crc;
		return (externRC == 0);
	}

	static void refurbish(S[] c) {
		bool first = true;
		foreach (S n; c) {
			if ((first && n.color == orange) || n.color == purple) {
				n.color = purple;
				roots[n] = n;
			} else {
				n.color = black;
				n.buffered = false;
			}
			first = false;
		}
	}

	static void freeCycle(S[] c) {
		foreach (S n; c) n.color = red;
		foreach (S n; c)
			foreach (S m; n.children)
				cyclicDecrement(m);
		foreach (S n; c) delete n;
	}

	static void cyclicDecrement(S m) {
		if (m.color != red) {
			if (m.color == orange) {
				m.rc--;
				m.crc--;
			} else
				decrement(m);
		}
	}
}


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.processCycles();
printf("remove root\n");
	S.decrement(t);
}