← 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: 2013-05-24 23:50:40 UTC
  • mto: This revision was merged to the branch mainline in revision 6576.
  • Revision ID: v.ladeuil+lp@free.fr-20130524235040-2wcup9uokmbn346p
Simpler.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 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
 
648
659
        self.assertEqual(0, len(index._leaf_node_cache))
649
660
 
650
661
    def test_trivial_constructor(self):
651
 
        transport = get_transport('trace+' + self.get_url(''))
652
 
        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)
653
664
        # Checks the page size at load, but that isn't logged yet.
654
 
        self.assertEqual([], transport._activity)
 
665
        self.assertEqual([], t._activity)
655
666
 
656
667
    def test_with_size_constructor(self):
657
 
        transport = get_transport('trace+' + self.get_url(''))
658
 
        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)
659
670
        # Checks the page size at load, but that isn't logged yet.
660
 
        self.assertEqual([], transport._activity)
 
671
        self.assertEqual([], t._activity)
661
672
 
662
673
    def test_empty_key_count_no_size(self):
663
674
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
664
 
        transport = get_transport('trace+' + self.get_url(''))
665
 
        transport.put_file('index', builder.finish())
666
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
667
 
        del transport._activity[:]
668
 
        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)
669
680
        self.assertEqual(0, index.key_count())
670
681
        # The entire index should have been requested (as we generally have the
671
682
        # size available, and doing many small readvs is inappropriate).
672
683
        # We can't tell how much was actually read here, but - check the code.
673
 
        self.assertEqual([('get', 'index')], transport._activity)
 
684
        self.assertEqual([('get', 'index')], t._activity)
674
685
 
675
686
    def test_empty_key_count(self):
676
687
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
 
        transport = get_transport('trace+' + self.get_url(''))
678
 
        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())
679
690
        self.assertEqual(72, size)
680
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
681
 
        del transport._activity[:]
682
 
        self.assertEqual([], transport._activity)
 
691
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
692
        del t._activity[:]
 
693
        self.assertEqual([], t._activity)
683
694
        self.assertEqual(0, index.key_count())
684
695
        # The entire index should have been read, as 4K > size
685
696
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
686
 
            transport._activity)
 
697
                         t._activity)
687
698
 
688
699
    def test_non_empty_key_count_2_2(self):
689
700
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
690
701
        nodes = self.make_nodes(35, 2, 2)
691
702
        for node in nodes:
692
703
            builder.add_node(*node)
693
 
        transport = get_transport('trace+' + self.get_url(''))
694
 
        size = transport.put_file('index', builder.finish())
695
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
696
 
        del transport._activity[:]
697
 
        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)
698
709
        self.assertEqual(70, index.key_count())
699
710
        # The entire index should have been read, as it is one page long.
700
711
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
701
 
            transport._activity)
702
 
        self.assertEqual(1173, size)
 
712
            t._activity)
 
713
        self.assertEqualsApproxCompressed(1173, size)
703
714
 
704
715
    def test_with_offset_no_size(self):
705
716
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
722
733
 
723
734
    def test__read_nodes_no_size_one_page_reads_once(self):
724
735
        self.make_index(nodes=[(('key',), 'value', ())])
725
 
        trans = get_transport('trace+' + self.get_url())
 
736
        trans = transport.get_transport_from_url('trace+' + self.get_url())
726
737
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
727
738
        del trans._activity[:]
728
739
        nodes = dict(index._read_nodes([0]))
729
740
        self.assertEqual([0], nodes.keys())
730
741
        node = nodes[0]
731
 
        self.assertEqual([('key',)], node.keys.keys())
 
742
        self.assertEqual([('key',)], node.all_keys())
732
743
        self.assertEqual([('get', 'index')], trans._activity)
733
744
 
734
745
    def test__read_nodes_no_size_multiple_pages(self):
736
747
        index.key_count()
737
748
        num_pages = index._row_offsets[-1]
738
749
        # Reopen with a traced transport and no size
739
 
        trans = get_transport('trace+' + self.get_url())
 
750
        trans = transport.get_transport_from_url('trace+' + self.get_url())
740
751
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
752
        del trans._activity[:]
742
753
        nodes = dict(index._read_nodes([0]))
747
758
        nodes = self.make_nodes(160, 2, 2)
748
759
        for node in nodes:
749
760
            builder.add_node(*node)
750
 
        transport = get_transport('trace+' + self.get_url(''))
751
 
        size = transport.put_file('index', builder.finish())
752
 
        self.assertEqual(17692, size)
753
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
754
 
        del transport._activity[:]
755
 
        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)
756
767
        self.assertEqual(320, index.key_count())
757
768
        # The entire index should not have been read.
758
769
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
759
 
            transport._activity)
 
770
                         t._activity)
760
771
 
