1
# Copyright (C) 2006, 2008, 2009 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
"""A simple least-recently-used (LRU) cache."""
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)
48
class LRUCache(object):
49
"""A class which manages a cache of entries, removing unused ones."""
51
def __init__(self, max_cache=100, after_cleanup_count=None):
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)
59
def __contains__(self, key):
60
return key in self._cache
62
def __getitem__(self, 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
94
return len(self._cache)
96
@symbol_versioning.deprecated_method(
97
symbol_versioning.deprecated_in((2, 5, 0)))
98
def add(self, key, value, cleanup=None):
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')
107
if key in self._cache:
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)
116
if len(self._cache) > self._max_cache:
117
# Trigger the cleanup
120
def cache_size(self):
121
"""Get the number of entries we will cache."""
122
return self._max_cache
124
def get(self, key, default=None):
125
node = self._cache.get(key, None)
128
self._record_access(node)
132
"""Get the list of keys currently cached.
134
Note that values returned here may not be available by the time you
135
request them later. This is simply meant as a peak into the current
138
:return: An unordered list of keys that are currently cached.
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)
150
"""Clear the cache until it shrinks to the requested size.
152
This does not completely wipe the cache, just makes sure it is under
153
the after_cleanup_count.
155
# Make sure the cache is shrunk to the correct size
156
while len(self._cache) > self._after_cleanup_count:
159
def _record_access(self, node):
160
"""Record that key was accessed."""
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
201
def _remove_lru(self):
202
"""Remove one entry from the lru, and handle consequences.
204
If there are no more references to the lru, then this entry should be
205
removed from the cache.
207
self._remove_node(self._least_recently_used)
210
"""Clear out all of the cache."""
211
# Clean up in LRU order
215
def resize(self, max_cache, after_cleanup_count=None):
216
"""Change the number of entries that will be cached."""
217
self._update_max_cache(max_cache,
218
after_cleanup_count=after_cleanup_count)
220
def _update_max_cache(self, max_cache, after_cleanup_count=None):
221
self._max_cache = max_cache
222
if after_cleanup_count is None:
223
self._after_cleanup_count = self._max_cache * 8 / 10
225
self._after_cleanup_count = min(after_cleanup_count,
230
class LRUSizeCache(LRUCache):
231
"""An LRUCache that removes things based on the size of the values.
233
This differs in that it doesn't care how many actual items there are,
234
it just restricts the cache to be cleaned up after so much data is stored.
236
The size of items added will be computed using compute_size(value), which
237
defaults to len() if not supplied.
240
def __init__(self, max_size=1024*1024, after_cleanup_size=None,
242
"""Create a new LRUSizeCache.
244
:param max_size: The max number of bytes to store before we start
245
clearing out entries.
246
:param after_cleanup_size: After cleaning up, shrink everything to this
248
:param compute_size: A function to compute the size of the values. We
249
use a function here, so that you can pass 'len' if you are just
250
using simple strings, or a more complex function if you are using
251
something like a list of strings, or even a custom object.
252
The function should take the form "compute_size(value) => integer".
253
If not supplied, it defaults to 'len()'
256
self._compute_size = compute_size
257
if compute_size is None:
258
self._compute_size = len
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)
267
value_len = self._compute_size(value)
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)
284
self._value_size += value_len
285
self._record_access(node)
287
if self._value_size > self._max_size:
292
"""Clear the cache until it shrinks to the requested size.
294
This does not completely wipe the cache, just makes sure it is under
295
the after_cleanup_size.
297
# Make sure the cache is shrunk to the correct size
298
while self._value_size > self._after_cleanup_size:
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
