« back to all changes in this revision
Viewing changes to bzrlib/_chk_map_pyx.pyx
- browse files at revision 4241.6.1
- compare with another revision
- compare with revision 6351.2.2
- download diff
- download tarball
- view history from revision 4241.6.1
- Committer: Ian Clatworthy
- Date: 2009-04-03 02:29:30 UTC
- mto: This revision was merged to the branch mainline in revision 4259.
- Revision ID: ian.clatworthy@canonical.com-20090403022930-epud0dn5421fp0a0
chk_map code from brisbane-core
added
removed
bzrlib/_chk_map_pyx.pyx
1
# Copyright (C) 2009 Canonical Ltd
2
#
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.
7
#
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.
12
#
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
16
17
18
cdef extern from *:
19
ctypedef unsigned int size_t
20
int memcmp(void *, void*, size_t)
21
void memcpy(void *, void*, size_t)
22
void *memchr(void *s, int c, size_t len)
23
long strtol(char *, char **, int)
24
void sprintf(char *, char *, ...)
25
26
cdef extern from "Python.h":
27
struct _PyObject:
28
pass
29
ctypedef _PyObject PyObject
30
int PyTuple_CheckExact(object p)
31
Py_ssize_t PyTuple_GET_SIZE(object t)
32
int PyString_CheckExact(object)
33
char *PyString_AS_STRING(object s)
34
Py_ssize_t PyString_GET_SIZE(object)
35
36
int PyDict_SetItem(object d, object k, object v) except -1
37
38
object PyTuple_New(Py_ssize_t count)
39
void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)
40
41
void Py_INCREF(object)
42
43
PyObject * PyTuple_GET_ITEM_ptr "PyTuple_GET_ITEM" (object t,
44
Py_ssize_t offset)
45
int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *p)
46
Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *s)
47
char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
48
object PyString_FromStringAndSize(char*, Py_ssize_t)
49
50
cdef extern from "zlib.h":
51
ctypedef unsigned long uLong
52
ctypedef unsigned int uInt
53
ctypedef unsigned char Bytef
54
55
uLong crc32(uLong crc, Bytef *buf, uInt len)
56
57
58
_LeafNode = None
59
_InternalNode = None
60
_unknown = None
61
62
# We shouldn't just copy this from _dirstate_helpers_c
63
cdef void* _my_memrchr(void *s, int c, size_t n):
64
# memrchr seems to be a GNU extension, so we have to implement it ourselves
65
cdef char *pos
66
cdef char *start
67
68
start = <char*>s
69
pos = start + n - 1
70
while pos >= start:
71
if pos[0] == c:
72
return <void*>pos
73
pos = pos - 1
74
return NULL
75
76
77
def _search_key_16(key):
78
"""See chk_map._search_key_16."""
79
cdef Py_ssize_t num_bits
80
cdef Py_ssize_t i, j
81
cdef Py_ssize_t num_out_bytes
82
cdef Bytef *c_bit
83
cdef uLong c_len
84
cdef uInt crc_val
85
cdef Py_ssize_t out_off
86
cdef char *c_out
87
cdef PyObject *bit
88
89
if not PyTuple_CheckExact(key):
90
raise TypeError('key %r is not a tuple' % (key,))
91
num_bits = PyTuple_GET_SIZE(key)
92
# 4 bytes per crc32, and another 1 byte between bits
93
num_out_bytes = (9 * num_bits) - 1
94
out = PyString_FromStringAndSize(NULL, num_out_bytes)
95
c_out = PyString_AS_STRING(out)
96
for i from 0 <= i < num_bits:
97
if i > 0:
98
c_out[0] = c'\x00'
99
c_out = c_out + 1
100
# We use the _ptr variant, because GET_ITEM returns a borrowed
101
# reference, and Pyrex assumes that returned 'object' are a new
102
# reference
103
bit = PyTuple_GET_ITEM_ptr(key, i)
104
if not PyString_CheckExact_ptr(bit):
105
raise TypeError('Bit %d of %r is not a string' % (i, key))
106
c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
107
c_len = PyString_GET_SIZE_ptr(bit)
108
crc_val = crc32(0, c_bit, c_len)
109
# Hex(val) order
110
sprintf(c_out, '%08X', crc_val)
111
c_out = c_out + 8
112
return out
113
114
115
def _search_key_255(key):
116
"""See chk_map._search_key_255."""
117
cdef Py_ssize_t num_bits
118
cdef Py_ssize_t i, j
119
cdef Py_ssize_t num_out_bytes
120
cdef Bytef *c_bit
121
cdef uLong c_len
122
cdef uInt crc_val
123
cdef Py_ssize_t out_off
124
cdef char *c_out
125
cdef PyObject *bit
126
127
if not PyTuple_CheckExact(key):
128
raise TypeError('key %r is not a tuple' % (key,))
129
num_bits = PyTuple_GET_SIZE(key)
130
# 4 bytes per crc32, and another 1 byte between bits
131
num_out_bytes = (5 * num_bits) - 1
132
out = PyString_FromStringAndSize(NULL, num_out_bytes)
133
c_out = PyString_AS_STRING(out)
134
for i from 0 <= i < num_bits:
135
if i > 0:
136
c_out[0] = c'\x00'
137
c_out = c_out + 1
138
bit = PyTuple_GET_ITEM_ptr(key, i)
139
if not PyString_CheckExact_ptr(bit):
140
raise TypeError('Bit %d of %r is not a string: %r' % (i, key,
141
<object>bit))
142
c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
143
c_len = PyString_GET_SIZE_ptr(bit)
144
crc_val = crc32(0, c_bit, c_len)
145
# MSB order
146
c_out[0] = (crc_val >> 24) & 0xFF
147
c_out[1] = (crc_val >> 16) & 0xFF
148
c_out[2] = (crc_val >> 8) & 0xFF
149
c_out[3] = (crc_val >> 0) & 0xFF
150
for j from 0 <= j < 4:
151
if c_out[j] == c'\n':
152
c_out[j] = c'_'
153
c_out = c_out + 4
154
return out
155
156
157
cdef int _get_int_from_line(char **cur, char *end, char *message) except -1:
158
"""Read a positive integer from the data stream.
159
160
:param cur: The start of the data, this will be moved to after the
161
trailing newline when done.
162
:param end: Do not parse any data past this byte.
163
:return: The integer stored in those bytes
164
"""
165
cdef int value
166
cdef char *next_line, *next
167
168
next_line = <char *>memchr(cur[0], c'\n', end - cur[0])
169
if next_line == NULL:
170
raise ValueError("Missing %s line\n" % message)
171
172
value = strtol(cur[0], &next, 10)
173
if next != next_line:
174
raise ValueError("%s line not a proper int\n" % message)
175
cur[0] = next_line + 1
176
return value
177
178
179
def _deserialise_leaf_node(bytes, key, search_key_func=None):
180
"""Deserialise bytes, with key key, into a LeafNode.
181
182
:param bytes: The bytes of the node.
183
:param key: The key that the serialised node has.
184
"""
185
cdef char *c_bytes, *cur, *next, *end
186
cdef char *next_line
187
cdef Py_ssize_t c_bytes_len, prefix_length, items_length
188
cdef int maximum_size, width, length, i, prefix_tail_len
189
cdef int num_value_lines, num_prefix_bits
190
cdef char *prefix, *value_start, *prefix_tail
191
cdef char *next_null, *last_null, *line_start
192
cdef char *c_entry, *entry_start
193
194
if _LeafNode is None:
195
from bzrlib import chk_map
196
_LeafNode = chk_map.LeafNode
197
_InternalNode = chk_map.InternalNode
198
_unknown = chk_map._unknown
199
200
result = _LeafNode(search_key_func=search_key_func)
201
# Splitlines can split on '\r' so don't use it, split('\n') adds an
202
# extra '' if the bytes ends in a final newline.
203
if not PyString_CheckExact(bytes):
204
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
205
206
c_bytes = PyString_AS_STRING(bytes)
207
c_bytes_len = PyString_GET_SIZE(bytes)
208
209
if c_bytes_len < 9 or memcmp(c_bytes, "chkleaf:\n", 9) != 0:
210
raise ValueError("not a serialised leaf node: %r" % bytes)
211
if c_bytes[c_bytes_len - 1] != c'\n':
212
raise ValueError("bytes does not end in a newline")
213
214
end = c_bytes + c_bytes_len
215
cur = c_bytes + 9
216
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
217
width = _get_int_from_line(&cur, end, "width")
218
length = _get_int_from_line(&cur, end, "length")
219
220
next_line = <char *>memchr(cur, c'\n', end - cur)
221
if next_line == NULL:
222
raise ValueError('Missing the prefix line\n')
223
prefix = cur
224
prefix_length = next_line - cur
225
cur = next_line + 1
226
227
prefix_bits = []
228
prefix_tail = prefix
229
num_prefix_bits = 0
230
next_null = <char *>memchr(prefix, c'\0', prefix_length)
231
while next_null != NULL:
232
num_prefix_bits = num_prefix_bits + 1
233
prefix_bits.append(
234
PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
235
prefix_tail = next_null + 1
236
next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
237
prefix_tail_len = next_line - prefix_tail
238
239
if num_prefix_bits >= width:
240
raise ValueError('Prefix has too many nulls versus width')
241
242
items_length = end - cur
243
items = {}
244
while cur < end:
245
line_start = cur
246
next_line = <char *>memchr(cur, c'\n', end - cur)
247
if next_line == NULL:
248
raise ValueError('null line\n')
249
last_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
250
if last_null == NULL:
251
raise ValueError('fail to find the num value lines null')
252
next_null = last_null + 1 # move past NULL
253
num_value_lines = _get_int_from_line(&next_null, next_line + 1,
254
"num value lines")
255
cur = next_line + 1
256
value_start = cur
257
# Walk num_value_lines forward
258
for i from 0 <= i < num_value_lines:
259
next_line = <char *>memchr(cur, c'\n', end - cur)
260
if next_line == NULL:
261
raise ValueError('missing trailing newline')
262
cur = next_line + 1
263
entry_bits = PyTuple_New(width)
264
for i from 0 <= i < num_prefix_bits:
265
entry = prefix_bits[i]
266
# SET_ITEM 'steals' a reference
267
Py_INCREF(entry)
268
PyTuple_SET_ITEM(entry_bits, i, entry)
269
value = PyString_FromStringAndSize(value_start, next_line - value_start)
270
# The next entry bit needs the 'tail' from the prefix, and first part
271
# of the line
272
entry_start = line_start
273
next_null = <char *>memchr(entry_start, c'\0',
274
last_null - entry_start + 1)
275
if next_null == NULL:
276
raise ValueError('bad no null, bad')
277
entry = PyString_FromStringAndSize(NULL,
278
prefix_tail_len + next_null - line_start)
279
c_entry = PyString_AS_STRING(entry)
280
if prefix_tail_len > 0:
281
memcpy(c_entry, prefix_tail, prefix_tail_len)
282
if next_null - line_start > 0:
283
memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
284
Py_INCREF(entry)
285
i = num_prefix_bits
286
PyTuple_SET_ITEM(entry_bits, i, entry)
287
while next_null != last_null: # We have remaining bits
288
i = i + 1
289
if i > width:
290
raise ValueError("Too many bits for entry")
291
entry_start = next_null + 1
292
next_null = <char *>memchr(entry_start, c'\0',
293
last_null - entry_start + 1)
294
if next_null == NULL:
295
raise ValueError('bad no null')
296
entry = PyString_FromStringAndSize(entry_start,
297
next_null - entry_start)
298
Py_INCREF(entry)
299
PyTuple_SET_ITEM(entry_bits, i, entry)
300
if len(entry_bits) != width:
301
raise AssertionError(
302
'Incorrect number of elements (%d vs %d)'
303
% (len(entry_bits)+1, width + 1))
304
PyDict_SetItem(items, entry_bits, value)
305
if len(items) != length:
306
raise ValueError("item count (%d) mismatch for key %s,"
307
" bytes %r" % (length, entry_bits, bytes))
308
result._items = items
309
result._len = length
310
result._maximum_size = maximum_size
311
result._key = key
312
result._key_width = width
313
result._raw_size = items_length + length * prefix_length
314
if length == 0:
315
result._search_prefix = None
316
result._common_serialised_prefix = None
317
else:
318
result._search_prefix = _unknown
319
result._common_serialised_prefix = PyString_FromStringAndSize(prefix,
320
prefix_length)
321
if c_bytes_len != result._current_size():
322
raise AssertionError('_current_size computed incorrectly %d != %d',
323
c_bytes_len, result._current_size())
324
return result
325
326
327
def _deserialise_internal_node(bytes, key, search_key_func=None):
328
cdef char *c_bytes, *cur, *next, *end
329
cdef char *next_line
330
cdef Py_ssize_t c_bytes_len, prefix_length
331
cdef int maximum_size, width, length, i, prefix_tail_len
332
cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
333
334
if _InternalNode is None:
335
from bzrlib import chk_map
336
_LeafNode = chk_map.LeafNode
337
_InternalNode = chk_map.InternalNode
338
_unknown = chk_map._unknown
339
result = _InternalNode(search_key_func=search_key_func)
340
341
if not PyString_CheckExact(bytes):
342
raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
343
344
c_bytes = PyString_AS_STRING(bytes)
345
c_bytes_len = PyString_GET_SIZE(bytes)
346
347
if c_bytes_len < 9 or memcmp(c_bytes, "chknode:\n", 9) != 0:
348
raise ValueError("not a serialised internal node: %r" % bytes)
349
if c_bytes[c_bytes_len - 1] != c'\n':
350
raise ValueError("bytes does not end in a newline")
351
352
items = {}
353
cur = c_bytes + 9
354
end = c_bytes + c_bytes_len
355
maximum_size = _get_int_from_line(&cur, end, "maximum_size")
356
width = _get_int_from_line(&cur, end, "width")
357
length = _get_int_from_line(&cur, end, "length")
358
359
next_line = <char *>memchr(cur, c'\n', end - cur)
360
if next_line == NULL:
361
raise ValueError('Missing the prefix line\n')
362
prefix = cur
363
prefix_length = next_line - cur
364
cur = next_line + 1
365
366
while cur < end:
367
# Find the null separator
368
next_line = <char *>memchr(cur, c'\n', end - cur)
369
if next_line == NULL:
370
raise ValueError('missing trailing newline')
371
next_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
372
if next_null == NULL:
373
raise ValueError('bad no null')
374
item_prefix = PyString_FromStringAndSize(NULL,
375
prefix_length + next_null - cur)
376
c_item_prefix = PyString_AS_STRING(item_prefix)
377
if prefix_length:
378
memcpy(c_item_prefix, prefix, prefix_length)
379
memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
380
flat_key = PyString_FromStringAndSize(next_null + 1,
381
next_line - next_null - 1)
382
PyDict_SetItem(items, item_prefix, (flat_key,))
383
cur = next_line + 1
384
assert len(items) > 0
385
result._items = items
386
result._len = length
387
result._maximum_size = maximum_size
388
result._key = key
389
result._key_width = width
390
# XXX: InternalNodes don't really care about their size, and this will
391
# change if we add prefix compression
392
result._raw_size = None # len(bytes)
393
result._node_width = len(item_prefix)
394
result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
395
return result
396
Loggerhead is a web-based interface for Breezy
Version: 2.0.1