Rev 3753: Cache node length to avoid full iteration on __len__ calls. in http://people.ubuntu.com/~robertc/baz2.0/repository

Robert Collins robertc at robertcollins.net
Wed Oct 22 07:41:04 BST 2008


At http://people.ubuntu.com/~robertc/baz2.0/repository

------------------------------------------------------------
revno: 3753
revision-id: robertc at robertcollins.net-20081022064059-wb4jp5sdx2t2whn5
parent: robertc at robertcollins.net-20081017025707-xicz4bqrrx35dfa0
committer: Robert Collins <robertc at robertcollins.net>
branch nick: repository
timestamp: Wed 2008-10-22 17:40:59 +1100
message:
  Cache node length to avoid full iteration on __len__ calls.
modified:
  bzrlib/chk_map.py              chk_map.py-20081001014447-ue6kkuhofvdecvxa-1
  bzrlib/inventory.py            inventory.py-20050309040759-6648b84ca2005b37
  bzrlib/tests/per_repository_chk/test_supported.py test_supported.py-20080925063728-k65ry0n2rhta6t34-1
  bzrlib/tests/test_chk_map.py   test_chk_map.py-20081001014447-ue6kkuhofvdecvxa-2
  bzrlib/tests/test_inv.py       testinv.py-20050722220913-1dc326138d1a5892
  bzrlib/tests/test_repository.py test_repository.py-20060131075918-65c555b881612f4d
=== modified file 'bzrlib/chk_map.py'
--- a/bzrlib/chk_map.py	2008-10-17 02:57:07 +0000
+++ b/bzrlib/chk_map.py	2008-10-22 06:40:59 +0000
@@ -101,6 +101,10 @@
         else:
             return self._root_node._key
 
+    def __len__(self):
+        self._ensure_root()
+        return len(self._root_node)
+
     def _map(self, key, value):
         """Map key to value."""
         self._ensure_root()
@@ -143,6 +147,7 @@
     def __init__(self):
         self._nodes = {}
         self._key = None
+        self._len = 0
 
     def add_child(self, name, child):
         """Add a child to the node.
@@ -153,6 +158,7 @@
         :param child: The child, a key tuple for the childs value.
         """
         self._nodes[name] = child
+        self._len += 1
         self._key = None
 
     def deserialise(self, bytes, key):
@@ -165,12 +171,17 @@
         nodes = {}
         if lines[0] != 'chkroot:':
             raise ValueError("not a serialised root node: %r" % bytes)
-        for line in lines[1:]:
+        length = int(lines[1])
+        for line in lines[2:]:
             name, value = line.split('\x00')
             nodes[name] = (value,)
         self._nodes = nodes
+        self._len = length
         self._key = key
 
+    def __len__(self):
+        return self._len
+
     def refs(self):
         """Get the CHK key references this node holds."""
         return self._nodes.values()
@@ -183,6 +194,7 @@
         :param name: The name to remove from the node.
         """
         del self._nodes[name]
+        self._len -= 1
         self._key = None
 
     def serialise(self):
@@ -191,6 +203,7 @@
         :return: A bytestring.
         """
         lines = ["chkroot:\n"]
+        lines.append("%d\n" % self._len)
         for name, child in sorted(self._nodes.items()):
             lines.append("%s\x00%s\n" % (name, child[0]))
         return "".join(lines)

=== modified file 'bzrlib/inventory.py'
--- a/bzrlib/inventory.py	2008-10-15 00:06:31 +0000
+++ b/bzrlib/inventory.py	2008-10-22 06:40:59 +0000
@@ -1478,8 +1478,7 @@
 
     def __len__(self):
         """Return the number of entries in the inventory."""
