← 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: Vincent Ladeuil
  • Date: 2012-03-13 16:42:20 UTC
  • mto: This revision was merged to the branch mainline in revision 6512.
  • Revision ID: v.ladeuil+lp@free.fr-20120313164220-atkou2zprhlspmwg
Mention that a given config option cannot be safely handled via both APIs at the same time.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
27
27
    lru_cache,
28
28
    osutils,
29
29
    tests,
 
30
    transport,
30
31
    )
31
32
from bzrlib.tests import (
32
33
    TestCaseWithTransport,
33
 
    condition_isinstance,
34
 
    multiply_tests,
35
 
    split_suite_by_condition,
36
 
    )
37
 
from bzrlib.transport import get_transport
38
 
 
39
 
 
40
 
def load_tests(standard_tests, module, loader):
41
 
    # parameterise the TestBTreeNodes tests
42
 
    node_tests, others = split_suite_by_condition(standard_tests,
43
 
        condition_isinstance(TestBTreeNodes))
 
34
    scenarios,
 
35
    )
 
36
from bzrlib.tests import (
 
37
    features,
 
38
    )
 
39
 
 
40
 
 
41
load_tests = scenarios.load_tests_apply_scenarios
 
42
 
 
43
 
 
44
def btreeparser_scenarios():
44
45
    import bzrlib._btree_serializer_py as py_module
45
46
    scenarios = [('python', {'parse_btree': py_module})]
46
47
    if compiled_btreeparser_feature.available():
47
 
        scenarios.append(('C', {'parse_btree':
48
 
                                compiled_btreeparser_feature.module}))
49
 
    return multiply_tests(node_tests, scenarios, others)
50
 
 
51
 
 
52
 
compiled_btreeparser_feature = tests.ModuleAvailableFeature(
53
 
                                'bzrlib._btree_serializer_pyx')
 
48
        scenarios.append(('C', 
 
49
            {'parse_btree': compiled_btreeparser_feature.module}))
 
50
    return scenarios
 
51
 
 
52
 
 
53
compiled_btreeparser_feature = features.ModuleAvailableFeature(
 
54
    'bzrlib._btree_serializer_pyx')
54
55
 
55
56
 
56
57
class BTreeTestCase(TestCaseWithTransport):
59
60
 
60
61
    def setUp(self):
61
62
        TestCaseWithTransport.setUp(self)
62
 
        self._original_header = btree_index._RESERVED_HEADER_BYTES
63
 
        def restore():
64
 
            btree_index._RESERVED_HEADER_BYTES = self._original_header
65
 
        self.addCleanup(restore)
66
 
        btree_index._RESERVED_HEADER_BYTES = 100
 
63
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
67
64
 
68
65
    def make_nodes(self, count, key_elements, reference_lists):
69
66
        """Generate count*key_elements sample nodes."""
103
100
 
104
101
    def shrink_page_size(self):
105
102
        """Shrink the default page size so that less fits in a page."""
106
 
        old_page_size = btree_index._PAGE_SIZE
107
 
        def cleanup():
108
 
            btree_index._PAGE_SIZE = old_page_size
109
 
        self.addCleanup(cleanup)
 
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
110
104
        btree_index._PAGE_SIZE = 2048
111
105
 
 
106
    def assertEqualsApproxCompressed(self, expected, actual, slop=6):
 
107
        """Check a count of compressed bytes is approximately as expected
 
108
 
 
109
        Relying on compressed length being stable even with fixed inputs is
 
110
        slightly bogus, but zlib is stable enough that this mostly works.
 
111
        """
 
112
        if not expected - slop < actual < expected + slop:
 
113
            self.fail("Expected around %d bytes compressed but got %d" %
 
114
                (expected, actual))
 
115
 
112
116
 
113
117
class TestBTreeBuilder(BTreeTestCase):
114
118
 
205
209
        temp_file = builder.finish()
206
210
        content = temp_file.read()
207
211
        del temp_file
