← 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: Andrew Bennetts
  • Date: 2010-01-15 05:30:30 UTC
  • mto: (4973.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4975.
  • Revision ID: andrew.bennetts@canonical.com-20100115053030-1d6qd89pnj8hmb55
Pass kinds (not pairs) to MergeHookParams.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 2009 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
#
17
17
 
18
18
"""Tests for btree indices."""
23
23
from bzrlib import (
24
24
    btree_index,
25
25
    errors,
 
26
    fifo_cache,
 
27
    lru_cache,
 
28
    osutils,
26
29
    tests,
27
30
    )
28
31
from bzrlib.tests import (
29
32
    TestCaseWithTransport,
30
 
    TestScenarioApplier,
31
 
    adapt_tests,
32
33
    condition_isinstance,
 
34
    multiply_tests,
33
35
    split_suite_by_condition,
34
36
    )
35
37
from bzrlib.transport import get_transport
39
41
    # parameterise the TestBTreeNodes tests
40
42
    node_tests, others = split_suite_by_condition(standard_tests,
41
43
        condition_isinstance(TestBTreeNodes))
42
 
    applier = TestScenarioApplier()
43
44
    import bzrlib._btree_serializer_py as py_module
44
 
    applier.scenarios = [('python', {'parse_btree': py_module})]
45
 
    if CompiledBtreeParserFeature.available():
46
 
        # Is there a way to do this that gets missing feature failures rather
47
 
        # than no indication to the user?
48
 
        import bzrlib._btree_serializer_c as c_module
49
 
        applier.scenarios.append(('C', {'parse_btree': c_module}))
50
 
    adapt_tests(node_tests, applier, others)
51
 
    return others
52
 
 
53
 
 
54
 
class _CompiledBtreeParserFeature(tests.Feature):
55
 
    def _probe(self):
56
 
        try:
57
 
            import bzrlib._btree_serializer_c
58
 
        except ImportError:
59
 
            return False
60
 
        return True
61
 
 
62
 
    def feature_name(self):
63
 
        return 'bzrlib._btree_serializer_c'
64
 
 
65
 
CompiledBtreeParserFeature = _CompiledBtreeParserFeature()
 
45
    scenarios = [('python', {'parse_btree': py_module})]
 
46
    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')
66
54
 
67
55
 
68
56
class BTreeTestCase(TestCaseWithTransport):
124
112
 
125
113
class TestBTreeBuilder(BTreeTestCase):
126
114
 
 
115
    def test_clear_cache(self):
 
116
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
117
        # This is a no-op, but we need the api to be consistent with other
 
118
        # BTreeGraphIndex apis.
 
119
        builder.clear_cache()
 
120
 
127
121
    def test_empty_1_0(self):
128
122
        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
129
123
        # NamedTemporaryFile dies on builder.finish().read(). weird.
155
149
        temp_file = builder.finish()
156
150
        content = temp_file.read()
157
151
        del temp_file
158
 
        self.assertEqual(158, len(content))
 
152
        self.assertEqual(131, len(content))
159
153
        self.assertEqual(
160
154
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=5\n"
161
155
            "row_lengths=1\n",
179
173
        temp_file = builder.finish()
180
174
        content = temp_file.read()
181
175
        del temp_file
182
 
        self.assertEqual(264, len(content))
 
176
        self.assertEqual(238, len(content))
183
177
        self.assertEqual(
184
178
            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=10\n"
185
179
            "row_lengths=1\n",
245
239
        temp_file = builder.finish()
246
240
        content = temp_file.read()
247
241
        del temp_file
248
 
        self.assertEqual(181, len(content))
 
242
        self.assertEqual(155, len(content))
249
243
        self.assertEqual(
250
244
            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"
251
245
            "row_lengths=1\n",
353
347
        # Test the parts of the index that take up memory are doing so
354
348
        # predictably.
355
349
        self.assertEqual(1, len(builder._nodes))
356
 
        self.assertEqual(1, len(builder._keys))
357
350
        self.assertIs(None, builder._nodes_by_key)
358
351
        builder.add_node(*nodes[1])
359
352
        self.assertEqual(0, len(builder._nodes))
360
 
        self.assertEqual(0, len(builder._keys))
361
353
        self.assertIs(None, builder._nodes_by_key)
362
354
        self.assertEqual(1, len(builder._backing_indices))
363
355
        self.assertEqual(2, builder._backing_indices[0].key_count())
364
356
        # now back to memory
365
357
        builder.add_node(*nodes[2])
366
358
        self.assertEqual(1, len(builder._nodes))
367
 
        self.assertEqual(1, len(builder._keys))
368
359
        self.assertIs(None, builder._nodes_by_key)
369
360
        # And spills to a second backing index combing all
370
361
        builder.add_node(*nodes[3])
371
362
        self.assertEqual(0, len(builder._nodes))
372
 
        self.assertEqual(0, len(builder._keys))
373
363
        self.assertIs(None, builder._nodes_by_key)
374
364
        self.assertEqual(2, len(builder._backing_indices))
375
365
        self.assertEqual(None, builder._backing_indices[0])
378
368
        builder.add_node(*nodes[4])
379
369
        builder.add_node(*nodes[5])
380
370
        self.assertEqual(0, len(builder._nodes))
381
 
        self.assertEqual(0, len(builder._keys))
382
371
        self.assertIs(None, builder._nodes_by_key)
383
372
        self.assertEqual(2, len(builder._backing_indices))
384
373
        self.assertEqual(2, builder._backing_indices[0].key_count())
434
423
        self.assertEqual(sorted(nodes), nodes)
435
424
        self.assertEqual(16, len(nodes))
436
425
 
 
426
    def test_spill_index_stress_1_1_no_combine(self):
 
427
        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
 
428
        builder.set_optimize(for_size=False, combine_backing_indices=False)
 
429
        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
 
430
        builder.add_node(*nodes[0])
 
431
        # Test the parts of the index that take up memory are doing so
 
432
        # predictably.
 
433
        self.assertEqual(1, len(builder._nodes))
 
434
        self.assertIs(None, builder._nodes_by_key)
 
435
        builder.add_node(*nodes[1])
 
436
        self.assertEqual(0, len(builder._nodes))
 
437
        self.assertIs(None, builder._nodes_by_key)
 
438
        self.assertEqual(1, len(builder._backing_indices))
 
439
        self.assertEqual(2, builder._backing_indices[0].key_count())
 
440
        # now back to memory
 
441
        builder.add_node(*nodes[2])
 
442
        self.assertEqual(1, len(builder._nodes))
 
443
        self.assertIs(None, builder._nodes_by_key)
 
444
        # And spills to a second backing index but doesn't combine
 
445
        builder.add_node(*nodes[3])
 
446
        self.assertEqual(0, len(builder._nodes))
 
447
        self.assertIs(None, builder._nodes_by_key)
 
448
        self.assertEqual(2, len(builder._backing_indices))
 
449
        for backing_index in builder._backing_indices:
 
450
            self.assertEqual(2, backing_index.key_count())
 
451
        # The next spills to the 3rd slot
 
452
        builder.add_node(*nodes[4])
 
453
        builder.add_node(*nodes[5])
 
454
        self.assertEqual(0, len(builder._nodes))
 
455
        self.assertIs(None, builder._nodes_by_key)
 
456
        self.assertEqual(3, len(builder._backing_indices))
 
457
        for backing_index in builder._backing_indices:
 
458
            self.assertEqual(2, backing_index.key_count())
 
459
        # Now spill a few more, and check that we don't combine
 
460
        builder.add_node(*nodes[6])
 
461
        builder.add_node(*nodes[7])
 
462
        builder.add_node(*nodes[8])
 
463
        builder.add_node(*nodes[9])
 
464
        builder.add_node(*nodes[10])
 
465
        builder.add_node(*nodes[11])
 
466
        builder.add_node(*nodes[12])
 
467
        self.assertEqual(6, len(builder._backing_indices))
 
468
        for backing_index in builder._backing_indices:
 
469
            self.assertEqual(2, backing_index.key_count())
 
470
        # Test that memory and disk are both used for query methods; and that
 
471
        # None is skipped over happily.
 
472
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
 
473
            list(builder.iter_all_entries()))
 
474
        # Two nodes - one memory one disk
 
475
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
476
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
477
        self.assertEqual(13, builder.key_count())
 
478
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
479
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
480
        builder.add_node(*nodes[13])
 
481
        builder.add_node(*nodes[14])
 
482
        builder.add_node(*nodes[15])
 
483
        self.assertEqual(8, len(builder._backing_indices))
 
484
        for backing_index in builder._backing_indices:
 
485
            self.assertEqual(2, backing_index.key_count())
 
486
        # Now finish, and check we got a correctly ordered tree
 
487
        transport = self.get_transport('')
 
488
        size = transport.put_file('index', builder.finish())
 
489
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
490
        nodes = list(index.iter_all_entries())
 
491
        self.assertEqual(sorted(nodes), nodes)
 
492
        self.assertEqual(16, len(nodes))
 
493
 
437
494
    def test_set_optimize(self):
438
495
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
439
496
        builder.set_optimize(for_size=True)
440
497
        self.assertTrue(builder._optimize_for_size)
441
498
        builder.set_optimize(for_size=False)
442
499
        self.assertFalse(builder._optimize_for_size)
 
500
        # test that we can set combine_backing_indices without effecting
 
501
        # _optimize_for_size
 
502
        obj = object()
 
503
        builder._optimize_for_size = obj
 
504
        builder.set_optimize(combine_backing_indices=False)
 
505
        self.assertFalse(builder._combine_backing_indices)
 
506
        self.assertIs(obj, builder._optimize_for_size)
 
507
        builder.set_optimize(combine_backing_indices=True)
 
508
        self.assertTrue(builder._combine_backing_indices)
 
509
        self.assertIs(obj, builder._optimize_for_size)
443
510
 
444
511
    def test_spill_index_stress_2_2(self):
445
512
        # test that references and longer keys don't confuse things.
449
516
        builder.add_node(*nodes[0])
450
517
        # Test the parts of the index that take up memory are doing so
451
518
        # predictably.
452
 
        self.assertEqual(1, len(builder._keys))
453
519
        self.assertEqual(1, len(builder._nodes))
454
520
        self.assertIs(None, builder._nodes_by_key)
455
521
        builder.add_node(*nodes[1])
456
 
        self.assertEqual(0, len(builder._keys))
457
522
        self.assertEqual(0, len(builder._nodes))
458
523
        self.assertIs(None, builder._nodes_by_key)
459
524
        self.assertEqual(1, len(builder._backing_indices))
462
527
        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict
463
528
        builder.add_node(*nodes[2])
464
529
        self.assertEqual(1, len(builder._nodes))
465
 
        self.assertEqual(1, len(builder._keys))
466
530
        self.assertIsNot(None, builder._nodes_by_key)
467
531
        self.assertNotEqual({}, builder._nodes_by_key)
468
532
        # We should have a new entry
470
534
        # And spills to a second backing index combing all
471
535
        builder.add_node(*nodes[3])
472
536
        self.assertEqual(0, len(builder._nodes))
473
 
        self.assertEqual(0, len(builder._keys))
474
537
        self.assertIs(None, builder._nodes_by_key)
475
538
        self.assertEqual(2, len(builder._backing_indices))
476
539
        self.assertEqual(None, builder._backing_indices[0])
479
542
        builder.add_node(*nodes[4])
480
543
        builder.add_node(*nodes[5])
481
544
        self.assertEqual(0, len(builder._nodes))
482
 
        self.assertEqual(0, len(builder._keys))
483
545
        self.assertIs(None, builder._nodes_by_key)
484
546
        self.assertEqual(2, len(builder._backing_indices))
485
547
        self.assertEqual(2, builder._backing_indices[0].key_count())
556
618
        size = trans.put_file('index', stream)
557
619
        return btree_index.BTreeGraphIndex(trans, 'index', size)
558
620
 
 
621
    def test_clear_cache(self):
 
622
        nodes = self.make_nodes(160, 2, 2)
 
623
        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)
 
624
        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))
 