-        # Might want to cache the length in the meta node.
-        return len([item for item in self])
+        return len(self.id_to_entry)
 
     def path2id(self, name):
         """Walk down through directories to return entry of last component.

=== modified file 'bzrlib/tests/per_repository_chk/test_supported.py'
--- a/bzrlib/tests/per_repository_chk/test_supported.py	2008-10-09 04:50:37 +0000
+++ b/bzrlib/tests/per_repository_chk/test_supported.py	2008-10-22 06:40:59 +0000
@@ -70,7 +70,7 @@
         try:
             repo.start_write_group()
             try:
-                repo.chk_bytes.add_lines((None,), None, ["chkroot:\n"],
+                repo.chk_bytes.add_lines((None,), None, ["chkroot:\n", "0\n"],
                     random_id=True)
             except:
                 repo.abort_write_group()
@@ -89,7 +89,7 @@
             repo.pack()
             self.assertEqual(
                 set([('sha1:062ef095245d8617d7671e50a71b529d13d93022',),
-                    ('sha1:572d8da882e1ebf0f50f1e2da2d7a9cadadf4db5',)]),
+                     ('sha1:8e13ef930ff710425830ffd5077146b259b49534',)]),
                 repo.chk_bytes.keys())
         finally:
             repo.unlock()
@@ -99,7 +99,7 @@
         try:
             self.assertEqual(
                 set([('sha1:062ef095245d8617d7671e50a71b529d13d93022',),
-                    ('sha1:572d8da882e1ebf0f50f1e2da2d7a9cadadf4db5',)]),
+                     ('sha1:8e13ef930ff710425830ffd5077146b259b49534',)]),
                 repo.chk_bytes.keys())
         finally:
             repo.unlock()

=== modified file 'bzrlib/tests/test_chk_map.py'
--- a/bzrlib/tests/test_chk_map.py	2008-10-09 04:50:37 +0000
+++ b/bzrlib/tests/test_chk_map.py	2008-10-22 06:40:59 +0000
@@ -37,9 +37,9 @@
         return stream.next().get_bytes_as("fulltext")
 
     def assertHasABMap(self, chk_bytes):
-        root_key = ('sha1:5c464bbd8fecba1aa2574c6d2eb26813d622ce17',)
+        root_key = ('sha1:674c986f86eacc7d9e4fbee45eda625e5689f9a4',)
         self.assertEqual(
-            "chkroot:\na\x00sha1:cb29f32e561a1b7f862c38ccfd6bc7c7d892f04b\n",
+            "chkroot:\n1\na\x00sha1:cb29f32e561a1b7f862c38ccfd6bc7c7d892f04b\n",
             self.read_bytes(chk_bytes, root_key))
         self.assertEqual(
             "chkvalue:\nb",
@@ -47,20 +47,26 @@
                 ("sha1:cb29f32e561a1b7f862c38ccfd6bc7c7d892f04b",)))
 
     def assertHasEmptyMap(self, chk_bytes):
-        root_key = ('sha1:572d8da882e1ebf0f50f1e2da2d7a9cadadf4db5',)
-        self.assertEqual("chkroot:\n", self.read_bytes(chk_bytes, root_key))
+        root_key = ('sha1:8e13ef930ff710425830ffd5077146b259b49534',)
+        self.assertEqual("chkroot:\n0\n", self.read_bytes(chk_bytes, root_key))
+
+    def _get_map(self, a_dict):
+        chk_bytes = self.get_chk_bytes()
+        root_key = CHKMap.from_dict(chk_bytes, a_dict)
+        chkmap = CHKMap(chk_bytes, root_key)
+        return chkmap
 
     def test_from_dict_empty(self):
         chk_bytes = self.get_chk_bytes()
         root_key = CHKMap.from_dict(chk_bytes, {})
-        self.assertEqual(('sha1:572d8da882e1ebf0f50f1e2da2d7a9cadadf4db5',),
+        self.assertEqual(('sha1:8e13ef930ff710425830ffd5077146b259b49534',),
             root_key)
         self.assertHasEmptyMap(chk_bytes)
 
     def test_from_dict_ab(self):
         chk_bytes = self.get_chk_bytes()
         root_key = CHKMap.from_dict(chk_bytes, {"a":"b"})
-        self.assertEqual(('sha1:5c464bbd8fecba1aa2574c6d2eb26813d622ce17',),
+        self.assertEqual(('sha1:674c986f86eacc7d9e4fbee45eda625e5689f9a4',),
             root_key)
         self.assertHasABMap(chk_bytes)
 
@@ -71,7 +77,7 @@
         root_key = CHKMap.from_dict(chk_bytes, {})
         chkmap = CHKMap(chk_bytes, root_key)
         new_root = chkmap.apply_delta([(None, "a", "b")])
-        self.assertEqual(('sha1:5c464bbd8fecba1aa2574c6d2eb26813d622ce17',),
+        self.assertEqual(('sha1:674c986f86eacc7d9e4fbee45eda625e5689f9a4',),
             new_root)
         self.assertHasABMap(chk_bytes)
         # The update should have left us with an in memory root node, with an
@@ -85,7 +91,7 @@
         root_key = CHKMap.from_dict(chk_bytes, {"a":"b"})
         chkmap = CHKMap(chk_bytes, root_key)
         new_root = chkmap.apply_delta([("a", None, None)])
-        self.assertEqual(('sha1:572d8da882e1ebf0f50f1e2da2d7a9cadadf4db5',),
+        self.assertEqual(('sha1:8e13ef930ff710425830ffd5077146b259b49534',),
             new_root)
         self.assertHasEmptyMap(chk_bytes)
         # The update should have left us with an in memory root node, with an
@@ -107,20 +113,25 @@
             sorted(list(chkmap.iteritems())))
 
     def test_iteritems_selected_one_of_two_items(self):
-        chk_bytes = self.get_chk_bytes()
-        root_key = CHKMap.from_dict(chk_bytes,
-            {"a":"content here", "b":"more content"})
-        chkmap = CHKMap(chk_bytes, root_key)
+        chkmap = self._get_map( {"a":"content here", "b":"more content"})
         self.assertEqual([("a", "content here")],
             sorted(list(chkmap.iteritems(["a"]))))
 
+    def test___len__empty(self):
+        chkmap = self._get_map({})
+        self.assertEqual(0, len(chkmap))
+
+    def test___len__2(self):
+        chkmap = self._get_map( {"foo":"bar", "gam":"quux"})
+        self.assertEqual(2, len(chkmap))
+
 
 class TestRootNode(TestCaseWithTransport):
 
     def test_serialise_empty(self):
         node = RootNode()
         bytes = node.serialise()
-        self.assertEqual("chkroot:\n", bytes)
+        self.assertEqual("chkroot:\n0\n", bytes)
 
     def test_add_child_resets_key(self):
         node = RootNode()
@@ -128,6 +139,19 @@
         node.add_child("c", ("sha1:1234",))
         self.assertEqual(None, node._key)
 
+    def test_add_child_increases_len(self):
+        node = RootNode()
+        node._key = ("something",)
+        node.add_child("c", ("sha1:1234",))
+        self.assertEqual(1, len(node))
+
+    def test_remove_child_decreases_len(self):
+        node = RootNode()
+        node.add_child("c", ("sha1:1234",))
+        node._key = ("something",)
+        node.remove_child("c")
+        self.assertEqual(0, len(node))
+
     def test_remove_child_removes_child(self):
         node = RootNode()
         node.add_child("a", ("sha1:4321",))
@@ -147,15 +171,16 @@
         # deserialising from a bytestring & key sets the nodes and the known
         # key.
         node = RootNode()
-        node.deserialise("chkroot:\nc\x00sha1:1234\n", ("foo",))
+        node.deserialise("chkroot:\n1\nc\x00sha1:1234\n", ("foo",))
         self.assertEqual({"c": ("sha1:1234",)}, node._nodes)
         self.assertEqual(("foo",), node._key)
+        self.assertEqual(1, len(node))
 
     def test_serialise_with_child(self):
         node = RootNode()
         node.add_child("c", ("sha1:1234",))
         bytes = node.serialise()
-        self.assertEqual("chkroot:\nc\x00sha1:1234\n", bytes)
+        self.assertEqual("chkroot:\n1\nc\x00sha1:1234\n", bytes)
 
 
 class TestValueNode(TestCaseWithTransport):

=== modified file 'bzrlib/tests/test_inv.py'
--- a/bzrlib/tests/test_inv.py	2008-10-13 06:36:20 +0000
+++ b/bzrlib/tests/test_inv.py	2008-10-22 06:40:59 +0000
@@ -219,7 +219,7 @@
             'chkinventory:\n',
             'revision_id: foo\n',
             'root_id: TREE_ROOT\n',
-            'id_to_entry: sha1:dc696b0cf291ac0d66bdcda3070f755494a586fc\n'
+            'id_to_entry: sha1:6fc2838d88d40dc7331087fb69d3ea72c023b3ee\n'
             ],
             chk_inv.to_lines())
 

=== modified file 'bzrlib/tests/test_repository.py'
--- a/bzrlib/tests/test_repository.py	2008-10-13 04:54:26 +0000
+++ b/bzrlib/tests/test_repository.py	2008-10-22 06:40:59 +0000
@@ -675,8 +675,8 @@
         repo.add_inventory(revid, inv, [])
         self.assertEqual(set([(revid,)]), repo.inventories.keys())
         self.assertEqual(
-            set([('sha1:a521a815c343d72dffac50e316246f1fade1a4d3',),
-                ('sha1:a12ffb3c1810005e8ed9388d29602e1e9e8e06ac',)]),
+            set([('sha1:a12ffb3c1810005e8ed9388d29602e1e9e8e06ac',),
+                 ('sha1:fd7f4d1237b9ae0021bd8c52e99a930430444c79',)]),
             repo.chk_bytes.keys())
 
 




More information about the bazaar-commits mailing list