/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: Jelmer Vernooij
  • Date: 2020-02-07 02:14:30 UTC
  • mto: This revision was merged to the branch mainline in revision 7492.
  • Revision ID: jelmer@jelmer.uk-20200207021430-m49iq3x4x8xlib6x
Drop python2 support.

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