1
# Copyright (C) 2009, 2010 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
PyObject *PyString_FromStringAndSize_ptr "PyString_FromStringAndSize" (char *, Py_ssize_t)
39
Py_ssize_t PyString_GET_SIZE(object)
40
void PyString_InternInPlace(PyObject **)
41
long PyInt_AS_LONG(object)
43
int PyDict_SetItem(object d, object k, object v) except -1
45
void Py_INCREF(object)
46
void Py_DECREF_ptr "Py_DECREF" (PyObject *)
48
object PyString_FromStringAndSize(char*, Py_ssize_t)
50
# cimport all of the definitions we will need to access
51
from _static_tuple_c cimport StaticTuple,\
52
import_static_tuple_c, StaticTuple_New, \
53
StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact, \
57
from zlib import crc32
60
# Set up the StaticTuple C_API functionality
61
import_static_tuple_c()
65
cdef object _InternalNode
70
# We shouldn't just copy this from _dirstate_helpers_pyx
71
cdef void* _my_memrchr(void *s, int c, size_t n): # cannot_raise
72
# memrchr seems to be a GNU extension, so we have to implement it ourselves
85
cdef object safe_interned_string_from_size(char *s, Py_ssize_t size):
89
'tried to create a string with an invalid size: %d @0x%x'
91
py_str = PyString_FromStringAndSize_ptr(s, size)
92
PyString_InternInPlace(&py_str)
93
result = <object>py_str
94
# Casting a PyObject* to an <object> triggers an INCREF from Pyrex, so we
95
# DECREF it to avoid geting immortal strings
100
def _search_key_16(key):
101
"""See chk_map._search_key_16."""
102
cdef Py_ssize_t num_bits
104
cdef Py_ssize_t num_out_bytes
105
cdef unsigned long crc_val
106
cdef Py_ssize_t out_off
110
# 4 bytes per crc32, and another 1 byte between bits
111
num_out_bytes = (9 * num_bits) - 1
112
out = PyString_FromStringAndSize(NULL, num_out_bytes)
113
c_out = PyString_AS_STRING(out)
114
for i from 0 <= i < num_bits:
118
crc_val = PyInt_AS_LONG(crc32(key[i]))
120
sprintf(c_out, '%08X', crc_val)
125
def _search_key_255(key):
126
"""See chk_map._search_key_255."""
127
cdef Py_ssize_t num_bits
129
cdef Py_ssize_t num_out_bytes
130
cdef unsigned long crc_val
131
cdef Py_ssize_t out_off
135
# 4 bytes per crc32, and another 1 byte between bits
136
num_out_bytes = (5 * num_bits) - 1
137
out = PyString_FromStringAndSize(NULL, num_out_bytes)
138
c_out = PyString_AS_STRING(out)
139
for i from 0 <= i < num_bits:
143
crc_val = PyInt_AS_LONG(crc32(key[i]))
145
c_out[0] = (crc_val >> 24) & 0xFF
146
c_out[1] = (crc_val >> 16) & 0xFF
147
c_out[2] = (crc_val >> 8) & 0xFF
148
c_out[3] = (crc_val >> 0) & 0xFF
149
for j from 0 <= j < 4:
150
if c_out[j] == c'\n':
156
cdef int _get_int_from_line(char **cur, char *end, char *message) except -1:
157
"""Read a positive integer from the data stream.
159
:param cur: The start of the data, this will be moved to after the
160
trailing newline when done.
161
:param end: Do not parse any data past this byte.
162
:return: The integer stored in those bytes
165
cdef char *next_line, *next
167
next_line = <char *>memchr(cur[0], c'\n', end - cur[0])
168
if next_line == NULL:
169
raise ValueError("Missing %s line\n" % message)
171
value = strtol(cur[0], &next, 10)
172
if next != next_line:
173
raise ValueError("%s line not a proper int\n" % message)
174
cur[0] = next_line + 1
178
cdef _import_globals():
179
"""Set the global attributes. Done lazy to avoid recursive import loops."""
180
global _LeafNode, _InternalNode, _unknown
182
from bzrlib import chk_map
183
_LeafNode = chk_map.LeafNode
184
_InternalNode = chk_map.InternalNode
185
_unknown = chk_map._unknown
188
def _deserialise_leaf_node(bytes, key, search_key_func=None):
189
"""Deserialise bytes, with key key, into a LeafNode.
191
:param bytes: The bytes of the node.
192
:param key: The key that the serialised node has.
194
cdef char *c_bytes, *cur, *next, *end
196
cdef Py_ssize_t c_bytes_len, prefix_length, items_length
197
cdef int maximum_size, width, length, i, prefix_tail_len
198
cdef int num_value_lines, num_prefix_bits
199
cdef char *prefix, *value_start, *prefix_tail
200
cdef char *next_null, *last_null, *line_start
201
cdef char *c_entry, *entry_start
202
cdef StaticTuple entry_bits
204
if _LeafNode is None:
207
result = _LeafNode(search_key_func=search_key_func)
208
# Splitlines can split on '\r' so don't use it, split('\n') adds an
209
# extra '' if the bytes ends in a final newline.
210
if not PyString_CheckExact(bytes):
211
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
213
c_bytes = PyString_AS_STRING(bytes)
214
c_bytes_len = PyString_GET_SIZE(bytes)
216
if c_bytes_len < 9 or memcmp(c_bytes, "chkleaf:\n", 9) != 0:
217
raise ValueError("not a serialised leaf node: %r" % bytes)
218
if c_bytes[c_bytes_len - 1] != c'\n':
219
raise ValueError("bytes does not end in a newline")
221
end = c_bytes + c_bytes_len
223
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
224
width = _get_int_from_line(&cur, end, "width")
225
length = _get_int_from_line(&cur, end, "length")
227
next_line = <char *>memchr(cur, c'\n', end - cur)
228
if next_line == NULL:
229
raise ValueError('Missing the prefix line\n')
231
prefix_length = next_line - cur
237
next_null = <char *>memchr(prefix, c'\0', prefix_length)
238
while next_null != NULL:
239
num_prefix_bits = num_prefix_bits + 1
241
PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
242
prefix_tail = next_null + 1
243
next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
244
prefix_tail_len = next_line - prefix_tail
246
if num_prefix_bits >= width:
247
raise ValueError('Prefix has too many nulls versus width')
249
items_length = end - cur
253
next_line = <char *>memchr(cur, c'\n', end - cur)
254
if next_line == NULL:
255
raise ValueError('null line\n')
256
last_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
257
if last_null == NULL:
258
raise ValueError('fail to find the num value lines null')
259
next_null = last_null + 1 # move past NULL
260
num_value_lines = _get_int_from_line(&next_null, next_line + 1,
264
# Walk num_value_lines forward
265
for i from 0 <= i < num_value_lines:
266
next_line = <char *>memchr(cur, c'\n', end - cur)
267
if next_line == NULL:
268
raise ValueError('missing trailing newline')
270
entry_bits = StaticTuple_New(width)
271
for i from 0 <= i < num_prefix_bits:
272
# TODO: Use PyList_GetItem, or turn prefix_bits into a
274
entry = prefix_bits[i]
275
# SET_ITEM 'steals' a reference
277
StaticTuple_SET_ITEM(entry_bits, i, entry)
278
value = PyString_FromStringAndSize(value_start, next_line - value_start)
279
# The next entry bit needs the 'tail' from the prefix, and first part
281
entry_start = line_start
282
next_null = <char *>memchr(entry_start, c'\0',
283
last_null - entry_start + 1)
284
if next_null == NULL:
285
raise ValueError('bad no null, bad')
286
entry = PyString_FromStringAndSize(NULL,
287
prefix_tail_len + next_null - line_start)
288
c_entry = PyString_AS_STRING(entry)
289
if prefix_tail_len > 0:
290
memcpy(c_entry, prefix_tail, prefix_tail_len)
291
if next_null - line_start > 0:
292
memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
295
StaticTuple_SET_ITEM(entry_bits, i, entry)
296
while next_null != last_null: # We have remaining bits
299
raise ValueError("Too many bits for entry")
300
entry_start = next_null + 1
301
next_null = <char *>memchr(entry_start, c'\0',
302
last_null - entry_start + 1)
303
if next_null == NULL:
304
raise ValueError('bad no null')
305
entry = PyString_FromStringAndSize(entry_start,
306
next_null - entry_start)
308
StaticTuple_SET_ITEM(entry_bits, i, entry)
309
if StaticTuple_GET_SIZE(entry_bits) != width:
310
raise AssertionError(
311
'Incorrect number of elements (%d vs %d)'
312
% (len(entry_bits)+1, width + 1))
313
entry_bits = StaticTuple_Intern(entry_bits)
314
PyDict_SetItem(items, entry_bits, value)
315
if len(items) != length:
316
raise ValueError("item count (%d) mismatch for key %s,"
317
" bytes %r" % (length, entry_bits, bytes))
318
result._items = items
320
result._maximum_size = maximum_size
322
result._key_width = width
323
result._raw_size = items_length + length * prefix_length
325
result._search_prefix = None
326
result._common_serialised_prefix = None
328
result._search_prefix = _unknown
329
result._common_serialised_prefix = PyString_FromStringAndSize(prefix,
331
if c_bytes_len != result._current_size():
332
raise AssertionError('_current_size computed incorrectly %d != %d',
333
c_bytes_len, result._current_size())
337
def _deserialise_internal_node(bytes, key, search_key_func=None):
338
cdef char *c_bytes, *cur, *next, *end
340
cdef Py_ssize_t c_bytes_len, prefix_length
341
cdef int maximum_size, width, length, i, prefix_tail_len
342
cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
344
if _InternalNode is None:
346
result = _InternalNode(search_key_func=search_key_func)
348
if not StaticTuple_CheckExact(key):
349
raise TypeError('key %r is not a StaticTuple' % (key,))
350
if not PyString_CheckExact(bytes):
351
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
353
c_bytes = PyString_AS_STRING(bytes)
354
c_bytes_len = PyString_GET_SIZE(bytes)
356
if c_bytes_len < 9 or memcmp(c_bytes, "chknode:\n", 9) != 0:
357
raise ValueError("not a serialised internal node: %r" % bytes)
358
if c_bytes[c_bytes_len - 1] != c'\n':
359
raise ValueError("bytes does not end in a newline")
363
end = c_bytes + c_bytes_len
364
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
365
width = _get_int_from_line(&cur, end, "width")
366
length = _get_int_from_line(&cur, end, "length")
368
next_line = <char *>memchr(cur, c'\n', end - cur)
369
if next_line == NULL:
370
raise ValueError('Missing the prefix line\n')
372
prefix_length = next_line - cur
376
# Find the null separator
377
next_line = <char *>memchr(cur, c'\n', end - cur)
378
if next_line == NULL:
379
raise ValueError('missing trailing newline')
380
next_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
381
if next_null == NULL:
382
raise ValueError('bad no null')
383
item_prefix = PyString_FromStringAndSize(NULL,
384
prefix_length + next_null - cur)
385
c_item_prefix = PyString_AS_STRING(item_prefix)
387
memcpy(c_item_prefix, prefix, prefix_length)
388
memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
389
flat_key = PyString_FromStringAndSize(next_null + 1,
390
next_line - next_null - 1)
391
flat_key = StaticTuple(flat_key).intern()
392
PyDict_SetItem(items, item_prefix, flat_key)
394
assert len(items) > 0
395
result._items = items
397
result._maximum_size = maximum_size
399
result._key_width = width
400
# XXX: InternalNodes don't really care about their size, and this will
401
# change if we add prefix compression
402
result._raw_size = None # len(bytes)
403
result._node_width = len(item_prefix)
404
result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
408
def _bytes_to_text_key(bytes):
409
"""Take a CHKInventory value string and return a (file_id, rev_id) tuple"""
411
cdef char *byte_str, *cur_end, *file_id_str, *byte_end
412
cdef char *revision_str
413
cdef Py_ssize_t byte_size, pos, file_id_len
415
if not PyString_CheckExact(bytes):
416
raise TypeError('bytes must be a string')
417
byte_str = PyString_AS_STRING(bytes)
418
byte_size = PyString_GET_SIZE(bytes)
419
byte_end = byte_str + byte_size
420
cur_end = <char*>memchr(byte_str, c':', byte_size)
422
raise ValueError('No kind section found.')
423
if cur_end[1] != c' ':
424
raise ValueError('Kind section should end with ": "')
425
file_id_str = cur_end + 2
426
# file_id is now the data up until the next newline
427
cur_end = <char*>memchr(file_id_str, c'\n', byte_end - file_id_str)
429
raise ValueError('no newline after file-id')
430
file_id = safe_interned_string_from_size(file_id_str,
431
cur_end - file_id_str)
432
# this is the end of the parent_str
433
cur_end = <char*>memchr(cur_end + 1, c'\n', byte_end - cur_end - 1)
435
raise ValueError('no newline after parent_str')
436
# end of the name str
437
cur_end = <char*>memchr(cur_end + 1, c'\n', byte_end - cur_end - 1)
439
raise ValueError('no newline after name str')
440
# the next section is the revision info
441
revision_str = cur_end + 1
442
cur_end = <char*>memchr(cur_end + 1, c'\n', byte_end - cur_end - 1)
444
# This is probably a dir: entry, which has revision as the last item
446
revision = safe_interned_string_from_size(revision_str,
447
cur_end - revision_str)
448
key = StaticTuple_New(2)
450
StaticTuple_SET_ITEM(key, 0, file_id)
452
StaticTuple_SET_ITEM(key, 1, revision)
453
return StaticTuple_Intern(key)
added
removed
bzrlib/_chk_map_pyx.pyx