625
        self.assertEqual([1, 4], index._row_lengths)
 
626
        self.assertIsNot(None, index._root_node)
 
627
        internal_node_pre_clear = index._internal_node_cache.keys()
 
628
        self.assertTrue(len(index._leaf_node_cache) > 0)
 
629
        index.clear_cache()
 
630
        # We don't touch _root_node or _internal_node_cache, both should be
 
631
        # small, and can save a round trip or two
 
632
        self.assertIsNot(None, index._root_node)
 
633
        # NOTE: We don't want to affect the _internal_node_cache, as we expect
 
634
        #       it will be small, and if we ever do touch this index again, it
 
635
        #       will save round-trips.  This assertion isn't very strong,
 
636
        #       becuase without a 3-level index, we don't have any internal
 
637
        #       nodes cached.
 
638
        self.assertEqual(internal_node_pre_clear,
 
639
                         index._internal_node_cache.keys())
 
640
        self.assertEqual(0, len(index._leaf_node_cache))
 
641
 
559
642
    def test_trivial_constructor(self):
560
643
        transport = get_transport('trace+' + self.get_url(''))
561
644
        index = btree_index.BTreeGraphIndex(transport, 'index', None)
608
691
        # The entire index should have been read, as it is one page long.
609
692
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
610
693
            transport._activity)