761
772
    def test_validate_one_page(self):
762
773
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
763
774
        nodes = self.make_nodes(45, 2, 2)
764
775
        for node in nodes:
765
776
            builder.add_node(*node)
766
 
        transport = get_transport('trace+' + self.get_url(''))
767
 
        size = transport.put_file('index', builder.finish())
768
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
769
 
        del transport._activity[:]
770
 
        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)
771
782
        index.validate()
772
783
        # The entire index should have been read linearly.
773
784
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
774
 
            transport._activity)
775
 
        self.assertEqual(1488, size)
 
785
                         t._activity)
 
786
        self.assertEqualsApproxCompressed(1488, size)
776
787
 
777
788
    def test_validate_two_pages(self):
778
789
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
790
        nodes = self.make_nodes(80, 2, 2)
780
791
        for node in nodes:
781
792
            builder.add_node(*node)
782
 
        transport = get_transport('trace+' + self.get_url(''))
783
 
        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())
784
795
        # Root page, 2 leaf pages
785
 
        self.assertEqual(9339, size)
786
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
787
 
        del transport._activity[:]
788
 
        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)
789
800
        index.validate()
 
801
        rem = size - 8192 # Number of remaining bytes after second block
790
802
        # The entire index should have been read linearly.
791
 
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
792
 
            ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
793
 
            transport._activity)
 
803
        self.assertEqual(
 
804
            [('readv', 'index', [(0, 4096)], False, None),
 
805
             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
 
806
            t._activity)
794
807
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
795
808
        # node and make validate find them.
796
809
 
797
810
    def test_eq_ne(self):
798
811
        # two indices are equal when constructed with the same parameters:
799
 
        transport1 = get_transport('trace+' + self.get_url(''))
800
 
        transport2 = get_transport(self.get_url(''))
801
 
        self.assertTrue(
802
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) ==
803
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
804
 
        self.assertTrue(
805
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
806
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
807
 
        self.assertFalse(
808
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
809
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
810
 
        self.assertFalse(
811
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
812
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
813
 
        self.assertFalse(
814
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
815
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
816
 
        self.assertFalse(
817
 
            btree_index.BTreeGraphIndex(transport1, 'index', None) !=
818
 
            btree_index.BTreeGraphIndex(transport1, 'index', None))
819
 
        self.assertFalse(
820
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
821
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20))
822
 
        self.assertTrue(
823
 
            btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
824
 
            btree_index.BTreeGraphIndex(transport2, 'index', 20))
825
 
        self.assertTrue(
826
 
            btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
827
 
            btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
828
 
        self.assertTrue(
829
 
            btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
830
 
            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))
831
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
        
832
853
    def test_iter_all_only_root_no_size(self):
833
854
        self.make_index(nodes=[(('key',), 'value', ())])
834
 
        trans = get_transport('trace+' + self.get_url(''))
835
 
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
836
 
        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[:]
837
858
        self.assertEqual([(('key',), 'value')],
838
859
                         [x[1:] for x in index.iter_all_entries()])
839
 
        self.assertEqual([('get', 'index')], trans._activity)
 
860
        self.assertEqual([('get', 'index')], t._activity)
840
861
 
841
862
    def test_iter_all_entries_reads(self):
842
863
        # iterating all entries reads the header, then does a linear
848
869
        nodes = self.make_nodes(10000, 2, 2)
849
870
        for node in nodes:
850
871
            builder.add_node(*node)
851
 
        transport = get_transport('trace+' + self.get_url(''))
852
 
        size = transport.put_file('index', builder.finish())
853
 
        self.assertEqual(1303220, size, 'number of expected bytes in the'
854
 
                                        ' output changed')
 
872
        t = transport.get_transport_from_url('trace+' + self.get_url(''))
 
873
        size = t.put_file('index', builder.finish())
855
874
        page_size = btree_index._PAGE_SIZE
856
875
        del builder
857
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
858
 
        del transport._activity[:]
859
 
        self.assertEqual([], transport._activity)
 
876
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
877
        del t._activity[:]
 
878
        self.assertEqual([], t._activity)
860
879
        found_nodes = self.time(list, index.iter_all_entries())
861
880
        bare_nodes = []
862
881
        for node in found_nodes:
873
892
        # The entire index should have been read
874
893
        total_pages = sum(index._row_lengths)
875
894
        self.assertEqual(total_pages, index._row_offsets[-1])
876
 
        self.assertEqual(1303220, size)
 
895
        self.assertEqualsApproxCompressed(1303220, size)
877
896
        # The start of the leaves
878
897
        first_byte = index._row_offsets[-2] * page_size
879
898
        readv_request = []
880
899
        for offset in range(first_byte, size, page_size):
881
900
            readv_request.append((offset, page_size))
882
901
        # The last page is truncated
883
 
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
 
902
        readv_request[-1] = (readv_request[-1][0], size % page_size)
884
903
        expected = [('readv', 'index', [(0, page_size)], False, None),
885
904
             ('readv',  'index', readv_request, False, None)]
886
 
        if expected != transport._activity:
 
905
        if expected != t._activity:
887
906
            self.assertEqualDiff(pprint.pformat(expected),
888
 
                                 pprint.pformat(transport._activity))
 
907
                                 pprint.pformat(t._activity))
889
908
 
890
909
    def _test_iter_entries_references_resolved(self):
891
910
        index = self.make_index(1, nodes=[
903
922
        nodes = self.make_nodes(160, 2, 2)
904
923
        for node in nodes:
905
924
            builder.add_node(*node)
906
 
        transport = get_transport('trace+' + self.get_url(''))
907
 
        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())
908
927
        del builder
909
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
910
 
        del transport._activity[:]
911
 
        self.assertEqual([], transport._activity)
 
928
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
929
        del t._activity[:]
 
930
        self.assertEqual([], t._activity)
912
931
        # search for one key
913
932
        found_nodes = list(index.iter_entries([nodes[30][0]]))
914
933
        bare_nodes = []
922
941
        # Should have read the root node, then one leaf page:
923
942
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
924
943
             ('readv',  'index', [(8192, 4096), ], False, None)],
925
 
            transport._activity)
 
944
            t._activity)
926
945
 
927
946
    def test_iter_key_prefix_1_element_key_None(self):
928
947
        index = self.make_index()
1111
1130
        min_l2_key = l2.min_key
1112
1131
        max_l1_key = l1.max_key
1113
1132
        self.assertTrue(max_l1_key < min_l2_key)
1114
 
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1133
        parents_min_l2_key = l2[min_l2_key][1][0]
1115
1134
        self.assertEqual((l1.max_key,), parents_min_l2_key)
1116
1135
        # Now, whatever key we select that would fall on the second page,
1117
1136
        # should give us all the parents until the page break
1130
1149
        parent_map = {}
1131
1150
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
1132
1151
                                            missing_keys)
