/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_btree_index.py

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

• reverse the comparison (4913 to 4665.6.1)
• stop comparing with revision 4665.6.1

Show diffs side-by-side

added

removed

bzrlib/tests/test_btree_index.py

23

23

from bzrlib import (

24

24

    btree_index,

25

25

    errors,

 

26

    fifo_cache,

 

27

    lru_cache,

26

28

    osutils,

27

29

    tests,

28

30

    )

122

124

 

123

125

class TestBTreeBuilder(BTreeTestCase):

124

126

 

 

127

    def test_clear_cache(self):

 

128

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

 

129

        # This is a no-op, but we need the api to be consistent with other

 

130

        # BTreeGraphIndex apis.

 

131

        builder.clear_cache()

 

132

 

125

133

    def test_empty_1_0(self):

126

134

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

127

135

        # NamedTemporaryFile dies on builder.finish().read(). weird.

153

161

        temp_file = builder.finish()

154

162

        content = temp_file.read()

155

163

        del temp_file

156

 

        self.assertEqual(158, len(content))

 

164

        self.assertEqual(131, len(content))

157

165

        self.assertEqual(

158

166

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

159

167

            "row_lengths=1\n",

177

185

        temp_file = builder.finish()

178

186

        content = temp_file.read()

179

187

        del temp_file

180

 

        self.assertEqual(264, len(content))

 

188

        self.assertEqual(238, len(content))

181

189

        self.assertEqual(

182

190

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

183

191

            "row_lengths=1\n",

243

251

        temp_file = builder.finish()

244

252

        content = temp_file.read()

245

253

        del temp_file

246

 

        self.assertEqual(181, len(content))

 

254

        self.assertEqual(155, len(content))

247

255

        self.assertEqual(

248

256

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

249

257

            "row_lengths=1\n",

351

359

        # Test the parts of the index that take up memory are doing so

352

360

        # predictably.

353

361

        self.assertEqual(1, len(builder._nodes))

354

 

        self.assertEqual(1, len(builder._keys))

355

362

        self.assertIs(None, builder._nodes_by_key)

356

363

        builder.add_node(*nodes[1])

357

364

        self.assertEqual(0, len(builder._nodes))

358

 

        self.assertEqual(0, len(builder._keys))

359

365

        self.assertIs(None, builder._nodes_by_key)

360

366

        self.assertEqual(1, len(builder._backing_indices))

361

367

        self.assertEqual(2, builder._backing_indices[0].key_count())

362

368

        # now back to memory

363

369

        builder.add_node(*nodes[2])

364

370

        self.assertEqual(1, len(builder._nodes))

365

 

        self.assertEqual(1, len(builder._keys))

366

371

        self.assertIs(None, builder._nodes_by_key)

367

372

        # And spills to a second backing index combing all

368

373

        builder.add_node(*nodes[3])

369

374

        self.assertEqual(0, len(builder._nodes))

370

 

        self.assertEqual(0, len(builder._keys))

371

375

        self.assertIs(None, builder._nodes_by_key)

372

376

        self.assertEqual(2, len(builder._backing_indices))

373

377

        self.assertEqual(None, builder._backing_indices[0])

376

380

        builder.add_node(*nodes[4])

377

381

        builder.add_node(*nodes[5])

378

382

        self.assertEqual(0, len(builder._nodes))

379

 

        self.assertEqual(0, len(builder._keys))

380

383

        self.assertIs(None, builder._nodes_by_key)

381

384

        self.assertEqual(2, len(builder._backing_indices))

382

385

        self.assertEqual(2, builder._backing_indices[0].key_count())

440

443

        # Test the parts of the index that take up memory are doing so

441

444

        # predictably.

442

445

        self.assertEqual(1, len(builder._nodes))

443

 

        self.assertEqual(1, len(builder._keys))

444

446

        self.assertIs(None, builder._nodes_by_key)

445

447

        builder.add_node(*nodes[1])

446

448

        self.assertEqual(0, len(builder._nodes))

447

 

        self.assertEqual(0, len(builder._keys))

448

449

        self.assertIs(None, builder._nodes_by_key)

449

450

        self.assertEqual(1, len(builder._backing_indices))

450

451

        self.assertEqual(2, builder._backing_indices[0].key_count())

451

452

        # now back to memory

452

453

        builder.add_node(*nodes[2])

453

454

        self.assertEqual(1, len(builder._nodes))

454

 

        self.assertEqual(1, len(builder._keys))

455

455

        self.assertIs(None, builder._nodes_by_key)

456

456

        # And spills to a second backing index but doesn't combine

457

457

        builder.add_node(*nodes[3])

458

458

        self.assertEqual(0, len(builder._nodes))

459

 

        self.assertEqual(0, len(builder._keys))

460

459

        self.assertIs(None, builder._nodes_by_key)

461

460

        self.assertEqual(2, len(builder._backing_indices))

462

461

        for backing_index in builder._backing_indices:

465

464

        builder.add_node(*nodes[4])

466

465

        builder.add_node(*nodes[5])

467

466

        self.assertEqual(0, len(builder._nodes))

468

 

        self.assertEqual(0, len(builder._keys))

469

467

        self.assertIs(None, builder._nodes_by_key)

470

468

        self.assertEqual(3, len(builder._backing_indices))

471

469

        for backing_index in builder._backing_indices:

530

528

        builder.add_node(*nodes[0])

531

529

        # Test the parts of the index that take up memory are doing so

532

530

        # predictably.

533

 

        self.assertEqual(1, len(builder._keys))

534

531

        self.assertEqual(1, len(builder._nodes))

535

532

        self.assertIs(None, builder._nodes_by_key)

536

533

        builder.add_node(*nodes[1])

537

 

        self.assertEqual(0, len(builder._keys))

538

534

        self.assertEqual(0, len(builder._nodes))

539

535

        self.assertIs(None, builder._nodes_by_key)

540

536

        self.assertEqual(1, len(builder._backing_indices))

543

539

        old = dict(builder._get_nodes_by_key()) #Build up the nodes by key dict

544

540

        builder.add_node(*nodes[2])

545

541

        self.assertEqual(1, len(builder._nodes))

546

 

        self.assertEqual(1, len(builder._keys))

547

542

        self.assertIsNot(None, builder._nodes_by_key)

548

543

        self.assertNotEqual({}, builder._nodes_by_key)

549

544

        # We should have a new entry

551

546

        # And spills to a second backing index combing all

552

547

        builder.add_node(*nodes[3])

553

548

        self.assertEqual(0, len(builder._nodes))

554

 

        self.assertEqual(0, len(builder._keys))

555

549

        self.assertIs(None, builder._nodes_by_key)

556

550

        self.assertEqual(2, len(builder._backing_indices))

557

551

        self.assertEqual(None, builder._backing_indices[0])

560

554

        builder.add_node(*nodes[4])

561

555

        builder.add_node(*nodes[5])

562

556

        self.assertEqual(0, len(builder._nodes))

563

 

        self.assertEqual(0, len(builder._keys))

564

557

        self.assertIs(None, builder._nodes_by_key)

565

558

        self.assertEqual(2, len(builder._backing_indices))

566

559

        self.assertEqual(2, builder._backing_indices[0].key_count())

637

630

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

638

631

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

639

632

 

 

633

    def test_clear_cache(self):

 

634

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

 

635

        index = self.make_index(ref_lists=2, key_elements=2, nodes=nodes)

 

636

        self.assertEqual(1, len(list(index.iter_entries([nodes[30][0]]))))

 

637

        self.assertEqual([1, 4], index._row_lengths)

 

638

        self.assertIsNot(None, index._root_node)

 

639

        internal_node_pre_clear = index._internal_node_cache.keys()

 

640

        self.assertTrue(len(index._leaf_node_cache) > 0)

 

641

        index.clear_cache()

 

642

        # We don't touch _root_node or _internal_node_cache, both should be

 

643

        # small, and can save a round trip or two

 

644

        self.assertIsNot(None, index._root_node)

 

645

        # NOTE: We don't want to affect the _internal_node_cache, as we expect

 

646

        #       it will be small, and if we ever do touch this index again, it

 

647

        #       will save round-trips.  This assertion isn't very strong,

 

648

        #       becuase without a 3-level index, we don't have any internal

 

649

        #       nodes cached.

 

650

        self.assertEqual(internal_node_pre_clear,

 

651

                         index._internal_node_cache.keys())

 

652

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

 

653

 

640

654

    def test_trivial_constructor(self):

641

655

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

642

656

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

689

703

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

690

704

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

691

705

            transport._activity)

692

 

        self.assertEqual(1199, size)

 

706

        self.assertEqual(1173, size)

693

707

 

694

708

    def test__read_nodes_no_size_one_page_reads_once(self):

695

709

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

743

757

        # The entire index should have been read linearly.

744

758

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

745

759

            transport._activity)

746

 

        self.assertEqual(1514, size)

 

760

        self.assertEqual(1488, size)

747

761

 

748

762

    def test_validate_two_pages(self):

749

763

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

1115

1129

        self.assertEqual({}, parent_map)

1116

1130

        self.assertEqual(set([('one',), ('two',)]), missing_keys)

1117

1131

 

 

1132

    def test_supports_unlimited_cache(self):

 

1133

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

 

1134

        # We need enough nodes to cause a page split (so we have both an

 

1135

        # internal node and a couple leaf nodes. 500 seems to be enough.)

 

1136

        nodes = self.make_nodes(500, 1, 0)

 

1137

        for node in nodes:

 

1138

            builder.add_node(*node)

 

1139

        stream = builder.finish()

 

1140

        trans = get_transport(self.get_url())

 

1141

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

 

1142

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

 

1143

        self.assertEqual(500, index.key_count())

 

1144

        # We have an internal node

 

1145

        self.assertEqual(2, len(index._row_lengths))

 

1146

        # We have at least 2 leaf nodes

 

1147

        self.assertTrue(index._row_lengths[-1] >= 2)

 

1148

        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)

 

