/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/lru_cache.py

  • Committer: John Arbash Meinel
  • Date: 2006-04-25 15:05:42 UTC
  • mfrom: (1185.85.85 bzr-encoding)
  • mto: This revision was merged to the branch mainline in revision 1752.
  • Revision ID: john@arbash-meinel.com-20060425150542-c7b518dca9928691
[merge] the old bzr-encoding changes, reparenting them on bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/lru_cache.py
1
 
# Copyright (C) 2006, 2008, 2009 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 least-recently-used (LRU) cache."""
18
 
 
19
 
from __future__ import absolute_import, division
20
 
 
21
 
from . import (
22
 
    trace,
23
 
    )
24
 
from .sixish import (
25
 
    viewitems,
26
 
    viewkeys,
27
 
    )
28
 
 
29
 
 
30
 
_null_key = object()
31
 
 
32
 
 
33
 
class _LRUNode(object):
34
 
    """This maintains the linked-list which is the lru internals."""
35
 
 
36
 
    __slots__ = ('prev', 'next_key', 'key', 'value')
37
 
 
38
 
    def __init__(self, key, value):
39
 
        self.prev = None
40
 
        self.next_key = _null_key
41
 
        self.key = key
42
 
        self.value = value
43
 
 
44
 
    def __repr__(self):
45
 
        if self.prev is None:
46
 
            prev_key = None
47
 
        else:
48
 
            prev_key = self.prev.key
49
 
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
50
 
                                     self.next_key, prev_key)
51
 
 
52
 
 
53
 
class LRUCache(object):
54
 
    """A class which manages a cache of entries, removing unused ones."""
55
 
 
56
 
    def __init__(self, max_cache=100, after_cleanup_count=None):
57
 
        self._cache = {}
58
 
        # The "HEAD" of the lru linked list
59
 
        self._most_recently_used = None
60
 
        # The "TAIL" of the lru linked list
61
 
        self._least_recently_used = None
62
 
        self._update_max_cache(max_cache, after_cleanup_count)
63
 
 
64
 
    def __contains__(self, key):
65
 
        return key in self._cache
66
 
 
67
 
    def __getitem__(self, key):
68
 
        cache = self._cache
69
 
        node = cache[key]
70
 
        # Inlined from _record_access to decrease the overhead of __getitem__
71
 
        # We also have more knowledge about structure if __getitem__ is
72
 
        # succeeding, then we know that self._most_recently_used must not be
73
 
        # None, etc.
74
 
        mru = self._most_recently_used
75
 
        if node is mru:
76
 
            # Nothing to do, this node is already at the head of the queue
77
 
            return node.value
78
 
        # Remove this node from the old location
79
 
        node_prev = node.prev
80
 
        next_key = node.next_key
81
 
        # benchmarking shows that the lookup of _null_key in globals is faster
82
 
        # than the attribute lookup for (node is self._least_recently_used)
83
 
        if next_key is _null_key:
84
 
            # 'node' is the _least_recently_used, because it doesn't have a
85
 
            # 'next' item. So move the current lru to the previous node.
86
 
            self._least_recently_used = node_prev
87
 
        else:
88
 
            node_next = cache[next_key]
89
 
            node_next.prev = node_prev
90
 
        node_prev.next_key = next_key
91
 
        # Insert this node at the front of the list
92
 
        node.next_key = mru.key
93
 
        mru.prev = node
94
 
        self._most_recently_used = node
95
 
        node.prev = None
96
 
        return node.value
97
 
 
98
 
    def __len__(self):
99
 
        return len(self._cache)
100
 
 
101
 
    def __setitem__(self, key, value):
102
 
        """Add a new value to the cache"""
103
 
        if key is _null_key:
104
 
            raise ValueError('cannot use _null_key as a key')
105
 
        if key in self._cache:
106
 
            node = self._cache[key]
107
 
            node.value = value
108
 
            self._record_access(node)
109
 
        else:
110
 
            node = _LRUNode(key, value)
111
 
            self._cache[key] = node
112
 
            self._record_access(node)
113
 
 
114
 
        if len(self._cache) > self._max_cache:
115
 
            # Trigger the cleanup
116
 
            self.cleanup()
