[Zodb-checkins] CVS: Packages/StorageGC - GCableGraph.py:1.3

[tim@digicool.com]

Update of /cvs-repository/Packages/StorageGC
In directory korak:/tmp/cvs-serv31123

Modified Files:
	GCableGraph.py 
Log Message:
Teach the GCable graph "storage" how to compute trash via mark-&-sweep too.
Since the M&S approach has nothing in common with the CycleGC approach (for
example, M&S doesn't even look at refcounts), this should be an excellent
check on CycleGC's results.  And since the M&S code is just for testing,
it's very simple code that doesn't worry about time or space efficiency
(unlike CycleGC, which worries about both, so is orders of magnitude hairier).



--- Updated File GCableGraph.py in package Packages/StorageGC --
--- GCableGraph.py	2001/04/19 19:41:44	1.2
+++ GCableGraph.py	2001/04/19 21:05:24	1.3
@@ -24,6 +24,10 @@
         self.succs[x].append(y)
         self.rc[y] += 1
 
+    def getnodes(self):
+        "Return list of all nodes."
+        return self.succs.keys()
+
     def dump(self, file=None):
         print >> file, "# nodes", len(self.rc)
 
@@ -58,6 +62,46 @@
             self.trash.sort()
         return self.trash
 
+    # Alternative (mark-&-sweep) method of computing trash.  Since
+    # this has nothing in common with CycleGC's approach (e.g., it
+    # doesn't use refcounts at all), it should be an excellent check
+    # on CycleGC's results.
+
+    def _transitive_closure(self, roots):
+        "Return all nodes reachable from roots, as a set (dict)."
+        tc = {}
+        alreadyknown = tc.has_key
+        candidates = roots[:]
+        push = candidates.append
+        pop = candidates.pop
+        while candidates:
+            c = pop()
+            if alreadyknown(c):
+                continue
+            tc[c] = 1
+            for kid in self.succs[c]:
+                if not alreadyknown(kid):
+                    push(kid)
+        return tc
+
+    def altTrash(self, startnodes, sorted=1):
+        "Compute the same trash list as CycleGC but via a different method."
+        tc = self._transitive_closure(startnodes)
+        # The result is everything in tc not reachable from outside tc.
+        outside_tc = {}
+        for x in self.getnodes():
+            if not tc.has_key(x):
+                outside_tc[x] = 1
+        reachable = self._transitive_closure(outside_tc.keys())
+        result = {}
+        for x in tc.keys():
+            if not reachable.has_key(x):
+                result[x] = 1
+        result = result.keys()
+        if sorted:
+            result.sort()
+        return result
+
 from CyclicGC import CycleGC
 
 g = RCGraph()
@@ -79,7 +123,7 @@
 g.addedge(8, 7)
 g.addedge(8, 6)
 g.addedge(6, 8)
-g.addedge(10, 2)  # should stop any trash collection
+#g.addedge(10, 2)  # should stop any trash collection
 g.dump()
 
 gc = CycleGC(g)
@@ -91,4 +135,8 @@
     gc.start(s)
     while not gc.done():
         gc.resume()
-    print "    trash found:", g.getTrash()
+    trash = g.getTrash()
+    print "    trash found:", trash
+    alt_trash = g.altTrash(s)
+    if trash != alt_trash:
+        raise ValueError("OOPS! altTrash returned %s" % alt_trash)