← 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: Colin Watson
  • Date: 2015-07-02 11:30:47 UTC
  • mto: This revision was merged to the branch mainline in revision 6605.
  • Revision ID: cjwatson@canonical.com-20150702113047-359s4zsi07wvfwso
Use assertLength.

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):
58
59
    # that they test.
59
60
 
60
61
    def setUp(self):
61
 
        TestCaseWithTransport.setUp(self)
 
62
        super(BTreeTestCase, self).setUp()
62
63
        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)
63
64
 
64
65
    def make_nodes(self, count, key_elements, reference_lists):
102
103
        self.overrideAttr(btree_index, '_PAGE_SIZE')
103
104
        btree_index._PAGE_SIZE = 2048
104
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
 
105
116
 
106
117
class TestBTreeBuilder(BTreeTestCase):
107
118
 
198
209
        temp_file = builder.finish()
199
210
        content = temp_file.read()
200
211
        del temp_file
201
 
        self.assertEqual(9283, len(content))
 
212
        self.assertEqualsApproxCompressed(9283, len(content))
202
213
        self.assertEqual(
203
214
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
204
215
            "row_lengths=1,2\n",
216
227
        leaf1_bytes = zlib.decompress(leaf1)
217
228
        sorted_node_keys = sorted(node[0] for node in nodes)
218
229
        node = btree_index._LeafNode(leaf1_bytes, 1, 0)
219
 
        self.assertEqual(231, len(node.keys))
220
 
        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())
221
232
        leaf2_bytes = zlib.decompress(leaf2)
222
233
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
223
 
        self.assertEqual(400 - 231, len(node.keys))
224
 
        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())
225
236
 
226
237
    def test_last_page_rounded_1_layer(self):
227
238
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
232
243
        temp_file = builder.finish()
233
244
        content = temp_file.read()
234
245
        del temp_file
235
 
        self.assertEqual(155, len(content))
 
246
        self.assertEqualsApproxCompressed(155, len(content))
236
247
        self.assertEqual(
237
248
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
238
249
            "row_lengths=1\n",
241
252
        leaf2 = content[74:]
242
253
        leaf2_bytes = zlib.decompress(leaf2)
243
254
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
244
 
        self.assertEqual(10, len(node.keys))
 
255
        self.assertEqual(10, len(node))
245
256
        sorted_node_keys = sorted(node[0] for node in nodes)
246
 
        self.assertEqual(sorted_node_keys, sorted(node.keys))
 
257
        self.assertEqual(sorted_node_keys, node.all_keys())
247
258
 
248
259
    def test_last_page_not_rounded_2_layer(self):
249
260
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
254
265
        temp_file = builder.finish()
255
266
        content = temp_file.read()
256
267
        del temp_file
257
 
        self.assertEqual(9283, len(content))
 
268
        self.assertEqualsApproxCompressed(9283, len(content))
258
269
        self.assertEqual(
259
270
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
260
271
            "row_lengths=1,2\n",
263
274
        leaf2 = content[8192:]
264
275
        leaf2_bytes = zlib.decompress(leaf2)
265
276
        node = btree_index._LeafNode(leaf2_bytes, 1, 0)
266
 
        self.assertEqual(400 - 231, len(node.keys))
 
277
        self.assertEqual(400 - 231, len(node))
267
278
        sorted_node_keys = sorted(node[0] for node in nodes)
268
 
        self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
 
279
        self.assertEqual(sorted_node_keys[231:], node.all_keys())
269
280
 
270
281
    def test_three_level_tree_details(self):
271
282
        # The left most pointer in the second internal node in a row should
280
291
 
281
292
        for node in nodes:
282
293
            builder.add_node(*node)
283
 
        transport = get_transport('trace+' + self.get_url(''))
284
 
        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))
285
296
        del builder
286
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
297
        index = btree_index.BTreeGraphIndex(t, 'index', size)
287
298
        # Seed the metadata, we're using internal calls now.
288
299
        index.key_count()
