← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-05-01 22:03:39 UTC
  • mfrom: (4287.1.11 1.15-lru-gc)
  • Revision ID: pqm@pqm.ubuntu.com-20090501220339-msx1b0ouap06xsp9
(jam) Change the _LRUNode implementation to avoid cyclic refs.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
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
51
        if self.cleanup is not None:
73
70
        # The "HEAD" of the lru linked list
74
71
        self._most_recently_used = None
75
72
        # The "TAIL" of the lru linked list
76
 
        self._last_recently_used = None
 
73
        self._least_recently_used = None
77
74
        self._update_max_cache(max_cache, after_cleanup_count)
78
75
 
79
76
    def __contains__(self, key):
80
77
        return key in self._cache
81
78
 
82
79
    def __getitem__(self, key):
83
 
        node = self._cache[key]
 
80
        cache = self._cache
 
81
        node = cache[key]
84
82
        # Inlined from _record_access to decrease the overhead of __getitem__
85
83
        # We also have more knowledge about structure if __getitem__ is
86
84
        # succeeding, then we know that self._most_recently_used must not be
89
87
        if node is mru:
90
88
            # Nothing to do, this node is already at the head of the queue
91
89
            return node.value
92
 
        elif node is self._last_recently_used:
93
 
            self._last_recently_used = node.prev
94
90
        # Remove this node from the old location
95
91
        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:
 
92
        next_key = node.next_key
 
93
        # benchmarking shows that the lookup of _null_key in globals is faster
 
94
        # than the attribute lookup for (node is self._least_recently_used)
 
95
        if next_key is _null_key:
 
96
            # 'node' is the _least_recently_used, because it doesn't have a
 
97
            # 'next' item. So move the current lru to the previous node.
 
98
            self._least_recently_used = node_prev
 
99
        else:
 
100
            node_next = cache[next_key]
100
101
            node_next.prev = node_prev
101
 
        # Insert this node to the front of the list
102
 
        node.next = mru
 
102
        node_prev.next_key = next_key
 
103
        # Insert this node at the front of the list
 
104
        node.next_key = mru.key
103
105
        mru.prev = node
104
106
        self._most_recently_used = node
105
107
        node.prev = None
117
119
                                     ' supposed to have a previous entry'
118
120
                                     ' %s' % (node,))
119
121
        while node is not None:
120
 
            if node.next is None:
121
 
                if node is not self._last_recently_used:
 
122
            if node.next_key is _null_key:
 
123
                if node is not self._least_recently_used:
122
124
                    raise AssertionError('only the last node should have'
123
125
                                         ' no next value: %s' % (node,))
 
126
                node_next = None
124
127
            else:
125
 
                if node.next.prev is not node:
 
128
                node_next = self._cache[node.next_key]
 
129
                if node_next.prev is not node:
126
130
                    raise AssertionError('inconsistency found, node.next.prev'
127
131
                                         ' != node: %s' % (node,))
128
132
            if node.prev is None:
131
135
                                         ' not have a previous node: %s'
132
136
                                         % (node,))
133
137
            else:
134
 
                if node.prev.next is not node:
 
138
                if node.prev.next_key != node.key:
135
139
                    raise AssertionError('inconsistency found, node.prev.next'
136
140
                                         ' != node: %s' % (node,))
137
141
            yield node
138
 
            node = node.next
 
142
            node = node_next
139
143
 
140
144
    def add(self, key, value, cleanup=None):
141
145
        """Add a new value to the cache.
148
152
        :param cleanup: None or a function taking (key, value) to indicate
149
153
                        'value' should be cleaned up.
150
154
        """
 
155
        if key is _null_key:
 
156
            raise ValueError('cannot use _null_key as a key')
151
157
        if key in self._cache:
152
158
            node = self._cache[key]
153
159
            node.run_cleanup()
207
213
        # Move 'node' to the front of the queue
208
214
        if self._most_recently_used is None:
209
215
            self._most_recently_used = node
210
 
            self._last_recently_used = node
 
216
            self._least_recently_used = node
211
217
            return
212
218
        elif node is self._most_recently_used:
213
219
            # Nothing to do, this node is already at the head of the queue
214
220
            return
215
 
        elif node is self._last_recently_used:
216
 
            self._last_recently_used = node.prev
217
221
        # We've taken care of the tail pointer, remove the node, and insert it
218
222
        # at the front
219
223
        # REMOVE
 
224
        if node is self._least_recently_used:
 
225
            self._least_recently_used = node.prev
220
226
        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
 
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
224
231
        # INSERT
225
 
        node.next = self._most_recently_used
 
232
        node.next_key = self._most_recently_used.key
 
233
        self._most_recently_used.prev = node
226
234
        self._most_recently_used = node
227
 
        node.next.prev = node
228
235
        node.prev = None
229
236
 
230
237
    def _remove_node(self, node):
231
 
        if node is self._last_recently_used:
232
 
            self._last_recently_used = node.prev
 
238
        if node is self._least_recently_used:
 
239
            self._least_recently_used = node.prev
233
240
        self._cache.pop(node.key)
234
241
        # If we have removed all entries, remove the head pointer as well
235
 
        if self._last_recently_used is None:
 
242
        if self._least_recently_used is None:
236
243
            self._most_recently_used = None
237
244
        node.run_cleanup()
238
245
        # Now remove this node from the linked list
239
246
        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
 
247
            node.prev.next_key = node.next_key
 
248
        if node.next_key is not _null_key:
 
249
            node_next = self._cache[node.next_key]
 
250
            node_next.prev = node.prev
243
251
        # And remove this node's pointers
244
252
        node.prev = None
245
 
        node.next = None
 
253
        node.next_key = _null_key
246
254
 
247
255
    def _remove_lru(self):
248
256
        """Remove one entry from the lru, and handle consequences.
250
258
        If there are no more references to the lru, then this entry should be
251
259
        removed from the cache.
252
260
        """
253
 
        self._remove_node(self._last_recently_used)
 
261
        self._remove_node(self._least_recently_used)
254
262
 
255
263
    def clear(self):
256
264
        """Clear out all of the cache."""
316
324
        :param cleanup: None or a function taking (key, value) to indicate
317
325
                        'value' should be cleaned up.
318
326
        """
 
327
        if key is _null_key:
 
328
            raise ValueError('cannot use _null_key as a key')
319
329
        node = self._cache.get(key, None)
320
330
        value_len = self._compute_size(value)
321
331
        if value_len >= self._after_cleanup_size: