17
17
"""A simple least-recently-used (LRU) cache."""
19
from __future__ import absolute_import, division
30
24
_null_key = object()
32
26
class _LRUNode(object):
33
27
"""This maintains the linked-list which is the lru internals."""
35
__slots__ = ('prev', 'next_key', 'key', 'value')
29
__slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
37
def __init__(self, key, value):
31
def __init__(self, key, value, cleanup=None):
39
33
self.next_key = _null_key
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
43
42
def __repr__(self):
44
43
if self.prev is None:
48
47
return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
49
48
self.next_key, prev_key)
50
def run_cleanup(self):
52
if self.cleanup is not None:
53
self.cleanup(self.key, self.value)
55
# cleanup might raise an exception, but we want to make sure
56
# to break refcycles, etc
52
61
class LRUCache(object):
53
62
"""A class which manages a cache of entries, removing unused ones."""
55
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.',
71
after_cleanup_count = after_cleanup_size
57
73
# The "HEAD" of the lru linked list
58
74
self._most_recently_used = None
97
113
def __len__(self):
98
114
return len(self._cache)
100
def __setitem__(self, key, value):
101
"""Add a new value to the cache"""
117
"""Walk the LRU list, only meant to be used in tests."""
118
node = self._most_recently_used
120
if node.prev is not None:
121
raise AssertionError('the _most_recently_used entry is not'
122
' supposed to have a previous entry'
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,))
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'
141
if node.prev.next_key != node.key:
142
raise AssertionError('inconsistency found, node.prev.next'
143
' != node: %s' % (node,))
147
def add(self, key, value, cleanup=None):
148
"""Add a new value to the cache.
150
Also, if the entry is ever removed from the cache, call
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.
102
158
if key is _null_key:
103
159
raise ValueError('cannot use _null_key as a key')
104
160
if key in self._cache:
105
161
node = self._cache[key]
107
self._record_access(node)
165
# Maintain the LRU properties, even if cleanup raises an
168
node.cleanup = cleanup
169
self._record_access(node)
109
node = _LRUNode(key, value)
171
node = _LRUNode(key, value, cleanup=cleanup)
110
172
self._cache[key] = node
111
173
self._record_access(node)
135
197
:return: An unordered list of keys that are currently cached.
137
# GZ 2016-06-04: Maybe just make this return the view?
138
return list(viewkeys(self._cache))
199
return self._cache.keys()
141
"""Get a new dict with the same key:value pairs as the cache"""
142
return dict((k, n.value) for k, n in viewitems(self._cache))
202
"""Get the key:value pairs as a dict."""
203
return dict((k, n.value) for k, n in self._cache.iteritems())
144
205
def cleanup(self):
145
206
"""Clear the cache until it shrinks to the requested size.
151
212
while len(self._cache) > self._after_cleanup_count:
152
213
self._remove_lru()
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)
154
219
def _record_access(self, node):
155
220
"""Record that key was accessed."""
156
221
# Move 'node' to the front of the queue
184
249
# If we have removed all entries, remove the head pointer as well
185
250
if self._least_recently_used is None:
186
251
self._most_recently_used = None
187
if node.prev is not None:
188
node.prev.next_key = node.next_key
189
if node.next_key is not _null_key:
190
node_next = self._cache[node.next_key]
191
node_next.prev = node.prev
192
# And remove this node's pointers
194
node.next_key = _null_key
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
264
node.next_key = _null_key
196
266
def _remove_lru(self):
197
267
"""Remove one entry from the lru, and handle consequences.
215
285
def _update_max_cache(self, max_cache, after_cleanup_count=None):
216
286
self._max_cache = max_cache
217
287
if after_cleanup_count is None:
218
self._after_cleanup_count = self._max_cache * 8 // 10
288
self._after_cleanup_count = self._max_cache * 8 / 10
220
290
self._after_cleanup_count = min(after_cleanup_count,
252
322
if compute_size is None:
253
323
self._compute_size = len
254
324
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
255
LRUCache.__init__(self, max_cache=max(int(max_size // 512), 1))
257
def __setitem__(self, key, value):
258
"""Add a new value to the cache"""
325
LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
327
def add(self, key, value, cleanup=None):
328
"""Add a new value to the cache.
330
Also, if the entry is ever removed from the cache, call
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.
259
338
if key is _null_key:
260
339
raise ValueError('cannot use _null_key as a key')
261
340
node = self._cache.get(key, None)
270
349
if node is not None:
271
350
# We won't be replacing the old node, so just remove it
272
351
self._remove_node(node)
352
if cleanup is not None:
275
node = _LRUNode(key, value)
356
node = _LRUNode(key, value, cleanup=cleanup)
276
357
self._cache[key] = node
278
self._value_size -= self._compute_size(node.value)
359
self._value_size -= node.size
360
node.size = value_len
279
361
self._value_size += value_len
280
362
self._record_access(node)
294
376
self._remove_lru()
296
378
def _remove_node(self, node):
297
self._value_size -= self._compute_size(node.value)
379
self._value_size -= node.size
298
380
LRUCache._remove_node(self, node)
300
382
def resize(self, max_size, after_cleanup_size=None):
301
383
"""Change the number of bytes that will be cached."""
302
384
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
303
max_cache = max(int(max_size // 512), 1)
385
max_cache = max(int(max_size/512), 1)
304
386
self._update_max_cache(max_cache)
306
388
def _update_max_size(self, max_size, after_cleanup_size=None):
307
389
self._max_size = max_size
308
390
if after_cleanup_size is None:
309
self._after_cleanup_size = self._max_size * 8 // 10
391
self._after_cleanup_size = self._max_size * 8 / 10
311
393
self._after_cleanup_size = min(after_cleanup_size, self._max_size)