/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: Gustav Hartvigsson
  • Date: 2021-01-09 21:36:27 UTC
  • Revision ID: gustav.hartvigsson@gmail.com-20210109213627-h1xwcutzy9m7a99b
Added 'Case Preserving Working Tree Use Cases' from Canonical Wiki

* Addod a page from the Canonical Bazaar wiki
  with information on the scmeatics of case
  perserving filesystems an a case insensitive
  filesystem works.
  
  * Needs re-work, but this will do as it is the
    same inforamoton as what was on the linked
    page in the currint documentation.

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()