← 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: Gary van der Merwe
  • Date: 2010-08-02 19:56:52 UTC
  • mfrom: (5050.3.18 2.2)
  • mto: (5050.3.19 2.2)
  • mto: This revision was merged to the branch mainline in revision 5371.
  • Revision ID: garyvdm@gmail.com-20100802195652-o1ppjemhwrr98i61
Merge lp:bzr/2.2.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
27
27
    lru_cache,
28
28
    osutils,
29
29
    tests,
 
30
    transport,
30
31
    )
31
32
from bzrlib.tests import (
32
33
    TestCaseWithTransport,
34
35
    multiply_tests,
35
36
    split_suite_by_condition,
36
37
    )
37
 
from bzrlib.transport import get_transport
38
38
 
39
39
 
40
40
def load_tests(standard_tests, module, loader):
280
280
 
281
281
        for node in nodes:
282
282
            builder.add_node(*node)
283
 
        transport = get_transport('trace+' + self.get_url(''))
284
 
        size = transport.put_file('index', self.time(builder.finish))
 
283
        t = transport.get_transport('trace+' + self.get_url(''))
 
284
        size = t.put_file('index', self.time(builder.finish))
285
285
        del builder
286
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
286
        index = btree_index.BTreeGraphIndex(t, 'index', size)
287
287
        # Seed the metadata, we're using internal calls now.
288
288
        index.key_count()
289
289
        self.assertEqual(3, len(index._row_lengths),
409
409
        self.assertEqual(None, builder._backing_indices[2])
410
410
        self.assertEqual(16, builder._backing_indices[3].key_count())
411
411
        # 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)
 
412
        t = self.get_transport('')
 
413
        size = t.put_file('index', builder.finish())
 
414
        index = btree_index.BTreeGraphIndex(t, 'index', size)
415
415
        nodes = list(index.iter_all_entries())
416
416
        self.assertEqual(sorted(nodes), nodes)
417
417
        self.assertEqual(16, len(nodes))
607
607
        for key, value, references in nodes:
608
608
            builder.add_node(key, value, references)
609
609
        stream = builder.finish()
610
 
        trans = get_transport('trace+' + self.get_url())
 
610
        trans = transport.get_transport('trace+' + self.get_url())
611
611
        size = trans.put_file('index', stream)
612
612
        return btree_index.BTreeGraphIndex(trans, 'index', size)
613
613
 
 
614
    def make_index_with_offset(self, ref_lists=1, key_elements=1, nodes=[],
 
615
                               offset=0):
 
616
        builder = btree_index.BTreeBuilder(key_elements=key_elements,
 
617
                                           reference_lists=ref_lists)
 
618
        builder.add_nodes(nodes)
 
619
        transport = self.get_transport('')
 
620
        # NamedTemporaryFile dies on builder.finish().read(). weird.
 
621
        temp_file = builder.finish()
 
622
        content = temp_file.read()
 
623
        del temp_file
 
624
        size = len(content)
 
625
        transport.put_bytes('index', (' '*offset)+content)
 
626
        return btree_index.BTreeGraphIndex(transport, 'index', size=size,
 
627
                                           offset=offset)
 
628
 
614
629
    def test_clear_cache(self):
615
630
        nodes = self.make_nodes(160, 2, 2)
616
631
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
633
648
        self.assertEqual(0, len(index._leaf_node_cache))
634
649
 
635
650
    def test_trivial_constructor(self):
636
 
        transport = get_transport('trace+' + self.get_url(''))
637
 
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
 
651
        t = transport.get_transport('trace+' + self.get_url(''))
 
652
        index = btree_index.BTreeGraphIndex(t, 'index', None)
638
653
        # Checks the page size at load, but that isn't logged yet.
639
 
        self.assertEqual([], transport._activity)
 
654
        self.assertEqual([], t._activity)
640
655
 
641
656
    def test_with_size_constructor(self):
642
 
        transport = get_transport('trace+' + self.get_url(''))
643
 
        index = btree_index.BTreeGraphIndex(transport, 'index', 1)
 
657
        t = transport.get_transport('trace+' + self.get_url(''))
 
658
        index = btree_index.BTreeGraphIndex(t, 'index', 1)
644
659
        # Checks the page size at load, but that isn't logged yet.
645
 
        self.assertEqual([], transport._activity)
 
660
        self.assertEqual([], t._activity)
646
661
 
647
662
    def test_empty_key_count_no_size(self):
648
663
        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)
 
