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); }