/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-04 17:12:29 UTC
  • mto: This revision was merged to the branch mainline in revision 4410.
  • Revision ID: john@arbash-meinel.com-20090604171229-kbgfatt63y3u3uh1
Some small tweaks to decoding strings (avoid passing over the length 2x)

Down to 1.1s (from 1.4s) for decoding all of bzr.dev.
Also, favor decoding strings and then lists in _decode_object, since that is the
frequency we have those types inside Revisions.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
19
19
from bzrlib import (
20
20
    debug,
21
21
    errors,
22
 
    osutils,
23
22
    revision,
 
23
    symbol_versioning,
24
24
    trace,
 
25
    tsort,
25
26
    )
26
 
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
28
28
STEP_UNIQUE_SEARCHER_EVERY = 5
29
29
 
60
60
        return 'DictParentsProvider(%r)' % self.ancestry
61
61
 
62
62
    def get_parent_map(self, keys):
63
 
        """See StackedParentsProvider.get_parent_map"""
 
63
        """See _StackedParentsProvider.get_parent_map"""
64
64
        ancestry = self.ancestry
65
65
        return dict((k, ancestry[k]) for k in keys if k in ancestry)
66
66
 
67
 
@deprecated_function(deprecated_in((1, 16, 0)))
68
 
def _StackedParentsProvider(*args, **kwargs):
69
 
    return StackedParentsProvider(*args, **kwargs)
70
 
 
71
 
class StackedParentsProvider(object):
72
 
    """A parents provider which stacks (or unions) multiple providers.
73
 
    
74
 
    The providers are queries in the order of the provided parent_providers.
75
 
    """
76
 
    
 
67
 
 
68
class _StackedParentsProvider(object):
 
69
 
77
70
    def __init__(self, parent_providers):
78
71
        self._parent_providers = parent_providers
79
72
 
80
73
    def __repr__(self):
81
 
        return "%s(%r)" % (self.__class__.__name__, self._parent_providers)
 
74
        return "_StackedParentsProvider(%r)" % self._parent_providers
82
75
 
83
76
    def get_parent_map(self, keys):
84
77
        """Get a mapping of keys => parents
155
148
        return dict(self._cache)
156
149
 
157
150
    def get_parent_map(self, keys):
158
 
        """See StackedParentsProvider.get_parent_map."""
 
151
        """See _StackedParentsProvider.get_parent_map."""
159
152
        cache = self._cache
160
153
        if cache is None:
161
154
            cache = self._get_parent_map(keys)
311
304
        # get there.
312
305
        return known_revnos[cur_tip] + num_steps
313
306
 
314
 
    def find_lefthand_distances(self, keys):
315
 
        """Find the distance to null for all the keys in keys.
316
 
 
317
 
        :param keys: keys to lookup.
318
 
        :return: A dict key->distance for all of keys.
319
 
        """
320
 
        # Optimisable by concurrent searching, but a random spread should get
321
 
        # some sort of hit rate.
322
 
        result = {}
323
 
        known_revnos = []
324
 
        ghosts = []
325
 
        for key in keys:
326
 
            try:
327
 
                known_revnos.append(
328
 
                    (key, self.find_distance_to_null(key, known_revnos)))
329
 
            except errors.GhostRevisionsHaveNoRevno:
330
 
                ghosts.append(key)
331
 
        for key in ghosts:
332
 
            known_revnos.append((key, -1))
333
 
        return dict(known_revnos)
334
 
 
335
307
    def find_unique_ancestors(self, unique_revision, common_revisions):
336
308
        """Find the unique ancestors for a revision versus others.
337
309
 
926
898
        An ancestor may sort after a descendant if the relationship is not
927
899
        visible in the supplied list of revisions.
928
900
        """
929
 
        from bzrlib import tsort
930
901
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
931
902
        return sorter.iter_topo_order()
932
903
 
1677
1648
            removed.add(node)
1678
1649
 
1679
1650
    return result
1680
 
 
1681
 
 
1682
 
class GraphThunkIdsToKeys(object):
1683
 
    """Forwards calls about 'ids' to be about keys internally."""
1684
 
 
1685
 
    def __init__(self, graph):
1686
 
        self._graph = graph
1687
 
 
1688
 
    def topo_sort(self):
1689
 
        return [r for (r,) in self._graph.topo_sort()]
1690
 
 
1691
 
    def heads(self, ids):
1692
 
        """See Graph.heads()"""
1693
 
        as_keys = [(i,) for i in ids]
1694
 
        head_keys = self._graph.heads(as_keys)
1695
 
        return set([h[0] for h in head_keys])
1696
 
 
1697
 
    def merge_sort(self, tip_revision):
1698
 
        return self._graph.merge_sort((tip_revision,))
1699
 
 
1700
 
 
1701
 
_counters = [0,0,0,0,0,0,0]
1702
 
try:
1703
 
    from bzrlib._known_graph_pyx import KnownGraph
1704
 
except ImportError, e:
1705
 
    osutils.failed_to_load_extension(e)
1706
 
    from bzrlib._known_graph_py import KnownGraph