611
 
        self.assertEqual(1199, size)
 
694
        self.assertEqual(1173, size)
612
695
 
613
696
    def test__read_nodes_no_size_one_page_reads_once(self):
614
697
        self.make_index(nodes=[(('key',), 'value', ())])
662
745
        # The entire index should have been read linearly.
663
746
        self.assertEqual([('readv', 'index', [(0, size)], False, None)],
664
747
            transport._activity)
665
 
        self.assertEqual(1514, size)
 
748
        self.assertEqual(1488, size)
666
749
 
667
750
    def test_validate_two_pages(self):
668
751
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
869
952
            (index, ('name', 'fin2'), 'beta', ((), ))]),
870
953
            set(index.iter_entries_prefix([('name', None)])))
871
954
 
 
955
    # XXX: external_references tests are duplicated in test_index.  We
 
956
    # probably should have per_graph_index tests...
 
957
    def test_external_references_no_refs(self):
 
958
        index = self.make_index(ref_lists=0, nodes=[])
 
959
        self.assertRaises(ValueError, index.external_references, 0)
 
960
 
 
961
    def test_external_references_no_results(self):
 
962
        index = self.make_index(ref_lists=1, nodes=[
 
963
            (('key',), 'value', ([],))])
 
964
        self.assertEqual(set(), index.external_references(0))
 