208
 
        self.assertEqual(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
209
213
        self.assertEqual(
210
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
211
215
            "row_lengths=1,2\n",
223
227
        leaf1_bytes = zlib.decompress(leaf1)
224
228
        sorted_node_keys = sorted(node[0] for node in nodes)
225
229
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
226
 
        self.assertEqual(231, len(node.keys))
227
 
        self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
 
230
        self.assertEqual(231, len(node))
 
231
        self.assertEqual(sorted_node_keys[:231], node.all_keys())
228
232
        leaf2_bytes = zlib.decompress(leaf2)
229
233
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
230
 
        self.assertEqual(400 - 231, len(node.keys))
231
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
234
        self.assertEqual(400 - 231, len(node))
 
235
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
232
236
 
233
237
    def test_last_page_rounded_1_layer(self):
234
238
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
239
243
        temp_file = builder.finish()
240
244
        content = temp_file.read()
241
245
        del temp_file
242
 
        self.assertEqual(155, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
243
247
        self.assertEqual(
244
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
245
249
            "row_lengths=1\n",
248
252
        leaf2 = content[74:]
249
253
        leaf2_bytes = zlib.decompress(leaf2)
250
254
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
251
 
        self.assertEqual(10, len(node.keys))
 
255
        self.assertEqual(10, len(node))
252
256
        sorted_node_keys = sorted(node[0] for node in nodes)
253
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
257
        self.assertEqual(sorted_node_keys, node.all_keys())
254
258
 
255
259
    def test_last_page_not_rounded_2_layer(self):
256
260
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
261
265
        temp_file = builder.finish()
262
266
        content = temp_file.read()
263
267
        del temp_file
264
 
        self.assertEqual(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
265
269
        self.assertEqual(
266
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
267
271
            "row_lengths=1,2\n",
270
274
        leaf2 = content[8192:]
271
275
        leaf2_bytes = zlib.decompress(leaf2)
272
276
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
273
 
        self.assertEqual(400 - 231, len(node.keys))
 
277
        self.assertEqual(400 - 231, len(node))
274
278
        sorted_node_keys = sorted(node[0] for node in nodes)
275
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
279
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
276
280
 
277
281
    def test_three_level_tree_details(self):
278
282
        # The left most pointer in the second internal node in a row should
287
291
 
288
292
        for node in nodes:
289
293
            builder.add_node(*node)
290
 
        transport = get_transport('trace+' + self.get_url(''))
291
 
        size = transport.put_file('index', self.time(builder.finish))
 
294
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
295
        size = t.put_file('index', self.time(builder.finish))
292
296
        del builder
293
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
297
        index = btree_index.BTreeGraphIndex(t, 'index', size)
294
298
        # Seed the metadata, we're using internal calls now.
295
299
        index.key_count()
296
300
        self.assertEqual(3, len(index._row_lengths),
309
313
        # in the second node it points at
310
314
        pos = index._row_offsets[2] + internal_node2.offset + 1
311
315
        leaf = index._get_leaf_nodes([pos])[pos]
312
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
316
        self.assertTrue(internal_node2.keys[0] in leaf)
313
317
 
314
318
    def test_2_leaves_2_2(self):
315
319
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
320
324
        temp_file = builder.finish()
321
325
        content = temp_file.read()
322
326
        del temp_file
323
 
        self.assertEqual(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
324
328
        self.assertEqual(
325
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
326
330
            "row_lengths=1,3\n",
416
420
        self.assertEqual(None, builder._backing_indices[2])
417
421
        self.assertEqual(16, builder._backing_indices[3].key_count())
418
422
        # Now finish, and check we got a correctly ordered tree
419
 
        transport = self.get_transport('')
420
 
        size = transport.put_file('index', builder.finish())
421
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
423
        t = self.get_transport('')
 
424
        size = t.put_file('index', builder.finish())
 
425
        index = btree_index.BTreeGraphIndex(t, 'index', size)
422
426
        nodes = list(index.iter_all_entries())
423
427
        self.assertEqual(sorted(nodes), nodes)
424
428
        self.assertEqual(16, len(nodes))
614
618
        for key, value, references in nodes:
615
619
            builder.add_node(key, value, references)
616
620
        stream = builder.finish()
617
 
        trans = get_transport('trace+' + self.get_url())
 
621
        trans = transport.get_transport_from_url('trace+' + self.get_url())
618
622
        size = trans.put_file('index', stream)
619
623
        return btree_index.BTreeGraphIndex(trans, 'index', size)
620
624
 
 
625
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
 
626
                               offset=0):
 
627
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
 
628
                                           reference_lists=ref_lists)
 
629
        builder.add_nodes(nodes)
 
630
        transport = self.get_transport('')
 
631
        # NamedTemporaryFile dies on builder.finish().read(). weird.
 
632
        temp_file = builder.finish()
 
633
        content = temp_file.read()
 
634
        del temp_file
 
635
        size = len(content)
 
636
        transport.put_bytes('index', (' '*offset)+content)
 
637
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
 
638
                                           offset=offset)
 
639
 
621
640
    def test_clear_cache(self):
622
641
        nodes = self.make_nodes(160, 2, 2)
623
642
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
640
659
        self.assertEqual(0, len(index._leaf_node_cache))
641
660
 
642
661
    def test_trivial_constructor(self):
643
 
        transport = get_transport('trace+' + self.get_url(''))
644
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
662
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
663
        index = btree_index.BTreeGraphIndex(t, 'index', None)
645
664
        # Checks the page size at load, but that isn't logged yet.
646
 
        self.assertEqual([], transport._activity)
 
665
        self.assertEqual([], t._activity)
647
666
 
648
667
    def test_with_size_constructor(self):
649
 
        transport = get_transport('trace+' + self.get_url(''))
650
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
668
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
669
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
651
670
        # Checks the page size at load, but that isn't logged yet.
652
 
        self.assertEqual([], transport._activity)
 
671
        self.assertEqual([], t._activity)
653
672
 
654
673
    def test_empty_key_count_no_size(self):
655
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
656
 
        transport = get_transport('trace+' + self.get_url(''))
657
 
        transport.put_file('index', builder.finish())
658
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
659
 
        del transport._activity[:]
660
 
        self.assertEqual([], transport._activity)
 
675
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
676
        t.put_file('index', builder.finish())
 
677
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
678
        del t._activity[:]
 
679
        self.assertEqual([], t._activity)
661
680
        self.assertEqual(0, index.key_count())
662
681
        # The entire index should have been requested (as we generally have the
663
682
        # size available, and doing many small readvs is inappropriate).
664
683
        # We can't tell how much was actually read here, but - check the code.
665
 
        self.assertEqual([('get', 'index')], transport._activity)
 
684
        self.assertEqual([('get', 'index')], t._activity)
666
685
 
667
686
    def test_empty_key_count(self):
668
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
669
 
        transport = get_transport('trace+' + self.get_url(''))
670
 
        size = transport.put_file('index', builder.finish())
 
688
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
689
        size = t.put_file('index', builder.finish())
671
690
        self.assertEqual(72, size)
672
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
673
 
        del transport._activity[:]
674
 
        self.assertEqual([], transport._activity)
 
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
692
        del t._activity[:]
 
693
        self.assertEqual([], t._activity)
675
694
        self.assertEqual(0, index.key_count())
676
695
        # The entire index should have been read, as 4K > size
677
696
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
678
 
            transport._activity)
 
697
                         t._activity)
679
698
 
680
699
    def test_non_empty_key_count_2_2(self):
681
700
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
682
701
        nodes = self.make_nodes(35, 2, 2)
683
702
        for node in nodes:
684
703
            builder.add_node(*node)
685
 
        transport = get_transport('trace+' + self.get_url(''))
686
 
        size = transport.put_file('index', builder.finish())
687
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
688
 
        del transport._activity[:]
689
 
        self.assertEqual([], transport._activity)
 
704
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
705
        size = t.put_file('index', builder.finish())
 
706
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
707
        del t._activity[:]
 
708
        self.assertEqual([], t._activity)
690
709
        self.assertEqual(70, index.key_count())
691
710
        # The entire index should have been read, as it is one page long.
692
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
693
 
            transport._activity)
694
 
        self.assertEqual(1173, size)
 
712
            t._activity)
 
713
        self.assertEqualsApproxCompressed(1173, size)
 
714
 
 
715
    def test_with_offset_no_size(self):
 
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
717
                                            offset=1234,
 
718
                                            nodes=self.make_nodes(200, 1, 1))
 
719
        index._size = None # throw away the size info
 
720
        self.assertEqual(200, index.key_count())
 
721
 
 
722
    def test_with_small_offset(self):
 
723
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
724
                                            offset=1234,
 
725
                                            nodes=self.make_nodes(200, 1, 1))
 
