Rev 4291: use indirection on both next and prev. in lp:///~jameinel/bzr/1.15-lru-gc
John Arbash Meinel
john at arbash-meinel.com
Wed Apr 15 23:02:15 BST 2009
At lp:///~jameinel/bzr/1.15-lru-gc
------------------------------------------------------------
revno: 4291
revision-id: john at arbash-meinel.com-20090415220144-ubls1xdzq9t04hao
parent: john at arbash-meinel.com-20090415181407-l2fjdkjrun9931k2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.15-lru-gc
timestamp: Wed 2009-04-15 17:01:44 -0500
message:
use indirection on both next and prev.
This was done because I thought we still had a cycle.
It turns out that we *actually* just had a frame referencing
my cache object, which caused 'del cache' to not actually
destroy it.
-------------- next part --------------
=== modified file 'bzrlib/lru_cache.py'
--- a/bzrlib/lru_cache.py 2009-04-15 18:14:07 +0000
+++ b/bzrlib/lru_cache.py 2009-04-15 22:01:44 +0000
@@ -25,11 +25,11 @@
class _LRUNode(object):
"""This maintains the linked-list which is the lru internals."""
- __slots__ = ('prev', 'next', 'key', 'value', 'cleanup', 'size')
+ __slots__ = ('prev_key', 'next_key', 'key', 'value', 'cleanup', 'size')
def __init__(self, key, value, cleanup=None):
- self.prev = None
- self.next = None
+ self.prev_key = None
+ self.next_key = None
self.key = key
self.value = value
self.cleanup = cleanup
@@ -39,16 +39,12 @@
self.size = None
def __repr__(self):
- if self.next is None:
- next = None
- else:
- next = self.next.key
- if self.prev is None:
- prev = None
- else:
- prev = self.prev.key
+ if self.next_key is None:
+ next_key = None
+ else:
+ next_key = self.next_key
return '%s(%r n:%r p:%r)' % (self.__class__.__name__, self.key,
- next, prev)
+ next_key, self.prev_key)
def run_cleanup(self):
if self.cleanup is not None:
@@ -89,20 +85,25 @@
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
- node_prev = node.prev
- node_next = node.next
- if node_prev is not None:
- node_prev.next = node_next
- if node_next is not None:
- node_next.prev = node_prev
- # Insert this node to the front of the list
- node.next = mru
- mru.prev = node
+ 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
+ next_key = node.next_key
+ node_prev.next_key = next_key
+ if next_key is None:
+ node_next = None
+ else:
+ node_next = self._cache[next_key]
+ node_next.prev_key = prev_key
+ # Insert this node at the front of the list
+ node.next_key = mru.key
+ mru.prev_key = node.key
self._most_recently_used = node
- node.prev = None
+ node.prev_key = None
return node.value
def __len__(self):
@@ -112,30 +113,33 @@
"""Walk the LRU list, only meant to be used in tests."""
node = self._most_recently_used
if node is not None:
- if node.prev is not None:
+ if node.prev_key is not None:
raise AssertionError('the _most_recently_used entry is not'
' supposed to have a previous entry'
' %s' % (node,))
while node is not None:
- if node.next is None:
+ if node.next_key is None:
if node is not self._last_recently_used:
raise AssertionError('only the last node should have'
' no next value: %s' % (node,))
+ node_next = None
else:
- if node.next.prev is not node:
+ node_next = self._cache[node.next_key]
+ if node_next.prev_key != node.key:
raise AssertionError('inconsistency found, node.next.prev'
' != node: %s' % (node,))
- if node.prev is None:
+ if node.prev_key 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:
- if node.prev.next is not node:
+ prev_node = self._cache[node.prev_key]
+ if prev_node.next_key != node.key:
raise AssertionError('inconsistency found, node.prev.next'
' != node: %s' % (node,))
yield node
- node = node.next
+ node = node_next
def add(self, key, value, cleanup=None):
"""Add a new value to the cache.
@@ -212,37 +216,49 @@
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 is not None:
- node.prev.next = node.next
- if node.next is not None:
- node.next.prev = node.prev
+ 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_key = node.next_key
+ if node.next_key is not None:
+ node_next = self._cache[node.next_key]
+ node_next.prev_key = node.prev_key
# INSERT
- node.next = self._most_recently_used
+ node.next_key = self._most_recently_used.key
+ self._most_recently_used.prev_key = node.key
self._most_recently_used = node
- node.next.prev = node
- node.prev = None
+ node.prev_key = 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.next is not None:
- node.next.prev = node.prev
+ if node_prev is not None:
+ node_prev.next_key = node.next_key
+ if node.next_key is not None:
+ node_next = self._cache[node.next_key]
+ node_next.prev_key = node.prev_key
# And remove this node's pointers
- node.prev = None
- node.next = None
+ node.prev_key = None
+ node.next_key = None
def _remove_lru(self):
"""Remove one entry from the lru, and handle consequences.
More information about the bazaar-commits
mailing list