/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/lru_cache.py

  • Committer: Vincent Ladeuil
  • Date: 2012-01-18 14:09:19 UTC
  • mto: This revision was merged to the branch mainline in revision 6468.
  • Revision ID: v.ladeuil+lp@free.fr-20120118140919-rlvdrhpc0nq1lbwi
Change set/remove to require a lock for the branch config files.

This means that tests (or any plugin for that matter) do not requires an
explicit lock on the branch anymore to change a single option. This also
means the optimisation becomes "opt-in" and as such won't be as
spectacular as it may be and/or harder to get right (nothing fails
anymore).

This reduces the diff by ~300 lines.

Code/tests that were updating more than one config option is still taking
a lock to at least avoid some IOs and demonstrate the benefits through
the decreased number of hpss calls.

The duplication between BranchStack and BranchOnlyStack will be removed
once the same sharing is in place for local config files, at which point
the Stack class itself may be able to host the changes.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
16
16
 
17
17
"""A simple least-recently-used (LRU) cache."""
18
18
 
 
19
from __future__ import absolute_import
 
20
 
19
21
from bzrlib import (
20
22
    symbol_versioning,
21
23
    trace,
26
28
class _LRUNode(object):
27
29
    """This maintains the linked-list which is the lru internals."""
28
30
 
29
 
    __slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
 
31
    __slots__ = ('prev', 'next_key', 'key', 'value')
30
32
 
31
 
    def __init__(self, key, value, cleanup=None):
 
33
    def __init__(self, key, value):
32
34
        self.prev = None
33
35
        self.next_key = _null_key
34
36
        self.key = key
35
37
        self.value = value
36
 
        self.cleanup = cleanup
37
 
        # TODO: We could compute this 'on-the-fly' like we used to, and remove
38
 
        #       one pointer from this object, we just need to decide if it
39
 
        #       actually costs us much of anything in normal usage
40
 
        self.size = None
41
38
 
42
39
    def __repr__(self):
43
40
        if self.prev is None:
47
44
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
48
45
                                     self.next_key, prev_key)
49
46
 
50
 
    def run_cleanup(self):
51
 
        try:
52
 
            if self.cleanup is not None:
53
 
                self.cleanup(self.key, self.value)
54
 
        finally:
55
 
            # cleanup might raise an exception, but we want to make sure
56
 
            # to break refcycles, etc
57
 
            self.cleanup = None
58
 
            self.value = None
59
 
 
60
47
 
61
48
class LRUCache(object):
62
49
    """A class which manages a cache of entries, removing unused ones."""
63
50
 
64
 
    def __init__(self, max_cache=100, after_cleanup_count=None,
65
 
                 after_cleanup_size=symbol_versioning.DEPRECATED_PARAMETER):
66
 
        if symbol_versioning.deprecated_passed(after_cleanup_size):
67
 
            symbol_versioning.warn('LRUCache.__init__(after_cleanup_size) was'
68
 
                                   ' deprecated in 1.11. Use'
69
 
                                   ' after_cleanup_count instead.',
70
 
                                   DeprecationWarning)
71
 
            after_cleanup_count = after_cleanup_size
 
51
    def __init__(self, max_cache=100, after_cleanup_count=None):
72
52
        self._cache = {}
73
53
        # The "HEAD" of the lru linked list
74
54
        self._most_recently_used = None
113
93
    def __len__(self):
114
94
        return len(self._cache)
115
95
 
116
 
    def _walk_lru(self):
117
 
        """Walk the LRU list, only meant to be used in tests."""
118
 
        node = self._most_recently_used
119
 
        if node is not None:
120
 
            if node.prev is not None:
121
 
                raise AssertionError('the _most_recently_used entry is not'
122
 
                                     ' supposed to have a previous entry'
123
 
                                     ' %s' % (node,))
124
 
        while node is not None:
125
 
            if node.next_key is _null_key:
126
 
                if node is not self._least_recently_used:
127
 
                    raise AssertionError('only the last node should have'
128
 
                                         ' no next value: %s' % (node,))
129
 
                node_next = None
130
 
            else:
131
 
                node_next = self._cache[node.next_key]
132
 
                if node_next.prev is not node:
133
 
                    raise AssertionError('inconsistency found, node.next.prev'
134
 
                                         ' != node: %s' % (node,))
135
 
            if node.prev is None:
136
 
                if node is not self._most_recently_used:
137
 
                    raise AssertionError('only the _most_recently_used should'
138
 
                                         ' not have a previous node: %s'
139
 
                                         % (node,))
140
 
            else:
141
 
                if node.prev.next_key != node.key:
142
 
                    raise AssertionError('inconsistency found, node.prev.next'
143
 
                                         ' != node: %s' % (node,))
144
 
            yield node
145
 
            node = node_next
146
 
 
 
96
    @symbol_versioning.deprecated_method(
 
97
        symbol_versioning.deprecated_in((2, 5, 0)))
147
98
    def add(self, key, value, cleanup=None):
