~bzr-pqm/bzr/bzr.dev

# Copyright (C) 2008, 2009, 2010 Canonical Ltd

#

# This program is free software; you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation; either version 2 of the License, or

# (at your option) any later version.

#

# This program is distributed in the hope that it will be useful,

# but WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

# GNU General Public License for more details.

#

# You should have received a copy of the GNU General Public License

# along with this program; if not, write to the Free Software

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

#

"""Tests for btree indices."""

import pprint

import zlib

from bzrlib import (

    btree_index,

    errors,

    fifo_cache,

    lru_cache,

    osutils,

    tests,

    transport,

    )

from bzrlib.tests import (

    TestCaseWithTransport,

    condition_isinstance,

    multiply_tests,

    split_suite_by_condition,

    )

def load_tests(standard_tests, module, loader):

    # parameterise the TestBTreeNodes tests

    node_tests, others = split_suite_by_condition(standard_tests,

        condition_isinstance(TestBTreeNodes))

    import bzrlib._btree_serializer_py as py_module

    scenarios = [('python', {'parse_btree': py_module})]

    if compiled_btreeparser_feature.available():

        scenarios.append(('C', {'parse_btree':

                                compiled_btreeparser_feature.module}))

    return multiply_tests(node_tests, scenarios, others)

compiled_btreeparser_feature = tests.ModuleAvailableFeature(

                                'bzrlib._btree_serializer_pyx')

class BTreeTestCase(TestCaseWithTransport):

    # test names here are suffixed by the key length and reference list count

    # that they test.

    def setUp(self):

        TestCaseWithTransport.setUp(self)

        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)

    def make_nodes(self, count, key_elements, reference_lists):

        """Generate count*key_elements sample nodes."""

        keys = []

        for prefix_pos in range(key_elements):

            if key_elements - 1:

                prefix = (str(prefix_pos) * 40,)

            else:

                prefix = ()

            for pos in xrange(count):

                # TODO: This creates odd keys. When count == 100,000, it

                #       creates a 240 byte key

                key = prefix + (str(pos) * 40,)

                value = "value:%s" % pos

                if reference_lists:

                    # generate some references

                    refs = []

                    for list_pos in range(reference_lists):

                        # as many keys in each list as its index + the key depth

                        # mod 2 - this generates both 0 length lists and

                        # ones slightly longer than the number of lists.

                        # It also ensures we have non homogeneous lists.

                        refs.append([])

                        for ref_pos in range(list_pos + pos % 2):

                            if pos % 2:

                                # refer to a nearby key

                                refs[-1].append(prefix + ("ref" + str(pos - 1) * 40,))

                            else:

                                # serial of this ref in the ref list

                                refs[-1].append(prefix + ("ref" + str(ref_pos) * 40,))

                        refs[-1] = tuple(refs[-1])

                    refs = tuple(refs)

                else:

                    refs = ()

                keys.append((key, value, refs))

        return keys

    def shrink_page_size(self):

        """Shrink the default page size so that less fits in a page."""

        self.overrideAttr(btree_index, '_PAGE_SIZE')

        btree_index._PAGE_SIZE = 2048

