~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

• browse files at revision 6591
• compare with another revision
• download diff
• download tarball
• view history from revision 6591

• reverse the comparison (6591 to 6079)
• stop comparing with revision 6079

Show diffs side-by-side

added

removed

bzrlib/tests/test_btree_index.py

59

59

    # that they test.

60

60

 

61

61

    def setUp(self):

62

 

        TestCaseWithTransport.setUp(self)

 

62

        super(BTreeTestCase, self).setUp()

63

63

        self.overrideAttr(btree_index, '_RESERVED_HEADER_BYTES', 100)

64

64

 

65

65

    def make_nodes(self, count, key_elements, reference_lists):

103

103

        self.overrideAttr(btree_index, '_PAGE_SIZE')

104

104

        btree_index._PAGE_SIZE = 2048

105

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

 

106

116

 

107

117

class TestBTreeBuilder(BTreeTestCase):

108

118

 

199

209

        temp_file = builder.finish()

200

210

        content = temp_file.read()

201

211

        del temp_file

202

 

        self.assertEqual(9283, len(content))

 

212

        self.assertEqualsApproxCompressed(9283, len(content))

203

213

        self.assertEqual(

204

214

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"

205

215

            "row_lengths=1,2\n",

233

243

        temp_file = builder.finish()

234

244

        content = temp_file.read()

235

245

        del temp_file

236

 

        self.assertEqual(155, len(content))

 

246

        self.assertEqualsApproxCompressed(155, len(content))

237

247

        self.assertEqual(

238

248

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=10\n"

239

249

            "row_lengths=1\n",

255

265

        temp_file = builder.finish()

256

266

        content = temp_file.read()

257

267

        del temp_file

258

 

        self.assertEqual(9283, len(content))

 

268

        self.assertEqualsApproxCompressed(9283, len(content))

259

269

        self.assertEqual(

260

270

            "B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"

261

271

            "row_lengths=1,2\n",

281

291

 

282

292

        for node in nodes:

283

293

            builder.add_node(*node)

284

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

294

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

285

295

        size = t.put_file('index', self.time(builder.finish))

286

296

        del builder

287

297

        index = btree_index.BTreeGraphIndex(t, 'index', size)

314

324

        temp_file = builder.finish()

315

325

        content = temp_file.read()

316

326

        del temp_file

317

 

        self.assertEqual(12643, len(content))

 

327

        self.assertEqualsApproxCompressed(12643, len(content))

318

328

        self.assertEqual(

319

329

            "B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"

320

330

            "row_lengths=1,3\n",

608

618

        for key, value, references in nodes:

609

619

            builder.add_node(key, value, references)

610

620

        stream = builder.finish()

611

 

        trans = transport.get_transport('trace+' + self.get_url())

 

621

        trans = transport.get_transport_from_url('trace+' + self.get_url())

612

622

        size = trans.put_file('index', stream)

613

623

        return btree_index.BTreeGraphIndex(trans, 'index', size)

614

624

 

649

659

        self.assertEqual(0, len(index._leaf_node_cache))

650

660

 

651

661

    def test_trivial_constructor(self):

652

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

662

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

653

663

        index = btree_index.BTreeGraphIndex(t, 'index', None)

654

664

        # Checks the page size at load, but that isn't logged yet.

655

665

        self.assertEqual([], t._activity)

656

666

 

657

667

    def test_with_size_constructor(self):

658

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

668

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

659

669

        index = btree_index.BTreeGraphIndex(t, 'index', 1)

660

670

        # Checks the page size at load, but that isn't logged yet.

661

671

        self.assertEqual([], t._activity)

662

672

 

663

673

    def test_empty_key_count_no_size(self):

664

674

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

665

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

675

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

666

676

        t.put_file('index', builder.finish())

667

677

        index = btree_index.BTreeGraphIndex(t, 'index', None)

668

678

        del t._activity[:]

675

685

 

676

686

    def test_empty_key_count(self):

677

687

        builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)

678

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

688

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

679

689

        size = t.put_file('index', builder.finish())

680

690

        self.assertEqual(72, size)

681

691

        index = btree_index.BTreeGraphIndex(t, 'index', size)

691

701

        nodes = self.make_nodes(35, 2, 2)

692

702

        for node in nodes:

693

703

            builder.add_node(*node)

694

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

704

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

695

705

        size = t.put_file('index', builder.finish())

696

706

        index = btree_index.BTreeGraphIndex(t, 'index', size)

697

707

        del t._activity[:]

700

710

        # The entire index should have been read, as it is one page long.

701

711

        self.assertEqual([('readv', 'index', [(0, size)], False, None)],

702

712

            t._activity)

703

 

        self.assertEqual(1173, size)

 

713

        self.assertEqualsApproxCompressed(1173, size)

704

714

 

705

715

    def test_with_offset_no_size(self):

706

716

        index = self.make_index_with_offset(key_elements=1, ref_lists=1,

723

733

 

724

734

    def test__read_nodes_no_size_one_page_reads_once(self):

725

735

        self.make_index(nodes=[(('key',), 'value', ())])

726

 

        trans = transport.get_transport('trace+' + self.get_url())

 

736

        trans = transport.get_transport_from_url('trace+' + self.get_url())

727

737

        index = btree_index.BTreeGraphIndex(trans, 'index', None)

728

738

        del trans._activity[:]

729

739

        nodes = dict(index._read_nodes([0]))

737

747

        index.key_count()

738

748

        num_pages = index._row_offsets[-1]

739

749

        # Reopen with a traced transport and no size

740

 

        trans = transport.get_transport('trace+' + self.get_url())

 

750

        trans = transport.get_transport_from_url('trace+' + self.get_url())

741

751

        index = btree_index.BTreeGraphIndex(trans, 'index', None)

742

752

        del trans._activity[:]

743

753

        nodes = dict(index._read_nodes([0]))

748

758

        nodes = self.make_nodes(160, 2, 2)

749

759

        for node in nodes:

750

760

            builder.add_node(*node)

751

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

761

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

752

762

        size = t.put_file('index', builder.finish())

753

 

        self.assertEqual(17692, size)

 

763

        self.assertEqualsApproxCompressed(17692, size)

754

764

        index = btree_index.BTreeGraphIndex(t, 'index', size)

755

765

        del t._activity[:]

756

766

        self.assertEqual([], t._activity)

764

774

        nodes = self.make_nodes(45, 2, 2)

765

775

        for node in nodes:

766

776

            builder.add_node(*node)

767

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

777

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

768

778

        size = t.put_file('index', builder.finish())

769

779

        index = btree_index.BTreeGraphIndex(t, 'index', size)

770

780

        del t._activity[:]

773

783

        # The entire index should have been read linearly.

774

784

        self.assertEqual([('readv', 'index', [(0, size)], False, None)],

775

785

                         t._activity)

776

 

        self.assertEqual(1488, size)

 

786

        self.assertEqualsApproxCompressed(1488, size)

777

787

 

778

788

    def test_validate_two_pages(self):

779

789

        builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)

780

790

        nodes = self.make_nodes(80, 2, 2)

781

791

        for node in nodes:

782

792

            builder.add_node(*node)

783

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

793

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

784

794

        size = t.put_file('index', builder.finish())

785

795

        # Root page, 2 leaf pages

786

 

        self.assertEqual(9339, size)

 

796

        self.assertEqualsApproxCompressed(9339, size)

787

797

        index = btree_index.BTreeGraphIndex(t, 'index', size)

788

798

        del t._activity[:]

789

799

        self.assertEqual([], t._activity)

790

800

        index.validate()

 

801

        rem = size - 8192 # Number of remaining bytes after second block

791

802

        # The entire index should have been read linearly.

792

803

        self.assertEqual(

793

804

            [('readv', 'index', [(0, 4096)], False, None),

794

 

             ('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],

 

805

             ('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],

795

806

            t._activity)

796

807

        # XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong

797

808

        # node and make validate find them.

798

809

 

799

810

    def test_eq_ne(self):

800

811

        # two indices are equal when constructed with the same parameters:

801

 

        t1 = transport.get_transport('trace+' + self.get_url(''))

 

812

        t1 = transport.get_transport_from_url('trace+' + self.get_url(''))

802

813

        t2 = self.get_transport()

803

814

        self.assertTrue(

804

815

            btree_index.BTreeGraphIndex(t1, 'index', None) ==

831

842

            btree_index.BTreeGraphIndex(t1, 'index', 10) !=

832

843

            btree_index.BTreeGraphIndex(t1, 'index', 20))

833

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

        

834

853

    def test_iter_all_only_root_no_size(self):

835

854

        self.make_index(nodes=[(('key',), 'value', ())])

836

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

855

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

837

856

        index = btree_index.BTreeGraphIndex(t, 'index', None)

838

857

        del t._activity[:]

839

858

        self.assertEqual([(('key',), 'value')],

850

869

        nodes = self.make_nodes(10000, 2, 2)

851

870

        for node in nodes:

852

871

            builder.add_node(*node)

853

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

872

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

854

873

        size = t.put_file('index', builder.finish())

855

 

        self.assertEqual(1303220, size, 'number of expected bytes in the'

856

 

                                        ' output changed')

857

874

        page_size = btree_index._PAGE_SIZE

858

875

        del builder

859

876

        index = btree_index.BTreeGraphIndex(t, 'index', size)

875

892

        # The entire index should have been read

876

893

        total_pages = sum(index._row_lengths)

877

894

        self.assertEqual(total_pages, index._row_offsets[-1])

878

 

        self.assertEqual(1303220, size)

 

895

        self.assertEqualsApproxCompressed(1303220, size)

879

896

        # The start of the leaves

880

897

        first_byte = index._row_offsets[-2] * page_size

881

898

        readv_request = []

882

899

        for offset in range(first_byte, size, page_size):

883

900

            readv_request.append((offset, page_size))

884

901

        # The last page is truncated

885

 

        readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)

 

902

        readv_request[-1] = (readv_request[-1][0], size % page_size)

886

903

        expected = [('readv', 'index', [(0, page_size)], False, None),

887

904

             ('readv',  'index', readv_request, False, None)]

888

905

        if expected != t._activity:

889

906

            self.assertEqualDiff(pprint.pformat(expected),

890

 

                                 pprint.pformat(transport._activity))

 

907

                                 pprint.pformat(t._activity))

891

908

 

892

909

    def _test_iter_entries_references_resolved(self):

893

910

        index = self.make_index(1, nodes=[

905

922

        nodes = self.make_nodes(160, 2, 2)

906

923

        for node in nodes:

907

924

            builder.add_node(*node)

908

 

        t = transport.get_transport('trace+' + self.get_url(''))

 

925

        t = transport.get_transport_from_url('trace+' + self.get_url(''))

909

926

        size = t.put_file('index', builder.finish())

910

927

        del builder

911

928

        index = btree_index.BTreeGraphIndex(t, 'index', size)

1189

1206

    scenarios = btreeparser_scenarios()

1190

1207

 

1191

1208

    def setUp(self):

1192

 

        BTreeTestCase.setUp(self)

 

1209

        super(TestBTreeNodes, self).setUp()

1193

1210

        self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)

1194

1211

 

1195

1212

    def test_LeafNode_1_0(self):

1354

1371

        BTreeGraphIndex with the recommended information.

1355

1372

        """

1356

1373

        index = btree_index.BTreeGraphIndex(

1357

 

            transport.get_transport('memory:///'), 'test-index', size=size)

 

1374

            transport.get_transport_from_url('memory:///'),

 

1375

            'test-index', size=size)

1358

1376

        if recommended_pages is not None:

1359

1377

            index._recommended_pages = recommended_pages

1360

1378

        return index

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1