289
300
        self.assertEqual(3, len(index._row_lengths),
302
313
        # in the second node it points at
303
314
        pos = index._row_offsets[2] + internal_node2.offset + 1
304
315
        leaf = index._get_leaf_nodes([pos])[pos]
305
 
        self.assertTrue(internal_node2.keys[0] in leaf.keys)
 
316
        self.assertTrue(internal_node2.keys[0] in leaf)
306
317
 
307
318
    def test_2_leaves_2_2(self):
308
319
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
313
324
        temp_file = builder.finish()
314
325
        content = temp_file.read()
315
326
        del temp_file
316
 
        self.assertEqual(12643, len(content))
 
327
        self.assertEqualsApproxCompressed(12643, len(content))
317
328
        self.assertEqual(
318
329
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
319
330
            "row_lengths=1,3\n",
409
420
        self.assertEqual(None, builder._backing_indices[2])
410
421
        self.assertEqual(16, builder._backing_indices[3].key_count())
411
422
        # Now finish, and check we got a correctly ordered tree
412
 
        transport = self.get_transport('')
413
 
        size = transport.put_file('index', builder.finish())
414
 
        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)
415
426
        nodes = list(index.iter_all_entries())
416
427
        self.assertEqual(sorted(nodes), nodes)
417
428
        self.assertEqual(16, len(nodes))
607
618
        for key, value, references in nodes:
608
619
            builder.add_node(key, value, references)
609
620
        stream = builder.finish()
610
 
        trans = get_transport('trace+' + self.get_url())
 
621
        trans = transport.get_transport_from_url('trace+' + self.get_url())
611
622
        size = trans.put_file('index', stream)
612
623
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
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
 
614
640
    def test_clear_cache(self):
615
641
        nodes = self.make_nodes(160, 2, 2)
616
642
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
633
659
        self.assertEqual(0, len(index._leaf_node_cache))
634
660
 
635
661
    def test_trivial_constructor(self):
636
 
        transport = get_transport('trace+' + self.get_url(''))
637
 
        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)
638
664
        # Checks the page size at load, but that isn't logged yet.
639
 
        self.assertEqual([], transport._activity)
 
665
        self.assertEqual([], t._activity)
640
666
 
641
667
    def test_with_size_constructor(self):
642
 
        transport = get_transport('trace+' + self.get_url(''))
643
 
        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)
644
670
        # Checks the page size at load, but that isn't logged yet.
645
 
        self.assertEqual([], transport._activity)
 
671
        self.assertEqual([], t._activity)
646
672
 
647
673
    def test_empty_key_count_no_size(self):
648
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
649
 
        transport = get_transport('trace+' + self.get_url(''))
650
 
        transport.put_file('index', builder.finish())
651
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
652
 
        del transport._activity[:]
653
 
        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)
654
680
        self.assertEqual(0, index.key_count())
655
681
        # The entire index should have been requested (as we generally have the
656
682
        # size available, and doing many small readvs is inappropriate).
657
683
        # We can't tell how much was actually read here, but - check the code.
658
 
        self.assertEqual([('get', 'index')], transport._activity)
 
684
        self.assertEqual([('get', 'index')], t._activity)
659
685
 
660
686
    def test_empty_key_count(self):
661
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
662
 
        transport = get_transport('trace+' + self.get_url(''))
663
 
        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())
664
690
        self.assertEqual(72, size)
665
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
666
 
        del transport._activity[:]
667
 
        self.assertEqual([], transport._activity)
 
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
692
        del t._activity[:]
 
693
        self.assertEqual([], t._activity)
668
694
        self.assertEqual(0, index.key_count())
669
695
        # The entire index should have been read, as 4K > size
670
696
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
671
 
            transport._activity)
 
697
                         t._activity)
672
698
 
673
699
    def test_non_empty_key_count_2_2(self):
674
700
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
675
701
        nodes = self.make_nodes(35, 2, 2)
676
702
        for node in nodes:
677
703
            builder.add_node(*node)
678
 
        transport = get_transport('trace+' + self.get_url(''))
679
 
        size = transport.put_file('index', builder.finish())
680
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
681
 
        del transport._activity[:]
682
 
        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)
683
709
        self.assertEqual(70, index.key_count())
684
710
        # The entire index should have been read, as it is one page long.
685
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
686
 
            transport._activity)
687
 
        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())
688
733
 
689
734
    def test__read_nodes_no_size_one_page_reads_once(self):
690
735
        self.make_index(nodes=[(('key',), 'value', ())])
691
 
        trans = get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
692
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
693
738
        del trans._activity[:]
694
739
        nodes = dict(index._read_nodes([0]))
695
740
        self.assertEqual([0], nodes.keys())
696
741
        node = nodes[0]
