/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/fifo_cache.py

  • Committer: Robert Collins
  • Date: 2005-12-24 02:20:45 UTC
  • mto: (1185.50.57 bzr-jam-integration)
  • mto: This revision was merged to the branch mainline in revision 1550.
  • Revision ID: robertc@robertcollins.net-20051224022045-14efc8dfa0e1a4e9
Start tests for api usage.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/fifo_cache.py
1
 
# Copyright (C) 2008 Canonical Ltd
2
 
#
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.
7
 
#
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.
12
 
#
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
16
 
 
17
 
"""A simple first-in-first-out (FIFO) cache."""
18
 
 
19
 
from collections import deque
20
 
 
21
 
 
22
 
class FIFOCache(dict):
23
 
    """A class which manages a cache of entries, removing old ones."""
24
 
 
25
 
    def __init__(self, max_cache=100, after_cleanup_count=None):
26
 
        dict.__init__(self)
27
 
        self._max_cache = max_cache
28
 
        if after_cleanup_count is None:
29
 
            self._after_cleanup_count = self._max_cache * 8 // 10
30
 
        else:
31
 
            self._after_cleanup_count = min(after_cleanup_count,
32
 
                                            self._max_cache)
33
 
        self._cleanup = {}  # map to cleanup functions when items are removed
34
 
        self._queue = deque()  # Track when things are accessed
35
 
 
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)
39
 
 
40
 
    def __delitem__(self, key):
41
 
        # Remove the key from an arbitrary location in the queue
42
 
        self._queue.remove(key)
43
 
        self._remove(key)
44
 
 
45
 
    def add(self, key, value, cleanup=None):
46
 
        """Add a new value to the cache.
47
 
 
48
 
        Also, if the entry is ever removed from the queue, call cleanup.
49
 
        Passing it the key and value being removed.
50
 
 
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
55
 
        """
56
 
        if key in self:
57
 
            # Remove the earlier reference to this key, adding it again bumps
58
 
            # it to the end of the queue
59
 
            del self[key]
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:
65
 
            self.cleanup()
66
 
 
67
 
    def cache_size(self):
68
 
        """Get the number of entries we will cache."""
69
 
        return self._max_cache
70
 
 
71
 
    def cleanup(self):
72
 
        """Clear the cache until it shrinks to the requested size.
73
 
 
74
 
        This does not completely wipe the cache, just makes sure it is under
75
 
        the after_cleanup_count.
76
 
        """
77
 
        # Make sure the cache is shrunk to the correct size
78
 
        while len(self) > self._after_cleanup_count:
79
 
            self._remove_oldest()
80
 
        if len(self._queue) != len(self):
81
 
            raise AssertionError('The length of the queue should always equal'
82
 
                                 ' the length of the dict. %s != %s'
83
 
                                 % (len(self._queue), len(self)))
84
 
 
85
 
    def clear(self):
86
 
        """Clear out all of the cache."""
87
 
        # Clean up in FIFO order
88
 
        while self:
89
 
            self._remove_oldest()
90
 
 
91
 
    def _remove(self, key):
92
 
        """Remove an entry, making sure to call any cleanup function."""
93
 
        cleanup = self._cleanup.pop(key, None)
94
 
        # We override self.pop() because it doesn't play well with cleanup
95
 
        # functions.
96
 
        val = dict.pop(self, key)
97
 
        if cleanup is not None:
98
 
            cleanup(key, val)
99
 
        return val
100
 
 
101
 
    def _remove_oldest(self):
102
 
        """Remove the oldest entry."""
103
 
        key = self._queue.popleft()
104
 
        self._remove(key)
105
 
 
106
 
    def resize(self, max_cache, after_cleanup_count=None):
107
 
        """Increase/decrease the number of cached entries.
108
 
 
109
 
        :param max_cache: The maximum number of entries to cache.
110
 
        :param after_cleanup_count: After cleanup, we should have at most this
111
 
            many entries. This defaults to 80% of max_cache.
112
 
        """
113
 
        self._max_cache = max_cache
114
 
        if after_cleanup_count is None:
115
 
            self._after_cleanup_count = max_cache * 8 // 10
116
 
        else:
117
 
            self._after_cleanup_count = min(max_cache, after_cleanup_count)
118
 
        if len(self) > self._max_cache:
119
 
            self.cleanup()
120
 
 
121
 
    # raise NotImplementedError on dict functions that would mutate the cache
122
 
    # which have not been properly implemented yet.
123
 
    def copy(self):
124
 
        raise NotImplementedError(self.copy)
125
 
 
126
 
    def pop(self, key, default=None):
127
 
        # If there is a cleanup() function, than it is unclear what pop()
128
 
        # should do. Specifically, we would have to call the cleanup on the
129
 
        # value before we return it, which should cause whatever resources were
130
 
        # allocated to be removed, which makes the return value fairly useless.
131
 
        # So instead, we just don't implement it.
132
 
        raise NotImplementedError(self.pop)
133
 
 
134
 
    def popitem(self):
135
 
        # See pop()
136
 
        raise NotImplementedError(self.popitem)
