← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: Launchpad Translations on behalf of bzr-core
  • Date: 2012-12-17 04:30:37 UTC
  • mto: (6581.1.1 trunk)
  • mto: This revision was merged to the branch mainline in revision 6582.
  • Revision ID: launchpad_translations_on_behalf_of_bzr-core-20121217043037-gdkzkow6s9fsa4o0
Launchpad automatic translations update.

Show diffs side-by-side

added added

removed removed

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