1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
# Copyright (C) 2008 Canonical Ltd
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
#
"""B+Tree index parsing."""
from bzrlib import static_tuple
def _parse_leaf_lines(bytes, key_length, ref_list_length):
lines = bytes.split('\n')
nodes = []
as_st = static_tuple.StaticTuple.from_sequence
stuple = static_tuple.StaticTuple
for line in lines[1:]:
if line == '':
return nodes
elements = line.split('\0', key_length)
# keys are tuples
key = as_st(elements[:key_length]).intern()
line = elements[-1]
references, value = line.rsplit('\0', 1)
if ref_list_length:
ref_lists = []
for ref_string in references.split('\t'):
ref_list = as_st([as_st(ref.split('\0')).intern()
for ref in ref_string.split('\r') if ref])
ref_lists.append(ref_list)
ref_lists = as_st(ref_lists)
node_value = stuple(value, ref_lists)
else:
node_value = stuple(value, stuple())
# No need for StaticTuple here as it is put into a dict
nodes.append((key, node_value))
return nodes
def _flatten_node(node, reference_lists):
"""Convert a node into the serialized form.
:param node: A tuple representing a node (key_tuple, value, references)
:param reference_lists: Does this index have reference lists?
:return: (string_key, flattened)
string_key The serialized key for referencing this node
flattened A string with the serialized form for the contents
"""
if reference_lists:
# TODO: Consider turning this back into the 'unoptimized' nested loop
# form. It is probably more obvious for most people, and this is
# just a reference implementation.
flattened_references = ['\r'.join(['\x00'.join(reference)
for reference in ref_list])
for ref_list in node[3]]
else:
flattened_references = []
string_key = '\x00'.join(node[1])
line = ("%s\x00%s\x00%s\n" % (string_key,
'\t'.join(flattened_references), node[2]))
return string_key, line
|