Rev 4290: (temporary) Revert back to double-linked list, just with the fix for actually removing nodes properly. in lp:///~jameinel/bzr/1.15-lru-gc
John Arbash Meinel
john at arbash-meinel.com
Wed Apr 15 19:14:36 BST 2009
At lp:///~jameinel/bzr/1.15-lru-gc
------------------------------------------------------------
revno: 4290
revision-id: john at arbash-meinel.com-20090415181407-l2fjdkjrun9931k2
parent: john at arbash-meinel.com-20090415180816-gt70a2f8zdy9zkn9
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.15-lru-gc
timestamp: Wed 2009-04-15 13:14:07 -0500
message:
(temporary) Revert back to double-linked list, just with the fix for actually removing nodes properly.
-------------- next part --------------
=== modified file 'bzrlib/lru_cache.py'
--- a/bzrlib/lru_cache.py 2009-04-15 18:08:16 +0000
+++ b/bzrlib/lru_cache.py 2009-04-15 18:14:07 +0000
@@ -25,10 +25,10 @@
class _LRUNode(object):
"""This maintains the linked-list which is the lru internals."""
- __slots__ = ('prev_key', 'next', 'key', 'value', 'cleanup', 'size')
+ __slots__ = ('prev', 'next', 'key', 'value', 'cleanup', 'size')
def __init__(self, key, value, cleanup=None):
- self.prev_key = None
+ self.prev = None
self.next = None
self.key = key
self.value = value
@@ -40,11 +40,15 @@
def __repr__(self):
if self.next is None:
- next_key = None
- else:
- next_key = self.next.key
+ next = None
+ else:
+ next = self.next.key
+ if self.prev is None:
+ prev = None
+ else:
+ prev = self.prev.key
return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
- next_key, self.prev_key)
+ next, prev)
def run_cleanup(self):
if self.cleanup is not None:
@@ -85,22 +89,20 @@
if node is mru:
# Nothing to do, this node is already at the head of the queue
return node.value
+ elif node is self._last_recently_used:
+ self._last_recently_used = node.prev
# Remove this node from the old location
- prev_key = node.prev_key
- if prev_key is None:
- assert False, 'prev_key is None, but node isn\'t mru'
- node_prev = self._cache[prev_key]
- if node is self._last_recently_used:
- self._last_recently_used = node_prev
+ node_prev = node.prev
node_next = node.next
- node_prev.next = node_next
+ if node_prev is not None:
+ node_prev.next = node_next
if node_next is not None:
- node_next.prev_key = prev_key
- # Insert this node at the front of the list
+ node_next.prev = node_prev
+ # Insert this node to the front of the list
node.next = mru
- mru.prev_key = node.key
+ mru.prev = node
self._most_recently_used = node
- node.prev_key = None
+ node.prev = None
return node.value
def __len__(self):
@@ -110,7 +112,7 @@
"""Walk the LRU list, only meant to be used in tests."""
node = self._most_recently_used
if node is not None:
- if node.prev_key is not None:
+ if node.prev is not None:
raise AssertionError('the _most_recently_used entry is not'
' supposed to have a previous entry'
' %s' % (node,))
@@ -120,17 +122,16 @@
raise AssertionError('only the last node should have'
' no next value: %s' % (node,))
else:
- if node.next.prev_key != node.key:
+ if node.next.prev is not node:
raise AssertionError('inconsistency found, node.next.prev'
' != node: %s' % (node,))
- if node.prev_key is None:
+ if node.prev is None:
if node is not self._most_recently_used:
raise AssertionError('only the _most_recently_used should'
' not have a previous node: %s'
% (node,))
else:
- prev_node = self._cache[node.prev_key]
- if prev_node.next is not node:
+ if node.prev.next is not node:
raise AssertionError('inconsistency found, node.prev.next'
' != node: %s' % (node,))
yield node
@@ -211,46 +212,36 @@
elif node is self._most_recently_used:
# Nothing to do, this node is already at the head of the queue
return
+ elif node is self._last_recently_used:
+ self._last_recently_used = node.prev
# We've taken care of the tail pointer, remove the node, and insert it
# at the front
# REMOVE
- if node.prev_key is None:
- node_prev = None
- else:
- node_prev = self._cache[node.prev_key]
- if node is self._last_recently_used:
- self._last_recently_used = node_prev
- if self._last_recently_used is None:
- import pdb; pdb.set_trace()
- if node_prev is not None:
- node_prev.next = node.next
+ if node.prev is not None:
+ node.prev.next = node.next
if node.next is not None:
- node.next.prev_key = node.prev_key
+ node.next.prev = node.prev
# INSERT
node.next = self._most_recently_used
self._most_recently_used = node
- node.next.prev_key = node.key
- node.prev_key = None
+ node.next.prev = node
+ node.prev = None
def _remove_node(self, node):
- if node.prev_key is None:
- node_prev = None
- else:
- node_prev = self._cache[node.prev_key]
if node is self._last_recently_used:
- self._last_recently_used = node_prev
+ self._last_recently_used = node.prev
self._cache.pop(node.key)
# If we have removed all entries, remove the head pointer as well
if self._last_recently_used is None:
self._most_recently_used = None
node.run_cleanup()
# Now remove this node from the linked list
- if node_prev is not None:
- node_prev.next = node.next
+ if node.prev is not None:
+ node.prev.next = node.next
if node.next is not None:
- node.next.prev_key = node.prev_key
+ node.next.prev = node.prev
# And remove this node's pointers
- node.prev_key = None
+ node.prev = None
node.next = None
def _remove_lru(self):
More information about the bazaar-commits
mailing list