← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: Joe Julian
  • Date: 2010-01-10 02:25:31 UTC
  • mto: (4634.119.7 2.0)
  • mto: This revision was merged to the branch mainline in revision 4959.
  • Revision ID: joe@julianfamily.org-20100110022531-wqk61rsagz8xsiga
https://launchpad.net/bugs/175839
Added MANIFEST.in to allow bdist_rpm to have all the required include files and tools. bdist_rpm will still fail to build correctly on some distributions due to a disttools bug http://bugs.python.org/issue644744

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
1
 
# Copyright (C) 2006, 2008 Canonical Ltd
 
1
# Copyright (C) 2006, 2008, 2009 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
21
21
    trace,
22
22
    )
23
23
 
 
24
_null_key = object()
24
25
 
25
26
class _LRUNode(object):
26
27
    """This maintains the linked-list which is the lru internals."""
27
28
 
28
 
    __slots__ = ('prev', 'next', 'key', 'value', 'cleanup', 'size')
 
29
    __slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
29
30
 
30
31
    def __init__(self, key, value, cleanup=None):
31
32
        self.prev = None
32
 
        self.next = None
 
33
        self.next_key = _null_key
33
34
        self.key = key
34
35
        self.value = value
35
36
        self.cleanup = cleanup
39
40
        self.size = None
40
41
 
41
42
    def __repr__(self):
42
 
        if self.next is None:
43
 
            next = None
44
 
        else:
45
 
            next = self.next.key
46
43
        if self.prev is None:
47
 
            prev = None
 
44
            prev_key = None
48
45
        else:
49
 
            prev = self.prev.key
 
46
            prev_key = self.prev.key
50
47
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
51
 
                                     next, prev)
 
48
                                     self.next_key, prev_key)
52
49
 
53
50
    def run_cleanup(self):
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
 
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
59
 
60
60
 
61
61
class LRUCache(object):
73
73
        # The "HEAD" of the lru linked list
74
74
        self._most_recently_used = None
75
75
        # The "TAIL" of the lru linked list
76
 
        self._last_recently_used = None
 
76
        self._least_recently_used = None
77
77
        self._update_max_cache(max_cache, after_cleanup_count)
78
78
 
79
79
    def __contains__(self, key):
80
80
        return key in self._cache
81
81
 
82
82
    def __getitem__(self, key):
83
 
        node = self._cache[key]
 
83
        cache = self._cache
 
84
        node = cache[key]
84
85
        # Inlined from _record_access to decrease the overhead of __getitem__
85
86
        # We also have more knowledge about structure if __getitem__ is
86
87
        # succeeding, then we know that self._most_recently_used must not be
89
90
        if node is mru:
90
91
            # Nothing to do, this node is already at the head of the queue
91
92
            return node.value
92
 
        elif node is self._last_recently_used:
93
 
            self._last_recently_used = node.prev
94
93
        # Remove this node from the old location
95
94
        node_prev = node.prev
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:
 
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]
100
104
            node_next.prev = node_prev
101
 
        # Insert this node to the front of the list
102
 
        node.next = mru
 
105
        node_prev.next_key = next_key
 
106
        # Insert this node at the front of the list
 
107
        node.next_key = mru.key
103
108
        mru.prev = node
104
109
        self._most_recently_used = node
105
110
        node.prev = None
117
122
                                     ' supposed to have a previous entry'
118
123
                                     ' %s' % (node,))
119
124
        while node is not None:
120
 
            if node.next is None:
121
 
                if node is not self._last_recently_used:
 
125
            if node.next_key is _null_key:
 
126
                if node is not self._least_recently_used:
122
127
                    raise AssertionError('only the last node should have'
123
128
                                         ' no next value: %s' % (node,))
 
129
                node_next = None
124
130
            else:
125
 
                if node.next.prev is not node:
 
131
                node_next = self._cache[node.next_key]
 
