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
32
ctypedef struct PyObject:
34
int PyTuple_CheckExact(object p)
35
Py_ssize_t PyTuple_GET_SIZE(object t)
36
int PyString_CheckExact(object)
37
char *PyString_AS_STRING(object s)
38
Py_ssize_t PyString_GET_SIZE(object)
40
int PyDict_SetItem(object d, object k, object v) except -1
42
object PyTuple_New(Py_ssize_t count)
43
void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)
45
void Py_INCREF(object)
47
PyObject * PyTuple_GET_ITEM_ptr "PyTuple_GET_ITEM" (object t,
49
int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *p)
50
Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *s)
51
char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
52
object PyString_FromStringAndSize(char*, Py_ssize_t)
54
# cimport all of the definitions we will need to access
55
from _static_tuple_c cimport StaticTuple,\
56
import_static_tuple_c, StaticTuple_New, \
57
StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
59
cdef extern from "_static_tuple_c.h":
60
# Defined explicitly rather than cimport-ing. Trying to use cimport, the
61
# type for PyObject is a different class that happens to have the same
63
PyObject * StaticTuple_GET_ITEM_ptr "StaticTuple_GET_ITEM" (StaticTuple,
66
cdef extern from "zlib.h":
67
ctypedef unsigned long uLong
68
ctypedef unsigned int uInt
69
ctypedef unsigned char Bytef
71
uLong crc32(uLong crc, Bytef *buf, uInt len)
74
# Set up the StaticTuple C_API functionality
75
import_static_tuple_c()
79
cdef object _InternalNode
84
# We shouldn't just copy this from _dirstate_helpers_pyx
85
cdef void* _my_memrchr(void *s, int c, size_t n):
86
# memrchr seems to be a GNU extension, so we have to implement it ourselves
99
def _search_key_16(key):
100
"""See chk_map._search_key_16."""
101
cdef Py_ssize_t num_bits
103
cdef Py_ssize_t num_out_bytes
107
cdef Py_ssize_t out_off
111
if not StaticTuple_CheckExact(key):
112
raise TypeError('key %r is not a StaticTuple' % (key,))
114
# 4 bytes per crc32, and another 1 byte between bits
115
num_out_bytes = (9 * num_bits) - 1
116
out = PyString_FromStringAndSize(NULL, num_out_bytes)
117
c_out = PyString_AS_STRING(out)
118
for i from 0 <= i < num_bits:
122
# We use the _ptr variant, because GET_ITEM returns a borrowed
123
# reference, and Pyrex assumes that returned 'object' are a new
125
bit = StaticTuple_GET_ITEM_ptr(key, i)
126
if not PyString_CheckExact_ptr(bit):
127
raise TypeError('Bit %d of %r is not a string' % (i, key))
128
c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
129
c_len = PyString_GET_SIZE_ptr(bit)
130
crc_val = crc32(0, c_bit, c_len)
132
sprintf(c_out, '%08X', crc_val)
137
def _search_key_255(key):
138
"""See chk_map._search_key_255."""
139
cdef Py_ssize_t num_bits
141
cdef Py_ssize_t num_out_bytes
145
cdef Py_ssize_t out_off
149
if not StaticTuple_CheckExact(key):
150
raise TypeError('key %r is not a StaticTuple' % (key,))
152
# 4 bytes per crc32, and another 1 byte between bits
153
num_out_bytes = (5 * num_bits) - 1
154
out = PyString_FromStringAndSize(NULL, num_out_bytes)
155
c_out = PyString_AS_STRING(out)
156
for i from 0 <= i < num_bits:
160
bit = StaticTuple_GET_ITEM_ptr(key, i)
161
if not PyString_CheckExact_ptr(bit):
162
raise TypeError('Bit %d of %r is not a string: %r'
163
% (i, key, <object>bit))
164
c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
165
c_len = PyString_GET_SIZE_ptr(bit)
166
crc_val = crc32(0, c_bit, c_len)
168
c_out[0] = (crc_val >> 24) & 0xFF
169
c_out[1] = (crc_val >> 16) & 0xFF
170
c_out[2] = (crc_val >> 8) & 0xFF
171
c_out[3] = (crc_val >> 0) & 0xFF
172
for j from 0 <= j < 4:
173
if c_out[j] == c'\n':
179
cdef int _get_int_from_line(char **cur, char *end, char *message) except -1:
180
"""Read a positive integer from the data stream.
182
:param cur: The start of the data, this will be moved to after the
183
trailing newline when done.
184
:param end: Do not parse any data past this byte.
185
:return: The integer stored in those bytes
188
cdef char *next_line, *next
190
next_line = <char *>memchr(cur[0], c'\n', end - cur[0])
191
if next_line == NULL:
192
raise ValueError("Missing %s line\n" % message)
194
value = strtol(cur[0], &next, 10)
195
if next != next_line:
196
raise ValueError("%s line not a proper int\n" % message)
197
cur[0] = next_line + 1
201
def _deserialise_leaf_node(bytes, key, search_key_func=None):
202
"""Deserialise bytes, with key key, into a LeafNode.
204
:param bytes: The bytes of the node.
205
:param key: The key that the serialised node has.
207
cdef char *c_bytes, *cur, *next, *end
209
cdef Py_ssize_t c_bytes_len, prefix_length, items_length
210
cdef int maximum_size, width, length, i, prefix_tail_len
211
cdef int num_value_lines, num_prefix_bits
212
cdef char *prefix, *value_start, *prefix_tail
213
cdef char *next_null, *last_null, *line_start
214
cdef char *c_entry, *entry_start
215
cdef StaticTuple entry_bits
217
if _LeafNode is None:
218
from bzrlib import chk_map
219
_LeafNode = chk_map.LeafNode
220
_InternalNode = chk_map.InternalNode
221
_unknown = chk_map._unknown
223
result = _LeafNode(search_key_func=search_key_func)
224
# Splitlines can split on '\r' so don't use it, split('\n') adds an
225
# extra '' if the bytes ends in a final newline.
226
if not PyString_CheckExact(bytes):
227
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
229
c_bytes = PyString_AS_STRING(bytes)
230
c_bytes_len = PyString_GET_SIZE(bytes)
232
if c_bytes_len < 9 or memcmp(c_bytes, "chkleaf:\n", 9) != 0:
233
raise ValueError("not a serialised leaf node: %r" % bytes)
234
if c_bytes[c_bytes_len - 1] != c'\n':
235
raise ValueError("bytes does not end in a newline")
237
end = c_bytes + c_bytes_len
239
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
240
width = _get_int_from_line(&cur, end, "width")
241
length = _get_int_from_line(&cur, end, "length")
243
next_line = <char *>memchr(cur, c'\n', end - cur)
244
if next_line == NULL:
245
raise ValueError('Missing the prefix line\n')
247
prefix_length = next_line - cur
253
next_null = <char *>memchr(prefix, c'\0', prefix_length)
254
while next_null != NULL:
255
num_prefix_bits = num_prefix_bits + 1
257
PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
258
prefix_tail = next_null + 1
259
next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
260
prefix_tail_len = next_line - prefix_tail
262
if num_prefix_bits >= width:
263
raise ValueError('Prefix has too many nulls versus width')
265
items_length = end - cur
269
next_line = <char *>memchr(cur, c'\n', end - cur)
270
if next_line == NULL:
271
raise ValueError('null line\n')
272
last_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
273
if last_null == NULL:
274
raise ValueError('fail to find the num value lines null')
275
next_null = last_null + 1 # move past NULL
276
num_value_lines = _get_int_from_line(&next_null, next_line + 1,
280
# Walk num_value_lines forward
281
for i from 0 <= i < num_value_lines:
282
next_line = <char *>memchr(cur, c'\n', end - cur)
283
if next_line == NULL:
284
raise ValueError('missing trailing newline')
286
entry_bits = StaticTuple_New(width)
287
for i from 0 <= i < num_prefix_bits:
288
# TODO: Use PyList_GetItem, or turn prefix_bits into a
290
entry = prefix_bits[i]
291
# SET_ITEM 'steals' a reference
293
StaticTuple_SET_ITEM(entry_bits, i, entry)
294
value = PyString_FromStringAndSize(value_start, next_line - value_start)
295
# The next entry bit needs the 'tail' from the prefix, and first part
297
entry_start = line_start
298
next_null = <char *>memchr(entry_start, c'\0',
299
last_null - entry_start + 1)
300
if next_null == NULL:
301
raise ValueError('bad no null, bad')
302
entry = PyString_FromStringAndSize(NULL,
303
prefix_tail_len + next_null - line_start)
304
c_entry = PyString_AS_STRING(entry)
305
if prefix_tail_len > 0:
306
memcpy(c_entry, prefix_tail, prefix_tail_len)
307
if next_null - line_start > 0:
308
memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
311
StaticTuple_SET_ITEM(entry_bits, i, entry)
312
while next_null != last_null: # We have remaining bits
315
raise ValueError("Too many bits for entry")
316
entry_start = next_null + 1
317
next_null = <char *>memchr(entry_start, c'\0',
318
last_null - entry_start + 1)
319
if next_null == NULL:
320
raise ValueError('bad no null')
321
entry = PyString_FromStringAndSize(entry_start,
322
next_null - entry_start)
324
StaticTuple_SET_ITEM(entry_bits, i, entry)
325
if len(entry_bits) != width:
326
raise AssertionError(
327
'Incorrect number of elements (%d vs %d)'
328
% (len(entry_bits)+1, width + 1))
329
entry_bits = StaticTuple_Intern(entry_bits)
330
PyDict_SetItem(items, entry_bits, value)
331
if len(items) != length:
332
raise ValueError("item count (%d) mismatch for key %s,"
333
" bytes %r" % (length, entry_bits, bytes))
334
result._items = items
336
result._maximum_size = maximum_size
338
result._key_width = width
339
result._raw_size = items_length + length * prefix_length
341
result._search_prefix = None
342
result._common_serialised_prefix = None
344
result._search_prefix = _unknown
345
result._common_serialised_prefix = PyString_FromStringAndSize(prefix,
347
if c_bytes_len != result._current_size():
348
raise AssertionError('_current_size computed incorrectly %d != %d',
349
c_bytes_len, result._current_size())
353
def _deserialise_internal_node(bytes, key, search_key_func=None):
354
cdef char *c_bytes, *cur, *next, *end
356
cdef Py_ssize_t c_bytes_len, prefix_length
357
cdef int maximum_size, width, length, i, prefix_tail_len
358
cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
360
if _InternalNode is None:
361
from bzrlib import chk_map
362
_LeafNode = chk_map.LeafNode
363
_InternalNode = chk_map.InternalNode
364
_unknown = chk_map._unknown
365
result = _InternalNode(search_key_func=search_key_func)
367
if not StaticTuple_CheckExact(key):
368
raise TypeError('key %r is not a StaticTuple' % (key,))
369
if not PyString_CheckExact(bytes):
370
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
372
c_bytes = PyString_AS_STRING(bytes)
373
c_bytes_len = PyString_GET_SIZE(bytes)
375
if c_bytes_len < 9 or memcmp(c_bytes, "chknode:\n", 9) != 0:
376
raise ValueError("not a serialised internal node: %r" % bytes)
377
if c_bytes[c_bytes_len - 1] != c'\n':
378
raise ValueError("bytes does not end in a newline")
382
end = c_bytes + c_bytes_len
383
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
384
width = _get_int_from_line(&cur, end, "width")
385
length = _get_int_from_line(&cur, end, "length")
387
next_line = <char *>memchr(cur, c'\n', end - cur)
388
if next_line == NULL:
389
raise ValueError('Missing the prefix line\n')
391
prefix_length = next_line - cur
395
# Find the null separator
396
next_line = <char *>memchr(cur, c'\n', end - cur)
397
if next_line == NULL:
398
raise ValueError('missing trailing newline')
399
next_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
400
if next_null == NULL:
401
raise ValueError('bad no null')
402
item_prefix = PyString_FromStringAndSize(NULL,
403
prefix_length + next_null - cur)
404
c_item_prefix = PyString_AS_STRING(item_prefix)
406
memcpy(c_item_prefix, prefix, prefix_length)
407
memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
408
flat_key = PyString_FromStringAndSize(next_null + 1,
409
next_line - next_null - 1)
410
flat_key = StaticTuple(flat_key).intern()
411
PyDict_SetItem(items, item_prefix, flat_key)
413
assert len(items) > 0
414
result._items = items
416
result._maximum_size = maximum_size
418
result._key_width = width
419
# XXX: InternalNodes don't really care about their size, and this will
420
# change if we add prefix compression
421
result._raw_size = None # len(bytes)
422
result._node_width = len(item_prefix)
423
result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
added
removed
bzrlib/_chk_map_pyx.pyx
