← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_btree_serializer_pyx.pyx

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-04-08 06:17:41 UTC
  • mfrom: (4797.33.16 apport)
  • Revision ID: pqm@pqm.ubuntu.com-20100408061741-m7vl6z97vu33riv7
(robertc) Make sure ExecutablePath and InterpreterPath are set in
        Apport. (Martin Pool, James Westby, lp:528114)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_btree_serializer_pyx.pyx
1
 
# Copyright (C) 2008 Canonical Ltd
 
1
# Copyright (C) 2008, 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
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
#
17
17
 
18
18
"""Pyrex extensions to btree node parsing."""
19
19
 
 
20
#python2.4 support
 
21
cdef extern from "python-compat.h":
 
22
    pass
 
23
 
20
24
cdef extern from "stdlib.h":
21
25
    ctypedef unsigned size_t
22
26
 
28
32
 
29
33
    char *PyString_AsString(object p) except NULL
30
34
    object PyString_FromStringAndSize(char *, Py_ssize_t)
 
35
    PyObject *PyString_FromStringAndSize_ptr "PyString_FromStringAndSize" (char *, Py_ssize_t)
31
36
    int PyString_CheckExact(object s)
32
37
    int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *)
33
38
    Py_ssize_t PyString_Size(object p)
34
39
    Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
35
40
    char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
 
41
    char * PyString_AS_STRING(object)
 
42
    Py_ssize_t PyString_GET_SIZE(object)
36
43
    int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
 
44
    void PyString_InternInPlace(PyObject **)
37
45
    int PyTuple_CheckExact(object t)
 
46
    object PyTuple_New(Py_ssize_t n_entries)
 
47
    void PyTuple_SET_ITEM(object, Py_ssize_t offset, object) # steals the ref
38
48
    Py_ssize_t PyTuple_GET_SIZE(object t)
39
49
    PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
 
50
    void Py_INCREF(object)
 
51
    void Py_DECREF_ptr "Py_DECREF" (PyObject *)
40
52
 
41
53
cdef extern from "string.h":
42
54
    void *memcpy(void *dest, void *src, size_t n)
45
57
    # void *memrchr(void *s, int c, size_t n)
46
58
    int strncmp(char *s1, char *s2, size_t n)
47
59
 
 
60
# It seems we need to import the definitions so that the pyrex compiler has
 
61
# local names to access them.
 
62
from _static_tuple_c cimport StaticTuple, \
 
63
    import_static_tuple_c, StaticTuple_New, \
 
64
    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
 
65
 
48
66
 
49
67
# TODO: Find some way to import this from _dirstate_helpers
50
 
cdef void* _my_memrchr(void *s, int c, size_t n):
 
68
cdef void* _my_memrchr(void *s, int c, size_t n): # cannot_raise
51
69
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
52
70
    # It is not present in any win32 standard library
53
71
    cdef char *pos
61
79
        pos = pos - 1
62
80
    return NULL
63
81
 
 
82
 
64
83
# TODO: Import this from _dirstate_helpers when it is merged
65
84
cdef object safe_string_from_size(char *s, Py_ssize_t size):
66
85
    if size < 0:
70
89
    return PyString_FromStringAndSize(s, size)
71
90
 
72
91
 
 
92
cdef object safe_interned_string_from_size(char *s, Py_ssize_t size):
 
93
    cdef PyObject *py_str
 
94
    if size < 0:
 
95
        raise AssertionError(
 
96
            'tried to create a string with an invalid size: %d @0x%x'
 
97
            % (size, <int>s))
 
98
    py_str = PyString_FromStringAndSize_ptr(s, size)
 
99
    PyString_InternInPlace(&py_str)
 
100
    result = <object>py_str
 
101
    # Casting a PyObject* to an <object> triggers an INCREF from Pyrex, so we
 
102
    # DECREF it to avoid geting immortal strings
 
103
    Py_DECREF_ptr(py_str)
 
104
    return result
 
105
 
 
106
from bzrlib import _static_tuple_c
 
107
# This sets up the StaticTuple C_API functionality
 
108
import_static_tuple_c()
 
109
 
 
110
 
