← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: Jonathan Lange
  • Date: 2009-05-01 06:42:30 UTC
  • mto: This revision was merged to the branch mainline in revision 4320.
  • Revision ID: jml@canonical.com-20090501064230-kyk7v49xt8cevd25
Remove InstallFailed, it's not needed anymore.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
1
 
# Copyright (C) 2006, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2006, 2008 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
17
17
"""A simple least-recently-used (LRU) cache."""
18
18
 
19
19
from bzrlib import (
 
20
    symbol_versioning,
20
21
    trace,
21
22
    )
22
23
 
23
 
_null_key = object()
24
24
 
25
25
class _LRUNode(object):
26
26
    """This maintains the linked-list which is the lru internals."""
27
27
 
28
 
    __slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
 
28
    __slots__ = ('prev', 'next', 'key', 'value', 'cleanup', 'size')
29
29
 
30
30
    def __init__(self, key, value, cleanup=None):
31
31
        self.prev = None
32
 
        self.next_key = _null_key
 
32
        self.next = None
33
33
        self.key = key
34
34
        self.value = value
35
35
        self.cleanup = cleanup
39
39
        self.size = None
40
40
 
41
41
    def __repr__(self):
 
42
        if self.next is None:
 
43
            next = None
 
44
        else:
 
45
            next = self.next.key
42
46
        if self.prev is None:
43
 
            prev_key = None
 
47
            prev = None
44
48
        else:
45
 
            prev_key = self.prev.key
 
49
            prev = self.prev.key
46
50
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
47
 
                                     self.next_key, prev_key)
 
51
                                     next, prev)
48
52
 
49
53
    def run_cleanup(self):
50
 
        try:
51
 
            if self.cleanup is not None:
52
 
                self.cleanup(self.key, self.value)
53
 
        finally:
54
 
            # cleanup might raise an exception, but we want to make sure
55
 
            # to break refcycles, etc
56
 
            self.cleanup = None
57
 
            self.value = None
 
54
        if self.cleanup is not None:
 
55
            self.cleanup(self.key, self.value)
 
56
        self.cleanup = None
 
57
        # Just make sure to break any refcycles, etc
 
58
        self.value = None
58
59
 
59
60
 
60
61
class LRUCache(object):
61
62
    """A class which manages a cache of entries, removing unused ones."""
62
63
 
63
 
    def __init__(self, max_cache=100, after_cleanup_count=None):
 
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
64
72
        self._cache = {}
65
73
        # The "HEAD" of the lru linked list
66
74
        self._most_recently_used = None
67
75
        # The "TAIL" of the lru linked list
68
 
        self._least_recently_used = None
 
76
        self._last_recently_used = None
69
77
        self._update_max_cache(max_cache, after_cleanup_count)
70
78
 
71
79
    def __contains__(self, key):
72
80
        return key in self._cache
73
81
 
74
82
    def __getitem__(self, key):
75
 
        cache = self._cache
76
 
        node = cache[key]
 
83
        node = self._cache[key]
77
84
        # Inlined from _record_access to decrease the overhead of __getitem__
78
85
        # We also have more knowledge about structure if __getitem__ is
79
86
        # succeeding, then we know that self._most_recently_used must not be
82
89
        if node is mru:
83
90
            # Nothing to do, this node is already at the head of the queue
84
91
            return node.value
 
92
        elif node is self._last_recently_used:
 
93
            self._last_recently_used = node.prev
85
94
        # Remove this node from the old location
86
95
        node_prev = node.prev
87
 
        next_key = node.next_key
88
 
        # benchmarking shows that the lookup of _null_key in globals is faster
89
 
        # than the attribute lookup for (node is self._least_recently_used)
90
 
        if next_key is _null_key:
91
 
            # 'node' is the _least_recently_used, because it doesn't have a
92
 
            # 'next' item. So move the current lru to the previous node.
93
 
            self._least_recently_used = node_prev
94
 
        else:
95
 
            node_next = cache[next_key]
 
96
        node_next = node.next
 
97
        if node_prev is not None:
 
98
            node_prev.next = node_next
 
99
        if node_next is not None:
96
100
            node_next.prev = node_prev
97
 
        node_prev.next_key = next_key
98
 
        # Insert this node at the front of the list
99
 
        node.next_key = mru.key
 
101
        # Insert this node to the front of the list
 
102
        node.next = mru
100
103
        mru.prev = node
101
104
        self._most_recently_used = node
102
105
        node.prev = None
114
117
                                     ' supposed to have a previous entry'
115
118
                                     ' %s' % (node,))
116
119
        while node is not None:
117
 
            if node.next_key is _null_key:
118
 
                if node is not self._least_recently_used:
 
120
            if node.next is None:
 
121
                if node is not self._last_recently_used:
119
122
                    raise AssertionError('only the last node should have'
120
123
                                         ' no next value: %s' % (node,))
121
 
                node_next = None
122
124
            else:
123
 
                node_next = self._cache[node.next_key]
124
 
                if node_next.prev is not node:
 
125
                if node.next.prev is not node:
