Rev 4419: Replace the existing KnownGraph._find_gdfo. in file:///home/vila/src/bzr/experimental/vila-better-heads/

[Vincent Ladeuil]

At file:///home/vila/src/bzr/experimental/vila-better-heads/

------------------------------------------------------------
revno: 4419
revision-id: v.ladeuil+lp at free.fr-20090618141237-k9u7mrithzstg15z
parent: v.ladeuil+lp at free.fr-20090618095138-rha25usmqwsfwoxv
committer: Vincent Ladeuil <v.ladeuil+lp at free.fr>
branch nick: vila-better-heads
timestamp: Thu 2009-06-18 16:12:37 +0200
message:
  Replace the existing KnownGraph._find_gdfo.
  
  * bzrlib/_known_graph_pyx.pyx:
  (_find_gdfo): pyrex version, almost as fast as the previous one,
  but we don't need the linear dominator so we can potentially save
  some time during __init__.
  
  * bzrlib/_known_graph_py.py:
  (KnownGraph._find_gdfo): Get rid of the inner function to stay in
  sync with the pyrex version.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-06-18 09:51:38 +0000
+++ b/bzrlib/_known_graph_py.py	2009-06-18 14:12:37 +0000
@@ -151,7 +151,13 @@
         pending = []
         known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
 
-        def update_childs(node):
+        for node in nodes.values():
+            if not node.parent_keys:
+                node.gdfo = 1
+                known_parent_gdfos[node.key] = 0
+                pending.append(node)
+        while pending:
+            node = pending.pop()
             for child_key in node.child_keys:
                 child = nodes[child_key]
                 known_parent_gdfos[child_key] += 1
@@ -162,14 +168,6 @@
                     # continue from there
                     pending.append(child)
 
-        for node in self._nodes.itervalues():
-            if not node.parent_keys:
-                node.gdfo = 1
-                known_parent_gdfos[node.key] = 0
-                update_childs(node)
-        while pending:
-            update_childs(pending.pop())
-
     def x_find_gdfo(self):
         def find_tails():
             return [node for node in self._nodes.itervalues()

=== modified file 'bzrlib/_known_graph_pyx.pyx'
--- a/bzrlib/_known_graph_pyx.pyx	2009-06-18 09:51:38 +0000
+++ b/bzrlib/_known_graph_pyx.pyx	2009-06-18 14:12:37 +0000
@@ -310,6 +310,31 @@
         return tails
 
     def _find_gdfo(self):
+        cdef _KnownGraphNode node
+        cdef _KnownGraphNode child
+
+        nodes = self._nodes
+        pending = []
+        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
+
+        for node in nodes.values():
+            if not node.parents:
+                node.gdfo = 1
+                known_parent_gdfos[node.key] = 0
+                pending.append(node)
+
+        while pending:
+            node = <_KnownGraphNode>pending.pop()
+            for child in node.children:
+                known_parent_gdfos[child.key] = known_parent_gdfos[child.key] + 1
+                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
+                    child.gdfo = node.gdfo + 1
+                if known_parent_gdfos[child.key] == len(child.parents):
+                    # We are the last parent updating that node, we can
+                    # continue from there
+                    pending.append(child)
+
+    def x_find_gdfo(self):
         cdef Py_ssize_t pos, pos2
         cdef _KnownGraphNode node
         cdef _KnownGraphNode child_node