← 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-03-27 22:29:55 UTC
  • mto: (3735.39.2 clean)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090327222955-utifmfm888zerixt
Implement apply_delta_to_source which doesn't have to malloc another string.

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