726
        self.assertEqual(200, index.key_count())
 
727
 
 
728
    def test_with_large_offset(self):
 
729
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
730
                                            offset=123456,
 
731
                                            nodes=self.make_nodes(200, 1, 1))
 
732
        self.assertEqual(200, index.key_count())
695
733
 
696
734
    def test__read_nodes_no_size_one_page_reads_once(self):
697
735
        self.make_index(nodes=[(('key',), 'value', ())])
698
 
        trans = get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
699
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
700
738
        del trans._activity[:]
701
739
        nodes = dict(index._read_nodes([0]))
702
740
        self.assertEqual([0], nodes.keys())
703
741
        node = nodes[0]
704
 
        self.assertEqual([('key',)], node.keys.keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
705
743
        self.assertEqual([('get', 'index')], trans._activity)
706
744
 
707
745
    def test__read_nodes_no_size_multiple_pages(self):
709
747
        index.key_count()
710
748
        num_pages = index._row_offsets[-1]
711
749
        # Reopen with a traced transport and no size
712
 
        trans = get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
713
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
714
752
        del trans._activity[:]
715
753
        nodes = dict(index._read_nodes([0]))
720
758
        nodes = self.make_nodes(160, 2, 2)
721
759
        for node in nodes:
722
760
            builder.add_node(*node)
723
 
        transport = get_transport('trace+' + self.get_url(''))
724
 
        size = transport.put_file('index', builder.finish())
725
 
        self.assertEqual(17692, size)
726
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
727
 
        del transport._activity[:]
728
 
        self.assertEqual([], transport._activity)
 
761
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
762
        size = t.put_file('index', builder.finish())
 
763
        self.assertEqualsApproxCompressed(17692, size)
 
764
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
765
        del t._activity[:]
 
766
        self.assertEqual([], t._activity)
729
767
        self.assertEqual(320, index.key_count())
730
768
        # The entire index should not have been read.
731
769
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
732
 
            transport._activity)
 
