26
25
class _LRUNode(object):
27
26
"""This maintains the linked-list which is the lru internals."""
29
__slots__ = ('prev', 'next_key', 'key', 'value')
28
__slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
31
def __init__(self, key, value):
30
def __init__(self, key, value, cleanup=None):
33
32
self.next_key = _null_key
35
self.cleanup = cleanup
36
# TODO: We could compute this 'on-the-fly' like we used to, and remove
37
# one pointer from this object, we just need to decide if it
38
# actually costs us much of anything in normal usage
37
41
def __repr__(self):
38
42
if self.prev is None:
42
46
return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
43
47
self.next_key, prev_key)
49
def run_cleanup(self):
51
if self.cleanup is not None:
52
self.cleanup(self.key, self.value)
54
# cleanup might raise an exception, but we want to make sure
55
# to break refcycles, etc
46
60
class LRUCache(object):
47
61
"""A class which manages a cache of entries, removing unused ones."""
91
105
def __len__(self):
92
106
return len(self._cache)
94
@symbol_versioning.deprecated_method(
95
symbol_versioning.deprecated_in((2, 5, 0)))
109
"""Walk the LRU list, only meant to be used in tests."""
110
node = self._most_recently_used
112
if node.prev is not None:
113
raise AssertionError('the _most_recently_used entry is not'
114
' supposed to have a previous entry'
116
while node is not None:
117
if node.next_key is _null_key:
118
if node is not self._least_recently_used:
119
raise AssertionError('only the last node should have'
120
' no next value: %s' % (node,))
123
node_next = self._cache[node.next_key]
124
if node_next.prev is not node:
125
raise AssertionError('inconsistency found, node.next.prev'
126
' != node: %s' % (node,))
127
if node.prev is None:
128
if node is not self._most_recently_used:
129
raise AssertionError('only the _most_recently_used should'
130
' not have a previous node: %s'
133
if node.prev.next_key != node.key:
134
raise AssertionError('inconsistency found, node.prev.next'
135
' != node: %s' % (node,))
96
139
def add(self, key, value, cleanup=None):
97
if cleanup is not None:
98
raise ValueError("Per-node cleanup functions no longer supported")
99
return self.__setitem__(key, value)
101
def __setitem__(self, key, value):
102
"""Add a new value to the cache"""
140
"""Add a new value to the cache.
142
Also, if the entry is ever removed from the cache, call
145
:param key: The key to store it under
146
:param value: The object to store
147
:param cleanup: None or a function taking (key, value) to indicate
148
'value' should be cleaned up.
103
150
if key is _null_key:
104
151
raise ValueError('cannot use _null_key as a key')
105
152
if key in self._cache:
106
153
node = self._cache[key]
108
self._record_access(node)
157
# Maintain the LRU properties, even if cleanup raises an
160
node.cleanup = cleanup
161
self._record_access(node)
110
node = _LRUNode(key, value)
163
node = _LRUNode(key, value, cleanup=cleanup)
111
164
self._cache[key] = node
112
165
self._record_access(node)
138
191
return self._cache.keys()
141
"""Get a new dict with the same key:value pairs as the cache"""
194
"""Get the key:value pairs as a dict."""
142
195
return dict((k, n.value) for k, n in self._cache.iteritems())
144
items = symbol_versioning.deprecated_method(
145
symbol_versioning.deprecated_in((2, 5, 0)))(as_dict)
147
197
def cleanup(self):
148
198
"""Clear the cache until it shrinks to the requested size.
154
204
while len(self._cache) > self._after_cleanup_count:
155
205
self._remove_lru()
207
def __setitem__(self, key, value):
208
"""Add a value to the cache, there will be no cleanup function."""
209
self.add(key, value, cleanup=None)
157
211
def _record_access(self, node):
158
212
"""Record that key was accessed."""
159
213
# Move 'node' to the front of the queue
187
241
# If we have removed all entries, remove the head pointer as well
188
242
if self._least_recently_used is None:
189
243
self._most_recently_used = None
190
if node.prev is not None:
191
node.prev.next_key = node.next_key
192
if node.next_key is not _null_key:
193
node_next = self._cache[node.next_key]
194
node_next.prev = node.prev
195
# And remove this node's pointers
197
node.next_key = _null_key
247
# cleanup might raise an exception, but we want to make sure to
248
# maintain the linked list
249
if node.prev is not None:
250
node.prev.next_key = node.next_key
251
if node.next_key is not _null_key:
252
node_next = self._cache[node.next_key]
253
node_next.prev = node.prev
254
# And remove this node's pointers
256
node.next_key = _null_key
199
258
def _remove_lru(self):
200
259
"""Remove one entry from the lru, and handle consequences.
257
316
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
258
317
LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
260
def __setitem__(self, key, value):
261
"""Add a new value to the cache"""
319
def add(self, key, value, cleanup=None):
320
"""Add a new value to the cache.
322
Also, if the entry is ever removed from the cache, call
325
:param key: The key to store it under
326
:param value: The object to store
327
:param cleanup: None or a function taking (key, value) to indicate
328
'value' should be cleaned up.
262
330
if key is _null_key:
263
331
raise ValueError('cannot use _null_key as a key')
264
332
node = self._cache.get(key, None)
273
341
if node is not None:
274
342
# We won't be replacing the old node, so just remove it
275
343
self._remove_node(node)
344
if cleanup is not None:
278
node = _LRUNode(key, value)
348
node = _LRUNode(key, value, cleanup=cleanup)
279
349
self._cache[key] = node
281
self._value_size -= self._compute_size(node.value)
351
self._value_size -= node.size
352
node.size = value_len
282
353
self._value_size += value_len
283
354
self._record_access(node)
297
368
self._remove_lru()
299
370
def _remove_node(self, node):
300
self._value_size -= self._compute_size(node.value)
371
self._value_size -= node.size
301
372
LRUCache._remove_node(self, node)
303
374
def resize(self, max_size, after_cleanup_size=None):
added
removed
bzrlib/lru_cache.py
