1
# Copyright (C) 2008 Canonical Ltd
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18
"""Pyrex extensions to btree node parsing."""
21
cdef extern from "python-compat.h":
24
cdef extern from "stdlib.h":
25
ctypedef unsigned size_t
27
cdef extern from "Python.h":
28
ctypedef int Py_ssize_t # Required for older pyrex versions
29
ctypedef struct PyObject:
31
int PyList_Append(object lst, object item) except -1
33
char *PyString_AsString(object p) except NULL
34
object PyString_FromStringAndSize(char *, Py_ssize_t)
35
int PyString_CheckExact(object s)
36
int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *)
37
Py_ssize_t PyString_Size(object p)
38
Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
39
char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
40
int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
41
int PyTuple_CheckExact(object t)
42
Py_ssize_t PyTuple_GET_SIZE(object t)
43
PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
45
cdef extern from "string.h":
46
void *memcpy(void *dest, void *src, size_t n)
47
void *memchr(void *s, int c, size_t n)
49
# void *memrchr(void *s, int c, size_t n)
50
int strncmp(char *s1, char *s2, size_t n)
53
# TODO: Find some way to import this from _dirstate_helpers
54
cdef void* _my_memrchr(void *s, int c, size_t n):
55
# memrchr seems to be a GNU extension, so we have to implement it ourselves
56
# It is not present in any win32 standard library
68
# TODO: Import this from _dirstate_helpers when it is merged
69
cdef object safe_string_from_size(char *s, Py_ssize_t size):
72
'tried to create a string with an invalid size: %d @0x%x'
74
return PyString_FromStringAndSize(s, size)
77
cdef class BTreeLeafParser:
78
"""Parse the leaf nodes of a BTree index.
80
:ivar bytes: The PyString object containing the uncompressed text for the
82
:ivar key_length: An integer describing how many pieces the keys have for
84
:ivar ref_list_length: An integer describing how many references this index
86
:ivar keys: A PyList of keys found in this node.
88
:ivar _cur_str: A pointer to the start of the next line to parse
89
:ivar _end_str: A pointer to the end of bytes
90
:ivar _start: Pointer to the location within the current line while
92
:ivar _header_found: True when we have parsed the header for this node
97
cdef int ref_list_length
102
# The current start point for parsing
105
cdef int _header_found
107
def __init__(self, bytes, key_length, ref_list_length):
109
self.key_length = key_length
110
self.ref_list_length = ref_list_length
114
self._header_found = 0
116
cdef extract_key(self, char * last):
119
:param last: points at the byte after the last byte permitted for the
123
cdef int loop_counter
127
while loop_counter < self.key_length:
128
loop_counter = loop_counter + 1
130
temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
132
if loop_counter == self.key_length:
137
failure_string = ("invalid key, wanted segment from " +
138
repr(safe_string_from_size(self._start,
139
last - self._start)))
140
raise AssertionError(failure_string)
141
# capture the key string
142
# TODO: Consider using PyIntern_FromString, the only caveat is that
143
# it assumes a NULL-terminated string, so we have to check if
144
# temp_ptr[0] == c'\0' or some other char.
145
key_element = safe_string_from_size(self._start,
146
temp_ptr - self._start)
147
# advance our pointer
148
self._start = temp_ptr + 1
149
PyList_Append(key_segments, key_element)
150
return tuple(key_segments)
152
cdef int process_line(self) except -1:
153
"""Process a line in the bytes."""
157
cdef char *next_start
158
cdef int loop_counter
160
self._start = self._cur_str
161
# Find the next newline
162
last = <char*>memchr(self._start, c'\n', self._end_str - self._start)
164
# Process until the end of the file
166
self._cur_str = self._end_str
168
# And the next string is right after it
169
self._cur_str = last + 1
170
# The last character is right before the '\n'
173
if last == self._start:
176
if last < self._start:
177
# Unexpected error condition - fail
179
if 0 == self._header_found:
180
# The first line in a leaf node is the header "type=leaf\n"
181
if strncmp("type=leaf", self._start, last - self._start) == 0:
182
self._header_found = 1
185
raise AssertionError('Node did not start with "type=leaf": %r'
186
% (safe_string_from_size(self._start, last - self._start)))
189
key = self.extract_key(last)
190
# find the value area
191
temp_ptr = <char*>_my_memrchr(self._start, c'\0', last - self._start)
196
# capture the value string
197
value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
198
# shrink the references end point
200
if self.ref_list_length:
203
while loop_counter < self.ref_list_length:
205
# extract a reference list
206
loop_counter = loop_counter + 1
207
if last < self._start:
209
# find the next reference list end point:
210
temp_ptr = <char*>memchr(self._start, c'\t', last - self._start)
212
# Only valid for the last list
213
if loop_counter != self.ref_list_length:
216
raise AssertionError("invalid key")
218
# scan to the end of the ref list area
222
# scan to the end of this ref list
224
next_start = temp_ptr + 1
225
# Now, there may be multiple keys in the ref list.
226
while self._start < ref_ptr:
227
# loop finding keys and extracting them
228
temp_ptr = <char*>memchr(self._start, c'\r',
229
ref_ptr - self._start)
231
# key runs to the end
233
PyList_Append(ref_list, self.extract_key(temp_ptr))
234
PyList_Append(ref_lists, tuple(ref_list))
235
# prepare for the next reference list
236
self._start = next_start
237
ref_lists = tuple(ref_lists)
238
node_value = (value, ref_lists)
240
if last != self._start:
241
# unexpected reference data present
243
node_value = (value, ())
244
PyList_Append(self.keys, (key, node_value))
248
cdef Py_ssize_t byte_count
249
if not PyString_CheckExact(self.bytes):
250
raise AssertionError('self.bytes is not a string.')
251
byte_count = PyString_Size(self.bytes)
252
self._cur_str = PyString_AsString(self.bytes)
253
# This points to the last character in the string
254
self._end_str = self._cur_str + byte_count
255
while self._cur_str < self._end_str:
260
def _parse_leaf_lines(bytes, key_length, ref_list_length):
261
parser = BTreeLeafParser(bytes, key_length, ref_list_length)
262
return parser.parse()
265
def _flatten_node(node, reference_lists):
266
"""Convert a node into the serialized form.
268
:param node: A tuple representing a node:
269
(index, key_tuple, value, references)
270
:param reference_lists: Does this index have reference lists?
271
:return: (string_key, flattened)
272
string_key The serialized key for referencing this node
273
flattened A string with the serialized form for the contents
275
cdef int have_reference_lists
276
cdef Py_ssize_t flat_len
277
cdef Py_ssize_t key_len
278
cdef Py_ssize_t node_len
281
cdef Py_ssize_t value_len
283
cdef Py_ssize_t refs_len
284
cdef Py_ssize_t next_len
285
cdef int first_ref_list
286
cdef int first_reference
288
cdef PyObject *ref_bit
289
cdef Py_ssize_t ref_bit_len
291
if not PyTuple_CheckExact(node):
292
raise TypeError('We expected a tuple() for node not: %s'
294
node_len = PyTuple_GET_SIZE(node)
295
have_reference_lists = reference_lists
296
if have_reference_lists:
298
raise ValueError('With ref_lists, we expected 4 entries not: %s'
301
raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
303
# I don't expect that we can do faster than string.join()
304
string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
306
# TODO: instead of using string joins, precompute the final string length,
307
# and then malloc a single string and copy everything in.
309
# TODO: We probably want to use PySequenceFast, because we have lists and
310
# tuples, but we aren't sure which we will get.
312
# line := string_key NULL flat_refs NULL value LF
313
# string_key := BYTES (NULL BYTES)*
314
# flat_refs := ref_list (TAB ref_list)*
315
# ref_list := ref (CR ref)*
316
# ref := BYTES (NULL BYTES)*
319
if have_reference_lists:
320
# Figure out how many bytes it will take to store the references
321
ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
322
next_len = len(ref_lists) # TODO: use a Py function
324
# If there are no nodes, we don't need to do any work
325
# Otherwise we will need (len - 1) '\t' characters to separate
326
# the reference lists
327
refs_len = refs_len + (next_len - 1)
328
for ref_list in ref_lists:
329
next_len = len(ref_list)
331
# We will need (len - 1) '\r' characters to separate the
333
refs_len = refs_len + (next_len - 1)
334
for reference in ref_list:
335
if not PyTuple_CheckExact(reference):
337
'We expect references to be tuples not: %s'
339
next_len = PyTuple_GET_SIZE(reference)
341
# We will need (len - 1) '\x00' characters to
342
# separate the reference key
343
refs_len = refs_len + (next_len - 1)
344
for i from 0 <= i < next_len:
345
ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
346
if not PyString_CheckExact_ptr(ref_bit):
347
raise TypeError('We expect reference bits'
348
' to be strings not: %s'
349
% type(<object>ref_bit))
350
refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
352
# So we have the (key NULL refs NULL value LF)
353
key_len = PyString_Size(string_key)
354
val = PyTuple_GET_ITEM_ptr_object(node, 2)
355
if not PyString_CheckExact_ptr(val):
356
raise TypeError('Expected a plain str for value not: %s'
358
value = PyString_AS_STRING_ptr(val)
359
value_len = PyString_GET_SIZE_ptr(val)
360
flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
361
line = PyString_FromStringAndSize(NULL, flat_len)
362
# Get a pointer to the new buffer
363
out = PyString_AsString(line)
364
memcpy(out, PyString_AsString(string_key), key_len)
370
for ref_list in ref_lists:
371
if first_ref_list == 0:
376
for reference in ref_list:
377
if first_reference == 0:
381
next_len = PyTuple_GET_SIZE(reference)
382
for i from 0 <= i < next_len:
386
ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
387
ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
388
memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
389
out = out + ref_bit_len
392
memcpy(out, value, value_len)
393
out = out + value_len
395
return string_key, line
added
removed
bzrlib/_btree_serializer_c.pyx
