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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
|
# 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
"""Pyrex extensions to btree node parsing."""
cdef extern from "stdlib.h":
ctypedef unsigned size_t
cdef extern from "Python.h":
int PyList_Append(object lst, object item) except -1
char *PyString_AsString(object p)
object PyString_FromStringAndSize(char *, Py_ssize_t)
int PyString_CheckExact(object s)
Py_ssize_t PyString_Size(object p)
int PyTuple_CheckExact(object t)
cdef extern from "string.h":
void *memcpy(void *dest, void *src, size_t n)
void *memchr(void *s, int c, size_t n)
# GNU extension
# void *memrchr(void *s, int c, size_t n)
int strncmp(char *s1, char *s2, size_t n)
# TODO: Find some way to import this from _dirstate_helpers
cdef void* _my_memrchr(void *s, int c, size_t n):
# memrchr seems to be a GNU extension, so we have to implement it ourselves
# It is not present in any win32 standard library
cdef char *pos
cdef char *start
start = <char*>s
pos = start + n - 1
while pos >= start:
if pos[0] == c:
return <void*>pos
pos = pos - 1
return NULL
# TODO: Import this from _dirstate_helpers when it is merged
cdef object safe_string_from_size(char *s, Py_ssize_t size):
if size < 0:
raise AssertionError(
'tried to create a string with an invalid size: %d @0x%x'
% (size, <int>s))
return PyString_FromStringAndSize(s, size)
cdef class BTreeLeafParser:
"""Parse the leaf nodes of a BTree index.
:ivar bytes: The PyString object containing the uncompressed text for the
node.
:ivar key_length: An integer describing how many pieces the keys have for
this index.
:ivar ref_list_length: An integer describing how many references this index
contains.
:ivar keys: A PyList of keys found in this node.
:ivar _cur_str: A pointer to the start of the next line to parse
:ivar _end_str: A pointer to the end of bytes
:ivar _start: Pointer to the location within the current line while
parsing.
:ivar _header_found: True when we have parsed the header for this node
"""
cdef object bytes
cdef int key_length
cdef int ref_list_length
cdef object keys
cdef char * _cur_str
cdef char * _end_str
# The current start point for parsing
cdef char * _start
cdef int _header_found
def __init__(self, bytes, key_length, ref_list_length):
self.bytes = bytes
self.key_length = key_length
self.ref_list_length = ref_list_length
self.keys = []
self._cur_str = NULL
self._end_str = NULL
self._header_found = 0
cdef extract_key(self, char * last):
"""Extract a key.
:param last: points at the byte after the last byte permitted for the
key.
"""
cdef char *temp_ptr
cdef int loop_counter
# keys are tuples
loop_counter = 0
key_segments = []
while loop_counter < self.key_length:
loop_counter = loop_counter + 1
# grab a key segment
temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
if temp_ptr == NULL:
if loop_counter == self.key_length:
# capture to last
temp_ptr = last
else:
# Invalid line
failure_string = ("invalid key, wanted segment from " +
repr(safe_string_from_size(self._start,
last - self._start)))
raise AssertionError(failure_string)
# capture the key string
key_element = safe_string_from_size(self._start,
temp_ptr - self._start)
# advance our pointer
self._start = temp_ptr + 1
PyList_Append(key_segments, key_element)
return tuple(key_segments)
cdef int process_line(self) except -1:
"""Process a line in the bytes."""
cdef char *last
cdef char *temp_ptr
cdef char *ref_ptr
cdef char *next_start
cdef int loop_counter
self._start = self._cur_str
# Find the next newline
last = <char*>memchr(self._start, c'\n', self._end_str - self._start)
if last == NULL:
# Process until the end of the file
last = self._end_str
self._cur_str = self._end_str
else:
# And the next string is right after it
self._cur_str = last + 1
# The last character is right before the '\n'
last = last
if last == self._start:
# parsed it all.
return 0
if last < self._start:
# Unexpected error condition - fail
return -1
if 0 == self._header_found:
# The first line in a leaf node is the header "type=leaf\n"
if strncmp("type=leaf", self._start, last - self._start) == 0:
self._header_found = 1
return 0
else:
raise AssertionError('Node did not start with "type=leaf": %r'
% (safe_string_from_size(self._start, last - self._start)))
return -1
key = self.extract_key(last)
# find the value area
temp_ptr = <char*>_my_memrchr(self._start, c'\0', last - self._start)
if temp_ptr == NULL:
# Invalid line
return -1
else:
# capture the value string
value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
# shrink the references end point
last = temp_ptr
if self.ref_list_length:
ref_lists = []
loop_counter = 0
while loop_counter < self.ref_list_length:
ref_list = []
# extract a reference list
loop_counter = loop_counter + 1
if last < self._start:
return -1
# find the next reference list end point:
temp_ptr = <char*>memchr(self._start, c'\t', last - self._start)
if temp_ptr == NULL:
# Only valid for the last list
if loop_counter != self.ref_list_length:
# Invalid line
return -1
raise AssertionError("invalid key")
else:
# scan to the end of the ref list area
ref_ptr = last
next_start = last
else:
# scan to the end of this ref list
ref_ptr = temp_ptr
next_start = temp_ptr + 1
# Now, there may be multiple keys in the ref list.
while self._start < ref_ptr:
# loop finding keys and extracting them
temp_ptr = <char*>memchr(self._start, c'\r',
ref_ptr - self._start)
if temp_ptr == NULL:
# key runs to the end
temp_ptr = ref_ptr
PyList_Append(ref_list, self.extract_key(temp_ptr))
PyList_Append(ref_lists, tuple(ref_list))
# prepare for the next reference list
self._start = next_start
ref_lists = tuple(ref_lists)
node_value = (value, ref_lists)
else:
if last != self._start:
# unexpected reference data present
return -1
node_value = (value, ())
PyList_Append(self.keys, (key, node_value))
return 0
def parse(self):
cdef Py_ssize_t byte_count
if not PyString_CheckExact(self.bytes):
raise AssertionError('self.bytes is not a string.')
byte_count = PyString_Size(self.bytes)
self._cur_str = PyString_AsString(self.bytes)
# This points to the last character in the string
self._end_str = self._cur_str + byte_count
while self._cur_str < self._end_str:
self.process_line()
return self.keys
def _parse_leaf_lines(bytes, key_length, ref_list_length):
parser = BTreeLeafParser(bytes, key_length, ref_list_length)
return parser.parse()
def _flatten_node(node, reference_lists):
"""Convert a node into the serialized form.
:param node: A tuple representing a node:
(index, 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
"""
cdef Py_ssize_t flat_len
cdef Py_ssize_t key_len
cdef char * value
cdef Py_ssize_t value_len
cdef char * s
# I don't expect that we can do faster than string.join()
string_key = '\x00'.join(node[1])
# TODO: instead of using string joins, precompute the final string length,
# and then malloc a single string and copy everything in.
# TODO: We probably want to use PySequenceFast, because we have lists and
# tuples, but we aren't sure which we will get.
# line := string_key NULL flat_refs NULL value LF
# string_key := BYTES (NULL BYTES)*
# flat_refs := ref_list (TAB ref_list)*
# ref_list := ref (CR ref)*
# ref := BYTES (NULL BYTES)*
# value := BYTES
if not reference_lists:
# Simple case, we only have the key and the value
# So we have the (key NULL NULL value LF)
key_len = PyString_Size(string_key)
value = PyString_AsString(node[2])
value_len = PyString_Size(node[2])
flat_len = (key_len + 1 + 1 + value_len + 1)
line = PyString_FromStringAndSize(NULL, flat_len)
# Get a pointer to the new buffer
s = PyString_AsString(line)
memcpy(s, PyString_AsString(string_key), key_len)
s[key_len] = c'\0'
s[key_len + 1] = c'\0'
memcpy(s + key_len + 2, value, value_len)
s[key_len + 2 + value_len] = c'\n'
else:
flattened_references = []
for ref_list in node[3]:
ref_keys = []
for reference in ref_list:
ref_keys.append('\x00'.join(reference))
flattened_references.append('\r'.join(ref_keys))
line = ("%s\x00%s\x00%s\n" % (string_key,
'\t'.join(flattened_references), node[2]))
return string_key, line
|