/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: Robert Collins
  • Date: 2010-05-06 23:41:35 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506234135-yivbzczw1sejxnxc
Lock methods on ``Tree``, ``Branch`` and ``Repository`` are now
expected to return an object which can be used to unlock them. This reduces
duplicate code when using cleanups. The previous 'tokens's returned by
``Branch.lock_write`` and ``Repository.lock_write`` are now attributes
on the result of the lock_write. ``repository.RepositoryWriteLockResult``
and ``branch.BranchWriteLockResult`` document this. (Robert Collins)

``log._get_info_for_log_files`` now takes an add_cleanup callable.
(Robert Collins)

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, division
20
 
 
21
 
from . import (
 
19
from bzrlib import (
 
20
    symbol_versioning,
22
21
    trace,
23
22
    )
24
 
from .sixish import (
25
 
    viewitems,
26
 
    viewkeys,
27
 
    )
28
 
 
29
23
 
30
24
_null_key = object()
31
25
 
32
 
 
33
26
class _LRUNode(object):
34
27
    """This maintains the linked-list which is the lru internals."""
35
28
 
36
 
    __slots__ = ('prev', 'next_key', 'key', 'value')
 
29
    __slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
37
30
 
38
 
    def __init__(self, key, value):
 
31
    def __init__(self, key, value, cleanup=None):
39
32
        self.prev = None
40
33
        self.next_key = _null_key
41
34
        self.key = key
42
35
        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
43
41
 
44
42
    def __repr__(self):
45
43
        if self.prev is None:
49
47
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
50
48
                                     self.next_key, prev_key)
51
49
 
 
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
 
52
60
 
53
61
class LRUCache(object):
54
62
    """A class which manages a cache of entries, removing unused ones."""
55
63
 
56
 
    def __init__(self, max_cache=100, after_cleanup_count=None):
 
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
57
72
        self._cache = {}
58
73
        # The "HEAD" of the lru linked list
59
74
        self._most_recently_used = None
98
113
    def __len__(self):
99
114
        return len(self._cache)
100
115
 
101
 
    def __setitem__(self, key, value):
102
 
        """Add a new value to the cache"""
 
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
 
 
147
    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
        """
103
158
        if key is _null_key:
104
159
            raise ValueError('cannot use _null_key as a key')
105
160
        if key in self._cache:
106
161
            node = self._cache[key]
107
 
            node.value = value
108
 
            self._record_access(node)
 
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
170
        else:
110
 
            node = _LRUNode(key, value)
 
171
            node = _LRUNode(key, value, cleanup=cleanup)
111
172
            self._cache[key] = node
112
173
            self._record_access(node)
113
174
 
135
196
 
136
197
        :return: An unordered list of keys that are currently cached.
137
198
        """
138
 
        # GZ 2016-06-04: Maybe just make this return the view?
139
 
        return list(viewkeys(self._cache))
 
199
        return self._cache.keys()
140
200
 
141
 
    def as_dict(self):
142
 
        """Get a new dict with the same key:value pairs as the cache"""
143
 
        return dict((k, n.value) for k, n in viewitems(self._cache))
 
201
    def items(self):
 
202
        """Get the key:value pairs as a dict."""
 
203
        return dict((k, n.value) for k, n in self._cache.iteritems())
144
204
 
145
205
    def cleanup(self):
146
206
        """Clear the cache until it shrinks to the requested size.
152
212
        while len(self._cache) > self._after_cleanup_count:
153
213
            self._remove_lru()
154
214
 
 
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
 
155
219
    def _record_access(self, node):
156
220
        """Record that key was accessed."""
157
221
        # Move 'node' to the front of the queue
185
249
        # If we have removed all entries, remove the head pointer as well
186
250
        if self._least_recently_used is None:
187
251
            self._most_recently_used = None
188
 
        if node.prev is not None:
189
 
            node.prev.next_key = node.next_key
190
 
        if node.next_key is not _null_key:
191
 
            node_next = self._cache[node.next_key]
192
 
            node_next.prev = node.prev
193
 
        # And remove this node's pointers
194
 
        node.prev = None
195
 
        node.next_key = _null_key
 
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
196
265
 
197
266
    def _remove_lru(self):
198
267
        """Remove one entry from the lru, and handle consequences.
216
285
    def _update_max_cache(self, max_cache, after_cleanup_count=None):
217
286
        self._max_cache = max_cache
218
287
        if after_cleanup_count is None:
219
 
            self._after_cleanup_count = self._max_cache * 8 // 10
 
288
            self._after_cleanup_count = self._max_cache * 8 / 10
220
289
        else:
221
290
            self._after_cleanup_count = min(after_cleanup_count,
222
291
                                            self._max_cache)
233
302
    defaults to len() if not supplied.
234
303
    """
235
304
 
236
 
    def __init__(self, max_size=1024 * 1024, after_cleanup_size=None,
 
305
    def __init__(self, max_size=1024*1024, after_cleanup_size=None,
237
306
                 compute_size=None):
238
307
        """Create a new LRUSizeCache.
239
308
 
253
322
        if compute_size is None:
254
323
            self._compute_size = len
255
324
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
256
 
        LRUCache.__init__(self, max_cache=max(int(max_size // 512), 1))
257
 
 
258
 
    def __setitem__(self, key, value):
259
 
        """Add a new value to the cache"""
 
325
        LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
 
326
 
 
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
        """
260
338
        if key is _null_key:
261
339
            raise ValueError('cannot use _null_key as a key')
262
340
        node = self._cache.get(key, None)
271
349
            if node is not None:
272
350
                # We won't be replacing the old node, so just remove it
273
351
                self._remove_node(node)
 
352
            if cleanup is not None:
 
353
                cleanup(key, value)
274
354
            return
275
355
        if node is None:
276
 
            node = _LRUNode(key, value)
 
356
            node = _LRUNode(key, value, cleanup=cleanup)
277
357
            self._cache[key] = node
278
358
        else:
279
 
            self._value_size -= self._compute_size(node.value)
 
359
            self._value_size -= node.size
 
360
        node.size = value_len
280
361
        self._value_size += value_len
281
362
        self._record_access(node)
282
363
 
295
376
            self._remove_lru()
296
377
 
297
378
    def _remove_node(self, node):
298
 
        self._value_size -= self._compute_size(node.value)
 
379
        self._value_size -= node.size
299
380
        LRUCache._remove_node(self, node)
300
381
 
301
382
    def resize(self, max_size, after_cleanup_size=None):
302
383
        """Change the number of bytes that will be cached."""
303
384
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
304
 
        max_cache = max(int(max_size // 512), 1)
 
385
        max_cache = max(int(max_size/512), 1)
305
386
        self._update_max_cache(max_cache)
306
387
 
307
388
    def _update_max_size(self, max_size, after_cleanup_size=None):
308
389
        self._max_size = max_size
309
390
        if after_cleanup_size is None:
310
 
            self._after_cleanup_size = self._max_size * 8 // 10
 
391
            self._after_cleanup_size = self._max_size * 8 / 10
311
392
        else:
312
393
            self._after_cleanup_size = min(after_cleanup_size, self._max_size)