125
126
                    raise AssertionError('inconsistency found, node.next.prev'
126
127
                                         ' != node: %s' % (node,))
127
128
            if node.prev is None:
130
131
                                         ' not have a previous node: %s'
131
132
                                         % (node,))
132
133
            else:
133
 
                if node.prev.next_key != node.key:
 
134
                if node.prev.next is not node:
134
135
                    raise AssertionError('inconsistency found, node.prev.next'
135
136
                                         ' != node: %s' % (node,))
136
137
            yield node
137
 
            node = node_next
 
138
            node = node.next
138
139
 
139
140
    def add(self, key, value, cleanup=None):
140
141
        """Add a new value to the cache.
147
148
        :param cleanup: None or a function taking (key, value) to indicate
148
149
                        'value' should be cleaned up.
149
150
        """
150
 
        if key is _null_key:
151
 
            raise ValueError('cannot use _null_key as a key')
152
151
        if key in self._cache:
153
152
            node = self._cache[key]
154
 
            try:
155
 
                node.run_cleanup()
156
 
            finally:
157
 
                # Maintain the LRU properties, even if cleanup raises an
158
 
                # exception
159
 
                node.value = value
160
 
                node.cleanup = cleanup
161
 
                self._record_access(node)
 
153
            node.run_cleanup()
 
154
            node.value = value
 
155
            node.cleanup = cleanup
162
156
        else:
163
157
            node = _LRUNode(key, value, cleanup=cleanup)
164
158
            self._cache[key] = node
165
 
            self._record_access(node)
 
159
        self._record_access(node)
166
160
 
167
161
        if len(self._cache) > self._max_cache:
168
162
            # Trigger the cleanup
213
207
        # Move 'node' to the front of the queue
214
208
        if self._most_recently_used is None:
215
209
            self._most_recently_used = node
216
 
            self._least_recently_used = node
 
210
            self._last_recently_used = node
217
211
            return
218
212
        elif node is self._most_recently_used:
219
213
            # Nothing to do, this node is already at the head of the queue
220
214
            return
 
215
        elif node is self._last_recently_used:
 
216
            self._last_recently_used = node.prev
221
217
        # We've taken care of the tail pointer, remove the node, and insert it
222
218
        # at the front
223
219
        # REMOVE
224
 
        if node is self._least_recently_used:
225
 
            self._least_recently_used = node.prev
226
220
        if node.prev is not None:
227
 
            node.prev.next_key = node.next_key
228
 
        if node.next_key is not _null_key:
229
 
            node_next = self._cache[node.next_key]
230
 
            node_next.prev = node.prev
 
221
            node.prev.next = node.next
 
222
        if node.next is not None:
 
223
            node.next.prev = node.prev
231
224
        # INSERT
232
 
        node.next_key = self._most_recently_used.key
233
 
        self._most_recently_used.prev = node
 
225
        node.next = self._most_recently_used
234
226
        self._most_recently_used = node
 
227
        node.next.prev = node
235
228
        node.prev = None
236
229
 
237
230
    def _remove_node(self, node):
238
 
        if node is self._least_recently_used:
239
 
            self._least_recently_used = node.prev
 
231
        if node is self._last_recently_used:
 
232
            self._last_recently_used = node.prev
240
233
        self._cache.pop(node.key)
241
234
        # If we have removed all entries, remove the head pointer as well
242
 
        if self._least_recently_used is None:
 
235
        if self._last_recently_used is None:
243
236
            self._most_recently_used = None
244
 
        try:
245
 
            node.run_cleanup()
246
 
        finally:
247
 
            # cleanup might raise an exception, but we want to make sure to
248
 
            # maintain the linked list
249
 
            if node.prev is not None:
250
 
                node.prev.next_key = node.next_key
251
 
            if node.next_key is not _null_key:
252
 
                node_next = self._cache[node.next_key]
253
 
                node_next.prev = node.prev
254
 
            # And remove this node's pointers
255
 
            node.prev = None
256
 
            node.next_key = _null_key
 
237
        node.run_cleanup()
 
238
        # Now remove this node from the linked list
 
239
        if node.prev is not None:
 
240
            node.prev.next = node.next
 
241
        if node.next is not None:
 
242
            node.next.prev = node.prev
 
243
        # And remove this node's pointers
 
244
        node.prev = None
 
245
        node.next = None
257
246
 
258
247
    def _remove_lru(self):
259
248
        """Remove one entry from the lru, and handle consequences.
261
250
        If there are no more references to the lru, then this entry should be
262
251
        removed from the cache.
263
252
        """
264
 
        self._remove_node(self._least_recently_used)
 
253
        self._remove_node(self._last_recently_used)
265
254
 
266
255
    def clear(self):
267
256
        """Clear out all of the cache."""
327
316
        :param cleanup: None or a function taking (key, value) to indicate
328
317
                        'value' should be cleaned up.
329
318
        """
330
 
        if key is _null_key:
331
 
            raise ValueError('cannot use _null_key as a key')
332
319
        node = self._cache.get(key, None)
333
320
        value_len = self._compute_size(value)
334
321
        if value_len >= self._after_cleanup_size: