← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Mark Hammond
  • Date: 2008-12-28 05:21:23 UTC
  • mfrom: (3920 +trunk)
  • mto: (3932.1.1 prepare-1.11)
  • mto: This revision was merged to the branch mainline in revision 3937.
  • Revision ID: mhammond@skippinet.com.au-20081228052123-f78xs5sbdkotshwf
merge trunk

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
24
24
    trace,
25
25
    tsort,
26
26
    )
27
 
from bzrlib.deprecated_graph import (node_distances, select_farthest)
28
27
 
29
28
STEP_UNIQUE_SEARCHER_EVERY = 5
30
29
 
99
98
 
100
99
 
101
100
class CachingParentsProvider(object):
102
 
    """A parents provider which will cache the revision => parents in a dict.
103
 
 
104
 
    This is useful for providers that have an expensive lookup.
 
101
    """A parents provider which will cache the revision => parents as a dict.
 
102
 
 
103
    This is useful for providers which have an expensive look up.
 
104
 
 
105
    Either a ParentsProvider or a get_parent_map-like callback may be
 
106
    supplied.  If it provides extra un-asked-for parents, they will be cached,
 
107
    but filtered out of get_parent_map.
 
108
 
 
109
    The cache is enabled by default, but may be disabled and re-enabled.
105
110
    """
 
111
    def __init__(self, parent_provider=None, get_parent_map=None):
 
112
        """Constructor.
106
113
 
107
 
    def __init__(self, parent_provider):
 
114
        :param parent_provider: The ParentProvider to use.  It or
 
115
            get_parent_map must be supplied.
 
116
        :param get_parent_map: The get_parent_map callback to use.  It or
 
117
            parent_provider must be supplied.
 
118
        """
108
119
        self._real_provider = parent_provider
109
 
        # Theoretically we could use an LRUCache here
 
120
        if get_parent_map is None:
 
121
            self._get_parent_map = self._real_provider.get_parent_map
 
122
        else:
 
123
            self._get_parent_map = get_parent_map
110
124
        self._cache = {}
 
125
        self._cache_misses = True
111
126
 
112
127
    def __repr__(self):
113
128
        return "%s(%r)" % (self.__class__.__name__, self._real_provider)
114
129
 
 
130
    def enable_cache(self, cache_misses=True):
 
131
        """Enable cache."""
 
132
        if self._cache is not None:
 
133
            raise AssertionError('Cache enabled when already enabled.')
 
134
        self._cache = {}
 
135
        self._cache_misses = cache_misses
 
136
 
 
137
    def disable_cache(self):
 
138
        """Disable and clear the cache."""
 
139
        self._cache = None
 
140
 
 
141
    def get_cached_map(self):
 
142
        """Return any cached get_parent_map values."""
 
143
        if self._cache is None:
 
144
            return None
 
145
        return dict((k, v) for k, v in self._cache.items()
 
146
                    if v is not None)
 
147
 
115
148
    def get_parent_map(self, keys):
116
 
        """See _StackedParentsProvider.get_parent_map"""
117
 
        needed = set()
118
 
        # If the _real_provider doesn't have a key, we cache a value of None,
119
 
        # which we then later use to realize we cannot provide a value for that
120
 
        # key.
121
 
        parent_map = {}
122
 
        cache = self._cache
123
 
        for key in keys:
124
 
            if key in cache:
125
 
                value = cache[key]
126
 
                if value is not None:
127
 
                    parent_map[key] = value
128
 
            else:
129
 
                needed.add(key)
130
 
 
131
 
        if needed:
132
 
            new_parents = self._real_provider.get_parent_map(needed)
133
 
            cache.update(new_parents)
134
 
            parent_map.update(new_parents)
135
 
            needed.difference_update(new_parents)
136
 
            cache.update(dict.fromkeys(needed, None))
137
 
        return parent_map
 
149
        """See _StackedParentsProvider.get_parent_map."""
 
150
        # Hack to build up the caching logic.
 
151
        ancestry = self._cache
 
152
        if ancestry is None:
 
153
            # Caching is disabled.
 
154
            missing_revisions = set(keys)
 
155
            ancestry = {}
 
156
        else:
 
157
            missing_revisions = set(key for key in keys if key not in ancestry)
 
158
        if missing_revisions:
 
159
            parent_map = self._get_parent_map(missing_revisions)
 
160
            ancestry.update(parent_map)
 
161
            if self._cache_misses:
 
162
                # None is never a valid parents list, so it can be used to
 
163
                # record misses.
 
164
                ancestry.update(dict((k, None) for k in missing_revisions
 
165
                                     if k not in parent_map))
 
166
        present_keys = [k for k in keys if ancestry.get(k) is not None]
 
167
        return dict((k, ancestry[k]) for k in present_keys)
138
168
 
139
169
 
140
170
class Graph(object):