664
        t = transport.get_transport('trace+' + self.get_url(''))
 
665
        t.put_file('index', builder.finish())
 
666
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
667
        del t._activity[:]
 
668
        self.assertEqual([], t._activity)
654
669
        self.assertEqual(0, index.key_count())
655
670
        # The entire index should have been requested (as we generally have the
656
671
        # size available, and doing many small readvs is inappropriate).
657
672
        # We can't tell how much was actually read here, but - check the code.
658
 
        self.assertEqual([('get', 'index')], transport._activity)
 
673
        self.assertEqual([('get', 'index')], t._activity)
659
674
 
660
675
    def test_empty_key_count(self):
661
676
        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())
 
677
        t = transport.get_transport('trace+' + self.get_url(''))
 
678
        size = t.put_file('index', builder.finish())
664
679
        self.assertEqual(72, size)
665
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
666
 
        del transport._activity[:]
667
 
        self.assertEqual([], transport._activity)
 
680
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
681
        del t._activity[:]
 
682
        self.assertEqual([], t._activity)
668
683
        self.assertEqual(0, index.key_count())
669
684
        # The entire index should have been read, as 4K > size
670
685
        self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
671
 
            transport._activity)
 
686
                         t._activity)
672
687
 
673
688
    def test_non_empty_key_count_2_2(self):
674
689
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
675
690
        nodes = self.make_nodes(35, 2, 2)
676
691
        for node in nodes:
677
692
            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)
 
693
        t = transport.get_transport('trace+' + self.get_url(''))
 
694
        size = t.put_file('index', builder.finish())
 
695
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
696
        del t._activity[:]
 
697
        self.assertEqual([], t._activity)
683
698
        self.assertEqual(70, index.key_count())
684
699
        # The entire index should have been read, as it is one page long.
685
700
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
686
 
            transport._activity)
 
701
            t._activity)
687
702
        self.assertEqual(1173, size)
688
703
 
 
704
    def test_with_offset_no_size(self):
 
705
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
706
                                            offset=1234,
 
707
                                            nodes=self.make_nodes(200, 1, 1))
 
708
        index._size = None # throw away the size info
 
709
        self.assertEqual(200, index.key_count())
 
710
 
 
711
    def test_with_small_offset(self):
 
712
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
713
                                            offset=1234,
 
714
                                            nodes=self.make_nodes(200, 1, 1))
 
715
        self.assertEqual(200, index.key_count())
 
716
 
 
717
    def test_with_large_offset(self):
 
718
        index = self.make_index_with_offset(key_elements=1, ref_lists=1,
 
719
                                            offset=123456,
 
720
                                            nodes=self.make_nodes(200, 1, 1))
 
721
        self.assertEqual(200, index.key_count())
 
722
 
689
723
    def test__read_nodes_no_size_one_page_reads_once(self):
690
724
        self.make_index(nodes=[(('key',), 'value', ())])
691
 
        trans = get_transport('trace+' + self.get_url())
 
725
        trans = transport.get_transport('trace+' + self.get_url())
692
726
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
693
727
        del trans._activity[:]
694
728
        nodes = dict(index._read_nodes([0]))
702
736
        index.key_count()
703
737
        num_pages = index._row_offsets[-1]
704
738
        # Reopen with a traced transport and no size
705
 
        trans = get_transport('trace+' + self.get_url())
 
739
        trans = transport.get_transport('trace+' + self.get_url())
706
740
        index = btree_index.BTreeGraphIndex(trans, 'index', None)
707
741
        del trans._activity[:]
708
742
        nodes = dict(index._read_nodes([0]))
713
747
        nodes = self.make_nodes(160, 2, 2)