965
 
 
966
    def test_external_references_missing_ref(self):
 
967
        missing_key = ('missing',)
 
968
        index = self.make_index(ref_lists=1, nodes=[
 
969
            (('key',), 'value', ([missing_key],))])
 
970
        self.assertEqual(set([missing_key]), index.external_references(0))
 
971
 
 
972
    def test_external_references_multiple_ref_lists(self):
 
973
        missing_key = ('missing',)
 
974
        index = self.make_index(ref_lists=2, nodes=[
 
975
            (('key',), 'value', ([], [missing_key]))])
 
976
        self.assertEqual(set([]), index.external_references(0))
 
977
        self.assertEqual(set([missing_key]), index.external_references(1))
 
978
 
 
979
    def test_external_references_two_records(self):
 
980
        index = self.make_index(ref_lists=1, nodes=[
 
981
            (('key-1',), 'value', ([('key-2',)],)),
 
982
            (('key-2',), 'value', ([],)),
 
983
            ])
 
984
        self.assertEqual(set([]), index.external_references(0))
 
985
 
 
986
    def test__find_ancestors_one_page(self):
 
987
        key1 = ('key-1',)
 
988
        key2 = ('key-2',)
 
989
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
990
            (key1, 'value', ([key2],)),
 
991
            (key2, 'value', ([],)),
 
992
            ])
 
993
        parent_map = {}
 
994
        missing_keys = set()
 
995
        search_keys = index._find_ancestors([key1], 0, parent_map, missing_keys)
 
996
        self.assertEqual({key1: (key2,), key2: ()}, parent_map)
 
997
        self.assertEqual(set(), missing_keys)
 
998
        self.assertEqual(set(), search_keys)
 
999
 
 
1000
    def test__find_ancestors_one_page_w_missing(self):
 
1001
        key1 = ('key-1',)
 
1002
        key2 = ('key-2',)
 
1003
        key3 = ('key-3',)
 
1004
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1005
            (key1, 'value', ([key2],)),
 
