13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
17
"""A simple least-recently-used (LRU) cache."""
19
from collections import deque
19
from __future__ import absolute_import
28
class _LRUNode(object):
29
"""This maintains the linked-list which is the lru internals."""
31
__slots__ = ('prev', 'next_key', 'key', 'value')
33
def __init__(self, key, value):
35
self.next_key = _null_key
43
prev_key = self.prev.key
44
return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
45
self.next_key, prev_key)
23
48
class LRUCache(object):
24
49
"""A class which manages a cache of entries, removing unused ones."""
26
def __init__(self, max_cache=100, after_cleanup_size=None):
27
self._max_cache = max_cache
28
if after_cleanup_size is None:
29
self._after_cleanup_size = self._max_cache
31
self._after_cleanup_size = min(after_cleanup_size, self._max_cache)
33
self._compact_queue_length = 4*self._max_cache
51
def __init__(self, max_cache=100, after_cleanup_count=None):
37
self._queue = deque() # Track when things are accessed
38
self._refcount = {} # number of entries in self._queue for each key
53
# The "HEAD" of the lru linked list
54
self._most_recently_used = None
55
# The "TAIL" of the lru linked list
56
self._least_recently_used = None
57
self._update_max_cache(max_cache, after_cleanup_count)
40
59
def __contains__(self, key):
41
60
return key in self._cache
43
62
def __getitem__(self, key):
44
val = self._cache[key]
45
self._record_access(key)
65
# Inlined from _record_access to decrease the overhead of __getitem__
66
# We also have more knowledge about structure if __getitem__ is
67
# succeeding, then we know that self._most_recently_used must not be
69
mru = self._most_recently_used
71
# Nothing to do, this node is already at the head of the queue
73
# Remove this node from the old location
75
next_key = node.next_key
76
# benchmarking shows that the lookup of _null_key in globals is faster
77
# than the attribute lookup for (node is self._least_recently_used)
78
if next_key is _null_key:
79
# 'node' is the _least_recently_used, because it doesn't have a
80
# 'next' item. So move the current lru to the previous node.
81
self._least_recently_used = node_prev
83
node_next = cache[next_key]
84
node_next.prev = node_prev
85
node_prev.next_key = next_key
86
# Insert this node at the front of the list
87
node.next_key = mru.key
89
self._most_recently_used = node
49
94
return len(self._cache)
96
@symbol_versioning.deprecated_method(
97
symbol_versioning.deprecated_in((2, 5, 0)))
51
98
def add(self, key, value, cleanup=None):
52
"""Add a new value to the cache.
54
Also, if the entry is ever removed from the queue, call cleanup.
55
Passing it the key and value being removed.
57
:param key: The key to store it under
58
:param value: The object to store
59
:param cleanup: None or a function taking (key, value) to indicate
60
'value' sohuld be cleaned up.
99
if cleanup is not None:
100
raise ValueError("Per-node cleanup functions no longer supported")
101
return self.__setitem__(key, value)
103
def __setitem__(self, key, value):
104
"""Add a new value to the cache"""
106
raise ValueError('cannot use _null_key as a key')
62
107
if key in self._cache:
64
self._cache[key] = value
65
self._cleanup[key] = cleanup
66
self._record_access(key)
108
node = self._cache[key]
110
self._record_access(node)
112
node = _LRUNode(key, value)
113
self._cache[key] = node
114
self._record_access(node)
68
116
if len(self._cache) > self._max_cache:
69
117
# Trigger the cleanup
120
def cache_size(self):
121
"""Get the number of entries we will cache."""
122
return self._max_cache
72
124
def get(self, key, default=None):
73
if key in self._cache:
125
node = self._cache.get(key, None)
128
self._record_access(node)
78
132
"""Get the list of keys currently cached.
86
140
return self._cache.keys()
143
"""Get a new dict with the same key:value pairs as the cache"""
144
return dict((k, n.value) for k, n in self._cache.iteritems())
146
items = symbol_versioning.deprecated_method(
147
symbol_versioning.deprecated_in((2, 5, 0)))(as_dict)
88
149
def cleanup(self):
89
150
"""Clear the cache until it shrinks to the requested size.
91
152
This does not completely wipe the cache, just makes sure it is under
92
the after_cleanup_size.
153
the after_cleanup_count.
94
155
# Make sure the cache is shrunk to the correct size
95
while len(self._cache) > self._after_cleanup_size:
156
while len(self._cache) > self._after_cleanup_count:
96
157
self._remove_lru()
98
def __setitem__(self, key, value):
99
"""Add a value to the cache, there will be no cleanup function."""
100
self.add(key, value, cleanup=None)
102
def _record_access(self, key):
159
def _record_access(self, node):
103
160
"""Record that key was accessed."""
104
self._queue.append(key)
105
# Can't use setdefault because you can't += 1 the result
106
self._refcount[key] = self._refcount.get(key, 0) + 1
108
# If our access queue is too large, clean it up too
109
if len(self._queue) > self._compact_queue_length:
110
self._compact_queue()
112
def _compact_queue(self):
113
"""Compact the queue, leaving things in sorted last appended order."""
115
for item in self._queue:
116
if self._refcount[item] == 1:
117
new_queue.append(item)
119
self._refcount[item] -= 1
120
self._queue = new_queue
121
# All entries should be of the same size. There should be one entry in
122
# queue for each entry in cache, and all refcounts should == 1
123
if not (len(self._queue) == len(self._cache) ==
124
len(self._refcount) == sum(self._refcount.itervalues())):
125
raise AssertionError()
127
def _remove(self, key):
128
"""Remove an entry, making sure to maintain the invariants."""
129
cleanup = self._cleanup.pop(key)
130
val = self._cache.pop(key)
131
if cleanup is not None:
161
# Move 'node' to the front of the queue
162
if self._most_recently_used is None:
163
self._most_recently_used = node
164
self._least_recently_used = node
166
elif node is self._most_recently_used:
167
# Nothing to do, this node is already at the head of the queue
169
# We've taken care of the tail pointer, remove the node, and insert it
172
if node is self._least_recently_used:
173
self._least_recently_used = node.prev
174
if node.prev is not None:
175
node.prev.next_key = node.next_key
176
if node.next_key is not _null_key:
177
node_next = self._cache[node.next_key]
178
node_next.prev = node.prev
180
node.next_key = self._most_recently_used.key
181
self._most_recently_used.prev = node
182
self._most_recently_used = node
185
def _remove_node(self, node):
186
if node is self._least_recently_used:
187
self._least_recently_used = node.prev
188
self._cache.pop(node.key)
189
# If we have removed all entries, remove the head pointer as well
190
if self._least_recently_used is None:
191
self._most_recently_used = None
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
199
node.next_key = _null_key
135
201
def _remove_lru(self):
136
202
"""Remove one entry from the lru, and handle consequences.
175
252
The function should take the form "compute_size(value) => integer".
176
253
If not supplied, it defaults to 'len()'
178
# This approximates that texts are > 0.5k in size. It only really
179
# effects when we clean up the queue, so we don't want it to be too
181
LRUCache.__init__(self, max_cache=int(max_size/512))
182
self._max_size = max_size
183
if after_cleanup_size is None:
184
self._after_cleanup_size = self._max_size
186
self._after_cleanup_size = min(after_cleanup_size, self._max_size)
188
255
self._value_size = 0
189
256
self._compute_size = compute_size
190
257
if compute_size is None:
191
258
self._compute_size = len
193
def add(self, key, value, cleanup=None):
194
"""Add a new value to the cache.
196
Also, if the entry is ever removed from the queue, call cleanup.
197
Passing it the key and value being removed.
199
:param key: The key to store it under
200
:param value: The object to store
201
:param cleanup: None or a function taking (key, value) to indicate
202
'value' sohuld be cleaned up.
204
if key in self._cache:
259
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
260
LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
262
def __setitem__(self, key, value):
263
"""Add a new value to the cache"""
265
raise ValueError('cannot use _null_key as a key')
266
node = self._cache.get(key, None)
206
267
value_len = self._compute_size(value)
207
268
if value_len >= self._after_cleanup_size:
269
# The new value is 'too big to fit', as it would fill up/overflow
270
# the cache all by itself
271
trace.mutter('Adding the key %r to an LRUSizeCache failed.'
272
' value %d is too big to fit in a the cache'
273
' with size %d %d', key, value_len,
274
self._after_cleanup_size, self._max_size)
276
# We won't be replacing the old node, so just remove it
277
self._remove_node(node)
280
node = _LRUNode(key, value)
281
self._cache[key] = node
283
self._value_size -= self._compute_size(node.value)
209
284
self._value_size += value_len
210
self._cache[key] = value
211
self._cleanup[key] = cleanup
212
self._record_access(key)
285
self._record_access(node)
214
287
if self._value_size > self._max_size:
215
288
# Time to cleanup
225
298
while self._value_size > self._after_cleanup_size:
226
299
self._remove_lru()
228
def _remove(self, key):
229
"""Remove an entry, making sure to maintain the invariants."""
230
val = LRUCache._remove(self, key)
231
self._value_size -= self._compute_size(val)
301
def _remove_node(self, node):
302
self._value_size -= self._compute_size(node.value)
303
LRUCache._remove_node(self, node)
305
def resize(self, max_size, after_cleanup_size=None):
306
"""Change the number of bytes that will be cached."""
307
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
308
max_cache = max(int(max_size/512), 1)
309
self._update_max_cache(max_cache)
311
def _update_max_size(self, max_size, after_cleanup_size=None):
312
self._max_size = max_size
313
if after_cleanup_size is None:
314
self._after_cleanup_size = self._max_size * 8 / 10
316
self._after_cleanup_size = min(after_cleanup_size, self._max_size)
added
removed
bzrlib/lru_cache.py
