← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: Vincent Ladeuil
  • Date: 2009-06-18 14:12:37 UTC
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: v.ladeuil+lp@free.fr-20090618141237-k9u7mrithzstg15z
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.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
310
310
        return tails
311
311
 
312
312
    def _find_gdfo(self):
 
313
        cdef _KnownGraphNode node
 
314
        cdef _KnownGraphNode child
 
315
 
 
316
        nodes = self._nodes
 
317
        pending = []
 
318
        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
 
319
 
 
320
        for node in nodes.values():
 
321
            if not node.parents:
 
322
                node.gdfo = 1
 
323
                known_parent_gdfos[node.key] = 0
 
324
                pending.append(node)
 
325
 
 
326
        while pending:
 
327
            node = <_KnownGraphNode>pending.pop()
 
328
            for child in node.children:
 
329
                known_parent_gdfos[child.key] = known_parent_gdfos[child.key] + 1
 
330
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
 
331
                    child.gdfo = node.gdfo + 1
 
332
                if known_parent_gdfos[child.key] == len(child.parents):
 
333
                    # We are the last parent updating that node, we can
 
334
                    # continue from there
 
335
                    pending.append(child)
 
336
 
 
337
    def x_find_gdfo(self):
313
338
        cdef Py_ssize_t pos, pos2
314
339
        cdef _KnownGraphNode node
315
340
        cdef _KnownGraphNode child_node