« back to all changes in this revision
Viewing changes to bzrlib/tests/test_btree_index.py
- browse files at revision 3641.5.17
- compare with another revision
- compare with revision 5304
- download diff
- download tarball
- view history from revision 3641.5.17
- Committer: John Arbash Meinel
- Date: 2008-08-26 00:56:10 UTC
- mto: This revision was merged to the branch mainline in revision 3653.
- Revision ID: john@arbash-meinel.com-20080826005610-275jq9uqje3prqry
Fix up the test suite now that things don't pack as well.
- files modified:
- bzrlib/tests/test_btree_index.py
added
removed
bzrlib/tests/test_btree_index.py
204
204
205
205
def test_2_leaves_1_0(self):
206
206
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
207
nodes = self.make_nodes(800, 1, 0)
207
nodes = self.make_nodes(400, 1, 0)
208
208
for node in nodes:
209
209
builder.add_node(*node)
210
210
# NamedTemporaryFile dies on builder.finish().read(). weird.
211
211
temp_file = builder.finish()
212
212
content = temp_file.read()
213
213
del temp_file
214
self.assertEqual(9602, len(content))
214
self.assertEqual(9283, len(content))
215
215
self.assertEqual(
216
"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=800\n"
216
"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
217
217
"row_lengths=1,2\n",
218
218
content[:77])
219
219
root = content[77:4096]
223
223
expected_root = (
224
224
"type=internal\n"
225
225
"offset=0\n"
226
) + ("635" * 40) + "\n"
226
) + ("307" * 40) + "\n"
227
227
self.assertEqual(expected_root, root_bytes)
228
228
# We already know serialisation works for leaves, check key selection:
229
229
leaf1_bytes = zlib.decompress(leaf1)
230
230
sorted_node_keys = sorted(node[0] for node in nodes)
231
231
node = btree_index._LeafNode(leaf1_bytes, 1, 0)
232
self.assertEqual(594, len(node.keys))
233
self.assertEqual(sorted_node_keys[:594], sorted(node.keys))
232
self.assertEqual(231, len(node.keys))
233
self.assertEqual(sorted_node_keys[:231], sorted(node.keys))
234
234
leaf2_bytes = zlib.decompress(leaf2)
235
235
node = btree_index._LeafNode(leaf2_bytes, 1, 0)
236
self.assertEqual(800 - 594, len(node.keys))
237
self.assertEqual(sorted_node_keys[594:], sorted(node.keys))
236
self.assertEqual(400 - 231, len(node.keys))
237
self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
238
238
239
239
def test_last_page_rounded_1_layer(self):
240
240
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
260
260
261
261
def test_last_page_not_rounded_2_layer(self):
262
262
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
263
nodes = self.make_nodes(800, 1, 0)
263
nodes = self.make_nodes(400, 1, 0)
264
264
for node in nodes:
265
265
builder.add_node(*node)
266
266
# NamedTemporaryFile dies on builder.finish().read(). weird.
267
267
temp_file = builder.finish()
268
268
content = temp_file.read()
269
269
del temp_file
270
self.assertEqual(9602, len(content))
270
self.assertEqual(9283, len(content))
271
271
self.assertEqual(
272
"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=800\n"
272
"B+Tree Graph Index 2\nnode_ref_lists=0\nkey_elements=1\nlen=400\n"
273
273
"row_lengths=1,2\n",
274
274
content[:77])
275
275
# Check the last page is well formed
276
276
leaf2 = content[8192:]
277
277
leaf2_bytes = zlib.decompress(leaf2)
278
278
node = btree_index._LeafNode(leaf2_bytes, 1, 0)
279
self.assertEqual(800 - 594, len(node.keys))
279
self.assertEqual(400 - 231, len(node.keys))
280
280
sorted_node_keys = sorted(node[0] for node in nodes)
281
self.assertEqual(sorted_node_keys[594:], sorted(node.keys))
281
self.assertEqual(sorted_node_keys[231:], sorted(node.keys))
282
282
283
283
def test_three_level_tree_details(self):
284
284
# The left most pointer in the second internal node in a row should
319
319
320
320
def test_2_leaves_2_2(self):
321
321
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
322
nodes = self.make_nodes(200, 2, 2)
322
nodes = self.make_nodes(100, 2, 2)
323
323
for node in nodes:
324
324
builder.add_node(*node)
325
325
# NamedTemporaryFile dies on builder.finish().read(). weird.
326
326
temp_file = builder.finish()
327
327
content = temp_file.read()
328
328
del temp_file
329
self.assertEqual(10639, len(content))
329
self.assertEqual(12643, len(content))
330
330
self.assertEqual(
331
"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=400\n"
332
"row_lengths=1,2\n",
331
"B+Tree Graph Index 2\nnode_ref_lists=2\nkey_elements=2\nlen=200\n"
332
"row_lengths=1,3\n",
333
333
content[:77])
334
334
root = content[77:4096]
335
335
leaf1 = content[4096:8192]
336
leaf2 = content[8192:]
336
leaf2 = content[8192:12288]
337
leaf3 = content[12288:]
337
338
root_bytes = zlib.decompress(root)
338
339
expected_root = (
339
340
"type=internal\n"
340
341
"offset=0\n"
341
"1111111111111111111111111111111111111111\x00"
342
) + ("151" * 40) + "\n"
342
+ ("0" * 40) + "\x00" + ("91" * 40) + "\n"
343
+ ("1" * 40) + "\x00" + ("81" * 40) + "\n"
344
)
343
345
self.assertEqual(expected_root, root_bytes)
344
346
# We assume the other leaf nodes have been written correctly - layering
345
347
# FTW.
606
608
builder.add_node(*node)
607
609
transport = get_transport('trace+' + self.get_url(''))
608
610
size = transport.put_file('index', builder.finish())
609
self.assertEqual(9152, size)
611
self.assertEqual(17692, size)
610
612
index = btree_index.BTreeGraphIndex(transport, 'index', size)
611
613
del transport._activity[:]
612
614
self.assertEqual([], transport._activity)
617
619
618
620
def test_validate_one_page(self):
619
621
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
622
nodes = self.make_nodes(45, 2, 2)
623
for node in nodes:
624
builder.add_node(*node)
625
transport = get_transport('trace+' + self.get_url(''))
626
size = transport.put_file('index', builder.finish())
627
index = btree_index.BTreeGraphIndex(transport, 'index', size)
628
del transport._activity[:]
629
self.assertEqual([], transport._activity)
630
index.validate()
631
# The entire index should have been read linearly.
632
self.assertEqual([('readv', 'index', [(0, size)], False, None)],
633
transport._activity)
634
self.assertEqual(1514, size)
635
636
def test_validate_two_pages(self):
637
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
620
638
nodes = self.make_nodes(80, 2, 2)
621
639
for node in nodes:
622
640
builder.add_node(*node)
623
641
transport = get_transport('trace+' + self.get_url(''))
624
642
size = transport.put_file('index', builder.finish())
625
index = btree_index.BTreeGraphIndex(transport, 'index', size)
626
del transport._activity[:]
627
self.assertEqual([], transport._activity)
628
index.validate()
629
# The entire index should have been read linearly.
630
self.assertEqual([('readv', 'index', [(0, size)], False, None)],
631
transport._activity)
632
self.assertEqual(2768, size)
633
634
def test_validate_two_pages(self):
635
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
636
nodes = self.make_nodes(160, 2, 2)
637
for node in nodes:
638
builder.add_node(*node)
639
transport = get_transport('trace+' + self.get_url(''))
640
size = transport.put_file('index', builder.finish())
641
643
# Root page, 2 leaf pages
642
self.assertEqual(9152, size)
644
self.assertEqual(9339, size)
643
645
index = btree_index.BTreeGraphIndex(transport, 'index', size)
644
646
del transport._activity[:]
645
647
self.assertEqual([], transport._activity)
646
648
index.validate()
647
649
# The entire index should have been read linearly.
648
650
self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
649
('readv', 'index', [(4096, 4096), (8192, 960)], False, None)],
651
('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
650
652
transport._activity)
651
653
# XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
652
654
# node and make validate find them.
691
693
# read.
692
694
self.shrink_page_size()
693
695
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
694
# 40k nodes is enough to create a two internal nodes on the second
696
# 20k nodes is enough to create a two internal nodes on the second
695
697
# level, with a 2K page size
696
nodes = self.make_nodes(20000, 2, 2)
698
nodes = self.make_nodes(10000, 2, 2)
697
699
for node in nodes:
698
700
builder.add_node(*node)
699
701
transport = get_transport('trace+' + self.get_url(''))
700
702
size = transport.put_file('index', builder.finish())
701
self.assertEqual(780162, size, 'number of expected bytes in the'
702
' output changed')
703
self.assertEqual(1303220, size, 'number of expected bytes in the'
704
' output changed')
703
705
page_size = btree_index._PAGE_SIZE
704
706
del builder
705
707
index = btree_index.BTreeGraphIndex(transport, 'index', size)
713
715
self.assertEqual(3, len(index._row_lengths),
714
716
"Not enough rows: %r" % index._row_lengths)
715
717
# Should be as long as the nodes we supplied
716
self.assertEqual(40000, len(found_nodes))
718
self.assertEqual(20000, len(found_nodes))
717
719
# Should have the same content
718
720
self.assertEqual(set(nodes), set(bare_nodes))
719
721
# Should have done linear scan IO up the index, ignoring
721
723
# The entire index should have been read
722
724
total_pages = sum(index._row_lengths)
723
725
self.assertEqual(total_pages, index._row_offsets[-1])
724
self.assertEqual(780162, size)
726
self.assertEqual(1303220, size)
725
727
# The start of the leaves
726
728
first_byte = index._row_offsets[-2] * page_size
727
729
readv_request = []
728
730
for offset in range(first_byte, size, page_size):
729
731
readv_request.append((offset, page_size))
730
732
# The last page is truncated
731
readv_request[-1] = (readv_request[-1][0], 780162 % page_size)
733
readv_request[-1] = (readv_request[-1][0], 1303220 % page_size)
732
734
expected = [('readv', 'index', [(0, page_size)], False, None),
733
735
('readv', 'index', readv_request, False, None)]
734
736
if expected != transport._activity:
769
771
self.assertEqual(nodes[30], bare_nodes[0])
770
772
# Should have read the root node, then one leaf page:
771
773
self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
772
('readv', 'index', [(4096, 4096), ], False, None)],
774
('readv', 'index', [(8192, 4096), ], False, None)],
773
775
transport._activity)
774
776
775
777
def test_iter_key_prefix_1_element_key_None(self):
Loggerhead is a web-based interface for Breezy
Version: 2.0.1