1006
            (key2, 'value', ([],)),
 
1007
            ])
 
1008
        parent_map = {}
 
1009
        missing_keys = set()
 
1010
        search_keys = index._find_ancestors([key2, key3], 0, parent_map,
 
1011
                                            missing_keys)
 
1012
        self.assertEqual({key2: ()}, parent_map)
 
1013
        # we know that key3 is missing because we read the page that it would
 
1014
        # otherwise be on
 
1015
        self.assertEqual(set([key3]), missing_keys)
 
1016
        self.assertEqual(set(), search_keys)
 
1017
 
 
1018
    def test__find_ancestors_one_parent_missing(self):
 
1019
        key1 = ('key-1',)
 
1020
        key2 = ('key-2',)
 
1021
        key3 = ('key-3',)
 
1022
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1023
            (key1, 'value', ([key2],)),
 
1024
            (key2, 'value', ([key3],)),
 
1025
            ])
 
1026
        parent_map = {}
 
1027
        missing_keys = set()
 
1028
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1029
                                            missing_keys)
 
1030
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1031
        self.assertEqual(set(), missing_keys)
 
1032
        # all we know is that key3 wasn't present on the page we were reading
 
1033
        # but if you look, the last key is key2 which comes before key3, so we
 
1034
        # don't know whether key3 would land on this page or not.
 
1035
        self.assertEqual(set([key3]), search_keys)
 
1036
        search_keys = index._find_ancestors(search_keys, 0, parent_map,
 
1037
                                            missing_keys)
 
1038
        # passing it back in, we are sure it is 'missing'
 
1039
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1040
        self.assertEqual(set([key3]), missing_keys)
 
1041
        self.assertEqual(set([]), search_keys)
 
1042
 
 
1043
    def test__find_ancestors_dont_search_known(self):
 
1044
        key1 = ('key-1',)
 
1045
        key2 = ('key-2',)
 
1046
        key3 = ('key-3',)
 
1047
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[
 
1048
            (key1, 'value', ([key2],)),
 
1049
            (key2, 'value', ([key3],)),
 
1050
            (key3, 'value', ([],)),
 
1051
            ])
 
1052
        # We already know about key2, so we won't try to search for key3
 
1053
        parent_map = {key2: (key3,)}
 
1054
        missing_keys = set()
 
1055
        search_keys = index._find_ancestors([key1], 0, parent_map,
 
1056
                                            missing_keys)
 
1057
        self.assertEqual({key1: (key2,), key2: (key3,)}, parent_map)
 
1058
        self.assertEqual(set(), missing_keys)
 
1059
        self.assertEqual(set(), search_keys)
 
1060
 
 
1061
    def test__find_ancestors_multiple_pages(self):
 
1062
        # We need to use enough keys that we actually cause a split
 
1063
        start_time = 1249671539
 
1064
        email = "joebob@example.com"
 
1065
        nodes = []
 
1066
        ref_lists = ((),)
 
1067
        rev_keys = []
 
1068
        for i in xrange(400):
 
1069
            rev_id = '%s-%s-%s' % (email,
 
1070
                                   osutils.compact_date(start_time + i),
 
1071
                                   osutils.rand_chars(16))
 
1072
            rev_key = (rev_id,)
 
1073
            nodes.append((rev_key, 'value', ref_lists))
 
1074
            # We have a ref 'list' of length 1, with a list of parents, with 1
 
1075
            # parent which is a key
 
1076
            ref_lists = ((rev_key,),)
 
1077
            rev_keys.append(rev_key)
 
1078
        index = self.make_index(ref_lists=1, key_elements=1, nodes=nodes)
 
1079
        self.assertEqual(400, index.key_count())
 
1080
        self.assertEqual(3, len(index._row_offsets))
 
1081
        nodes = dict(index._read_nodes([1, 2]))
 
1082
        l1 = nodes[1]
 
1083
        l2 = nodes[2]
 
1084
        min_l2_key = l2.min_key
 
1085
        max_l1_key = l1.max_key
 
1086
        self.assertTrue(max_l1_key < min_l2_key)
 
1087
        parents_min_l2_key = l2.keys[min_l2_key][1][0]
 
1088
        self.assertEqual((l1.max_key,), parents_min_l2_key)
 
