Rev 4297: Restore the ability to handle None as a key. in lp:///~jameinel/bzr/1.15-lru-gc

[John Arbash Meinel]

At lp:///~jameinel/bzr/1.15-lru-gc

------------------------------------------------------------
revno: 4297
revision-id: john at arbash-meinel.com-20090416220625-hejrugy3r5qwlut9
parent: john at arbash-meinel.com-20090416205818-arnw8c6tvnjrs3h5
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.15-lru-gc
timestamp: Thu 2009-04-16 17:06:25 -0500
message:
  Restore the ability to handle None as a key.
  We now use _null_key instead of None to indicate the end-of-refs.
  This means we now check that _null_key isn't used as an actual key.
  This slows us down from 7.1 => 7.3s or so.
  Interestingly, the globals lookup of _null_key was faster than
  node is self._lru (7.5s+). I was a bit surprised at that.
-------------- next part --------------
=== modified file 'bzrlib/lru_cache.py'
--- a/bzrlib/lru_cache.py	2009-04-16 20:58:18 +0000
+++ b/bzrlib/lru_cache.py	2009-04-16 22:06:25 +0000
@@ -21,6 +21,7 @@
     trace,
     )
 
+_null_key = object()
 
 class _LRUNode(object):
     """This maintains the linked-list which is the lru internals."""
@@ -29,7 +30,7 @@
 
     def __init__(self, key, value, cleanup=None):
         self.prev = None
-        self.next_key = None
+        self.next_key = _null_key
         self.key = key
         self.value = value
         self.cleanup = cleanup
@@ -89,7 +90,9 @@
         # Remove this node from the old location
         node_prev = node.prev
         next_key = node.next_key
-        if next_key is None:
+        # benchmarking shows that the lookup of _null_key in globals is faster
+        # than the attribute lookup for (node is self._last_recently_used)
+        if next_key is _null_key:
             # 'node' is the _last_recently_used, because it doesn't have a
             # 'next' item. So move the current lru to the previous node.
             self._last_recently_used = node_prev
@@ -116,7 +119,7 @@
                                      ' supposed to have a previous entry'
                                      ' %s' % (node,))
         while node is not None:
-            if node.next_key is None:
+            if node.next_key is _null_key:
                 if node is not self._last_recently_used:
                     raise AssertionError('only the last node should have'
                                          ' no next value: %s' % (node,))
@@ -149,9 +152,8 @@
         :param cleanup: None or a function taking (key, value) to indicate
                         'value' should be cleaned up.
         """
-        if key is None:
-            # We use None to indicate non-entries in our key following code.
-            raise ValueError('LRUCache cannot map None as a key')
+        if key is _null_key:
+            raise ValueError('cannot use _null_key as a key')
         if key in self._cache:
             node = self._cache[key]
             node.run_cleanup()
@@ -223,7 +225,7 @@
             self._last_recently_used = node.prev
         if node.prev is not None:
             node.prev.next_key = node.next_key
-        if node.next_key is not None:
+        if node.next_key is not _null_key:
             node_next = self._cache[node.next_key]
             node_next.prev = node.prev
         # INSERT
@@ -243,12 +245,12 @@
         # Now remove this node from the linked list
         if node.prev is not None:
             node.prev.next_key = node.next_key
-        if node.next_key is not None:
+        if node.next_key is not _null_key:
             node_next = self._cache[node.next_key]
             node_next.prev = node.prev
         # And remove this node's pointers
         node.prev = None
-        node.next_key = None
+        node.next_key = _null_key
 
     def _remove_lru(self):
         """Remove one entry from the lru, and handle consequences.
@@ -322,6 +324,8 @@
         :param cleanup: None or a function taking (key, value) to indicate
                         'value' should be cleaned up.
         """
+        if key is _null_key:
+            raise ValueError('cannot use _null_key as a key')
         node = self._cache.get(key, None)
         value_len = self._compute_size(value)
         if value_len >= self._after_cleanup_size:

=== modified file 'bzrlib/tests/test_lru_cache.py'
--- a/bzrlib/tests/test_lru_cache.py	2009-04-16 20:58:18 +0000
+++ b/bzrlib/tests/test_lru_cache.py	2009-04-16 22:06:25 +0000
@@ -46,6 +46,27 @@
         self.failUnless('foo' in cache)
         self.failIf('bar' in cache)
 
+    def test_map_None(self):
+        # Make sure that we can properly map None as a key.
+        cache = lru_cache.LRUCache(max_cache=10)
+        self.failIf(None in cache)
+        cache[None] = 1
+        self.assertEqual(1, cache[None])
+        cache[None] = 2
+        self.assertEqual(2, cache[None])
+        # Test the various code paths of __getitem__, to make sure that we can
+        # handle when None is the key for the LRU and the MRU
+        cache[1] = 3
+        cache[None] = 1
+        cache[None]
+        cache[1]
+        cache[None]
+        self.assertEqual([None, 1], [n.key for n in cache._walk_lru()])
+
+    def test_add__null_key(self):
+        cache = lru_cache.LRUCache(max_cache=10)
+        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
+
     def test_overflow(self):
         """Adding extra entries will pop out old ones."""
         cache = lru_cache.LRUCache(max_cache=1, after_cleanup_count=1)
@@ -279,6 +300,10 @@
         self.assertEqual(int(cache._max_size*0.8), cache._after_cleanup_size)
         self.assertEqual(0, cache._value_size)
 
+    def test_add__null_key(self):
+        cache = lru_cache.LRUSizeCache()
+        self.assertRaises(ValueError, cache.add, lru_cache._null_key, 1)
+
     def test_add_tracks_size(self):
         cache = lru_cache.LRUSizeCache()
         self.assertEqual(0, cache._value_size)