73
111
cdef class BTreeLeafParser:
74
112
    """Parse the leaf nodes of a BTree index.
75
113
 
108
146
        self._cur_str = NULL
109
147
        self._end_str = NULL
110
148
        self._header_found = 0
 
149
        # keys are tuples
111
150
 
112
151
    cdef extract_key(self, char * last):
113
152
        """Extract a key.
117
156
        """
118
157
        cdef char *temp_ptr
119
158
        cdef int loop_counter
120
 
        # keys are tuples
121
 
        loop_counter = 0
122
 
        key_segments = []
123
 
        while loop_counter < self.key_length:
124
 
            loop_counter = loop_counter + 1
 
159
        cdef StaticTuple key
 
160
 
 
161
        key = StaticTuple_New(self.key_length)
 
162
        for loop_counter from 0 <= loop_counter < self.key_length:
125
163
            # grab a key segment
126
164
            temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
127
165
            if temp_ptr == NULL:
128
 
                if loop_counter == self.key_length:
 
166
                if loop_counter + 1 == self.key_length:
129
167
                    # capture to last
130
168
                    temp_ptr = last
131
169
                else:
135
173
                                                   last - self._start)))
136
174
                    raise AssertionError(failure_string)
137
175
            # capture the key string
138
 
            # TODO: Consider using PyIntern_FromString, the only caveat is that
139
 
            # it assumes a NULL-terminated string, so we have to check if
140
 
            # temp_ptr[0] == c'\0' or some other char.
141
 
            key_element = safe_string_from_size(self._start,
142
 
                                                temp_ptr - self._start)
 
176
            if (self.key_length == 1
 
177
                and (temp_ptr - self._start) == 45
 
178
                and strncmp(self._start, 'sha1:', 5) == 0):
 
179
                key_element = safe_string_from_size(self._start,
 
180
                                                    temp_ptr - self._start)
 
181
            else:
 
182
                key_element = safe_interned_string_from_size(self._start,
 
183
                                                         temp_ptr - self._start)
143
184
            # advance our pointer
144
185
            self._start = temp_ptr + 1
145
 
            PyList_Append(key_segments, key_element)
146
 
        return tuple(key_segments)
 
186
            Py_INCREF(key_element)
 
187
            StaticTuple_SET_ITEM(key, loop_counter, key_element)
 
188
        key = StaticTuple_Intern(key)
 
189
        return key
147
190
 
148
191
    cdef int process_line(self) except -1:
149
192
        """Process a line in the bytes."""
152
195
        cdef char *ref_ptr
153
196
        cdef char *next_start
154
197
        cdef int loop_counter
 
198
        cdef Py_ssize_t str_len
155
199
 
156
200
        self._start = self._cur_str
157
201
        # Find the next newline
164
208
            # And the next string is right after it
165
209
            self._cur_str = last + 1
166
210
            # The last character is right before the '\n'
167
 
            last = last
168
211
 
169
212
        if last == self._start:
170
213
            # parsed it all.
171
214
            return 0
172
215
        if last < self._start:
173
216
            # Unexpected error condition - fail
174
 
            return -1
 
217
            raise AssertionError("last < self._start")
175
218
        if 0 == self._header_found:
176
219
            # The first line in a leaf node is the header "type=leaf\n"
177
220
            if strncmp("type=leaf", self._start, last - self._start) == 0:
180
223
            else:
181
224
                raise AssertionError('Node did not start with "type=leaf": %r'
182
225
                    % (safe_string_from_size(self._start, last - self._start)))
183
 
                return -1
184
226
 
185
227
        key = self.extract_key(last)
186
228
        # find the value area
187
229
        temp_ptr = <char*>_my_memrchr(self._start, c'\0', last - self._start)
188
230
        if temp_ptr == NULL:
189
231
            # Invalid line
190
 
            return -1
 
232
            raise AssertionError("Failed to find the value area")
191
233
        else:
192
 
            # capture the value string
193
 
            value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
 
234
            # Because of how conversions were done, we ended up with *lots* of
 
235
            # values that are identical. These are all of the 0-length nodes
 
236
            # that are referred to by the TREE_ROOT (and likely some other
 
237
            # directory nodes.) For example, bzr has 25k references to
 
238
            # something like '12607215 328306 0 0', which ends up consuming 1MB
 
239
            # of memory, just for those strings.
 
240
            str_len = last - temp_ptr - 1
 
241
            if (str_len > 4
 
242
                and strncmp(" 0 0", last - 4, 4) == 0):
 
243
                # This drops peak mem for bzr.dev from 87.4MB => 86.2MB
 
244
                # For Launchpad 236MB => 232MB
 
245
                value = safe_interned_string_from_size(temp_ptr + 1, str_len)
 
246
            else:
 
247
                value = safe_string_from_size(temp_ptr + 1, str_len)
194
248
            # shrink the references end point
195
249
            last = temp_ptr
 
250
 
196
251
        if self.ref_list_length:
197
 
            ref_lists = []
 
252
            ref_lists = StaticTuple_New(self.ref_list_length)
198
253
            loop_counter = 0
199
254
            while loop_counter < self.ref_list_length:
200
255
                ref_list = []
201
256
                # extract a reference list
202
257
                loop_counter = loop_counter + 1
203
258
                if last < self._start:
204
 
                    return -1
 
259
                    raise AssertionError("last < self._start")
205
260
                # find the next reference list end point:
206
261
                temp_ptr = <char*>memchr(self._start, c'\t', last - self._start)
207
262
                if temp_ptr == NULL:
208
263
                    # Only valid for the last list
209
264
                    if loop_counter != self.ref_list_length:
210
265
                        # Invalid line
211
 
                        return -1
212
 
                        raise AssertionError("invalid key")
 
266
                        raise AssertionError(
 
267
                            "invalid key, loop_counter != self.ref_list_length")
213
268
                    else:
214
269
                        # scan to the end of the ref list area
215
270
                        ref_ptr = last
226
281
                    if temp_ptr == NULL:
227
282
                        # key runs to the end
228
283
                        temp_ptr = ref_ptr
 
284
 
229
285
                    PyList_Append(ref_list, self.extract_key(temp_ptr))
230
 
                PyList_Append(ref_lists, tuple(ref_list))
 
286
                ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
 
287
                Py_INCREF(ref_list)
 
288
                StaticTuple_SET_ITEM(ref_lists, loop_counter - 1, ref_list)
231
289
                # prepare for the next reference list
232
290
                self._start = next_start
233
 
            ref_lists = tuple(ref_lists)
234
 
            node_value = (value, ref_lists)
 
291
            node_value = StaticTuple(value, ref_lists)
235
292
        else:
236
293
            if last != self._start:
237
294
                # unexpected reference data present
238
 
                return -1
239
 
            node_value = (value, ())
240
 
        PyList_Append(self.keys, (key, node_value))
 
295
                raise AssertionError("unexpected reference data present")
 
296
            node_value = StaticTuple(value, StaticTuple())
 
297
        PyList_Append(self.keys, StaticTuple(key, node_value))
241
298
        return 0
242
299
 
243
300
    def parse(self):
272
329
    cdef Py_ssize_t flat_len
273
330
    cdef Py_ssize_t key_len
274
331
    cdef Py_ssize_t node_len
275
 
    cdef PyObject * val
276
332
    cdef char * value
277
333
    cdef Py_ssize_t value_len
278
334
    cdef char * out
281
337
    cdef int first_ref_list
282
338
    cdef int first_reference
283
339
    cdef int i
284
 
    cdef PyObject *ref_bit
285
340
    cdef Py_ssize_t ref_bit_len
286
341
 
287
 
    if not PyTuple_CheckExact(node):
288
 
        raise TypeError('We expected a tuple() for node not: %s'
 
342
    if not PyTuple_CheckExact(node) and not StaticTuple_CheckExact(node):
 
343
        raise TypeError('We expected a tuple() or StaticTuple() for node not: %s'
289
344
            % type(node))
290
 
    node_len = PyTuple_GET_SIZE(node)
 
345
    node_len = len(node)
291
346
    have_reference_lists = reference_lists
292
347
    if have_reference_lists:
293
348
        if node_len != 4:
296
351
    elif node_len < 3:
297
352
        raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
298
353
            % len(node))
299
 
    # I don't expect that we can do faster than string.join()
300
 
    string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
 
354
    # TODO: We can probably do better than string.join(), namely
 
355
    #       when key has only 1 item, we can just grab that string
 
356
    #       And when there are 2 items, we could do a single malloc + len() + 1
 
357
    #       also, doing .join() requires a PyObject_GetAttrString call, which
 
358
    #       we could also avoid.
 
359
    # TODO: Note that pyrex 0.9.6 generates fairly crummy code here, using the
 
360
    #       python object interface, versus 0.9.8+ which uses a helper that
 
361
    #       checks if this supports the sequence interface.
 
362
    #       We *could* do more work on our own, and grab the actual items
 
363
    #       lists. For now, just ask people to use a better compiler. :)
 
364
    string_key = '\0'.join(node[1])
301
365
 
302
366
    # TODO: instead of using string joins, precompute the final string length,
303
367
    #       and then malloc a single string and copy everything in.
314
378
    refs_len = 0
315
379
    if have_reference_lists:
316
380
        # Figure out how many bytes it will take to store the references
317
 
        ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
 
381
        ref_lists = node[3]
318
382
        next_len = len(ref_lists) # TODO: use a Py function
319
383
        if next_len > 0:
320
384
            # If there are no nodes, we don't need to do any work
328
392
                    # references
329
393
                    refs_len = refs_len + (next_len - 1)
330
394
                    for reference in ref_list:
331
 
                        if not PyTuple_CheckExact(reference):
 
395
                        if (not PyTuple_CheckExact(reference)
 
396
                            and not StaticTuple_CheckExact(reference)):
332
397
                            raise TypeError(
333
398
                                'We expect references to be tuples not: %s'
334
399
                                % type(reference))
335
 
                        next_len = PyTuple_GET_SIZE(reference)
 
400
                        next_len = len(reference)
336
401
                        if next_len > 0:
337
402
                            # We will need (len - 1) '\x00' characters to
338
403
                            # separate the reference key
339
404
                            refs_len = refs_len + (next_len - 1)
340
 
                            for i from 0 <= i < next_len:
341
 
                                ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
342
 
                                if not PyString_CheckExact_ptr(ref_bit):
 
405
                            for ref_bit in reference:
 
406
                                if not PyString_CheckExact(ref_bit):
343
407
                                    raise TypeError('We expect reference bits'
344
408
                                        ' to be strings not: %s'
345
409
                                        % type(<object>ref_bit))
346
 
                                refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
 
410
                                refs_len = refs_len + PyString_GET_SIZE(ref_bit)
347
411
 
348
412
    # So we have the (key NULL refs NULL value LF)
349
413
    key_len = PyString_Size(string_key)
350
 
    val = PyTuple_GET_ITEM_ptr_object(node, 2)
351
 
    if not PyString_CheckExact_ptr(val):
 
414
    val = node[2]
 
415
    if not PyString_CheckExact(val):
352
416
        raise TypeError('Expected a plain str for value not: %s'
353
 
                        % type(<object>val))
354
 
    value = PyString_AS_STRING_ptr(val)
355
 
    value_len = PyString_GET_SIZE_ptr(val)
 
417
                        % type(val))
 
418
    value = PyString_AS_STRING(val)
 
419
    value_len = PyString_GET_SIZE(val)
356
420
    flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
357
421
    line = PyString_FromStringAndSize(NULL, flat_len)
358
422
    # Get a pointer to the new buffer
374
438
                    out[0] = c'\r'
375
439
                    out = out + 1
376
440
                first_reference = 0
377
 
                next_len = PyTuple_GET_SIZE(reference)
 
441
                next_len = len(reference)
378
442
                for i from 0 <= i < next_len:
379
443
                    if i != 0:
380
444
                        out[0] = c'\x00'
381
445
                        out = out + 1
382
 
                    ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
383
 
                    ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
384
 
                    memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
 
446
                    ref_bit = reference[i]
 
447
                    ref_bit_len = PyString_GET_SIZE(ref_bit)
 
448
                    memcpy(out, PyString_AS_STRING(ref_bit), ref_bit_len)
385
449
                    out = out + ref_bit_len
386
450
    out[0] = c'\0'
387
451
    out = out  + 1