697
 
        self.assertEqual([('key',)], node.keys.keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
698
743
        self.assertEqual([('get', 'index')], trans._activity)
699
744
 
700
745
    def test__read_nodes_no_size_multiple_pages(self):
702
747
        index.key_count()
703
748
        num_pages = index._row_offsets[-1]
704
749
        # Reopen with a traced transport and no size
705
 
        trans = get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
706
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
707
752
        del trans._activity[:]
708
753
        nodes = dict(index._read_nodes([0]))
713
758
        nodes = self.make_nodes(160, 2, 2)
714
759
        for node in nodes:
715
760
            builder.add_node(*node)
716
 
        transport = get_transport('trace+' + self.get_url(''))
717
 
        size = transport.put_file('index', builder.finish())
718
 
        self.assertEqual(17692, size)
719
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
720
 
        del transport._activity[:]
721
 
        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)
722
767
        self.assertEqual(320, index.key_count())
723
768
        # The entire index should not have been read.
724
769
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
725
 
            transport._activity)
 
770
                         t._activity)
726
771
 
727
772
    def test_validate_one_page(self):
728
773
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
729
774
        nodes = self.make_nodes(45, 2, 2)
730
775
        for node in nodes:
731
776
            builder.add_node(*node)
732
 
        transport = get_transport('trace+' + self.get_url(''))
733
 
        size = transport.put_file('index', builder.finish())
734
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
735
 
        del transport._activity[:]
736
 
        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)
737
782
        index.validate()
738
783
        # The entire index should have been read linearly.
739
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
740
 
            transport._activity)
741
 
        self.assertEqual(1488, size)
 
785
                         t._activity)
 
786
        self.assertEqualsApproxCompressed(1488, size)
742
787
 
743
788
    def test_validate_two_pages(self):
744
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
745
790
        nodes = self.make_nodes(80, 2, 2)
746
791
        for node in nodes:
747
792
            builder.add_node(*node)
748
 
        transport = get_transport('trace+' + self.get_url(''))
749
 
        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())
750
795
        # Root page, 2 leaf pages
751
 
        self.assertEqual(9339, size)
752
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
753
 
        del transport._activity[:]
754
 
        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)
755
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
756
802
        # The entire index should have been read linearly.
757
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
758
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
759
 
            transport._activity)
 