714
748
        for node in nodes:
715
749
            builder.add_node(*node)
716
 
        transport = get_transport('trace+' + self.get_url(''))
717
 
        size = transport.put_file('index', builder.finish())
 
750
        t = transport.get_transport('trace+' + self.get_url(''))
 
751
        size = t.put_file('index', builder.finish())
718
752
        self.assertEqual(17692, size)
719
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
720
 
        del transport._activity[:]
721
 
        self.assertEqual([], transport._activity)
 
753
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
754
        del t._activity[:]
 
755
        self.assertEqual([], t._activity)
722
756
        self.assertEqual(320, index.key_count())
723
757
        # The entire index should not have been read.
724
758
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
725
 
            transport._activity)
 
759
                         t._activity)
726
760
 
727
761
    def test_validate_one_page(self):
728
762
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
729
763
        nodes = self.make_nodes(45, 2, 2)
730
764
        for node in nodes:
731
765
            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)
 
766
        t = transport.get_transport('trace+' + self.get_url(''))
 
767
        size = t.put_file('index', builder.finish())
 
768
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
769
        del t._activity[:]
 
770
        self.assertEqual([], t._activity)
737
771
        index.validate()
738
772
        # The entire index should have been read linearly.
739
773
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
740
 
            transport._activity)
 
774
                         t._activity)
741
775
        self.assertEqual(1488, size)
742
776
 
743
777
    def test_validate_two_pages(self):
745
779
        nodes = self.make_nodes(80, 2, 2)
746
780
        for node in nodes:
747
781
            builder.add_node(*node)
748
 
        transport = get_transport('trace+' + self.get_url(''))
749
 
        size = transport.put_file('index', builder.finish())
 
782
        t = transport.get_transport('trace+' + self.get_url(''))
 
783
        size = t.put_file('index', builder.finish())
750
784
        # Root page, 2 leaf pages
751
785
        self.assertEqual(9339, size)
752
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
753
 
        del transport._activity[:]
754
 
        self.assertEqual([], transport._activity)
 
786
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
787
        del t._activity[:]
 
788
        self.assertEqual([], t._activity)
755
789
        index.validate()
756
790
        # 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)
 