132
                if node_next.prev is not node:
126
133
                    raise AssertionError('inconsistency found, node.next.prev'
127
134
                                         ' != node: %s' % (node,))
128
135
            if node.prev is None:
131
138
                                         ' not have a previous node: %s'
132
139
                                         % (node,))
133
140
            else:
134
 
                if node.prev.next is not node:
 
141
                if node.prev.next_key != node.key:
135
142
                    raise AssertionError('inconsistency found, node.prev.next'
136
143
                                         ' != node: %s' % (node,))
137
144
            yield node
138
 
            node = node.next
 
145
            node = node_next
139
146
 
140
147
    def add(self, key, value, cleanup=None):
141
148
        """Add a new value to the cache.
148
155
        :param cleanup: None or a function taking (key, value) to indicate
149
156
                        'value' should be cleaned up.
150
157
        """
 
158
        if key is _null_key:
 
159
            raise ValueError('cannot use _null_key as a key')
151
160
        if key in self._cache:
152
161
            node = self._cache[key]
153
 
            node.run_cleanup()
154
 
            node.value = value
155
 
            node.cleanup = cleanup
 
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)
156
170
        else:
157
171
            node = _LRUNode(key, value, cleanup=cleanup)
158
172
            self._cache[key] = node
159
 
        self._record_access(node)
 
173
            self._record_access(node)
160
174
 
161
175
        if len(self._cache) > self._max_cache:
162
176
            # Trigger the cleanup
207
221
        # Move 'node' to the front of the queue
208
222
        if self._most_recently_used is None:
209
223
            self._most_recently_used = node
210
 
            self._last_recently_used = node
 
224
            self._least_recently_used = node
211
225
            return
212
226
        elif node is self._most_recently_used:
213
227
            # Nothing to do, this node is already at the head of the queue
214
228
            return
215
 
        elif node is self._last_recently_used:
216
 
            self._last_recently_used = node.prev
217
229
        # We've taken care of the tail pointer, remove the node, and insert it
218
230
        # at the front
219
231
        # REMOVE
 
232
        if node is self._least_recently_used:
 
233
            self._least_recently_used = node.prev
220
234
        if node.prev is not None:
221
 
            node.prev.next = node.next
222
 
        if node.next is not None:
223
 
            node.next.prev = node.prev
 
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
224
239
        # INSERT
225
 
        node.next = self._most_recently_used
 
240
        node.next_key = self._most_recently_used.key
 
241
        self._most_recently_used.prev = node
226
242
        self._most_recently_used = node
227
 
        node.next.prev = node
228
243
        node.prev = None
229
244
 
230
245
    def _remove_node(self, node):
231
 
        if node is self._last_recently_used:
232
 
            self._last_recently_used = node.prev
 
246
        if node is self._least_recently_used:
 
247
            self._least_recently_used = node.prev
233
248
        self._cache.pop(node.key)
234
249
        # If we have removed all entries, remove the head pointer as well
235
 
        if self._last_recently_used is None:
 
250
        if self._least_recently_used is None:
236
251
            self._most_recently_used = None
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
 
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
246
265
 
247
266
    def _remove_lru(self):
248
267
        """Remove one entry from the lru, and handle consequences.
250
269
        If there are no more references to the lru, then this entry should be
251
270
        removed from the cache.
252
271
        """
253
 
        self._remove_node(self._last_recently_used)
 
272
        self._remove_node(self._least_recently_used)
254
273
 
255
274
    def clear(self):
256
275
        """Clear out all of the cache."""
316
335
        :param cleanup: None or a function taking (key, value) to indicate
317
336
                        'value' should be cleaned up.
318
337
        """
 
338
        if key is _null_key:
 
339
            raise ValueError('cannot use _null_key as a key')
319
340
        node = self._cache.get(key, None)
320
341
        value_len = self._compute_size(value)
321
342
        if value_len >= self._after_cleanup_size: