~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: Martin Pool
  • Date: 2009-07-10 07:14:02 UTC
  • mto: (4525.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4526.
  • Revision ID: mbp@sourcefrog.net-20090710071402-dga5lhvdup5jeere
Rename remaining *_implementations tests

Show diffs side-by-side

added added

removed removed

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