← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-10 19:56:16 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090610195616-alggpr46n0bmjjhf
Get an initial pyrex implementation.

Initial results show it to actually be slightly slower than pure python.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
18
18
"""
19
19
 
20
20
import heapq
 
21
 
21
22
from bzrlib import (
22
23
    revision,
23
24
    )
61
62
        self._nodes = {}
62
63
        # Maps {sorted(revision_id, revision_id): heads}
63
64
        self._known_heads = {}
 
65
        self.do_cache = do_cache
64
66
        self._initialize_nodes(parent_map)
65
 
        self.do_cache = do_cache
 
67
        self._find_linear_dominators()
 
68
        self._find_gdfo()
66
69
 
67
70
    def _initialize_nodes(self, parent_map):
68
71
        """Populate self._nodes.
87
90
                    parent_node = _KnownGraphNode(parent_key, None)
88
91
                    nodes[parent_key] = parent_node
89
92
                parent_node.child_keys.append(key)
90
 
        self._find_linear_dominators()
91
 
        self._find_gdfo()
92
93
 
93
94
    def _find_linear_dominators(self):
94
95
        """For each node in the set, find any linear dominators.
279
280
        heappop = heapq.heappop
280
281
        heappush = heapq.heappush
281
282
        while queue and len(candidate_nodes) > 1:
282
 
            _, next = heappop(queue)
283
 
            # assert next.ancestor_of is not None
284
 
            next_ancestor_of = next.ancestor_of
 
283
            _, node = heappop(queue)
 
284
            # assert node.ancestor_of is not None
 
285
            next_ancestor_of = node.ancestor_of
285
286
            if len(next_ancestor_of) == num_candidates:
286
287
                # This node is now considered 'common'
287
288
                # Make sure all parent nodes are marked as such
294
295
                    if parent_node.ancestor_of is not None:
295
296
                        parent_node.ancestor_of = next_ancestor_of
296
297
                continue
297
 
            if next.parent_keys is None:
 
298
            if node.parent_keys is None:
298
299
                # This is a ghost
299
300
                continue
300
301
            # Now project the current nodes ancestor list to the parent nodes,
302
303
            # Note: using linear_dominator speeds things up quite a bit
303
304
            #       enough that we actually start to be slightly faster
304
305
            #       than the default heads() implementation
305
 
            if next.linear_dominator != next.key:
 
306
            if node.linear_dominator != node.key:
306
307
                # We are at the tip of a long linear region
307
308
                # We know that there is nothing between here and the tail
308
309
                # that is interesting, so skip to the end
309
 
                parent_keys = [next.linear_dominator]
 
310
                parent_keys = [node.linear_dominator]
310
311
            else:
311
 
                parent_keys = next.parent_keys
 
312
                parent_keys = node.parent_keys
312
313
            for parent_key in parent_keys:
313
314
                if parent_key in candidate_nodes:
314
315
                    candidate_nodes.pop(parent_key)
332
333
                node.ancestor_of = None
333
334
        cleanup()
334
335
        return frozenset(candidate_nodes)
335
 
 
336
 
    def get_parent_map(self, keys):
337
 
        # Thunk to match the Graph._parents_provider api.
338
 
        nodes = [self._nodes[key] for key in keys]
339
 
        return dict((node.key, node.parent_keys)
340
 
                    for node in nodes if node.parent_keys is not None)