← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_chk_map_pyx.pyx

  • Committer: Martin
  • Date: 2010-05-16 15:18:43 UTC
  • mfrom: (5235 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5239.
  • Revision ID: gzlist@googlemail.com-20100516151843-lu53u7caehm3ie3i
Merge bzr.dev to resolve conflicts in NEWS and _chk_map_pyx

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_chk_map_pyx.pyx
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2009, 2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
 
18
#python2.4 support
 
19
cdef extern from "python-compat.h":
 
20
    pass
 
21
 
18
22
cdef extern from *:
19
23
    ctypedef unsigned int size_t
20
24
    int memcmp(void *, void*, size_t)
24
28
    void sprintf(char *, char *, ...)
25
29
 
26
30
cdef extern from "Python.h":
27
 
    struct _PyObject:
 
31
    ctypedef int Py_ssize_t # Required for older pyrex versions
 
32
    ctypedef struct PyObject:
28
33
        pass
29
 
    ctypedef _PyObject PyObject
30
34
    int PyTuple_CheckExact(object p)
31
35
    Py_ssize_t PyTuple_GET_SIZE(object t)
32
36
    int PyString_CheckExact(object)
33
37
    char *PyString_AS_STRING(object s)
 
38
    PyObject *PyString_FromStringAndSize_ptr "PyString_FromStringAndSize" (char *, Py_ssize_t)
34
39
    Py_ssize_t PyString_GET_SIZE(object)
 
40
    void PyString_InternInPlace(PyObject **)
 
41
    long PyInt_AS_LONG(object)
35
42
 
36
43
    int PyDict_SetItem(object d, object k, object v) except -1
37
44
 
38
 
    object PyTuple_New(Py_ssize_t count)
39
 
    void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)
40
 
 
41
45
    void Py_INCREF(object)
 
46
    void Py_DECREF_ptr "Py_DECREF" (PyObject *)
42
47
 
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
48
    object PyString_FromStringAndSize(char*, Py_ssize_t)
49
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
 
 
 
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, \
 
54
    StaticTuple_GET_SIZE
 
55
 
 
56
cdef object crc32
 
57
from zlib import crc32
 
58
 
 
59
 
 
60
# Set up the StaticTuple C_API functionality
 
61
import_static_tuple_c()
 
62
 
 
63
cdef object _LeafNode
58
64
_LeafNode = None
 
65
cdef object _InternalNode
59
66
_InternalNode = None
 
67
cdef object _unknown
60
68
_unknown = None
61
69
 
62
 
# We shouldn't just copy this from _dirstate_helpers_c
63
 
cdef void* _my_memrchr(void *s, int c, size_t n):
 
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
64
72
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
65
73
    cdef char *pos
66
74
    cdef char *start
74
82
    return NULL
75
83
 
76
84
 
 
85
cdef object safe_interned_string_from_size(char *s, Py_ssize_t size):
 
86
    cdef PyObject *py_str
 
87
    if size < 0:
 
88
        raise AssertionError(
 
89
            'tried to create a string with an invalid size: %d @0x%x'
 
90
            % (size, <int>s))
 
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
 
96
    Py_DECREF_ptr(py_str)
 
97
    return result
 
98
 
 
99
 
77
100
def _search_key_16(key):
78
101
    """See chk_map._search_key_16."""
79
102
    cdef Py_ssize_t num_bits
80
103
    cdef Py_ssize_t i, j
81
104
    cdef Py_ssize_t num_out_bytes
82
 
    cdef Bytef *c_bit
83
 
    cdef uLong c_len
84
 
    cdef uInt crc_val
 
105
    cdef unsigned long crc_val
85
106
    cdef Py_ssize_t out_off
86
107
    cdef char *c_out
87
 
    cdef PyObject *bit
88
108
 
89
 
    if not PyTuple_CheckExact(key):
90
 
        raise TypeError('key %r is not a tuple' % (key,))
91
 
    num_bits = PyTuple_GET_SIZE(key)
 
109
    num_bits = len(key)
92
110
    # 4 bytes per crc32, and another 1 byte between bits
93
111
    num_out_bytes = (9 * num_bits) - 1
94
112
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
97
115
        if i > 0:
98
116
            c_out[0] = c'\x00'
99
117
            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)
 
118
        crc_val = PyInt_AS_LONG(crc32(key[i]))
109
119
        # Hex(val) order
110
120
        sprintf(c_out, '%08X', crc_val)
111
121
        c_out = c_out + 8
117
127
    cdef Py_ssize_t num_bits
118
128
    cdef Py_ssize_t i, j
119
129
    cdef Py_ssize_t num_out_bytes
120
 
    cdef Bytef *c_bit
121
 
    cdef uLong c_len
122
 
    cdef uInt crc_val
 
130
    cdef unsigned long crc_val
123
131
    cdef Py_ssize_t out_off
124
132
    cdef char *c_out
125
 
    cdef PyObject *bit
126
133
 
127
 
    if not PyTuple_CheckExact(key):
128
 
        raise TypeError('key %r is not a tuple' % (key,))
129
 
    num_bits = PyTuple_GET_SIZE(key)
 
134
    num_bits = len(key)
130
135
    # 4 bytes per crc32, and another 1 byte between bits
131
136
    num_out_bytes = (5 * num_bits) - 1
132
137
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
135
140
        if i > 0:
136
141
            c_out[0] = c'\x00'
137
142
            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)
 
