1
# Copyright (C) 2009 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19
cdef extern from "python-compat.h":
23
ctypedef unsigned int size_t
24
int memcmp(void *, void*, size_t)
25
void memcpy(void *, void*, size_t)
26
void *memchr(void *s, int c, size_t len)
27
long strtol(char *, char **, int)
28
void sprintf(char *, char *, ...)
30
cdef extern from "Python.h":
31
ctypedef int Py_ssize_t # Required for older pyrex versions
34
ctypedef _PyObject PyObject
35
int PyTuple_CheckExact(object p)
36
Py_ssize_t PyTuple_GET_SIZE(object t)
37
int PyString_CheckExact(object)
38
char *PyString_AS_STRING(object s)
39
Py_ssize_t PyString_GET_SIZE(object)
41
int PyDict_SetItem(object d, object k, object v) except -1
43
object PyTuple_New(Py_ssize_t count)
44
void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)
46
void Py_INCREF(object)
48
PyObject * PyTuple_GET_ITEM_ptr "PyTuple_GET_ITEM" (object t,
50
int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *p)
51
Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *s)
52
char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
53
object PyString_FromStringAndSize(char*, Py_ssize_t)
55
cdef extern from "zlib.h":
56
ctypedef unsigned long uLong
57
ctypedef unsigned int uInt
58
ctypedef unsigned char Bytef
60
uLong crc32(uLong crc, Bytef *buf, uInt len)
62
# It seems we need to import the definitions so that the pyrex compiler has
63
# local names to access them.
64
from _static_tuple_c cimport StaticTuple,\
65
import_static_tuple_c, STATIC_TUPLE_ALL_STRING, StaticTuple_New, \
66
StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
69
from bzrlib import _static_tuple_c
70
# This sets up the StaticTuple C_API functionality
71
if import_static_tuple_c() != 0:
72
raise ImportError('der borken')
76
cdef object _InternalNode
81
# We shouldn't just copy this from _dirstate_helpers_pyx
82
cdef void* _my_memrchr(void *s, int c, size_t n):
83
# memrchr seems to be a GNU extension, so we have to implement it ourselves
96
def _search_key_16(key):
97
"""See chk_map._search_key_16."""
98
cdef Py_ssize_t num_bits
100
cdef Py_ssize_t num_out_bytes
104
cdef Py_ssize_t out_off
108
if not PyTuple_CheckExact(key) and not StaticTuple_CheckExact(key):
109
raise TypeError('key %r is not a tuple' % (key,))
111
# 4 bytes per crc32, and another 1 byte between bits
112
num_out_bytes = (9 * num_bits) - 1
113
out = PyString_FromStringAndSize(NULL, num_out_bytes)
114
c_out = PyString_AS_STRING(out)
115
for i from 0 <= i < num_bits:
119
# We use the _ptr variant, because GET_ITEM returns a borrowed
120
# reference, and Pyrex assumes that returned 'object' are a new
122
# XXX: This needs to be updated for PySequence_GetItem since both
123
# PyTuple and StaticTuple support that api
124
bit = key[i]# PyTuple_GET_ITEM_ptr(key, i)
125
if not PyString_CheckExact(bit):
126
raise TypeError('Bit %d of %r is not a string' % (i, key))
127
c_bit = <Bytef *>PyString_AS_STRING(bit)
128
c_len = PyString_GET_SIZE(bit)
129
crc_val = crc32(0, c_bit, c_len)
131
sprintf(c_out, '%08X', crc_val)
136
def _search_key_255(key):
137
"""See chk_map._search_key_255."""
138
cdef Py_ssize_t num_bits
140
cdef Py_ssize_t num_out_bytes
144
cdef Py_ssize_t out_off
148
if not PyTuple_CheckExact(key) and not StaticTuple_CheckExact(key):
149
raise TypeError('key %r is not a tuple' % (key,))
151
# 4 bytes per crc32, and another 1 byte between bits
152
num_out_bytes = (5 * num_bits) - 1
153
out = PyString_FromStringAndSize(NULL, num_out_bytes)
154
c_out = PyString_AS_STRING(out)
155
for i from 0 <= i < num_bits:
159
bit = key[i] # PyTuple_GET_ITEM_ptr(key, i)
160
if not PyString_CheckExact(bit):
161
raise TypeError('Bit %d of %r is not a string: %r' % (i, key,
163
c_bit = <Bytef *>PyString_AS_STRING(bit)
164
c_len = PyString_GET_SIZE(bit)
165
crc_val = crc32(0, c_bit, c_len)
167
c_out[0] = (crc_val >> 24) & 0xFF
168
c_out[1] = (crc_val >> 16) & 0xFF
169
c_out[2] = (crc_val >> 8) & 0xFF
170
c_out[3] = (crc_val >> 0) & 0xFF
171
for j from 0 <= j < 4:
172
if c_out[j] == c'\n':
178
cdef int _get_int_from_line(char **cur, char *end, char *message) except -1:
179
"""Read a positive integer from the data stream.
181
:param cur: The start of the data, this will be moved to after the
182
trailing newline when done.
183
:param end: Do not parse any data past this byte.
184
:return: The integer stored in those bytes
187
cdef char *next_line, *next
189
next_line = <char *>memchr(cur[0], c'\n', end - cur[0])
190
if next_line == NULL:
191
raise ValueError("Missing %s line\n" % message)
193
value = strtol(cur[0], &next, 10)
194
if next != next_line:
195
raise ValueError("%s line not a proper int\n" % message)
196
cur[0] = next_line + 1
200
def _deserialise_leaf_node(bytes, key, search_key_func=None):
201
"""Deserialise bytes, with key key, into a LeafNode.
203
:param bytes: The bytes of the node.
204
:param key: The key that the serialised node has.
206
cdef char *c_bytes, *cur, *next, *end
208
cdef Py_ssize_t c_bytes_len, prefix_length, items_length
209
cdef int maximum_size, width, length, i, prefix_tail_len
210
cdef int num_value_lines, num_prefix_bits
211
cdef char *prefix, *value_start, *prefix_tail
212
cdef char *next_null, *last_null, *line_start
213
cdef char *c_entry, *entry_start
214
cdef StaticTuple entry_bits
216
if _LeafNode is None:
217
from bzrlib import chk_map
218
_LeafNode = chk_map.LeafNode
219
_InternalNode = chk_map.InternalNode
220
_unknown = chk_map._unknown
222
result = _LeafNode(search_key_func=search_key_func)
223
# Splitlines can split on '\r' so don't use it, split('\n') adds an
224
# extra '' if the bytes ends in a final newline.
225
if not PyString_CheckExact(bytes):
226
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
228
c_bytes = PyString_AS_STRING(bytes)
229
c_bytes_len = PyString_GET_SIZE(bytes)
231
if c_bytes_len < 9 or memcmp(c_bytes, "chkleaf:\n", 9) != 0:
232
raise ValueError("not a serialised leaf node: %r" % bytes)
233
if c_bytes[c_bytes_len - 1] != c'\n':
234
raise ValueError("bytes does not end in a newline")
236
end = c_bytes + c_bytes_len
238
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
239
width = _get_int_from_line(&cur, end, "width")
240
length = _get_int_from_line(&cur, end, "length")
242
next_line = <char *>memchr(cur, c'\n', end - cur)
243
if next_line == NULL:
244
raise ValueError('Missing the prefix line\n')
246
prefix_length = next_line - cur
252
next_null = <char *>memchr(prefix, c'\0', prefix_length)
253
while next_null != NULL:
254
num_prefix_bits = num_prefix_bits + 1
256
PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
257
prefix_tail = next_null + 1
258
next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
259
prefix_tail_len = next_line - prefix_tail
261
if num_prefix_bits >= width:
262
raise ValueError('Prefix has too many nulls versus width')
264
items_length = end - cur
268
next_line = <char *>memchr(cur, c'\n', end - cur)
269
if next_line == NULL:
270
raise ValueError('null line\n')
271
last_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
272
if last_null == NULL:
273
raise ValueError('fail to find the num value lines null')
274
next_null = last_null + 1 # move past NULL
275
num_value_lines = _get_int_from_line(&next_null, next_line + 1,
279
# Walk num_value_lines forward
280
for i from 0 <= i < num_value_lines:
281
next_line = <char *>memchr(cur, c'\n', end - cur)
282
if next_line == NULL:
283
raise ValueError('missing trailing newline')
285
entry_bits = StaticTuple_New(width)
286
for i from 0 <= i < num_prefix_bits:
287
entry = prefix_bits[i]
288
# SET_ITEM 'steals' a reference
290
StaticTuple_SET_ITEM(entry_bits, i, entry)
291
value = PyString_FromStringAndSize(value_start, next_line - value_start)
292
# The next entry bit needs the 'tail' from the prefix, and first part
294
entry_start = line_start
295
next_null = <char *>memchr(entry_start, c'\0',
296
last_null - entry_start + 1)
297
if next_null == NULL:
298
raise ValueError('bad no null, bad')
299
entry = PyString_FromStringAndSize(NULL,
300
prefix_tail_len + next_null - line_start)
301
c_entry = PyString_AS_STRING(entry)
302
if prefix_tail_len > 0:
303
memcpy(c_entry, prefix_tail, prefix_tail_len)
304
if next_null - line_start > 0:
305
memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
308
StaticTuple_SET_ITEM(entry_bits, i, entry)
309
while next_null != last_null: # We have remaining bits
312
raise ValueError("Too many bits for entry")
313
entry_start = next_null + 1
314
next_null = <char *>memchr(entry_start, c'\0',
315
last_null - entry_start + 1)
316
if next_null == NULL:
317
raise ValueError('bad no null')
318
entry = PyString_FromStringAndSize(entry_start,
319
next_null - entry_start)
321
StaticTuple_SET_ITEM(entry_bits, i, entry)
322
if len(entry_bits) != width:
323
raise AssertionError(
324
'Incorrect number of elements (%d vs %d)'
325
% (len(entry_bits)+1, width + 1))
326
entry_bits = StaticTuple_Intern(entry_bits)
327
PyDict_SetItem(items, entry_bits, value)
328
if len(items) != length:
329
raise ValueError("item count (%d) mismatch for key %s,"
330
" bytes %r" % (length, entry_bits, bytes))
331
result._items = items
333
result._maximum_size = maximum_size
335
result._key_width = width
336
result._raw_size = items_length + length * prefix_length
338
result._search_prefix = None
339
result._common_serialised_prefix = None
341
result._search_prefix = _unknown
342
result._common_serialised_prefix = PyString_FromStringAndSize(prefix,
344
if c_bytes_len != result._current_size():
345
raise AssertionError('_current_size computed incorrectly %d != %d',
346
c_bytes_len, result._current_size())
350
def _deserialise_internal_node(bytes, key, search_key_func=None):
351
cdef char *c_bytes, *cur, *next, *end
353
cdef Py_ssize_t c_bytes_len, prefix_length
354
cdef int maximum_size, width, length, i, prefix_tail_len
355
cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
357
if _InternalNode is None:
358
from bzrlib import chk_map
359
_LeafNode = chk_map.LeafNode
360
_InternalNode = chk_map.InternalNode
361
_unknown = chk_map._unknown
362
result = _InternalNode(search_key_func=search_key_func)
364
if not PyString_CheckExact(bytes):
365
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
367
c_bytes = PyString_AS_STRING(bytes)
368
c_bytes_len = PyString_GET_SIZE(bytes)
370
if c_bytes_len < 9 or memcmp(c_bytes, "chknode:\n", 9) != 0:
371
raise ValueError("not a serialised internal node: %r" % bytes)
372
if c_bytes[c_bytes_len - 1] != c'\n':
373
raise ValueError("bytes does not end in a newline")
377
end = c_bytes + c_bytes_len
378
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
379
width = _get_int_from_line(&cur, end, "width")
380
length = _get_int_from_line(&cur, end, "length")
382
next_line = <char *>memchr(cur, c'\n', end - cur)
383
if next_line == NULL:
384
raise ValueError('Missing the prefix line\n')
386
prefix_length = next_line - cur
390
# Find the null separator
391
next_line = <char *>memchr(cur, c'\n', end - cur)
392
if next_line == NULL:
393
raise ValueError('missing trailing newline')
394
next_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
395
if next_null == NULL:
396
raise ValueError('bad no null')
397
item_prefix = PyString_FromStringAndSize(NULL,
398
prefix_length + next_null - cur)
399
c_item_prefix = PyString_AS_STRING(item_prefix)
401
memcpy(c_item_prefix, prefix, prefix_length)
402
memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
403
flat_key = PyString_FromStringAndSize(next_null + 1,
404
next_line - next_null - 1)
405
flat_key = StaticTuple(flat_key).intern()
406
PyDict_SetItem(items, item_prefix, flat_key)
408
assert len(items) > 0
409
result._items = items
411
result._maximum_size = maximum_size
413
result._key_width = width
414
# XXX: InternalNodes don't really care about their size, and this will
415
# change if we add prefix compression
416
result._raw_size = None # len(bytes)
417
result._node_width = len(item_prefix)
418
result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
422
_key_type = StaticTuple
added
removed
bzrlib/_chk_map_pyx.pyx
