← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2008-08-22 21:05:15 UTC
  • mto: This revision was merged to the branch mainline in revision 3653.
  • Revision ID: john@arbash-meinel.com-20080822210515-f8qwnjnpqk560gly
Fix up the test suite, now that we pack more efficiently.
Unfortunately, that means upping the node count for the iter_all and
three_level tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
203
203
        temp_file = builder.finish()
204
204
        content = temp_file.read()
205
205
        del temp_file
206
 
        self.assertEqual(10646, len(content))
 
206
        self.assertEqual(9602, len(content))
207
207
        self.assertEqual(
208
208
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=800\n"
209
209
            "row_lengths=1,2\n",
215
215
        expected_root = (
216
216
            "type=internal\n"
217
217
            "offset=0\n"
218
 
            "503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503503\n"
219
 
            )
 
218
            ) + ("635" * 40) + "\n"
220
219
        self.assertEqual(expected_root, root_bytes)
221
220
        # We already know serialisation works for leaves, check key selection:
222
221
        leaf1_bytes = zlib.decompress(leaf1)
223
222
        sorted_node_keys = sorted(node[0] for node in nodes)
224
223
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
225
 
        self.assertEqual(448, len(node.keys))
226
 
        self.assertEqual(sorted_node_keys[:448], sorted(node.keys))
 
224
        self.assertEqual(594, len(node.keys))
 
225
        self.assertEqual(sorted_node_keys[:594], sorted(node.keys))
227
226
        leaf2_bytes = zlib.decompress(leaf2)
228
227
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
229
 
        self.assertEqual(800 - 448, len(node.keys))
230
 
        self.assertEqual(sorted_node_keys[448:], sorted(node.keys))
 
228
        self.assertEqual(800 - 594, len(node.keys))
 
229
        self.assertEqual(sorted_node_keys[594:], sorted(node.keys))
231
230
 
232
231
    def test_last_page_rounded_1_layer(self):
233
232
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
260
259
        temp_file = builder.finish()
261
260
        content = temp_file.read()
262
261
        del temp_file
263
 
        self.assertEqual(10646, len(content))
 
262
        self.assertEqual(9602, len(content))
264
263
        self.assertEqual(
265
264
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=800\n"
266
265
            "row_lengths=1,2\n",
269
268
        leaf2 = content[8192:]
270
269
        leaf2_bytes = zlib.decompress(leaf2)
271
270
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
272
 
        self.assertEqual(800 - 448, len(node.keys))
 
271
        self.assertEqual(800 - 594, len(node.keys))
273
272
        sorted_node_keys = sorted(node[0] for node in nodes)
274
 
        self.assertEqual(sorted_node_keys[448:], sorted(node.keys))
 
273
        self.assertEqual(sorted_node_keys[594:], sorted(node.keys))
275
274
 
276
275
    def test_three_level_tree_details(self):
277
276
        # The left most pointer in the second internal node in a row should
278
277
        # pointer to the second node that the internal node is for, _not_
279
278
        # the first, otherwise the first node overlaps with the last node of
280
279
        # the prior internal node on that row.
281
 
        # We will be adding 100,000 nodes, so spill at 100,001 to prevent
 
280
        # We will be adding 140,000 nodes, so spill at 200,001 to prevent
282
281
        # having to flush anything out to disk.
283
282
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
284
 
                                           spill_at=100001)
285
 
        # 100K nodes is *just* enough to create a two internal nodes on the
 
283
                                           spill_at=200001)
 
284
        # 140K nodes is *just* enough to create a two internal nodes on the
286
285
        # second level
287
 
        nodes = self.make_nodes(50000, 2, 2)
 
286
        nodes = self.make_nodes(70000, 2, 2)
288
287
 
289
288
        for node in nodes:
290
289
            builder.add_node(*node)
321
320
        temp_file = builder.finish()
322
321
        content = temp_file.read()
323
322
        del temp_file
324
 
        self.assertEqual(10574, len(content))
 
323
        self.assertEqual(10639, len(content))
325
324
        self.assertEqual(
326
325
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=400\n"
327
326
            "row_lengths=1,2\n",
334
333
            "type=internal\n"
335
334
            "offset=0\n"
336
335
            "1111111111111111111111111111111111111111\x00"
337
 
            "126126126126126126126126126126126126126126126126126126126"
338
 
            "126126126126126126126126126126126126126126126126126126126126126\n"
339
 
            )
 
336
            ) + ("151" * 40) + "\n"