1133
 
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1152
        self.assertEqual(l1.all_keys(), sorted(parent_map))
1134
1153
        self.assertEqual(set(), missing_keys)
1135
1154
        self.assertEqual(set(), search_keys)
1136
1155
 
1152
1171
        for node in nodes:
1153
1172
            builder.add_node(*node)
1154
1173
        stream = builder.finish()
1155
 
        trans = get_transport(self.get_url())
 
1174
        trans = self.get_transport()
1156
1175
        size = trans.put_file('index', stream)
1157
1176
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1158
1177
        self.assertEqual(500, index.key_count())
1184
1203
 
1185
1204
class TestBTreeNodes(BTreeTestCase):
1186
1205
 
 
1206
    scenarios = btreeparser_scenarios()
 
1207
 
1187
1208
    def setUp(self):
1188
 
        BTreeTestCase.setUp(self)
 
1209
        super(TestBTreeNodes, self).setUp()
1189
1210
        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1190
1211
 
1191
1212
    def test_LeafNode_1_0(self):
1204
1225
            ("2222222222222222222222222222222222222222",): ("value:2", ()),
1205
1226
            ("3333333333333333333333333333333333333333",): ("value:3", ()),
1206
1227
            ("4444444444444444444444444444444444444444",): ("value:4", ()),
1207
 
            }, node.keys)
 
1228
            }, dict(node.all_items()))
1208
1229
 
1209
1230
    def test_LeafNode_2_2(self):
1210
1231
        node_bytes = ("type=leaf\n"
1224
1245
            ('11', '33'): ('value:3',
1225
1246
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1226
1247
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1227
 
            }, node.keys)
 
1248
            }, dict(node.all_items()))
1228
1249
 
1229
1250
    def test_InternalNode_1(self):
1230
1251
        node_bytes = ("type=internal\n"
1265
1286
            ('11', '33'): ('value:3',
1266
1287
                ((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1267
1288
            ('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1268
 
            }, node.keys)
 
1289
            }, dict(node.all_items()))
1269
1290
 
1270
1291
    def assertFlattened(self, expected, key, value, refs):
1271
1292
        flat_key, flat_line = self.parse_btree._flatten_node(
1349
1370
        This doesn't actually create anything on disk, it just primes a
1350
1371
        BTreeGraphIndex with the recommended information.
1351
1372
        """
1352
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1353
 
                                            'test-index', size=size)
 
1373
        index = btree_index.BTreeGraphIndex(
 
1374
            transport.get_transport_from_url('memory:///'),
 
1375
            'test-index', size=size)
1354
1376
        if recommended_pages is not None:
1355
1377
            index._recommended_pages = recommended_pages
1356
1378
        return index