137
 
 
138
 
    def setdefault(self, key, defaultval=None):
139
 
        """similar to dict.setdefault"""
140
 
        if key in self:
141
 
            return self[key]
142
 
        self[key] = defaultval
143
 
        return defaultval
144
 
 
145
 
    def update(self, *args, **kwargs):
146
 
        """Similar to dict.update()"""
147
 
        if len(args) == 1:
148
 
            arg = args[0]
149
 
            if isinstance(arg, dict):
150
 
                for key in arg:
151
 
                    self.add(key, arg[key])
152
 
            else:
153
 
                for key, val in args[0]:
154
 
                    self.add(key, val)
155
 
        elif len(args) > 1:
156
 
            raise TypeError('update expected at most 1 argument, got %d'
157
 
                            % len(args))
158
 
        if kwargs:
159
 
            for key in kwargs:
160
 
                self.add(key, kwargs[key])
161
 
 
162
 
 
163
 
class FIFOSizeCache(FIFOCache):
164
 
    """An FIFOCache that removes things based on the size of the values.
165
 
 
166
 
    This differs in that it doesn't care how many actual items there are,
167
 
    it restricts the cache to be cleaned based on the size of the data.
168
 
    """
169
 
 
170
 
    def __init__(self, max_size=1024 * 1024, after_cleanup_size=None,
171
 
                 compute_size=None):
172
 
        """Create a new FIFOSizeCache.
173
 
 
174
 
        :param max_size: The max number of bytes to store before we start
175
 
            clearing out entries.
176
 
        :param after_cleanup_size: After cleaning up, shrink everything to this
177
 
            size (defaults to 80% of max_size).
178
 
        :param compute_size: A function to compute the size of a value. If
179
 
            not supplied we default to 'len'.
180
 
        """
181
 
        # Arbitrary, we won't really be using the value anyway.
182
 
        FIFOCache.__init__(self, max_cache=max_size)
183
 
        self._max_size = max_size
184
 
        if after_cleanup_size is None:
185
 
            self._after_cleanup_size = self._max_size * 8 // 10
186
 
        else:
187
 
            self._after_cleanup_size = min(after_cleanup_size, self._max_size)
188
 
 
189
 
        self._value_size = 0
190
 
        self._compute_size = compute_size
191
 
        if compute_size is None:
192
 
            self._compute_size = len
193
 
 
194
 
    def add(self, key, value, cleanup=None):
195
 
        """Add a new value to the cache.
196
 
 
197
 
        Also, if the entry is ever removed from the queue, call cleanup.
198
 
        Passing it the key and value being removed.
199
 
 
200
 
        :param key: The key to store it under
201
 
        :param value: The object to store, this value by itself is >=
202
 
            after_cleanup_size, then we will not store it at all.
203
 
        :param cleanup: None or a function taking (key, value) to indicate
204
 
                        'value' sohuld be cleaned up.
205
 
        """
206
 
        # Even if the new value won't be stored, we need to remove the old
207
 
        # value
208
 
        if key in self:
209
 
            # Remove the earlier reference to this key, adding it again bumps
210
 
            # it to the end of the queue
211
 
            del self[key]
212
 
        value_len = self._compute_size(value)
213
 
        if value_len >= self._after_cleanup_size:
214
 
            return
215
 
        self._queue.append(key)
216
 
        dict.__setitem__(self, key, value)
217
 
        if cleanup is not None:
218
 
            self._cleanup[key] = cleanup
219
 
        self._value_size += value_len
220
 
        if self._value_size > self._max_size:
221
 
            # Time to cleanup
222
 
            self.cleanup()
223
 
 
224
 
    def cache_size(self):
225
 
        """Get the number of bytes we will cache."""
226
 
        return self._max_size
227
 
 
228
 
    def cleanup(self):
229
 
        """Clear the cache until it shrinks to the requested size.
230
 
 
231
 
        This does not completely wipe the cache, just makes sure it is under
232
 
        the after_cleanup_size.
233
 
        """
234
 
        # Make sure the cache is shrunk to the correct size
235
 
        while self._value_size > self._after_cleanup_size:
236
 
            self._remove_oldest()
237
 
 
238
 
    def _remove(self, key):
239
 
        """Remove an entry, making sure to maintain the invariants."""
240
 
        val = FIFOCache._remove(self, key)
241
 
        self._value_size -= self._compute_size(val)
242
 
        return val
243
 
 
244
 
    def resize(self, max_size, after_cleanup_size=None):
245
 
        """Increase/decrease the amount of cached data.
246
 
 
247
 
        :param max_size: The maximum number of bytes to cache.
248
 
        :param after_cleanup_size: After cleanup, we should have at most this
249
 
            many bytes cached. This defaults to 80% of max_size.
250
 
        """
251
 
        FIFOCache.resize(self, max_size)
252
 
        self._max_size = max_size
253
 
        if after_cleanup_size is None:
254
 
            self._after_cleanup_size = max_size * 8 // 10
255
 
        else:
256
 
            self._after_cleanup_size = min(max_size, after_cleanup_size)
257
 
        if self._value_size > self._max_size:
258
 
            self.cleanup()