770
                         t._activity)
733
771
 
734
772
    def test_validate_one_page(self):
735
773
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
736
774
        nodes = self.make_nodes(45, 2, 2)
737
775
        for node in nodes:
738
776
            builder.add_node(*node)
739
 
        transport = get_transport('trace+' + self.get_url(''))
740
 
        size = transport.put_file('index', builder.finish())
741
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
742
 
        del transport._activity[:]
743
 
        self.assertEqual([], transport._activity)
 
777
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
778
        size = t.put_file('index', builder.finish())
 
779
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
780
        del t._activity[:]
 
781
        self.assertEqual([], t._activity)
744
782
        index.validate()
745
783
        # The entire index should have been read linearly.
746
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
747
 
            transport._activity)
748
 
        self.assertEqual(1488, size)
 
785
                         t._activity)
 
786
        self.assertEqualsApproxCompressed(1488, size)
749
787
 
750
788
    def test_validate_two_pages(self):
751
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
752
790
        nodes = self.make_nodes(80, 2, 2)
753
791
        for node in nodes:
754
792
            builder.add_node(*node)
755
 
        transport = get_transport('trace+' + self.get_url(''))
756
 
        size = transport.put_file('index', builder.finish())
 
793
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
794
        size = t.put_file('index', builder.finish())
757
795
        # Root page, 2 leaf pages
758
 
        self.assertEqual(9339, size)
759
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
760
 
        del transport._activity[:]
761
 
        self.assertEqual([], transport._activity)
 
796
        self.assertEqualsApproxCompressed(9339, size)
 
797
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
798
        del t._activity[:]
 
799
        self.assertEqual([], t._activity)
762
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
763
802
        # The entire index should have been read linearly.
764
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
765
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
766
 
            transport._activity)
 
