Rev 3804: Refactor the LeafNode.map() code so we can do _check_remap more cheaply. in http://bzr.arbash-meinel.com/branches/bzr/brisbane/chk_map

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/brisbane/chk_map

------------------------------------------------------------
revno: 3804
revision-id: john at arbash-meinel.com-20081202235625-h5fo44xy2hxeopo2
parent: john at arbash-meinel.com-20081202234745-80n34m4wg4gcgx8i
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: chk_map
timestamp: Tue 2008-12-02 17:56:25 -0600
message:
  Refactor the LeafNode.map() code so we can do _check_remap more cheaply.
  
  LeafNode.map() was actually doing all the work to split into many leaf nodes, but
  all we care about is *if* we would have to do that.
  Also, we don't have to do as many safety checks because we know that all the child
  keys that we would be adding cannot already be present.
-------------- next part --------------
=== modified file 'bzrlib/chk_map.py'
--- a/bzrlib/chk_map.py	2008-12-02 23:47:45 +0000
+++ b/bzrlib/chk_map.py	2008-12-02 23:56:25 +0000
@@ -493,17 +493,30 @@
         #       then that can be done via the C extension
         return 2 + len('\x00'.join(key)) + len(value)
 
+    def _map_no_split(self, key, value):
+        """Map a key to a value.
+
+        This assumes either the key does not already exist, or you have already
+        removed its size and length from self.
+
+        :return: True if adding this node should cause us to split.
+        """
+        self._items[key] = value
+        self._size += self._key_value_len(key, value)
+        self._len += 1
+        if (self._len > 1
+            and self._maximum_size
+            and self._current_size() > self._maximum_size):
+            return True
+        return False
+
     def map(self, store, key, value):
         """Map key to value."""
         if key in self._items:
             self._size -= self._key_value_len(key, self._items[key])
             self._len -= 1
-        self._items[key] = value
-        self._size += self._key_value_len(key, value)
-        self._len += 1
         self._key = None
-        if (self._maximum_size and self._current_size() > self._maximum_size and
-            self._len > 1):
+        if self._map_no_split(key, value):
             common_prefix = self.unique_serialised_prefix()
             split_at = len(common_prefix) + 1
             result = {}
@@ -934,17 +947,10 @@
                     # Without looking at any leaf nodes, we are sure
                     return self
                 for key, value in node._items.iteritems():
-                    # TODO: it is expensive to have it actually do the split,
-                    #       when all we care about is whether it *would* split.
-                    #       Refactor the code a bit so we can just check
-                    #       without actually having to do all the work
-                    next_prefix, new_nodes = new_leaf.map(store, key, value)
-                    if len(new_nodes) > 1:
-                        # These nodes cannot fit in a single leaf, so we are
-                        # done
+                    if new_leaf._map_no_split(key, value):
+                        # Adding this key would cause a split, so we know we
+                        # don't need to collapse
                         return self
-                    else:
-                        assert new_leaf is new_nodes[0][1]
         # So far, everything fits. Page in the rest of the nodes, and see if it
         # holds true.
         if keys:
@@ -971,17 +977,8 @@
                     # We know we won't fit
                     return self
                 for key, value in node._items.iteritems():
-                    # TODO: it is expensive to have it actually do the split,
-                    #       when all we care about is whether it *would* split.
-                    #       Refactor the code a bit so we can just check
-                    #       without actually having to do all the work
-                    next_prefix, new_nodes = new_leaf.map(store, key, value)
-                    if len(new_nodes) > 1:
-                        # These nodes cannot fit in a single leaf, so we are
-                        # done
+                    if new_leaf._map_no_split(key, value):
                         return self
-                    else:
-                        assert new_leaf is new_nodes[0][1]
 
         # We have gone to every child, and everything fits in a single leaf
         # node, we no longer need this internal node