117
 
 
118
 
    def cache_size(self):
119
 
        """Get the number of entries we will cache."""
120
 
        return self._max_cache
121
 
 
122
 
    def get(self, key, default=None):
123
 
        node = self._cache.get(key, None)
124
 
        if node is None:
125
 
            return default
126
 
        self._record_access(node)
127
 
        return node.value
128
 
 
129
 
    def keys(self):
130
 
        """Get the list of keys currently cached.
131
 
 
132
 
        Note that values returned here may not be available by the time you
133
 
        request them later. This is simply meant as a peak into the current
134
 
        state.
135
 
 
136
 
        :return: An unordered list of keys that are currently cached.
137
 
        """
138
 
        # GZ 2016-06-04: Maybe just make this return the view?
139
 
        return list(viewkeys(self._cache))
140
 
 
141
 
    def as_dict(self):
142
 
        """Get a new dict with the same key:value pairs as the cache"""
143
 
        return dict((k, n.value) for k, n in viewitems(self._cache))
144
 
 
145
 
    def cleanup(self):
146
 
        """Clear the cache until it shrinks to the requested size.
147
 
 
148
 
        This does not completely wipe the cache, just makes sure it is under
149
 
        the after_cleanup_count.
150
 
        """
151
 
        # Make sure the cache is shrunk to the correct size
152
 
        while len(self._cache) > self._after_cleanup_count:
153
 
            self._remove_lru()
154
 
 
155
 
    def _record_access(self, node):
156
 
        """Record that key was accessed."""
157
 
        # Move 'node' to the front of the queue
158
 
        if self._most_recently_used is None:
159
 
            self._most_recently_used = node
160
 
            self._least_recently_used = node
161
 
            return
162
 
        elif node is self._most_recently_used:
163
 
            # Nothing to do, this node is already at the head of the queue
164
 
            return
165
 
        # We've taken care of the tail pointer, remove the node, and insert it
166
 
        # at the front
167
 
        # REMOVE
168
 
        if node is self._least_recently_used:
169
 
            self._least_recently_used = node.prev
170
 
        if node.prev is not None:
171
 
            node.prev.next_key = node.next_key
172
 
        if node.next_key is not _null_key:
173
 
            node_next = self._cache[node.next_key]
174
 
            node_next.prev = node.prev
175
 
        # INSERT
176
 
        node.next_key = self._most_recently_used.key
177
 
        self._most_recently_used.prev = node
178
 
        self._most_recently_used = node
179
 
        node.prev = None
180
 
 
181
 
    def _remove_node(self, node):
182
 
        if node is self._least_recently_used:
183
 
            self._least_recently_used = node.prev
184
 
        self._cache.pop(node.key)
185
 
        # If we have removed all entries, remove the head pointer as well
186
 
        if self._least_recently_used is None:
187
 
            self._most_recently_used = None
188
 
        if node.prev is not None:
189
 
            node.prev.next_key = node.next_key
190
 
        if node.next_key is not _null_key:
191
 
            node_next = self._cache[node.next_key]
192
 
            node_next.prev = node.prev
193
 
        # And remove this node's pointers
194
 
        node.prev = None
195
 
        node.next_key = _null_key
196
 
 
197
 
    def _remove_lru(self):
198
 
        """Remove one entry from the lru, and handle consequences.
199
 
 
200
 
        If there are no more references to the lru, then this entry should be
201
 
        removed from the cache.
202
 
        """
203
 
        self._remove_node(self._least_recently_used)
204
 
 
205
 
    def clear(self):
206
 
        """Clear out all of the cache."""
207
 
        # Clean up in LRU order
208
 
        while self._cache:
209
 
            self._remove_lru()
210
 
 
211
 
    def resize(self, max_cache, after_cleanup_count=None):
212
 
        """Change the number of entries that will be cached."""
213
 
        self._update_max_cache(max_cache,
214
 
                               after_cleanup_count=after_cleanup_count)
215
 
 
216
 
    def _update_max_cache(self, max_cache, after_cleanup_count=None):
217
 
        self._max_cache = max_cache
218
 
        if after_cleanup_count is None:
219
 
            self._after_cleanup_count = self._max_cache * 8 // 10