class TestBTreeBuilder(BTreeTestCase):

    def test_clear_cache(self):

        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)

        # This is a no-op, but we need the api to be consistent with other

        # BTreeGraphIndex apis.

        builder.clear_cache()

    def test_empty_1_0(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=0\n"

            "row_lengths=\n",

            content)

    def test_empty_2_1(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=1)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=1\nkey_elements=2\nlen=0\n"

            "row_lengths=\n",

            content)

    def test_root_leaf_1_0(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(5, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(131, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"

            "row_lengths=1\n",

            content[:73])

        node_content = content[73:]

        node_bytes = zlib.decompress(node_content)

        expected_node = ("type=leaf\n"

            "0000000000000000000000000000000000000000\x00\x00value:0\n"

            "1111111111111111111111111111111111111111\x00\x00value:1\n"

            "2222222222222222222222222222222222222222\x00\x00value:2\n"

            "3333333333333333333333333333333333333333\x00\x00value:3\n"

            "4444444444444444444444444444444444444444\x00\x00value:4\n")

        self.assertEqual(expected_node, node_bytes)

    def test_root_leaf_2_2(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        nodes = self.make_nodes(5, 2, 2)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(238, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"

            "row_lengths=1\n",

            content[:74])

        node_content = content[74:]

        node_bytes = zlib.decompress(node_content)

        expected_node = (

            "type=leaf\n"

            "0000000000000000000000000000000000000000\x000000000000000000000000000000000000000000\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:0\n"

            "0000000000000000000000000000000000000000\x001111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\r0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:1\n"

            "0000000000000000000000000000000000000000\x002222222222222222222222222222222222222222\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:2\n"

            "0000000000000000000000000000000000000000\x003333333333333333333333333333333333333333\x000000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\t0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\r0000000000000000000000000000000000000000\x00ref2222222222222222222222222222222222222222\x00value:3\n"

            "0000000000000000000000000000000000000000\x004444444444444444444444444444444444444444\x00\t0000000000000000000000000000000000000000\x00ref0000000000000000000000000000000000000000\x00value:4\n"

            "1111111111111111111111111111111111111111\x000000000000000000000000000000000000000000\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:0\n"

            "1111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x001111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\r1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:1\n"

            "1111111111111111111111111111111111111111\x002222222222222222222222222222222222222222\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:2\n"

            "1111111111111111111111111111111111111111\x003333333333333333333333333333333333333333\x001111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\t1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\r1111111111111111111111111111111111111111\x00ref2222222222222222222222222222222222222222\x00value:3\n"

            "1111111111111111111111111111111111111111\x004444444444444444444444444444444444444444\x00\t1111111111111111111111111111111111111111\x00ref0000000000000000000000000000000000000000\x00value:4\n"

            ""

            )

        self.assertEqual(expected_node, node_bytes)

    def test_2_leaves_1_0(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(400, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(9283, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"

            "row_lengths=1,2\n",

            content[:77])

        root = content[77:4096]

        leaf1 = content[4096:8192]

        leaf2 = content[8192:]

        root_bytes = zlib.decompress(root)

        expected_root = (

            "type=internal\n"

            "offset=0\n"

            ) + ("307" * 40) + "\n"

        self.assertEqual(expected_root, root_bytes)

        # We already know serialisation works for leaves, check key selection:

        leaf1_bytes = zlib.decompress(leaf1)

        sorted_node_keys = sorted(node[0] for node in nodes)

        node = btree_index._LeafNode(leaf1_bytes, 1, 0)

        self.assertEqual(231, len(node.keys))

        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))

        leaf2_bytes = zlib.decompress(leaf2)

        node = btree_index._LeafNode(leaf2_bytes, 1, 0)

        self.assertEqual(400 - 231, len(node.keys))

        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))

    def test_last_page_rounded_1_layer(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(10, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(155, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"

            "row_lengths=1\n",

            content[:74])

        # Check thelast page is well formed

        leaf2 = content[74:]

        leaf2_bytes = zlib.decompress(leaf2)

        node = btree_index._LeafNode(leaf2_bytes, 1, 0)

        self.assertEqual(10, len(node.keys))

        sorted_node_keys = sorted(node[0] for node in nodes)

        self.assertEqual(sorted_node_keys, sorted(node.keys))

    def test_last_page_not_rounded_2_layer(self):

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

        nodes = self.make_nodes(400, 1, 0)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(9283, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"

            "row_lengths=1,2\n",

            content[:77])

        # Check the last page is well formed

        leaf2 = content[8192:]

        leaf2_bytes = zlib.decompress(leaf2)

        node = btree_index._LeafNode(leaf2_bytes, 1, 0)

        self.assertEqual(400 - 231, len(node.keys))

        sorted_node_keys = sorted(node[0] for node in nodes)

        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))

    def test_three_level_tree_details(self):

        # The left most pointer in the second internal node in a row should

        # pointer to the second node that the internal node is for, _not_

        # the first, otherwise the first node overlaps with the last node of

        # the prior internal node on that row.

        self.shrink_page_size()

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        # 40K nodes is enough to create a two internal nodes on the second

        # level, with a 2K page size

        nodes = self.make_nodes(20000, 2, 2)

        for node in nodes:

            builder.add_node(*node)

        t = transport.get_transport('trace+' + self.get_url(''))

        size = t.put_file('index', self.time(builder.finish))

        del builder

        index = btree_index.BTreeGraphIndex(t, 'index', size)

        # Seed the metadata, we're using internal calls now.

        index.key_count()

        self.assertEqual(3, len(index._row_lengths),

            "Not enough rows: %r" % index._row_lengths)

        self.assertEqual(4, len(index._row_offsets))

        self.assertEqual(sum(index._row_lengths), index._row_offsets[-1])

        internal_nodes = index._get_internal_nodes([0, 1, 2])

        root_node = internal_nodes[0]

        internal_node1 = internal_nodes[1]

        internal_node2 = internal_nodes[2]

        # The left most node node2 points at should be one after the right most

        # node pointed at by node1.

        self.assertEqual(internal_node2.offset, 1 + len(internal_node1.keys))

        # The left most key of the second node pointed at by internal_node2

        # should be its first key. We can check this by looking for its first key

        # in the second node it points at

        pos = index._row_offsets[2] + internal_node2.offset + 1

        leaf = index._get_leaf_nodes([pos])[pos]

        self.assertTrue(internal_node2.keys[0] in leaf.keys)

    def test_2_leaves_2_2(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        nodes = self.make_nodes(100, 2, 2)

        for node in nodes:

            builder.add_node(*node)

        # NamedTemporaryFile dies on builder.finish().read(). weird.

        temp_file = builder.finish()

        content = temp_file.read()

        del temp_file

        self.assertEqual(12643, len(content))

        self.assertEqual(

            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"

            "row_lengths=1,3\n",

            content[:77])

        root = content[77:4096]

        leaf1 = content[4096:8192]

        leaf2 = content[8192:12288]

        leaf3 = content[12288:]

        root_bytes = zlib.decompress(root)

        expected_root = (

            "type=internal\n"

            "offset=0\n"

            + ("0" * 40) + "\x00" + ("91" * 40) + "\n"

            + ("1" * 40) + "\x00" + ("81" * 40) + "\n"

            )

        self.assertEqual(expected_root, root_bytes)

        # We assume the other leaf nodes have been written correctly - layering

        # FTW.

    def test_spill_index_stress_1_1(self):

        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)

        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]

        builder.add_node(*nodes[0])

        # Test the parts of the index that take up memory are doing so

        # predictably.

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        builder.add_node(*nodes[1])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(1, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        # now back to memory

        builder.add_node(*nodes[2])

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        # And spills to a second backing index combing all

        builder.add_node(*nodes[3])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # The next spills to the 2-len slot

        builder.add_node(*nodes[4])

        builder.add_node(*nodes[5])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # Next spill combines

        builder.add_node(*nodes[6])

        builder.add_node(*nodes[7])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(8, builder._backing_indices[2].key_count())

        # And so forth - counting up in binary.

        builder.add_node(*nodes[8])

        builder.add_node(*nodes[9])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(8, builder._backing_indices[2].key_count())

        builder.add_node(*nodes[10])

        builder.add_node(*nodes[11])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(4, builder._backing_indices[1].key_count())

        self.assertEqual(8, builder._backing_indices[2].key_count())

        builder.add_node(*nodes[12])

        # Test that memory and disk are both used for query methods; and that

        # None is skipped over happily.

        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],

            list(builder.iter_all_entries()))

        # Two nodes - one memory one disk

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))

        self.assertEqual(13, builder.key_count())

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))

        builder.add_node(*nodes[13])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(4, builder._backing_indices[1].key_count())

        self.assertEqual(8, builder._backing_indices[2].key_count())

        builder.add_node(*nodes[14])

        builder.add_node(*nodes[15])

        self.assertEqual(4, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(None, builder._backing_indices[2])

        self.assertEqual(16, builder._backing_indices[3].key_count())

        # Now finish, and check we got a correctly ordered tree

        t = self.get_transport('')

        size = t.put_file('index', builder.finish())

        index = btree_index.BTreeGraphIndex(t, 'index', size)

        nodes = list(index.iter_all_entries())

        self.assertEqual(sorted(nodes), nodes)

        self.assertEqual(16, len(nodes))

    def test_spill_index_stress_1_1_no_combine(self):

        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)

        builder.set_optimize(for_size=False, combine_backing_indices=False)

        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]

        builder.add_node(*nodes[0])

        # Test the parts of the index that take up memory are doing so

        # predictably.

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        builder.add_node(*nodes[1])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(1, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        # now back to memory

        builder.add_node(*nodes[2])

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        # And spills to a second backing index but doesn't combine

        builder.add_node(*nodes[3])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

            self.assertEqual(2, backing_index.key_count())

        # The next spills to the 3rd slot

        builder.add_node(*nodes[4])

        builder.add_node(*nodes[5])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(3, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

            self.assertEqual(2, backing_index.key_count())

        # Now spill a few more, and check that we don't combine

        builder.add_node(*nodes[6])

        builder.add_node(*nodes[7])

        builder.add_node(*nodes[8])

        builder.add_node(*nodes[9])

        builder.add_node(*nodes[10])

        builder.add_node(*nodes[11])

        builder.add_node(*nodes[12])

        self.assertEqual(6, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

            self.assertEqual(2, backing_index.key_count())

        # Test that memory and disk are both used for query methods; and that

        # None is skipped over happily.

        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],

            list(builder.iter_all_entries()))

        # Two nodes - one memory one disk

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))

        self.assertEqual(13, builder.key_count())

        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),

            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))

        builder.add_node(*nodes[13])

        builder.add_node(*nodes[14])

        builder.add_node(*nodes[15])

        self.assertEqual(8, len(builder._backing_indices))

        for backing_index in builder._backing_indices:

            self.assertEqual(2, backing_index.key_count())

        # Now finish, and check we got a correctly ordered tree

        transport = self.get_transport('')

        size = transport.put_file('index', builder.finish())

        index = btree_index.BTreeGraphIndex(transport, 'index', size)

        nodes = list(index.iter_all_entries())

        self.assertEqual(sorted(nodes), nodes)

        self.assertEqual(16, len(nodes))

    def test_set_optimize(self):

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

        builder.set_optimize(for_size=True)

        self.assertTrue(builder._optimize_for_size)

        builder.set_optimize(for_size=False)

        self.assertFalse(builder._optimize_for_size)

        # test that we can set combine_backing_indices without effecting

        # _optimize_for_size

        obj = object()

        builder._optimize_for_size = obj

        builder.set_optimize(combine_backing_indices=False)

        self.assertFalse(builder._combine_backing_indices)

        self.assertIs(obj, builder._optimize_for_size)

        builder.set_optimize(combine_backing_indices=True)

        self.assertTrue(builder._combine_backing_indices)

        self.assertIs(obj, builder._optimize_for_size)

    def test_spill_index_stress_2_2(self):

        # test that references and longer keys don't confuse things.

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,

            spill_at=2)

        nodes = self.make_nodes(16, 2, 2)

        builder.add_node(*nodes[0])

        # Test the parts of the index that take up memory are doing so

        # predictably.

        self.assertEqual(1, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        builder.add_node(*nodes[1])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(1, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        # now back to memory

        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict

        builder.add_node(*nodes[2])

        self.assertEqual(1, len(builder._nodes))

        self.assertIsNot(None, builder._nodes_by_key)

        self.assertNotEqual({}, builder._nodes_by_key)

        # We should have a new entry

        self.assertNotEqual(old, builder._nodes_by_key)

        # And spills to a second backing index combing all

        builder.add_node(*nodes[3])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # The next spills to the 2-len slot

        builder.add_node(*nodes[4])

        builder.add_node(*nodes[5])

        self.assertEqual(0, len(builder._nodes))

        self.assertIs(None, builder._nodes_by_key)

        self.assertEqual(2, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(4, builder._backing_indices[1].key_count())

        # Next spill combines

        builder.add_node(*nodes[6])

        builder.add_node(*nodes[7])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(None, builder._backing_indices[0])

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(8, builder._backing_indices[2].key_count())

        # And so forth - counting up in binary.

        builder.add_node(*nodes[8])

        builder.add_node(*nodes[9])

        self.assertEqual(3, len(builder._backing_indices))

        self.assertEqual(2, builder._backing_indices[0].key_count())

        self.assertEqual(None, builder._backing_indices[1])

        self.assertEqual(8, builder._backing_indices[2].key_count())