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

  • Committer: Jelmer Vernooij
  • Date: 2020-04-05 19:11:34 UTC
  • mto: (7490.7.16 work)
  • mto: This revision was merged to the branch mainline in revision 7501.
  • Revision ID: jelmer@jelmer.uk-20200405191134-0aebh8ikiwygxma5
Populate the .gitignore file.

Show diffs side-by-side

added added

removed removed

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