1
# Copyright (C) 2008 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
"""A simple first-in-first-out (FIFO) cache."""
19
from collections import deque
22
class FIFOCache(dict):
23
"""A class which manages a cache of entries, removing old ones."""
25
def __init__(self, max_cache=100, after_cleanup_count=None):
27
self._max_cache = max_cache
28
if after_cleanup_count is None:
29
self._after_cleanup_count = self._max_cache * 8 / 10
31
self._after_cleanup_count = min(after_cleanup_count,
33
self._cleanup = {} # map to cleanup functions when items are removed
34
self._queue = deque() # Track when things are accessed
36
def __setitem__(self, key, value):
37
"""Add a value to the cache, there will be no cleanup function."""
38
self.add(key, value, cleanup=None)
40
def __delitem__(self, key):
41
# Remove the key from an arbitrary location in the queue
42
self._queue.remove(key)
45
def add(self, key, value, cleanup=None):
46
"""Add a new value to the cache.
48
Also, if the entry is ever removed from the queue, call cleanup.
49
Passing it the key and value being removed.
51
:param key: The key to store it under
52
:param value: The object to store
53
:param cleanup: None or a function taking (key, value) to indicate
54
'value' should be cleaned up
57
# Remove the earlier reference to this key, adding it again bumps
58
# it to the end of the queue
60
self._queue.append(key)
61
dict.__setitem__(self, key, value)
62
if cleanup is not None:
63
self._cleanup[key] = cleanup
64
if len(self) > self._max_cache:
68
"""Clear the cache until it shrinks to the requested size.
70
This does not completely wipe the cache, just makes sure it is under
71
the after_cleanup_count.
73
# Make sure the cache is shrunk to the correct size
74
while len(self) > self._after_cleanup_count:
76
if len(self._queue) != len(self):
77
raise AssertionError('The length of the queue should always equal'
78
' the length of the dict. %s != %s'
79
% (len(self._queue), len(self)))
82
"""Clear out all of the cache."""
83
# Clean up in FIFO order
87
def _remove(self, key):
88
"""Remove an entry, making sure to call any cleanup function."""
89
cleanup = self._cleanup.pop(key, None)
90
# We override self.pop() because it doesn't play well with cleanup
92
val = dict.pop(self, key)
93
if cleanup is not None:
97
def _remove_oldest(self):
98
"""Remove the oldest entry."""
99
key = self._queue.popleft()
102
# raise NotImplementedError on dict functions that would mutate the cache
103
# which have not been properly implemented yet.
105
raise NotImplementedError(self.copy)
107
def pop(self, key, default=None):
108
# If there is a cleanup() function, than it is unclear what pop()
109
# should do. Specifically, we would have to call the cleanup on the
110
# value before we return it, which should cause whatever resources were
111
# allocated to be removed, which makes the return value fairly useless.
112
# So instead, we just don't implement it.
113
raise NotImplementedError(self.pop)
117
raise NotImplementedError(self.popitem)
119
def setdefault(self, key, defaultval=None):
120
"""similar to dict.setdefault"""
123
self[key] = defaultval
126
def update(self, *args, **kwargs):
127
"""Similar to dict.update()"""
130
if isinstance(arg, dict):
131
for key, val in arg.iteritems():
134
for key, val in args[0]:
137
raise TypeError('update expected at most 1 argument, got %d'
140
for key, val in kwargs.iteritems():
144
class FIFOSizeCache(FIFOCache):
145
"""An FIFOCache that removes things based on the size of the values.
147
This differs in that it doesn't care how many actual items there are,
148
it restricts the cache to be cleaned based on the size of the data.
151
def __init__(self, max_size=1024*1024, after_cleanup_size=None,
153
"""Create a new FIFOSizeCache.
155
:param max_size: The max number of bytes to store before we start
156
clearing out entries.
157
:param after_cleanup_size: After cleaning up, shrink everything to this
158
size (defaults to 80% of max_size).
159
:param compute_size: A function to compute the size of a value. If
160
not supplied we default to 'len'.
162
# Arbitrary, we won't really be using the value anyway.
163
FIFOCache.__init__(self, max_cache=max_size)
164
self._max_size = max_size
165
if after_cleanup_size is None:
166
self._after_cleanup_size = self._max_size * 8 / 10
168
self._after_cleanup_size = min(after_cleanup_size, self._max_size)
171
self._compute_size = compute_size
172
if compute_size is None:
173
self._compute_size = len
175
def add(self, key, value, cleanup=None):
176
"""Add a new value to the cache.
178
Also, if the entry is ever removed from the queue, call cleanup.
179
Passing it the key and value being removed.
181
:param key: The key to store it under
182
:param value: The object to store, this value by itself is >=
183
after_cleanup_size, then we will not store it at all.
184
:param cleanup: None or a function taking (key, value) to indicate
185
'value' sohuld be cleaned up.
187
# Even if the new value won't be stored, we need to remove the old
190
# Remove the earlier reference to this key, adding it again bumps
191
# it to the end of the queue
193
value_len = self._compute_size(value)
194
if value_len >= self._after_cleanup_size:
196
self._queue.append(key)
197
dict.__setitem__(self, key, value)
198
if cleanup is not None:
199
self._cleanup[key] = cleanup
200
self._value_size += value_len
201
if self._value_size > self._max_size:
206
"""Clear the cache until it shrinks to the requested size.
208
This does not completely wipe the cache, just makes sure it is under
209
the after_cleanup_size.
211
# Make sure the cache is shrunk to the correct size
212
while self._value_size > self._after_cleanup_size:
213
self._remove_oldest()
215
def _remove(self, key):
216
"""Remove an entry, making sure to maintain the invariants."""
217
val = FIFOCache._remove(self, key)
218
self._value_size -= self._compute_size(val)
added
removed
bzrlib/fifo_cache.py