220
 
        else:
221
 
            self._after_cleanup_count = min(after_cleanup_count,
222
 
                                            self._max_cache)
223
 
        self.cleanup()
224
 
 
225
 
 
226
 
class LRUSizeCache(LRUCache):
227
 
    """An LRUCache that removes things based on the size of the values.
228
 
 
229
 
    This differs in that it doesn't care how many actual items there are,
230
 
    it just restricts the cache to be cleaned up after so much data is stored.
231
 
 
232
 
    The size of items added will be computed using compute_size(value), which
233
 
    defaults to len() if not supplied.
234
 
    """
235
 
 
236
 
    def __init__(self, max_size=1024 * 1024, after_cleanup_size=None,
237
 
                 compute_size=None):
238
 
        """Create a new LRUSizeCache.
239
 
 
240
 
        :param max_size: The max number of bytes to store before we start
241
 
            clearing out entries.
242
 
        :param after_cleanup_size: After cleaning up, shrink everything to this
243
 
            size.
244
 
        :param compute_size: A function to compute the size of the values. We
245
 
            use a function here, so that you can pass 'len' if you are just
246
 
            using simple strings, or a more complex function if you are using
247
 
            something like a list of strings, or even a custom object.
248
 
            The function should take the form "compute_size(value) => integer".
249
 
            If not supplied, it defaults to 'len()'
250
 
        """
251
 
        self._value_size = 0
252
 
        self._compute_size = compute_size
253
 
        if compute_size is None:
254
 
            self._compute_size = len
255
 
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
256
 
        LRUCache.__init__(self, max_cache=max(int(max_size // 512), 1))
257
 
 
258
 
    def __setitem__(self, key, value):
259
 
        """Add a new value to the cache"""
260
 
        if key is _null_key:
261
 
            raise ValueError('cannot use _null_key as a key')
262
 
        node = self._cache.get(key, None)
263
 
        value_len = self._compute_size(value)
264
 
        if value_len >= self._after_cleanup_size:
265
 
            # The new value is 'too big to fit', as it would fill up/overflow
266
 
            # the cache all by itself
267
 
            trace.mutter('Adding the key %r to an LRUSizeCache failed.'
268
 
                         ' value %d is too big to fit in a the cache'
269
 
                         ' with size %d %d', key, value_len,
270
 
                         self._after_cleanup_size, self._max_size)
271
 
            if node is not None:
272
 
                # We won't be replacing the old node, so just remove it
273
 
                self._remove_node(node)
274
 
            return
275
 
        if node is None:
276
 
            node = _LRUNode(key, value)
277
 
            self._cache[key] = node
278
 
        else:
279
 
            self._value_size -= self._compute_size(node.value)
280
 
        self._value_size += value_len
281
 
        self._record_access(node)
282
 
 
283
 
        if self._value_size > self._max_size:
284
 
            # Time to cleanup
285
 
            self.cleanup()
286
 
 
287
 
    def cleanup(self):
288
 
        """Clear the cache until it shrinks to the requested size.
289
 
 
290
 
        This does not completely wipe the cache, just makes sure it is under
291
 
        the after_cleanup_size.
292
 
        """
293
 
        # Make sure the cache is shrunk to the correct size
294
 
        while self._value_size > self._after_cleanup_size:
295
 
            self._remove_lru()
296
 
 
297
 
    def _remove_node(self, node):
298
 
        self._value_size -= self._compute_size(node.value)
299
 
        LRUCache._remove_node(self, node)
300
 
 
301
 
    def resize(self, max_size, after_cleanup_size=None):
302
 
        """Change the number of bytes that will be cached."""
303
 
        self._update_max_size(max_size, after_cleanup_size=after_cleanup_size)
304
 
        max_cache = max(int(max_size // 512), 1)
305
 
        self._update_max_cache(max_cache)
306
 
 
307
 
    def _update_max_size(self, max_size, after_cleanup_size=None):
308
 
        self._max_size = max_size
309
 
        if after_cleanup_size is None:
310
 
            self._after_cleanup_size = self._max_size * 8 // 10
311
 
        else:
312
 
            self._after_cleanup_size = min(after_cleanup_size, self._max_size)