803
        self.assertEqual(
 
804
            [('readv', 'index', [(0, 4096)], False, None),
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
806
            t._activity)
767
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
768
808
        # node and make validate find them.
769
809
 
770
810
    def test_eq_ne(self):
771
811
        # two indices are equal when constructed with the same parameters:
772
 
        transport1 = get_transport('trace+' + self.get_url(''))
773
 
        transport2 = get_transport(self.get_url(''))
774
 
        self.assertTrue(
775
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
776
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
777
 
        self.assertTrue(
778
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
779
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
780
 
        self.assertFalse(
781
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
782
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
783
 
        self.assertFalse(
784
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
785
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
786
 
        self.assertFalse(
787
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
788
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
789
 
        self.assertFalse(
790
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
791
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
792
 
        self.assertFalse(
793
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
794
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
795
 
        self.assertTrue(
796
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
797
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
798
 
        self.assertTrue(
799
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
800
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
801
 
        self.assertTrue(
802
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
803
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
 
812
        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
 
813
        t2 = self.get_transport()
 
814
        self.assertTrue(
 
815
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
816
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
817
        self.assertTrue(
 
818
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
819
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
820
        self.assertFalse(
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
822
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
823
        self.assertFalse(
 
824
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
825
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
826
        self.assertFalse(
 
827
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
828
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
829
        self.assertFalse(
 
830
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
831
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
832
        self.assertFalse(
 
833
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
834
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
835
        self.assertTrue(
 
836
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
837
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
838
        self.assertTrue(
 
839
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
840
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
841
        self.assertTrue(
 
842
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
843
            btree_index.BTreeGraphIndex(t1, 'index', 20))
804
844
 
 
845
    def test_key_too_big(self):
 
846
        # the size that matters here is the _compressed_ size of the key, so we can't
 
847
        # do a simple character repeat.
 
848
        bigKey = ''.join(map(repr, xrange(btree_index._PAGE_SIZE)))
 
849
        self.assertRaises(errors.BadIndexKey,
 
850
                          self.make_index,
 
851
                          nodes=[((bigKey,), 'value', ())])
 
852
        
805
853
    def test_iter_all_only_root_no_size(self):
806
854
        self.make_index(nodes=[(('key',), 'value', ())])
807
 
        trans = get_transport('trace+' + self.get_url(''))
808
 
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
809
 
        del trans._activity[:]
 
855
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
856
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
857
        del t._activity[:]
810
858
        self.assertEqual([(('key',), 'value')],
811
859
                         [x[1:] for x in index.iter_all_entries()])
812
 
        self.assertEqual([('get', 'index')], trans._activity)
 
860
        self.assertEqual([('get', 'index')], t._activity)
813
861
 
814
862
    def test_iter_all_entries_reads(self):
815
863
        # iterating all entries reads the header, then does a linear
821
869
        nodes = self.make_nodes(10000, 2, 2)
822
870
        for node in nodes:
823
871
            builder.add_node(*node)
824
 
        transport = get_transport('trace+' + self.get_url(''))
825
 
        size = transport.put_file('index', builder.finish())
826
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
827
 
                                        ' output changed')
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
873
        size = t.put_file('index', builder.finish())
828
874
        page_size = btree_index._PAGE_SIZE
829
875
        del builder
830
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
831
 
        del transport._activity[:]
832
 
        self.assertEqual([], transport._activity)
 
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
877
        del t._activity[:]
 
878
        self.assertEqual([], t._activity)
833
879
        found_nodes = self.time(list, index.iter_all_entries())
834
880
        bare_nodes = []
835
881
        for node in found_nodes:
846
892
        # The entire index should have been read
847
893
        total_pages = sum(index._row_lengths)
848
894
        self.assertEqual(total_pages, index._row_offsets[-1])
849
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
850
896
        # The start of the leaves
851
897
        first_byte = index._row_offsets[-2] * page_size
852
898
        readv_request = []
853
899
        for offset in range(first_byte, size, page_size):
854
900
            readv_request.append((offset, page_size))
855
901
        # The last page is truncated
856
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
857
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
858
904
             ('readv',  'index', readv_request, False, None)]
859
 
        if expected != transport._activity:
 
905
        if expected != t._activity:
860
906
            self.assertEqualDiff(pprint.pformat(expected),
861
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
862
908
 
863
909
    def _test_iter_entries_references_resolved(self):
864
910
        index = self.make_index(1, nodes=[
876
922
        nodes = self.make_nodes(160, 2, 2)
877
923
        for node in nodes:
878
924
            builder.add_node(*node)
879
 
        transport = get_transport('trace+' + self.get_url(''))
880
 
        size = transport.put_file('index', builder.finish())
 
925
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
926
        size = t.put_file('index', builder.finish())
881
927
        del builder
882
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
883
 
        del transport._activity[:]
884
 
        self.assertEqual([], transport._activity)
 
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
929
        del t._activity[:]
 
930
        self.assertEqual([], t._activity)
885
931
        # search for one key
886
932
        found_nodes = list(index.iter_entries([nodes[30][0]]))
887
933
        bare_nodes = []
895
941
        # Should have read the root node, then one leaf page:
896
942
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
897
943
             ('readv',  'index', [(8192, 4096), ], False, None)],
898
 
            transport._activity)
 
944
            t._activity)
899
945
 
900
946
    def test_iter_key_prefix_1_element_key_None(self):
901
947
        index = self.make_index()
1084
1130
        min_l2_key = l2.min_key
1085
1131
        max_l1_key = l1.max_key
1086
1132
        self.assertTrue(max_l1_key < min_l2_key)
1087
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1133
        parents_min_l2_key = l2[min_l2_key][1][0]
1088
1134
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1089
1135
        # Now, whatever key we select that would fall on the second page,
1090
1136
        # should give us all the parents until the page break
1103
1149
        parent_map = {}
1104
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1105
1151
                                            missing_keys)
1106
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1152
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1107
1153
        self.assertEqual(set(), missing_keys)
1108
1154
        self.assertEqual(set(), search_keys)
1109
1155
 
1125
1171
        for node in nodes:
1126
1172
            builder.add_node(*node)
1127
1173
        stream = builder.finish()
1128
 
        trans = get_transport(self.get_url())
 
1174
        trans = self.get_transport()
1129
1175
        size = trans.put_file('index', stream)
1130
1176
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1131
1177
        self.assertEqual(500, index.key_count())
1157
1203
 
1158
1204
class TestBTreeNodes(BTreeTestCase):
1159
1205
 
1160
 
    def restore_parser(self):
1161
 
        btree_index._btree_serializer = self.saved_parser
 
1206
    scenarios = btreeparser_scenarios()
1162
1207
 
1163
1208
    def setUp(self):
1164
1209
        BTreeTestCase.setUp(self)
1165
 
        self.saved_parser = btree_index._btree_serializer
1166
 
        self.addCleanup(self.restore_parser)
1167
 
        btree_index._btree_serializer = self.parse_btree
 
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1168
1211
 
1169
1212
    def test_LeafNode_1_0(self):
1170
1213
        node_bytes = ("type=leaf\n"
1182
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1183
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1184
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1185
 
            }, node.keys)
 
1228
            }, dict(node.all_items()))
1186
1229
 
1187
1230
    def test_LeafNode_2_2(self):
1188
1231
        node_bytes = ("type=leaf\n"
1202
1245
            ('11', '33'): ('value:3',
1203
1246
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1204
1247
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1205
 
            }, node.keys)
 
1248
            }, dict(node.all_items()))
1206
1249
 
1207
1250
    def test_InternalNode_1(self):
1208
1251
        node_bytes = ("type=internal\n"
1243
1286
            ('11', '33'): ('value:3',
1244
1287
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1245
1288
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1246
 
            }, node.keys)
 
1289
            }, dict(node.all_items()))
1247
1290
 
1248
1291
    def assertFlattened(self, expected, key, value, refs):
1249
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1327
1370
        This doesn't actually create anything on disk, it just primes a
1328
1371
        BTreeGraphIndex with the recommended information.
1329
1372
        """
1330
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1331
 
                                            'test-index', size=size)
 
1373
        index = btree_index.BTreeGraphIndex(
 
1374
            transport.get_transport_from_url('memory:///'),
 
1375
            'test-index', size=size)
1332
1376
        if recommended_pages is not None:
1333
1377
            index._recommended_pages = recommended_pages
1334
1378
        return index