791
        self.assertEqual(
 
792
            [('readv', 'index', [(0, 4096)], False, None),
 
793
             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
 
794
            t._activity)
760
795
        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
761
796
        # node and make validate find them.
762
797
 
763
798
    def test_eq_ne(self):
764
799
        # 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))
 
800
        t1 = transport.get_transport('trace+' + self.get_url(''))
 
801
        t2 = transport.get_transport(self.get_url(''))
 
802
        self.assertTrue(
 
803
            btree_index.BTreeGraphIndex(t1, 'index', None) ==
 
804
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
805
        self.assertTrue(
 
806
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
807
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
808
        self.assertFalse(
 
809
            btree_index.BTreeGraphIndex(t1, 'index', 20) ==
 
810
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
811
        self.assertFalse(
 
812
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
 
813
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
814
        self.assertFalse(
 
815
            btree_index.BTreeGraphIndex(t1, 'index', 10) ==
 
816
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
817
        self.assertFalse(
 
818
            btree_index.BTreeGraphIndex(t1, 'index', None) !=
 
819
            btree_index.BTreeGraphIndex(t1, 'index', None))
 
820
        self.assertFalse(
 
821
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
822
            btree_index.BTreeGraphIndex(t1, 'index', 20))
 
823
        self.assertTrue(
 
824
            btree_index.BTreeGraphIndex(t1, 'index', 20) !=
 
825
            btree_index.BTreeGraphIndex(t2, 'index', 20))
 
826
        self.assertTrue(
 
827
            btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
 
828
            btree_index.BTreeGraphIndex(t1, 'inde2', 20))
 
829
        self.assertTrue(
 
830
            btree_index.BTreeGraphIndex(t1, 'index', 10) !=
 
831
            btree_index.BTreeGraphIndex(t1, 'index', 20))
797
832
 
798
833
    def test_iter_all_only_root_no_size(self):
799
834
        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[:]
 
835
        t = transport.get_transport('trace+' + self.get_url(''))
 
836
        index = btree_index.BTreeGraphIndex(t, 'index', None)
 
837
        del t._activity[:]
803
838
        self.assertEqual([(('key',), 'value')],
804
839
                         [x[1:] for x in index.iter_all_entries()])
805
 
        self.assertEqual([('get', 'index')], trans._activity)
 
840
        self.assertEqual([('get', 'index')], t._activity)
806
841
 
807
842
    def test_iter_all_entries_reads(self):
808
843
        # iterating all entries reads the header, then does a linear
814
849
        nodes = self.make_nodes(10000, 2, 2)
815
850
        for node in nodes:
816
851
            builder.add_node(*node)
817
 
        transport = get_transport('trace+' + self.get_url(''))
818
 
        size = transport.put_file('index', builder.finish())
 
852
        t = transport.get_transport('trace+' + self.get_url(''))
 
853
        size = t.put_file('index', builder.finish())
819
854
        self.assertEqual(1303220, size, 'number of expected bytes in the'
820
855
                                        ' output changed')
821
856
        page_size = btree_index._PAGE_SIZE
822
857
        del builder
823
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
824
 
        del transport._activity[:]
825
 
        self.assertEqual([], transport._activity)
 
858
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
859
        del t._activity[:]
 
860
        self.assertEqual([], t._activity)
826
861
        found_nodes = self.time(list, index.iter_all_entries())
827
862
        bare_nodes = []
828
863
        for node in found_nodes:
849
884
        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
850
885
        expected = [('readv', 'index', [(0, page_size)], False, None),
851
886
             ('readv',  'index', readv_request, False, None)]
852
 
        if expected != transport._activity:
 
887
        if expected != t._activity:
853
888
            self.assertEqualDiff(pprint.pformat(expected),
854
889
                                 pprint.pformat(transport._activity))
855
890
 
869
904
        nodes = self.make_nodes(160, 2, 2)
870
905
        for node in nodes:
871
906
            builder.add_node(*node)
872
 
        transport = get_transport('trace+' + self.get_url(''))
873
 
        size = transport.put_file('index', builder.finish())
 
907
        t = transport.get_transport('trace+' + self.get_url(''))
 
908
        size = t.put_file('index', builder.finish())
874
909
        del builder
875
 
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
876
 
        del transport._activity[:]
877
 
        self.assertEqual([], transport._activity)
 
910
        index = btree_index.BTreeGraphIndex(t, 'index', size)
 
911
        del t._activity[:]
 
912
        self.assertEqual([], t._activity)
878
913
        # search for one key
879
914
        found_nodes = list(index.iter_entries([nodes[30][0]]))
880
915
        bare_nodes = []
888
923
        # Should have read the root node, then one leaf page:
889
924
        self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
890
925
             ('readv',  'index', [(8192, 4096), ], False, None)],
891
 
            transport._activity)
 
926
            t._activity)
892
927
 
893
928
    def test_iter_key_prefix_1_element_key_None(self):
894
929
        index = self.make_index()
1118
1153
        for node in nodes:
1119
1154
            builder.add_node(*node)
1120
1155
        stream = builder.finish()
1121
 
        trans = get_transport(self.get_url())
 
1156
        trans = transport.get_transport(self.get_url())
1122
1157
        size = trans.put_file('index', stream)
1123
1158
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
1124
1159
        self.assertEqual(500, index.key_count())
1315
1350
        This doesn't actually create anything on disk, it just primes a
1316
1351
        BTreeGraphIndex with the recommended information.
1317
1352
        """
1318
 
        index = btree_index.BTreeGraphIndex(get_transport('memory:///'),
1319
 
                                            'test-index', size=size)
 
1353
        index = btree_index.BTreeGraphIndex(
 
1354
            transport.get_transport('memory:///'), 'test-index', size=size)
1320
1355
        if recommended_pages is not None:
1321
1356
            index._recommended_pages = recommended_pages
1322
1357
        return index