148
 
        """Add a new value to the cache.
149
 
 
150
 
        Also, if the entry is ever removed from the cache, call
151
 
        cleanup(key, value).
152
 
 
153
 
        :param key: The key to store it under
154
 
        :param value: The object to store
155
 
        :param cleanup: None or a function taking (key, value) to indicate
156
 
                        'value' should be cleaned up.
157
 
        """
 
99
        if cleanup is not None:
 
100
            raise ValueError("Per-node cleanup functions no longer supported")
 
101
        return self.__setitem__(key, value)
 
102
 
 
103
    def __setitem__(self, key, value):
 
104
        """Add a new value to the cache"""
158
105
        if key is _null_key:
159
106
            raise ValueError('cannot use _null_key as a key')
160
107
        if key in self._cache:
161
108
            node = self._cache[key]
162
 
            try:
163
 
                node.run_cleanup()
164
 
            finally:
165
 
                # Maintain the LRU properties, even if cleanup raises an
166
 
                # exception
167
 
                node.value = value
168
 
                node.cleanup = cleanup
169
 
                self._record_access(node)
 
109
            node.value = value
 
110
            self._record_access(node)
170
111
        else:
171
 
            node = _LRUNode(key, value, cleanup=cleanup)
 
112
            node = _LRUNode(key, value)
172
113
            self._cache[key] = node
173
114
            self._record_access(node)
174
115
 
198
139
        """
199
140
        return self._cache.keys()
200
141
 
201
 
    def items(self):
202
 
        """Get the key:value pairs as a dict."""
 
142
    def as_dict(self):
 
143
        """Get a new dict with the same key:value pairs as the cache"""
203
144
        return dict((k, n.value) for k, n in self._cache.iteritems())
204
145
 
 
146
    items = symbol_versioning.deprecated_method(
 
147
        symbol_versioning.deprecated_in((2, 5, 0)))(as_dict)
 
148
 
205
149
    def cleanup(self):
206
150
        """Clear the cache until it shrinks to the requested size.
207
151
 
212
156
        while len(self._cache) > self._after_cleanup_count:
213
157
            self._remove_lru()
214
158
 
215
 
    def __setitem__(self, key, value):
216
 
        """Add a value to the cache, there will be no cleanup function."""
217
 
        self.add(key, value, cleanup=None)
218
 
 
219
159
    def _record_access(self, node):
220
160
        """Record that key was accessed."""
221
161
        # Move 'node' to the front of the queue
249
189
        # If we have removed all entries, remove the head pointer as well
250
190
        if self._least_recently_used is None:
251
191
            self._most_recently_used = None
252
 
        try:
253
 
            node.run_cleanup()
254
 
        finally:
255
 
            # cleanup might raise an exception, but we want to make sure to
256
 
            # maintain the linked list
257
 
            if node.prev is not None:
258
 
                node.prev.next_key = node.next_key
259
 
            if node.next_key is not _null_key:
260
 
                node_next = self._cache[node.next_key]
261
 
                node_next.prev = node.prev
262
 
            # And remove this node's pointers
263
 
            node.prev = None
264
 
            node.next_key = _null_key
 
192
        if node.prev is not None:
 
193
            node.prev.next_key = node.next_key
 
194
        if node.next_key is not _null_key:
 
195
            node_next = self._cache[node.next_key]
 
196
            node_next.prev = node.prev
 
197
        # And remove this node's pointers
 
198
        node.prev = None
 
199
        node.next_key = _null_key
265
200
 
266
201
    def _remove_lru(self):
267
202
        """Remove one entry from the lru, and handle consequences.
324
259
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
325
260
        LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
326
261
 
327
 
    def add(self, key, value, cleanup=None):
328
 
        """Add a new value to the cache.
329
 
 
330
 
        Also, if the entry is ever removed from the cache, call
331
 
        cleanup(key, value).
332
 
 
333
 
        :param key: The key to store it under
334
 
        :param value: The object to store
335
 
        :param cleanup: None or a function taking (key, value) to indicate
336
 
                        'value' should be cleaned up.
337
 
        """
 
262
    def __setitem__(self, key, value):
 
263
        """Add a new value to the cache"""
338
264
        if key is _null_key:
339
265
            raise ValueError('cannot use _null_key as a key')
340
266
        node = self._cache.get(key, None)
349
275
            if node is not None:
350
276
                # We won't be replacing the old node, so just remove it
351
277
                self._remove_node(node)
352
 
            if cleanup is not None:
353
 
                cleanup(key, value)
354
278
            return
355
279
        if node is None:
356
 
            node = _LRUNode(key, value, cleanup=cleanup)
 
280
            node = _LRUNode(key, value)
357
281
            self._cache[key] = node
358
282
        else:
359
 
            self._value_size -= node.size
360
 
        node.size = value_len
 
283
            self._value_size -= self._compute_size(node.value)
361
284
        self._value_size += value_len
362
285
        self._record_access(node)
363
286
 
376
299
            self._remove_lru()
377
300
 
378
301
    def _remove_node(self, node):
379
 
        self._value_size -= node.size
 
302
        self._value_size -= self._compute_size(node.value)
380
303
        LRUCache._remove_node(self, node)
381
304
 
382
305
    def resize(self, max_size, after_cleanup_size=None):