← 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: Matt Nordhoff
  • Date: 2009-04-04 02:50:01 UTC
  • mfrom: (4253 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4256.
  • Revision ID: mnordhoff@mattnordhoff.com-20090404025001-z1403k0tatmc8l91
Merge bzr.dev, fixing conflicts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_btree_index.py
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."""
27
27
    )
28
28
from bzrlib.tests import (
29
29
    TestCaseWithTransport,
30
 
    TestScenarioApplier,
31
 
    adapt_tests,
32
30
    condition_isinstance,
 
31
    multiply_tests,
33
32
    split_suite_by_condition,
34
33
    )
35
34
from bzrlib.transport import get_transport
39
38
    # parameterise the TestBTreeNodes tests
40
39
    node_tests, others = split_suite_by_condition(standard_tests,
41
40
        condition_isinstance(TestBTreeNodes))
42
 
    applier = TestScenarioApplier()
43
41
    import bzrlib._btree_serializer_py as py_module
44
 
    applier.scenarios = [('python', {'parse_btree': py_module})]
 
42
    scenarios = [('python', {'parse_btree': py_module})]
45
43
    if CompiledBtreeParserFeature.available():
46
44
        # Is there a way to do this that gets missing feature failures rather
47
45
        # than no indication to the user?
48
46
        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
 
47
        scenarios.append(('C', {'parse_btree': c_module}))
 
48
    return multiply_tests(node_tests, scenarios, others)
52
49
 
53
50
 
54
51
class _CompiledBtreeParserFeature(tests.Feature):
434
431
        self.assertEqual(sorted(nodes), nodes)
435
432
        self.assertEqual(16, len(nodes))
436
433
 
 
434
    def test_spill_index_stress_1_1_no_combine(self):
 
435
        builder = btree_index.BTreeBuilder(key_elements=1, spill_at=2)
 
436
        builder.set_optimize(for_size=False, combine_backing_indices=False)
 
437
        nodes = [node[0:2] for node in self.make_nodes(16, 1, 0)]
 
438
        builder.add_node(*nodes[0])
 
439
        # Test the parts of the index that take up memory are doing so
 
440
        # predictably.
 
441
        self.assertEqual(1, len(builder._nodes))
 
442
        self.assertEqual(1, len(builder._keys))
 
443
        self.assertIs(None, builder._nodes_by_key)
 
444
        builder.add_node(*nodes[1])
 
445
        self.assertEqual(0, len(builder._nodes))
 
446
        self.assertEqual(0, len(builder._keys))
 
447
        self.assertIs(None, builder._nodes_by_key)
 
448
        self.assertEqual(1, len(builder._backing_indices))
 
449
        self.assertEqual(2, builder._backing_indices[0].key_count())
 
450
        # now back to memory
 
451
        builder.add_node(*nodes[2])
 
452
        self.assertEqual(1, len(builder._nodes))
 
453
        self.assertEqual(1, len(builder._keys))
 
454
        self.assertIs(None, builder._nodes_by_key)
 
455
        # And spills to a second backing index but doesn't combine
 
456
        builder.add_node(*nodes[3])
 
457
        self.assertEqual(0, len(builder._nodes))
 
458
        self.assertEqual(0, len(builder._keys))
 
459
        self.assertIs(None, builder._nodes_by_key)
 
460
        self.assertEqual(2, len(builder._backing_indices))
 
461
        for backing_index in builder._backing_indices:
 
462
            self.assertEqual(2, backing_index.key_count())
 
463
        # The next spills to the 3rd slot
 
464
        builder.add_node(*nodes[4])
 
465
        builder.add_node(*nodes[5])
 
466
        self.assertEqual(0, len(builder._nodes))
 
467
        self.assertEqual(0, len(builder._keys))
 
468
        self.assertIs(None, builder._nodes_by_key)
 
469
        self.assertEqual(3, len(builder._backing_indices))
 
470
        for backing_index in builder._backing_indices:
 
471
            self.assertEqual(2, backing_index.key_count())
 
472
        # Now spill a few more, and check that we don't combine
 
473
        builder.add_node(*nodes[6])
 
474
        builder.add_node(*nodes[7])
 
475
        builder.add_node(*nodes[8])
 
476
        builder.add_node(*nodes[9])
 
477
        builder.add_node(*nodes[10])
 
478
        builder.add_node(*nodes[11])
 
479
        builder.add_node(*nodes[12])
 
480
        self.assertEqual(6, len(builder._backing_indices))
 
481
        for backing_index in builder._backing_indices:
 
482
            self.assertEqual(2, backing_index.key_count())
 
483
        # Test that memory and disk are both used for query methods; and that
 
484
        # None is skipped over happily.
 
485
        self.assertEqual([(builder,) + node for node in sorted(nodes[:13])],
 
486
            list(builder.iter_all_entries()))
 
487
        # Two nodes - one memory one disk
 
488
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
489
            set(builder.iter_entries([nodes[12][0], nodes[11][0]])))
 
490
        self.assertEqual(13, builder.key_count())
 
491
        self.assertEqual(set([(builder,) + node for node in nodes[11:13]]),
 
492
            set(builder.iter_entries_prefix([nodes[12][0], nodes[11][0]])))
 
493
        builder.add_node(*nodes[13])
 
494
        builder.add_node(*nodes[14])
 
495
        builder.add_node(*nodes[15])
 
496
        self.assertEqual(8, len(builder._backing_indices))
 
497
        for backing_index in builder._backing_indices:
 
498
            self.assertEqual(2, backing_index.key_count())
 
499
        # Now finish, and check we got a correctly ordered tree
 
500
        transport = self.get_transport('')
 
501
        size = transport.put_file('index', builder.finish())
 
502
        index = btree_index.BTreeGraphIndex(transport, 'index', size)
 
503
        nodes = list(index.iter_all_entries())
 
504
        self.assertEqual(sorted(nodes), nodes)
 
505
        self.assertEqual(16, len(nodes))
 
506
 
437
507
    def test_set_optimize(self):
438
508
        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
439
509
        builder.set_optimize(for_size=True)
440
510
        self.assertTrue(builder._optimize_for_size)
441
511
        builder.set_optimize(for_size=False)
442
512
        self.assertFalse(builder._optimize_for_size)
 
513
        # test that we can set combine_backing_indices without effecting
 
514
        # _optimize_for_size
 
515
        obj = object()
 
516
        builder._optimize_for_size = obj
 
517
        builder.set_optimize(combine_backing_indices=False)
 
518
        self.assertFalse(builder._combine_backing_indices)
 
519
        self.assertIs(obj, builder._optimize_for_size)
 
520
        builder.set_optimize(combine_backing_indices=True)
 
521
        self.assertTrue(builder._combine_backing_indices)
 
522
        self.assertIs(obj, builder._optimize_for_size)
443
523
 
444
524
    def test_spill_index_stress_2_2(self):
445
525
        # test that references and longer keys don't confuse things.