1149

        self.assertEqual(btree_index._NODE_CACHE_SIZE,

 

1150

                         index._leaf_node_cache._max_cache)

 

1151

        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)

 

1152

        self.assertEqual(100, index._internal_node_cache._max_cache)

 

1153

        # No change if unlimited_cache=False is passed

 

1154

        index = btree_index.BTreeGraphIndex(trans, 'index', size,

 

1155

                                            unlimited_cache=False)

 

1156

        self.assertIsInstance(index._leaf_node_cache, lru_cache.LRUCache)

 

1157

        self.assertEqual(btree_index._NODE_CACHE_SIZE,

 

1158

                         index._leaf_node_cache._max_cache)

 

1159

        self.assertIsInstance(index._internal_node_cache, fifo_cache.FIFOCache)

 

1160

        self.assertEqual(100, index._internal_node_cache._max_cache)

 

1161

        index = btree_index.BTreeGraphIndex(trans, 'index', size,

 

1162

                                            unlimited_cache=True)

 

1163

        self.assertIsInstance(index._leaf_node_cache, dict)

 

1164

        self.assertIs(type(index._internal_node_cache), dict)

 

1165

        # Exercise the lookup code

 

1166

        entries = set(index.iter_entries([n[0] for n in nodes]))

 

1167

        self.assertEqual(500, len(entries))

 

1168

 

1118

1169

 

1119

1170

class TestBTreeNodes(BTreeTestCase):

1120

1171

 

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0