340
337
        self.assertEqual(expected_root, root_bytes)
341
338
        # We assume the other leaf nodes have been written correctly - layering
342
339
        # FTW.
594
591
        # The entire index should have been read, as it is one page long.
595
592
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
596
593
            transport._activity)
597
 
        self.assertEqual(1593, size)
 
594
        self.assertEqual(1199, size)
598
595
 
599
596
    def test_2_levels_key_count_2_2(self):
600
597
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
603
600
            builder.add_node(*node)
604
601
        transport = get_transport('trace+' + self.get_url(''))
605
602
        size = transport.put_file('index', builder.finish())
606
 
        self.assertEqual(10242, size)
 
603
        self.assertEqual(9152, size)
607
604
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
608
605
        del transport._activity[:]
609
606
        self.assertEqual([], transport._activity)
626
623
        # The entire index should have been read linearly.
627
624
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
628
625
            transport._activity)
629
 
        self.assertEqual(3846, size)
 
626
        self.assertEqual(2768, size)
630
627
 
631
628
    def test_validate_two_pages(self):
632
629
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
636
633
        transport = get_transport('trace+' + self.get_url(''))
637
634
        size = transport.put_file('index', builder.finish())
638
635
        # Root page, 2 leaf pages
639
 
        self.assertEqual(10242, size)
 
636
        self.assertEqual(9152, size)
640
637
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
641
638
        del transport._activity[:]
642
639
        self.assertEqual([], transport._activity)
643
640
        index.validate()
644
641
        # The entire index should have been read linearly.
645
642
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
646
 
            ('readv', 'index', [(4096, 4096), (8192, 2050)], False, None)],
 
643
            ('readv', 'index', [(4096, 4096), (8192, 960)], False, None)],
647
644
            transport._activity)
648
645
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
649
646
        # node and make validate find them.
687
684
        # iterating all entries reads the header, then does a linear
688
685
        # read.
689
686
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2,
690
 
                                           spill_at=100001)
691
 
        # 100k nodes is enough to create a three-level index, which shows that
 
687
                                           spill_at=200001)
 
688
        # 140k nodes is enough to create a three-level index, which shows that
692
689
        # we skip the internal nodes and just read the leaf nodes.
693
 
        nodes = self.make_nodes(50000, 2, 2)
 
690
        nodes = self.make_nodes(70000, 2, 2)
694
691
        for node in nodes:
695
692
            builder.add_node(*node)
696
693
        transport = get_transport('trace+' + self.get_url(''))
697
694
        size = transport.put_file('index', builder.finish())
698
 
        self.assertEqual(2026722, size, 'number of expected bytes in the'
 
695
        self.assertEqual(2624681, size, 'number of expected bytes in the'
699
696
                                        ' output changed')
700
697
        del builder
701
698
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
702
699
        del transport._activity[:]
703
700
        self.assertEqual([], transport._activity)
704
 
        found_nodes = list(index.iter_all_entries())
 
701
        found_nodes = self.time(list, index.iter_all_entries())
705
702
        bare_nodes = []
706
703
        for node in found_nodes:
707
704
            self.assertTrue(node[0] is index)
709
706
        self.assertEqual(3, len(index._row_lengths),
710
707
            "Not enough rows: %r" % index._row_lengths)
711
708
        # Should be as long as the nodes we supplied
712
 
        self.assertEqual(100000, len(found_nodes))
 
709
        self.assertEqual(140000, len(found_nodes))
713
710
        # Should have the same content
714
711
        self.assertEqual(set(nodes), set(bare_nodes))
715
712
        # Should have done linear scan IO up the index, ignoring
717
714
        # The entire index should have been read
718
715
        total_pages = sum(index._row_lengths)
719
716
        self.assertEqual(total_pages, index._row_offsets[-1])
720
 
        self.assertEqual(2026722, size)
 
717
        self.assertEqual(2624681, size)
721
718
        # The start of the leaves
722
719
        first_byte = index._row_offsets[-2] * btree_index._PAGE_SIZE
723
720
        readv_request = []
724
721
        for offset in range(first_byte, size, 4096):
725
722
            readv_request.append((offset, 4096))
726
723
        # The last page is truncated
727
 
        readv_request[-1] = (readv_request[-1][0], 3298)
 
724
        readv_request[-1] = (readv_request[-1][0], 2624681 % 4096)
728
725
        expected = [('readv', 'index', [(0, 4096)], False, None),
729
726
             ('readv',  'index', readv_request, False, None)]
730
727
        if expected != transport._activity: