← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/lru_cache.py

  • Committer: John Arbash Meinel
  • Date: 2009-04-16 19:55:28 UTC
  • mto: This revision was merged to the branch mainline in revision 4323.
  • Revision ID: john@arbash-meinel.com-20090416195528-bb69o9sepyh0fmk8
Switch to using prev as the object and next_key as the pointer.
This shouldn't really change the __getitem__ time, but it should make removing
the lru a tiny bit more straightforward.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/lru_cache.py
25
25
class _LRUNode(object):
26
26
    """This maintains the linked-list which is the lru internals."""
27
27
 
28
 
    __slots__ = ('prev_key', 'next_key', 'key', 'value', 'cleanup', 'size')
 
28
    __slots__ = ('prev', 'next_key', 'key', 'value', 'cleanup', 'size')
29
29
 
30
30
    def __init__(self, key, value, cleanup=None):
31
 
        self.prev_key = None
 
31
        self.prev = None
32
32
        self.next_key = None
33
33
        self.key = key
34
34
        self.value = value
39
39
        self.size = None
40
40
 
41
41
    def __repr__(self):
42
 
        if self.next_key is None:
43
 
            next_key = None
 
42
        if self.prev is None:
 
43
            prev_key = None
44
44
        else:
45
 
            next_key = self.next_key
 
45
            prev_key = self.prev_key
46
46
        return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
47
 
                                     next_key, self.prev_key)
 
47
                                     self.next_key, prev_key)
48
48
 
49
49
    def run_cleanup(self):
50
50
        if self.cleanup is not None:
86
86
            # Nothing to do, this node is already at the head of the queue
87
87
            return node.value
88
88
        # Remove this node from the old location
89
 
        prev_key = node.prev_key
90
 
        if prev_key is None:
91
 
            assert False, 'prev_key is None, but node isn\'t mru'
92
 
        node_prev = self._cache[prev_key]
 
89
        node_prev = node.prev
93
90
        if node is self._last_recently_used:
94
91
            self._last_recently_used = node_prev
95
92
        next_key = node.next_key
98
95
            node_next = None
99
96
        else:
100
97
            node_next = self._cache[next_key]
101
 
            node_next.prev_key = prev_key
 
98
            node_next.prev = node_prev
102
99
        # Insert this node at the front of the list
103
100
        node.next_key = mru.key
104
 
        mru.prev_key = node.key
 
101
        mru.prev = node
105
102
        self._most_recently_used = node
106
 
        node.prev_key = None
 
103
        node.prev = None
107
104
        return node.value
108
105
 
109
106
    def __len__(self):
113
110
        """Walk the LRU list, only meant to be used in tests."""
114
111
        node = self._most_recently_used
115
112
        if node is not None:
116
 
            if node.prev_key is not None:
 
113
            if node.prev is not None:
117
114
                raise AssertionError('the _most_recently_used entry is not'
118
115
                                     ' supposed to have a previous entry'
119
116
                                     ' %s' % (node,))
125
122
                node_next = None
126
123
            else:
127
124
                node_next = self._cache[node.next_key]
128
 
                if node_next.prev_key != node.key:
 
125
                if node_next.prev is not node:
129
126
                    raise AssertionError('inconsistency found, node.next.prev'
130
127
                                         ' != node: %s' % (node,))
131
 
            if node.prev_key is None:
 
128
            if node.prev is None:
132
129
                if node is not self._most_recently_used:
133
130
                    raise AssertionError('only the _most_recently_used should'
134
131
                                         ' not have a previous node: %s'
135
132
                                         % (node,))
136
133
            else:
137
 
                prev_node = self._cache[node.prev_key]
138
 
                if prev_node.next_key != node.key:
 
134
                if node.prev.next_key != node.key:
139
135
                    raise AssertionError('inconsistency found, node.prev.next'
140
136
                                         ' != node: %s' % (node,))
141
137
            yield node
219
215
        # We've taken care of the tail pointer, remove the node, and insert it
220
216
        # at the front
221
217
        # REMOVE
222
 
        if node.prev_key is None:
223
 
            node_prev = None
224
 
        else:
225
 
            node_prev = self._cache[node.prev_key]
226
218
        if node is self._last_recently_used:
227
 
            self._last_recently_used = node_prev
228
 
        if self._last_recently_used is None:
229
 
            import pdb; pdb.set_trace()
230
 
        if node_prev is not None:
231
 
            node_prev.next_key = node.next_key
 
219
            self._last_recently_used = node.prev
 
220
        if node.prev is not None:
 
221
            node.prev.next_key = node.next_key
232
222
        if node.next_key is not None:
233
223
            node_next = self._cache[node.next_key]
234
 
            node_next.prev_key = node.prev_key
 
224
            node_next.prev = node.prev
235
225
        # INSERT
236
226
        node.next_key = self._most_recently_used.key
237
 
        self._most_recently_used.prev_key = node.key
 
227
        self._most_recently_used.prev = node
238
228
        self._most_recently_used = node
239
 
        node.prev_key = None
 
229
        node.prev = None
240
230
 
241
231
    def _remove_node(self, node):
242
 
        if node.prev_key is None:
243
 
            node_prev = None
244
 
        else:
245
 
            node_prev = self._cache[node.prev_key]
246
232
        if node is self._last_recently_used:
247
 
            self._last_recently_used = node_prev
 
233
            self._last_recently_used = node.prev
248
234
        self._cache.pop(node.key)
249
235
        # If we have removed all entries, remove the head pointer as well
250
236
        if self._last_recently_used is None:
251
237
            self._most_recently_used = None
252
238
        node.run_cleanup()
253
239
        # Now remove this node from the linked list
254
 
        if node_prev is not None:
255
 
            node_prev.next_key = node.next_key
 
240
        if node.prev is not None:
 
241
            node.prev.next_key = node.next_key
256
242
        if node.next_key is not None:
257
243
            node_next = self._cache[node.next_key]
258
 
            node_next.prev_key = node.prev_key
 
244
            node_next.prev = node.prev
259
245
        # And remove this node's pointers
260
 
        node.prev_key = None
 
246
        node.prev = None
261
247
        node.next_key = None
262
248
 
263
249
    def _remove_lru(self):