644
660
# becuase without a 3-level index, we don't have any internal
646
662
self.assertEqual(internal_node_pre_clear,
647
index._internal_node_cache.keys())
663
set(index._internal_node_cache))
648
664
self.assertEqual(0, len(index._leaf_node_cache))
650
666
def test_trivial_constructor(self):
651
transport = get_transport('trace+' + self.get_url(''))
652
index = btree_index.BTreeGraphIndex(transport, 'index', None)
667
t = transport.get_transport_from_url('trace+' + self.get_url(''))
668
index = btree_index.BTreeGraphIndex(t, 'index', None)
653
669
# Checks the page size at load, but that isn't logged yet.
654
self.assertEqual([], transport._activity)
670
self.assertEqual([], t._activity)
656
672
def test_with_size_constructor(self):
657
transport = get_transport('trace+' + self.get_url(''))
658
index = btree_index.BTreeGraphIndex(transport, 'index', 1)
673
t = transport.get_transport_from_url('trace+' + self.get_url(''))
674
index = btree_index.BTreeGraphIndex(t, 'index', 1)
659
675
# Checks the page size at load, but that isn't logged yet.
660
self.assertEqual([], transport._activity)
676
self.assertEqual([], t._activity)
662
678
def test_empty_key_count_no_size(self):
663
679
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
664
transport = get_transport('trace+' + self.get_url(''))
665
transport.put_file('index', builder.finish())
666
index = btree_index.BTreeGraphIndex(transport, 'index', None)
667
del transport._activity[:]
668
self.assertEqual([], transport._activity)
680
t = transport.get_transport_from_url('trace+' + self.get_url(''))
681
t.put_file('index', builder.finish())
682
index = btree_index.BTreeGraphIndex(t, 'index', None)
684
self.assertEqual([], t._activity)
669
685
self.assertEqual(0, index.key_count())
670
686
# The entire index should have been requested (as we generally have the
671
687
# size available, and doing many small readvs is inappropriate).
672
688
# We can't tell how much was actually read here, but - check the code.
673
self.assertEqual([('get', 'index')], transport._activity)
689
self.assertEqual([('get', 'index')], t._activity)
675
691
def test_empty_key_count(self):
676
692
builder = btree_index.BTreeBuilder(key_elements=1, reference_lists=0)
677
transport = get_transport('trace+' + self.get_url(''))
678
size = transport.put_file('index', builder.finish())
693
t = transport.get_transport_from_url('trace+' + self.get_url(''))
694
size = t.put_file('index', builder.finish())
679
695
self.assertEqual(72, size)
680
index = btree_index.BTreeGraphIndex(transport, 'index', size)
681
del transport._activity[:]
682
self.assertEqual([], transport._activity)
696
index = btree_index.BTreeGraphIndex(t, 'index', size)
698
self.assertEqual([], t._activity)
683
699
self.assertEqual(0, index.key_count())
684
700
# The entire index should have been read, as 4K > size
685
701
self.assertEqual([('readv', 'index', [(0, 72)], False, None)],
688
704
def test_non_empty_key_count_2_2(self):
689
705
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
690
706
nodes = self.make_nodes(35, 2, 2)
691
707
for node in nodes:
692
708
builder.add_node(*node)
693
transport = get_transport('trace+' + self.get_url(''))
694
size = transport.put_file('index', builder.finish())
695
index = btree_index.BTreeGraphIndex(transport, 'index', size)
696
del transport._activity[:]
697
self.assertEqual([], transport._activity)
709
t = transport.get_transport_from_url('trace+' + self.get_url(''))
710
size = t.put_file('index', builder.finish())
711
index = btree_index.BTreeGraphIndex(t, 'index', size)
713
self.assertEqual([], t._activity)
698
714
self.assertEqual(70, index.key_count())
699
715
# The entire index should have been read, as it is one page long.
700
716
self.assertEqual([('readv', 'index', [(0, size)], False, None)],
702
self.assertEqual(1173, size)
718
self.assertEqualApproxCompressed(1173, size)
704
720
def test_with_offset_no_size(self):
705
721
index = self.make_index_with_offset(key_elements=1, ref_lists=1,
736
752
index.key_count()
737
753
num_pages = index._row_offsets[-1]
738
754
# Reopen with a traced transport and no size
739
trans = get_transport('trace+' + self.get_url())
755
trans = transport.get_transport_from_url('trace+' + self.get_url())
740
756
index = btree_index.BTreeGraphIndex(trans, 'index', None)
741
757
del trans._activity[:]
742
758
nodes = dict(index._read_nodes([0]))
743
self.assertEqual(range(num_pages), nodes.keys())
759
self.assertEqual(list(range(num_pages)), sorted(nodes))
745
761
def test_2_levels_key_count_2_2(self):
746
762
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
747
763
nodes = self.make_nodes(160, 2, 2)
748
764
for node in nodes:
749
765
builder.add_node(*node)
750
transport = get_transport('trace+' + self.get_url(''))
751
size = transport.put_file('index', builder.finish())
752
self.assertEqual(17692, size)
753
index = btree_index.BTreeGraphIndex(transport, 'index', size)
754
del transport._activity[:]
755
self.assertEqual([], transport._activity)
766
t = transport.get_transport_from_url('trace+' + self.get_url(''))
767
size = t.put_file('index', builder.finish())
768
self.assertEqualApproxCompressed(17692, size)
769
index = btree_index.BTreeGraphIndex(t, 'index', size)
771
self.assertEqual([], t._activity)
756
772
self.assertEqual(320, index.key_count())
757
773
# The entire index should not have been read.
758
774
self.assertEqual([('readv', 'index', [(0, 4096)], False, None)],
761
777
def test_validate_one_page(self):
762
778
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
763
779
nodes = self.make_nodes(45, 2, 2)
764
780
for node in nodes:
765
781
builder.add_node(*node)
766
transport = get_transport('trace+' + self.get_url(''))
767
size = transport.put_file('index', builder.finish())
768
index = btree_index.BTreeGraphIndex(transport, 'index', size)
769
del transport._activity[:]
770
self.assertEqual([], transport._activity)
782
t = transport.get_transport_from_url('trace+' + self.get_url(''))
783
size = t.put_file('index', builder.finish())
784
index = btree_index.BTreeGraphIndex(t, 'index', size)
786
self.assertEqual([], t._activity)
772
788
# The entire index should have been read linearly.
773
789
self.assertEqual([('readv', 'index', [(0, size)], False, None)],
775
self.assertEqual(1488, size)
791
self.assertEqualApproxCompressed(1488, size)
777
793
def test_validate_two_pages(self):
778
794
builder = btree_index.BTreeBuilder(key_elements=2, reference_lists=2)
779
795
nodes = self.make_nodes(80, 2, 2)
780
796
for node in nodes:
781
797
builder.add_node(*node)
782
transport = get_transport('trace+' + self.get_url(''))
783
size = transport.put_file('index', builder.finish())
798
t = transport.get_transport_from_url('trace+' + self.get_url(''))
799
size = t.put_file('index', builder.finish())
784
800
# Root page, 2 leaf pages
785
self.assertEqual(9339, size)
786
index = btree_index.BTreeGraphIndex(transport, 'index', size)
787
del transport._activity[:]
788
self.assertEqual([], transport._activity)
801
self.assertEqualApproxCompressed(9339, size)
802
index = btree_index.BTreeGraphIndex(t, 'index', size)
804
self.assertEqual([], t._activity)
806
rem = size - 8192 # Number of remaining bytes after second block
790
807
# The entire index should have been read linearly.
791
self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
792
('readv', 'index', [(4096, 4096), (8192, 1147)], False, None)],
809
[('readv', 'index', [(0, 4096)], False, None),
810
('readv', 'index', [(4096, 4096), (8192, rem)], False, None)],
794
812
# XXX: TODO: write some badly-ordered nodes, and some pointers-to-wrong
795
813
# node and make validate find them.
797
815
def test_eq_ne(self):
798
816
# two indices are equal when constructed with the same parameters:
799
transport1 = get_transport('trace+' + self.get_url(''))
800
transport2 = get_transport(self.get_url(''))
802
btree_index.BTreeGraphIndex(transport1, 'index', None) ==
803
btree_index.BTreeGraphIndex(transport1, 'index', None))
805
btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
806
btree_index.BTreeGraphIndex(transport1, 'index', 20))
808
btree_index.BTreeGraphIndex(transport1, 'index', 20) ==
809
btree_index.BTreeGraphIndex(transport2, 'index', 20))
811
btree_index.BTreeGraphIndex(transport1, 'inde1', 20) ==
812
btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
814
btree_index.BTreeGraphIndex(transport1, 'index', 10) ==
815
btree_index.BTreeGraphIndex(transport1, 'index', 20))
817
btree_index.BTreeGraphIndex(transport1, 'index', None) !=
818
btree_index.BTreeGraphIndex(transport1, 'index', None))
820
btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
821
btree_index.BTreeGraphIndex(transport1, 'index', 20))
823
btree_index.BTreeGraphIndex(transport1, 'index', 20) !=
824
btree_index.BTreeGraphIndex(transport2, 'index', 20))
826
btree_index.BTreeGraphIndex(transport1, 'inde1', 20) !=
827
btree_index.BTreeGraphIndex(transport1, 'inde2', 20))
829
btree_index.BTreeGraphIndex(transport1, 'index', 10) !=
830
btree_index.BTreeGraphIndex(transport1, 'index', 20))
817
t1 = transport.get_transport_from_url('trace+' + self.get_url(''))
818
t2 = self.get_transport()
820
btree_index.BTreeGraphIndex(t1, 'index', None) ==
821
btree_index.BTreeGraphIndex(t1, 'index', None))
823
btree_index.BTreeGraphIndex(t1, 'index', 20) ==
824
btree_index.BTreeGraphIndex(t1, 'index', 20))
826
btree_index.BTreeGraphIndex(t1, 'index', 20) ==
827
btree_index.BTreeGraphIndex(t2, 'index', 20))
829
btree_index.BTreeGraphIndex(t1, 'inde1', 20) ==
830
btree_index.BTreeGraphIndex(t1, 'inde2', 20))
832
btree_index.BTreeGraphIndex(t1, 'index', 10) ==
833
btree_index.BTreeGraphIndex(t1, 'index', 20))
835
btree_index.BTreeGraphIndex(t1, 'index', None) !=
836
btree_index.BTreeGraphIndex(t1, 'index', None))
838
btree_index.BTreeGraphIndex(t1, 'index', 20) !=
839
btree_index.BTreeGraphIndex(t1, 'index', 20))
841
btree_index.BTreeGraphIndex(t1, 'index', 20) !=
842
btree_index.BTreeGraphIndex(t2, 'index', 20))
844
btree_index.BTreeGraphIndex(t1, 'inde1', 20) !=
845
btree_index.BTreeGraphIndex(t1, 'inde2', 20))
847
btree_index.BTreeGraphIndex(t1, 'index', 10) !=
848
btree_index.BTreeGraphIndex(t1, 'index', 20))
850
def test_key_too_big(self):
851
# the size that matters here is the _compressed_ size of the key, so we can't
852
# do a simple character repeat.
853
bigKey = b''.join(b'%d' % n for n in range(btree_index._PAGE_SIZE))
854
self.assertRaises(_mod_index.BadIndexKey,
856
nodes=[((bigKey,), b'value', ())])
832
858
def test_iter_all_only_root_no_size(self):
833
self.make_index(nodes=[(('key',), 'value', ())])
834
trans = get_transport('trace+' + self.get_url(''))
835
index = btree_index.BTreeGraphIndex(trans, 'index', None)
836
del trans._activity[:]
837
self.assertEqual([(('key',), 'value')],
859
self.make_index(nodes=[((b'key',), b'value', ())])
860
t = transport.get_transport_from_url('trace+' + self.get_url(''))
861
index = btree_index.BTreeGraphIndex(t, 'index', None)
863
self.assertEqual([((b'key',), b'value')],
838
864
[x[1:] for x in index.iter_all_entries()])
839
self.assertEqual([('get', 'index')], trans._activity)
865
self.assertEqual([('get', 'index')], t._activity)
841
867
def test_iter_all_entries_reads(self):
842
868
# iterating all entries reads the header, then does a linear
922
938
# Should have read the root node, then one leaf page:
923
939
self.assertEqual([('readv', 'index', [(0, 4096)], False, None),
924
940
('readv', 'index', [(8192, 4096), ], False, None)],
927
943
def test_iter_key_prefix_1_element_key_None(self):
928
944
index = self.make_index()
929
self.assertRaises(errors.BadIndexKey, list,
945
self.assertRaises(_mod_index.BadIndexKey, list,
930
946
index.iter_entries_prefix([(None, )]))
932
948
def test_iter_key_prefix_wrong_length(self):
933
949
index = self.make_index()
934
self.assertRaises(errors.BadIndexKey, list,
935
index.iter_entries_prefix([('foo', None)]))
950
self.assertRaises(_mod_index.BadIndexKey, list,
951
index.iter_entries_prefix([(b'foo', None)]))
936
952
index = self.make_index(key_elements=2)
937
self.assertRaises(errors.BadIndexKey, list,
938
index.iter_entries_prefix([('foo', )]))
939
self.assertRaises(errors.BadIndexKey, list,
940
index.iter_entries_prefix([('foo', None, None)]))
953
self.assertRaises(_mod_index.BadIndexKey, list,
954
index.iter_entries_prefix([(b'foo', )]))
955
self.assertRaises(_mod_index.BadIndexKey, list,
956
index.iter_entries_prefix([(b'foo', None, None)]))
942
958
def test_iter_key_prefix_1_key_element_no_refs(self):
943
index = self.make_index( nodes=[
944
(('name', ), 'data', ()),
945
(('ref', ), 'refdata', ())])
946
self.assertEqual(set([(index, ('name', ), 'data'),
947
(index, ('ref', ), 'refdata')]),
948
set(index.iter_entries_prefix([('name', ), ('ref', )])))
959
index = self.make_index(nodes=[
960
((b'name', ), b'data', ()),
961
((b'ref', ), b'refdata', ())])
962
self.assertEqual({(index, (b'name', ), b'data'),
963
(index, (b'ref', ), b'refdata')},
964
set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
950
966
def test_iter_key_prefix_1_key_element_refs(self):
951
967
index = self.make_index(1, nodes=[
952
(('name', ), 'data', ([('ref', )], )),
953
(('ref', ), 'refdata', ([], ))])
954
self.assertEqual(set([(index, ('name', ), 'data', ((('ref',),),)),
955
(index, ('ref', ), 'refdata', ((), ))]),
956
set(index.iter_entries_prefix([('name', ), ('ref', )])))
968
((b'name', ), b'data', ([(b'ref', )], )),
969
((b'ref', ), b'refdata', ([], ))])
970
self.assertEqual({(index, (b'name', ), b'data', (((b'ref',),),)),
971
(index, (b'ref', ), b'refdata', ((), ))},
972
set(index.iter_entries_prefix([(b'name', ), (b'ref', )])))
958
974
def test_iter_key_prefix_2_key_element_no_refs(self):
959
975
index = self.make_index(key_elements=2, nodes=[
960
(('name', 'fin1'), 'data', ()),
961
(('name', 'fin2'), 'beta', ()),
962
(('ref', 'erence'), 'refdata', ())])
963
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
964
(index, ('ref', 'erence'), 'refdata')]),
965
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
966
self.assertEqual(set([(index, ('name', 'fin1'), 'data'),
967
(index, ('name', 'fin2'), 'beta')]),
968
set(index.iter_entries_prefix([('name', None)])))
976
((b'name', b'fin1'), b'data', ()),
977
((b'name', b'fin2'), b'beta', ()),
978
((b'ref', b'erence'), b'refdata', ())])
979
self.assertEqual({(index, (b'name', b'fin1'), b'data'),
980
(index, (b'ref', b'erence'), b'refdata')},
981
set(index.iter_entries_prefix(
982
[(b'name', b'fin1'), (b'ref', b'erence')])))
983
self.assertEqual({(index, (b'name', b'fin1'), b'data'),
984
(index, (b'name', b'fin2'), b'beta')},
985
set(index.iter_entries_prefix([(b'name', None)])))
970
987
def test_iter_key_prefix_2_key_element_refs(self):
971
988
index = self.make_index(1, key_elements=2, nodes=[
972
(('name', 'fin1'), 'data', ([('ref', 'erence')], )),
973
(('name', 'fin2'), 'beta', ([], )),
974
(('ref', 'erence'), 'refdata', ([], ))])
975
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
976
(index, ('ref', 'erence'), 'refdata', ((), ))]),
977
set(index.iter_entries_prefix([('name', 'fin1'), ('ref', 'erence')])))
978
self.assertEqual(set([(index, ('name', 'fin1'), 'data', ((('ref', 'erence'),),)),
979
(index, ('name', 'fin2'), 'beta', ((), ))]),
980
set(index.iter_entries_prefix([('name', None)])))
989
((b'name', b'fin1'), b'data', ([(b'ref', b'erence')], )),
990
((b'name', b'fin2'), b'beta', ([], )),
991
((b'ref', b'erence'), b'refdata', ([], ))])
993
{(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
994
(index, (b'ref', b'erence'), b'refdata', ((), ))},
995
set(index.iter_entries_prefix(
996
[(b'name', b'fin1'), (b'ref', b'erence')])))
998
{(index, (b'name', b'fin1'), b'data', (((b'ref', b'erence'),),)),
999
(index, (b'name', b'fin2'), b'beta', ((), ))},
1000
set(index.iter_entries_prefix([(b'name', None)])))
982
1002
# XXX: external_references tests are duplicated in test_index. We
983
1003
# probably should have per_graph_index tests...
988
1008
def test_external_references_no_results(self):
989
1009
index = self.make_index(ref_lists=1, nodes=[
990
(('key',), 'value', ([],))])
1010
((b'key',), b'value', ([],))])
991
1011
self.assertEqual(set(), index.external_references(0))
993
1013
def test_external_references_missing_ref(self):
994
missing_key = ('missing',)
1014
missing_key = (b'missing',)
995
1015
index = self.make_index(ref_lists=1, nodes=[
996
(('key',), 'value', ([missing_key],))])
997
self.assertEqual(set([missing_key]), index.external_references(0))
1016
((b'key',), b'value', ([missing_key],))])
1017
self.assertEqual({missing_key}, index.external_references(0))
999
1019
def test_external_references_multiple_ref_lists(self):
1000
missing_key = ('missing',)
1020
missing_key = (b'missing',)
1001
1021
index = self.make_index(ref_lists=2, nodes=[
1002
(('key',), 'value', ([], [missing_key]))])
1022
((b'key',), b'value', ([], [missing_key]))])
1003
1023
self.assertEqual(set([]), index.external_references(0))
1004
self.assertEqual(set([missing_key]), index.external_references(1))
1024
self.assertEqual({missing_key}, index.external_references(1))
1006
1026
def test_external_references_two_records(self):
1007
1027
index = self.make_index(ref_lists=1, nodes=[
1008
(('key-1',), 'value', ([('key-2',)],)),
1009
(('key-2',), 'value', ([],)),
1028
((b'key-1',), b'value', ([(b'key-2',)],)),
1029
((b'key-2',), b'value', ([],)),
1011
1031
self.assertEqual(set([]), index.external_references(0))
1013
1033
def test__find_ancestors_one_page(self):
1016
1036
index = self.make_index(ref_lists=1, key_elements=1, nodes=[
1017
(key1, 'value', ([key2],)),
1018
(key2, 'value', ([],)),
1037
(key1, b'value', ([key2],)),
1038
(key2, b'value', ([],)),
1020
1040
parent_map = {}
1021
1041
missing_keys = set()
1185
1205
class TestBTreeNodes(BTreeTestCase):
1207
scenarios = btreeparser_scenarios()
1187
1209
def setUp(self):
1188
BTreeTestCase.setUp(self)
1210
super(TestBTreeNodes, self).setUp()
1189
1211
self.overrideAttr(btree_index, '_btree_serializer', self.parse_btree)
1191
1213
def test_LeafNode_1_0(self):
1192
node_bytes = ("type=leaf\n"
1193
"0000000000000000000000000000000000000000\x00\x00value:0\n"
1194
"1111111111111111111111111111111111111111\x00\x00value:1\n"
1195
"2222222222222222222222222222222222222222\x00\x00value:2\n"
1196
"3333333333333333333333333333333333333333\x00\x00value:3\n"
1197
"4444444444444444444444444444444444444444\x00\x00value:4\n")
1214
node_bytes = (b"type=leaf\n"
1215
b"0000000000000000000000000000000000000000\x00\x00value:0\n"
1216
b"1111111111111111111111111111111111111111\x00\x00value:1\n"
1217
b"2222222222222222222222222222222222222222\x00\x00value:2\n"
1218
b"3333333333333333333333333333333333333333\x00\x00value:3\n"
1219
b"4444444444444444444444444444444444444444\x00\x00value:4\n")
1198
1220
node = btree_index._LeafNode(node_bytes, 1, 0)
1199
1221
# We do direct access, or don't care about order, to leaf nodes most of
1200
1222
# the time, so a dict is useful:
1201
1223
self.assertEqual({
1202
("0000000000000000000000000000000000000000",): ("value:0", ()),
1203
("1111111111111111111111111111111111111111",): ("value:1", ()),
1204
("2222222222222222222222222222222222222222",): ("value:2", ()),
1205
("3333333333333333333333333333333333333333",): ("value:3", ()),
1206
("4444444444444444444444444444444444444444",): ("value:4", ()),
1224
(b"0000000000000000000000000000000000000000",): (b"value:0", ()),
1225
(b"1111111111111111111111111111111111111111",): (b"value:1", ()),
1226
(b"2222222222222222222222222222222222222222",): (b"value:2", ()),
1227
(b"3333333333333333333333333333333333333333",): (b"value:3", ()),
1228
(b"4444444444444444444444444444444444444444",): (b"value:4", ()),
1229
}, dict(node.all_items()))
1209
1231
def test_LeafNode_2_2(self):
1210
node_bytes = ("type=leaf\n"
1211
"00\x0000\x00\t00\x00ref00\x00value:0\n"
1212
"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1213
"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1214
"11\x0044\x00\t11\x00ref00\x00value:4\n"
1232
node_bytes = (b"type=leaf\n"
1233
b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1234
b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1235
b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1236
b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1217
1239
node = btree_index._LeafNode(node_bytes, 2, 2)
1218
1240
# We do direct access, or don't care about order, to leaf nodes most of
1219
1241
# the time, so a dict is useful:
1220
1242
self.assertEqual({
1221
('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
1222
('00', '11'): ('value:1',
1223
((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
1224
('11', '33'): ('value:3',
1225
((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1226
('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1243
(b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1244
(b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1245
((b'00', b'ref00'), (b'01', b'ref01')))),
1246
(b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1247
((b'11', b'ref22'), (b'11', b'ref22')))),
1248
(b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1249
}, dict(node.all_items()))
1229
1251
def test_InternalNode_1(self):
1230
node_bytes = ("type=internal\n"
1232
"0000000000000000000000000000000000000000\n"
1233
"1111111111111111111111111111111111111111\n"
1234
"2222222222222222222222222222222222222222\n"
1235
"3333333333333333333333333333333333333333\n"
1236
"4444444444444444444444444444444444444444\n"
1252
node_bytes = (b"type=internal\n"
1254
b"0000000000000000000000000000000000000000\n"
1255
b"1111111111111111111111111111111111111111\n"
1256
b"2222222222222222222222222222222222222222\n"
1257
b"3333333333333333333333333333333333333333\n"
1258
b"4444444444444444444444444444444444444444\n"
1238
1260
node = btree_index._InternalNode(node_bytes)
1239
1261
# We want to bisect to find the right children from this node, so a
1240
1262
# vector is most useful.
1241
1263
self.assertEqual([
1242
("0000000000000000000000000000000000000000",),
1243
("1111111111111111111111111111111111111111",),
1244
("2222222222222222222222222222222222222222",),
1245
("3333333333333333333333333333333333333333",),
1246
("4444444444444444444444444444444444444444",),
1264
(b"0000000000000000000000000000000000000000",),
1265
(b"1111111111111111111111111111111111111111",),
1266
(b"2222222222222222222222222222222222222222",),
1267
(b"3333333333333333333333333333333333333333",),
1268
(b"4444444444444444444444444444444444444444",),
1248
1270
self.assertEqual(1, node.offset)
1250
1272
def test_LeafNode_2_2(self):
1251
node_bytes = ("type=leaf\n"
1252
"00\x0000\x00\t00\x00ref00\x00value:0\n"
1253
"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1254
"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1255
"11\x0044\x00\t11\x00ref00\x00value:4\n"
1273
node_bytes = (b"type=leaf\n"
1274
b"00\x0000\x00\t00\x00ref00\x00value:0\n"
1275
b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n"
1276
b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n"
1277
b"11\x0044\x00\t11\x00ref00\x00value:4\n"
1258
1280
node = btree_index._LeafNode(node_bytes, 2, 2)
1259
1281
# We do direct access, or don't care about order, to leaf nodes most of
1260
1282
# the time, so a dict is useful:
1261
1283
self.assertEqual({
1262
('00', '00'): ('value:0', ((), (('00', 'ref00'),))),
1263
('00', '11'): ('value:1',
1264
((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01')))),
1265
('11', '33'): ('value:3',
1266
((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22')))),
1267
('11', '44'): ('value:4', ((), (('11', 'ref00'),)))
1284
(b'00', b'00'): (b'value:0', ((), ((b'00', b'ref00'),))),
1285
(b'00', b'11'): (b'value:1', (((b'00', b'ref00'),),
1286
((b'00', b'ref00'), (b'01', b'ref01')))),
1287
(b'11', b'33'): (b'value:3', (((b'11', b'ref22'),),
1288
((b'11', b'ref22'), (b'11', b'ref22')))),
1289
(b'11', b'44'): (b'value:4', ((), ((b'11', b'ref00'),)))
1290
}, dict(node.all_items()))
1270
1292
def assertFlattened(self, expected, key, value, refs):
1271
1293
flat_key, flat_line = self.parse_btree._flatten_node(
1272
1294
(None, key, value, refs), bool(refs))
1273
self.assertEqual('\x00'.join(key), flat_key)
1295
self.assertEqual(b'\x00'.join(key), flat_key)
1274
1296
self.assertEqual(expected, flat_line)
1276
1298
def test__flatten_node(self):
1277
self.assertFlattened('key\0\0value\n', ('key',), 'value', [])
1278
self.assertFlattened('key\0tuple\0\0value str\n',
1279
('key', 'tuple'), 'value str', [])
1280
self.assertFlattened('key\0tuple\0triple\0\0value str\n',
1281
('key', 'tuple', 'triple'), 'value str', [])
1282
self.assertFlattened('k\0t\0s\0ref\0value str\n',
1283
('k', 't', 's'), 'value str', [[('ref',)]])
1284
self.assertFlattened('key\0tuple\0ref\0key\0value str\n',
1285
('key', 'tuple'), 'value str', [[('ref', 'key')]])
1286
self.assertFlattened("00\x0000\x00\t00\x00ref00\x00value:0\n",
1287
('00', '00'), 'value:0', ((), (('00', 'ref00'),)))
1288
self.assertFlattened(
1289
"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
1290
('00', '11'), 'value:1',
1291
((('00', 'ref00'),), (('00', 'ref00'), ('01', 'ref01'))))
1292
self.assertFlattened(
1293
"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
1294
('11', '33'), 'value:3',
1295
((('11', 'ref22'),), (('11', 'ref22'), ('11', 'ref22'))))
1296
self.assertFlattened(
1297
"11\x0044\x00\t11\x00ref00\x00value:4\n",
1298
('11', '44'), 'value:4', ((), (('11', 'ref00'),)))
1299
self.assertFlattened(b'key\0\0value\n', (b'key',), b'value', [])
1300
self.assertFlattened(b'key\0tuple\0\0value str\n',
1301
(b'key', b'tuple'), b'value str', [])
1302
self.assertFlattened(b'key\0tuple\0triple\0\0value str\n',
1303
(b'key', b'tuple', b'triple'), b'value str', [])
1304
self.assertFlattened(b'k\0t\0s\0ref\0value str\n',
1305
(b'k', b't', b's'), b'value str', [[(b'ref',)]])
1306
self.assertFlattened(b'key\0tuple\0ref\0key\0value str\n',
1307
(b'key', b'tuple'), b'value str', [[(b'ref', b'key')]])
1308
self.assertFlattened(b"00\x0000\x00\t00\x00ref00\x00value:0\n",
1309
(b'00', b'00'), b'value:0', ((), ((b'00', b'ref00'),)))
1310
self.assertFlattened(
1311
b"00\x0011\x0000\x00ref00\t00\x00ref00\r01\x00ref01\x00value:1\n",
1312
(b'00', b'11'), b'value:1',
1313
(((b'00', b'ref00'),), ((b'00', b'ref00'), (b'01', b'ref01'))))
1314
self.assertFlattened(
1315
b"11\x0033\x0011\x00ref22\t11\x00ref22\r11\x00ref22\x00value:3\n",
1316
(b'11', b'33'), b'value:3',
1317
(((b'11', b'ref22'),), ((b'11', b'ref22'), (b'11', b'ref22'))))
1318
self.assertFlattened(
1319
b"11\x0044\x00\t11\x00ref00\x00value:4\n",
1320
(b'11', b'44'), b'value:4', ((), ((b'11', b'ref00'),)))
1301
1323
class TestCompiledBtree(tests.TestCase):