803
        self.assertEqual(
 
804
            [('readv', 'index', [(0, 4096)], False, None),
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
806
            t._activity)
760
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
761
808
        # node and make validate find them.
762
809
 
763
810
    def test_eq_ne(self):
764
811
        # two indices are equal when constructed with the same parameters:
765
 
        transport1 = get_transport('trace+' + self.get_url(''))
766
 
        transport2 = get_transport(self.get_url(''))
767
 
        self.assertTrue(
768
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
769
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
770
 
        self.assertTrue(
771
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
772
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
773
 
        self.assertFalse(
774
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
775
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
776
 
        self.assertFalse(
777
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
778
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
779
 
        self.assertFalse(
780
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
781
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
782
 
        self.assertFalse(
783
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
784
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
785
 
        self.assertFalse(
786
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
787
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
788
 
        self.assertTrue(
789
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
790
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
791
 
        self.assertTrue(
792
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
793
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
794
 
        self.assertTrue(
795
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
796
 
            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))
797
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
        
798
853
    def test_iter_all_only_root_no_size(self):
799
854
        self.make_index(nodes=[(('key',), 'value', ())])
800
 
        trans = get_transport('trace+' + self.get_url(''))
801
 
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
802
 
        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[:]
803
858
        self.assertEqual([(('key',), 'value')],
804
859
                         [x[1:] for x in index.iter_all_entries()])
805
 
        self.assertEqual([('get', 'index')], trans._activity)
 
860
        self.assertEqual([('get', 'index')], t._activity)
806
861
 
807
862
    def test_iter_all_entries_reads(self):
808
863
        # iterating all entries reads the header, then does a linear
814
869
        nodes = self.make_nodes(10000, 2, 2)
815
870
        for node in nodes:
816
871
            builder.add_node(*node)
817
 
        transport = get_transport('trace+' + self.get_url(''))
818
 
        size = transport.put_file('index', builder.finish())
819
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
820
 
                                        ' output changed')
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
873
        size = t.put_file('index', builder.finish())
821
874
        page_size = btree_index._PAGE_SIZE
822
875
        del builder
823
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
824
 
        del transport._activity[:]
825
 
        self.assertEqual([], transport._activity)
 
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
877
        del t._activity[:]
 
878
        self.assertEqual([], t._activity)
826
879
        found_nodes = self.time(list, index.iter_all_entries())
827
880
        bare_nodes = []
828
881
        for node in found_nodes:
839
892
        # The entire index should have been read
840
893
        total_pages = sum(index._row_lengths)
841
894
        self.assertEqual(total_pages, index._row_offsets[-1])
842
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
843
896
        # The start of the leaves
844
897
        first_byte = index._row_offsets[-2] * page_size
845
898
        readv_request = []
846
899
        for offset in range(first_byte, size, page_size):
847
900
            readv_request.append((offset, page_size))
848
901
        # The last page is truncated
849
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
850
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
851
904
             ('readv',  'index', readv_request, False, None)]
852
 
        if expected != transport._activity:
 
905
        if expected != t._activity:
853
906
            self.assertEqualDiff(pprint.pformat(expected),
854
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
855
908
 
856
909
    def _test_iter_entries_references_resolved(self):
857
910
        index = self.make_index(1, nodes=[
869
922
        nodes = self.make_nodes(160, 2, 2)
870
923
        for node in nodes:
871
924
            builder.add_node(*node)
872
 
        transport = get_transport('trace+' + self.get_url(''))
873
 
        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())
874
927
        del builder
875
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
876
 
        del transport._activity[:]
877
 
        self.assertEqual([], transport._activity)
 
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
929
        del t._activity[:]
 
930
        self.assertEqual([], t._activity)
878
931
        # search for one key
879
932
        found_nodes = list(index.iter_entries([nodes[30][0]]))
880
933
        bare_nodes = []
888
941
        # Should have read the root node, then one leaf page:
889
942
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
890
943
             ('readv',  'index', [(8192, 4096), ], False, None)],
891
 
            transport._activity)
 
944
            t._activity)
892
945
 
893
946
    def test_iter_key_prefix_1_element_key_None(self):
894
947
        index = self.make_index()
1077
1130
        min_l2_key = l2.min_key
1078
1131
        max_l1_key = l1.max_key
1079
1132
        self.assertTrue(max_l1_key < min_l2_key)
1080
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1133
        parents_min_l2_key = l2[min_l2_key][1][0]
1081
1134
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1082
1135
        # Now, whatever key we select that would fall on the second page,
1083
1136
        # should give us all the parents until the page break
1096
1149
        parent_map = {}
1097
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1098
1151
                                            missing_keys)
1099
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1152
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1100
1153
        self.assertEqual(set(), missing_keys)
1101
1154
        self.assertEqual(set(), search_keys)
1102
1155
 
1118
1171
        for node in nodes:
1119
1172
            builder.add_node(*node)
1120
1173
        stream = builder.finish()
1121
 
        trans = get_transport(self.get_url())
 
1174
        trans = self.get_transport()
1122
1175
        size = trans.put_file('index', stream)
1123
1176
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1124
1177
        self.assertEqual(500, index.key_count())
1150
1203
 
1151
1204
class TestBTreeNodes(BTreeTestCase):
1152
1205
 
 
1206
    scenarios = btreeparser_scenarios()
 
1207
 
1153
1208
    def setUp(self):
1154
 
        BTreeTestCase.setUp(self)
 
1209
        super(TestBTreeNodes, self).setUp()
1155
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1156
1211
 
1157
1212
    def test_LeafNode_1_0(self):
1170
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1171
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1172
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1173
 
            }, node.keys)
 
1228
            }, dict(node.all_items()))
1174
1229
 
1175
1230
    def test_LeafNode_2_2(self):
1176
1231
        node_bytes = ("type=leaf\n"
1190
1245
            ('11', '33'): ('value:3',
1191
1246
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1192
1247
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1193
 
            }, node.keys)
 
1248
            }, dict(node.all_items()))
1194
1249
 
1195
1250
    def test_InternalNode_1(self):
1196
1251
        node_bytes = ("type=internal\n"
1231
1286
            ('11', '33'): ('value:3',
1232
1287
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1233
1288
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1234
 
            }, node.keys)
 
1289
            }, dict(node.all_items()))
1235
1290
 
1236
1291
    def assertFlattened(self, expected, key, value, refs):
1237
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1315
1370
        This doesn't actually create anything on disk, it just primes a
1316
1371
        BTreeGraphIndex with the recommended information.
1317
1372
        """
1318
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1319
 
                                            'test-index', size=size)
 
1373
        index = btree_index.BTreeGraphIndex(
 
1374
            transport.get_transport_from_url('memory:///'),
 
1375
            'test-index', size=size)
1320
1376
        if recommended_pages is not None:
1321
1377
            index._recommended_pages = recommended_pages
1322
1378
        return index