1089
        # Now, whatever key we select that would fall on the second page,
 
1090
        # should give us all the parents until the page break
 
1091
        key_idx = rev_keys.index(min_l2_key)
 
1092
        next_key = rev_keys[key_idx+1]
 
1093
        # So now when we get the parent map, we should get the key we are
 
1094
        # looking for, min_l2_key, and then a reference to go look for the
 
1095
        # parent of that key
 
1096
        parent_map = {}
 
1097
        missing_keys = set()
 
1098
        search_keys = index._find_ancestors([next_key], 0, parent_map,
 
1099
                                            missing_keys)
 
1100
        self.assertEqual([min_l2_key, next_key], sorted(parent_map))
 
1101
        self.assertEqual(set(), missing_keys)
 
1102
        self.assertEqual(set([max_l1_key]), search_keys)
 
1103
        parent_map = {}
 
1104
        search_keys = index._find_ancestors([max_l1_key], 0, parent_map,
 
1105
                                            missing_keys)
 
1106
        self.assertEqual(sorted(l1.keys), sorted(parent_map))
 
1107
        self.assertEqual(set(), missing_keys)
 
1108
        self.assertEqual(set(), search_keys)
 
1109
 
 
1110
    def test__find_ancestors_empty_index(self):
 
1111
        index = self.make_index(ref_lists=1, key_elements=1, nodes=[])
 
1112
        parent_map = {}
 
1113
        missing_keys = set()
 
1114
        search_keys = index._find_ancestors([('one',), ('two',)], 0, parent_map,
 
1115
                                            missing_keys)
 
1116
        self.assertEqual(set(), search_keys)
 
1117
        self.assertEqual({}, parent_map)
 
1118
        self.assertEqual(set([('one',), ('two',)]), missing_keys)
 
1119
 
 
1120
    def test_supports_unlimited_cache(self):
 
1121
        builder = btree_index.BTreeBuilder(reference_lists=0, key_elements=1)
 
1122
        # We need enough nodes to cause a page split (so we have both an
 
1123
        # internal node and a couple leaf nodes. 500 seems to be enough.)
 
1124
        nodes = self.make_nodes(500, 1, 0)
 
1125
        for node in nodes:
 
1126
            builder.add_node(*node)
 
1127
        stream = builder.finish()
 
1128
        trans = get_transport(self.get_url())
 
1129
        size = trans.put_file('index', stream)
 
1130
        index = btree_index.BTreeGraphIndex(trans, 'index', size)
 
1131
        self.assertEqual(500, index.key_count())
 
1132
        # We have an internal node
 
1133
        self.assertEqual(2, len(index._row_lengths))
 
1134
        # We have at least 2 leaf nodes
 
1135
        self.assertTrue(index._row_lengths[-1] >= 2)
 
1136
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1137
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1138
                         index._leaf_node_cache._max_cache)
 
1139
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1140
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1141
        # No change if unlimited_cache=False is passed
 
1142
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1143
                                            unlimited_cache=False)
 
1144
        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)
 
1145
        self.assertEqual(btree_index._NODE_CACHE_SIZE,
 
1146
                         index._leaf_node_cache._max_cache)
 
1147
        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)
 
1148
        self.assertEqual(100, index._internal_node_cache._max_cache)
 
1149
        index = btree_index.BTreeGraphIndex(trans, 'index', size,
 
1150
                                            unlimited_cache=True)
 
1151
        self.assertIsInstance(index._leaf_node_cache, dict)
 
1152
        self.assertIs(type(index._internal_node_cache), dict)
 
1153
        # Exercise the lookup code
 
1154
        entries = set(index.iter_entries([n[0] for n in nodes]))
 
1155
        self.assertEqual(500, len(entries))
 
1156
 
872
1157
 
873
1158
class TestBTreeNodes(BTreeTestCase):
874
1159
 
996
1281
    def test_exists(self):
997
1282
        # This is just to let the user know if they don't have the feature
998
1283
        # available
999
 
        self.requireFeature(CompiledBtreeParserFeature)
 
1284
        self.requireFeature(compiled_btreeparser_feature)
1000
1285
 
1001
1286
 
1002
1287
class TestMultiBisectRight(tests.TestCase):