1
# Copyright (C) 2006 Canonical Ltd
1
# Copyright (C) 2006, 2008 Canonical Ltd
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
17
17
"""A simple least-recently-used (LRU) cache."""
19
19
from collections import deque
21
from bzrlib import symbol_versioning
23
24
class LRUCache(object):
24
25
"""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
27
def __init__(self, max_cache=100, after_cleanup_count=None,
28
after_cleanup_size=symbol_versioning.DEPRECATED_PARAMETER):
29
if symbol_versioning.deprecated_passed(after_cleanup_size):
30
symbol_versioning.warn('LRUCache.__init__(after_cleanup_size) was'
31
' deprecated in 1.11. Use'
32
' after_cleanup_count instead.',
34
after_cleanup_count = after_cleanup_size
37
37
self._queue = deque() # Track when things are accessed
38
38
self._refcount = {} # number of entries in self._queue for each key
39
self._update_max_cache(max_cache, after_cleanup_count)
40
41
def __contains__(self, key):
41
42
return key in self._cache
89
91
"""Clear the cache until it shrinks to the requested size.
91
93
This does not completely wipe the cache, just makes sure it is under
92
the after_cleanup_size.
94
the after_cleanup_count.
94
96
# Make sure the cache is shrunk to the correct size
95
while len(self._cache) > self._after_cleanup_size:
97
while len(self._cache) > self._after_cleanup_count:
99
# No need to compact the queue at this point, because the code that
100
# calls this would have already triggered it based on queue length
98
102
def __setitem__(self, key, value):
99
103
"""Add a value to the cache, there will be no cleanup function."""
127
131
def _remove(self, key):
128
132
"""Remove an entry, making sure to maintain the invariants."""
129
cleanup = self._cleanup.pop(key)
133
cleanup = self._cleanup.pop(key, None)
130
134
val = self._cache.pop(key)
131
135
if cleanup is not None:
132
136
cleanup(key, val)
150
154
while self._cache:
151
155
self._remove_lru()
157
def resize(self, max_cache, after_cleanup_count=None):
158
"""Change the number of entries that will be cached."""
159
self._update_max_cache(max_cache,
160
after_cleanup_count=after_cleanup_count)
162
def _update_max_cache(self, max_cache, after_cleanup_count=None):
163
self._max_cache = max_cache
164
if after_cleanup_count is None:
165
self._after_cleanup_count = self._max_cache * 8 / 10
167
self._after_cleanup_count = min(after_cleanup_count, self._max_cache)
169
self._compact_queue_length = 4*self._max_cache
170
if len(self._queue) > self._compact_queue_length:
171
self._compact_queue()
154
175
class LRUSizeCache(LRUCache):
155
176
"""An LRUCache that removes things based on the size of the values.
175
196
The function should take the form "compute_size(value) => integer".
176
197
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
199
self._value_size = 0
189
200
self._compute_size = compute_size
190
201
if compute_size is None:
191
202
self._compute_size = len
203
# This approximates that texts are > 0.5k in size. It only really
204
# effects when we clean up the queue, so we don't want it to be too
206
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
207
LRUCache.__init__(self, max_cache=max(int(max_size/512), 1))
193
209
def add(self, key, value, cleanup=None):
194
210
"""Add a new value to the cache.
229
246
"""Remove an entry, making sure to maintain the invariants."""
230
247
val = LRUCache._remove(self, key)
231
248
self._value_size -= self._compute_size(val)
250
def resize(self, max_size, after_cleanup_size=None):
251
"""Change the number of bytes that will be cached."""
252
self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
253
max_cache = max(int(max_size/512), 1)
254
self._update_max_cache(max_cache)
256
def _update_max_size(self, max_size, after_cleanup_size=None):
257
self._max_size = max_size
258
if after_cleanup_size is None:
259
self._after_cleanup_size = self._max_size * 8 / 10
261
self._after_cleanup_size = min(after_cleanup_size, self._max_size)
added
removed
bzrlib/lru_cache.py
