← 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: John Arbash Meinel
  • Date: 2009-03-27 22:29:55 UTC
  • mto: (3735.39.2 clean)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090327222955-utifmfm888zerixt
Implement apply_delta_to_source which doesn't have to malloc another string.

Show diffs side-by-side

added added

removed removed

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