143
        crc_val = PyInt_AS_LONG(crc32(key[i]))
145
144
        # MSB order
146
145
        c_out[0] = (crc_val >> 24) & 0xFF
147
146
        c_out[1] = (crc_val >> 16) & 0xFF
176
175
    return value
177
176
 
178
177
 
 
178
cdef _import_globals():
 
179
    """Set the global attributes. Done lazy to avoid recursive import loops."""
 
180
    global _LeafNode, _InternalNode, _unknown
 
181
 
 
182
    from bzrlib import chk_map
 
183
    _LeafNode = chk_map.LeafNode
 
184
    _InternalNode = chk_map.InternalNode
 
185
    _unknown = chk_map._unknown
 
186
 
 
187
 
179
188
def _deserialise_leaf_node(bytes, key, search_key_func=None):
180
189
    """Deserialise bytes, with key key, into a LeafNode.
181
190
 
190
199
    cdef char *prefix, *value_start, *prefix_tail
191
200
    cdef char *next_null, *last_null, *line_start
192
201
    cdef char *c_entry, *entry_start
 
202
    cdef StaticTuple entry_bits
193
203
 
194
204
    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
 
205
        _import_globals()
199
206
 
200
207
    result = _LeafNode(search_key_func=search_key_func)
201
208
    # Splitlines can split on '\r' so don't use it, split('\n') adds an
260
267
            if next_line == NULL:
261
268
                raise ValueError('missing trailing newline')
262
269
            cur = next_line + 1
263
 
        entry_bits = PyTuple_New(width)
 
270
        entry_bits = StaticTuple_New(width)
264
271
        for i from 0 <= i < num_prefix_bits:
 
272
            # TODO: Use PyList_GetItem, or turn prefix_bits into a
 
273
            #       tuple/StaticTuple
265
274
            entry = prefix_bits[i]
266
275
            # SET_ITEM 'steals' a reference
267
276
            Py_INCREF(entry)
268
 
            PyTuple_SET_ITEM(entry_bits, i, entry)
 
277
            StaticTuple_SET_ITEM(entry_bits, i, entry)
269
278
        value = PyString_FromStringAndSize(value_start, next_line - value_start)
270
279
        # The next entry bit needs the 'tail' from the prefix, and first part
271
280
        # of the line
283
292
            memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
284
293
        Py_INCREF(entry)
285
294
        i = num_prefix_bits
286
 
        PyTuple_SET_ITEM(entry_bits, i, entry)
 
295
        StaticTuple_SET_ITEM(entry_bits, i, entry)
287
296
        while next_null != last_null: # We have remaining bits
288
297
            i = i + 1
289
298
            if i > width:
296
305
            entry = PyString_FromStringAndSize(entry_start,
297
306
                                               next_null - entry_start)
298
307
            Py_INCREF(entry)
299
 
            PyTuple_SET_ITEM(entry_bits, i, entry)
300
 
        if len(entry_bits) != width:
 
308
            StaticTuple_SET_ITEM(entry_bits, i, entry)
 
309
        if StaticTuple_GET_SIZE(entry_bits) != width:
301
310
            raise AssertionError(
302
311
                'Incorrect number of elements (%d vs %d)'
303
312
                % (len(entry_bits)+1, width + 1))
 
313
        entry_bits = StaticTuple_Intern(entry_bits)
304
314
        PyDict_SetItem(items, entry_bits, value)
305
315
    if len(items) != length:
306
316
        raise ValueError("item count (%d) mismatch for key %s,"
332
342
    cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
333
343
 
334
344
    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
 
345
        _import_globals()
339
346
    result = _InternalNode(search_key_func=search_key_func)
340
347
 
 
348
    if not StaticTuple_CheckExact(key):
 
349
        raise TypeError('key %r is not a StaticTuple' % (key,))
341
350
    if not PyString_CheckExact(bytes):
342
351
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
343
352
 
379
388
        memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
380
389
        flat_key = PyString_FromStringAndSize(next_null + 1,
381
390
                                              next_line - next_null - 1)
382
 
        PyDict_SetItem(items, item_prefix, (flat_key,))
 
391
        flat_key = StaticTuple(flat_key).intern()
 
392
        PyDict_SetItem(items, item_prefix, flat_key)
383
393
        cur = next_line + 1
384
394
    assert len(items) > 0
385
395
    result._items = items
394
404
    result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
395
405
    return result
396
406
 
 
407
 
 
408
def _bytes_to_text_key(bytes):
 
409
    """Take a CHKInventory value string and return a (file_id, rev_id) tuple"""
 
410
    cdef StaticTuple key
 
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
 
414
 
 
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)
 
421
    if cur_end == NULL:
 
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)
 
428
    if cur_end == NULL:
 
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)
 
434
    if cur_end == NULL:
 
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)
 
438
    if cur_end == NULL:
 
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)
 
443
    if cur_end == NULL:
 
444
        # This is probably a dir: entry, which has revision as the last item
 
445
        cur_end = byte_end
 
446
    revision = safe_interned_string_from_size(revision_str,
 
447
        cur_end - revision_str)
 
448
    key = StaticTuple_New(2)
 
449
    Py_INCREF(file_id)
 
450
    StaticTuple_SET_ITEM(key, 0, file_id) 
 
451
    Py_INCREF(revision)
 
452
    StaticTuple_SET_ITEM(key, 1, revision) 
 
453
    return StaticTuple_Intern(key)