← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_parse_btree_c.pyx

  • Committer: John Arbash Meinel
  • Date: 2008-08-19 23:12:01 UTC
  • mto: This revision was merged to the branch mainline in revision 3644.
  • Revision ID: john@arbash-meinel.com-20080819231201-hc361se0f7okf08y
Bring in the btree_index and chunk_writer code and their tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_parse_btree_c.pyx
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
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
 
#
17
16
 
18
17
"""Pyrex extensions to btree node parsing."""
19
18
 
 
19
import sys
 
20
 
20
21
cdef extern from "stdlib.h":
21
22
    ctypedef unsigned size_t
 
23
    long int strtol(char *nptr, char **endptr, int base)
 
24
 
22
25
 
23
26
cdef extern from "Python.h":
24
 
    ctypedef struct PyObject:
25
 
        pass
 
27
    int PyDict_CheckExact(object)
 
28
    void *PyDict_GetItem_void "PyDict_GetItem" (object p, object key)
 
29
    int PyDict_SetItem(object p, object key, object val) except -1
 
30
 
26
31
    int PyList_Append(object lst, object item) except -1
27
 
 
28
 
    char *PyString_AsString(object p) except NULL
29
 
    object PyString_FromStringAndSize(char *, Py_ssize_t)
30
 
    int PyString_CheckExact(object s)
31
 
    int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *)
32
 
    Py_ssize_t PyString_Size(object p)
33
 
    Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
34
 
    char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
35
 
    int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
36
 
    int PyTuple_CheckExact(object t)
37
 
    Py_ssize_t PyTuple_GET_SIZE(object t)
38
 
    PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
 
32
    object PyList_GET_ITEM(object lst, int index)
 
33
    int PyList_CheckExact(object)
 
34
 
 
35
    void *PyTuple_GetItem_void_void "PyTuple_GET_ITEM" (void* tpl, int index)
 
36
 
 
37
    char *PyString_AsString(object p)
 
38
    object PyString_FromStringAndSize(char *, int)
 
39
    object PyString_FromString(char *)
 
40
    int PyString_Size(object p)
 
41
 
 
42
    void Py_INCREF(object)
 
43
 
39
44
 
40
45
cdef extern from "string.h":
41
 
    void *memcpy(void *dest, void *src, size_t n)
42
46
    void *memchr(void *s, int c, size_t n)
43
 
    # GNU extension
44
47
    # void *memrchr(void *s, int c, size_t n)
45
48
    int strncmp(char *s1, char *s2, size_t n)
46
49
 
47
50
 
48
 
# TODO: Find some way to import this from _dirstate_helpers
49
51
cdef void* _my_memrchr(void *s, int c, size_t n):
50
52
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
51
53
    # It is not present in any win32 standard library
60
62
        pos = pos - 1
61
63
    return NULL
62
64
 
63
 
# TODO: Import this from _dirstate_helpers when it is merged
64
 
cdef object safe_string_from_size(char *s, Py_ssize_t size):
65
 
    if size < 0:
66
 
        raise AssertionError(
67
 
            'tried to create a string with an invalid size: %d @0x%x'
68
 
            % (size, <int>s))
69
 
    return PyString_FromStringAndSize(s, size)
70
 
 
71
65
 
72
66
cdef class BTreeLeafParser:
73
 
    """Parse the leaf nodes of a BTree index.
74
 
 
75
 
    :ivar bytes: The PyString object containing the uncompressed text for the
76
 
        node.
77
 
    :ivar key_length: An integer describing how many pieces the keys have for
78
 
        this index.
79
 
    :ivar ref_list_length: An integer describing how many references this index
80
 
        contains.
81
 
    :ivar keys: A PyList of keys found in this node.
82
 
 
83
 
    :ivar _cur_str: A pointer to the start of the next line to parse
84
 
    :ivar _end_str: A pointer to the end of bytes
85
 
    :ivar _start: Pointer to the location within the current line while
86
 
        parsing.
87
 
    :ivar _header_found: True when we have parsed the header for this node
88
 
    """
89
67
 
90
68
    cdef object bytes
91
69
    cdef int key_length
92
70
    cdef int ref_list_length
93
71
    cdef object keys
94
72
 
95
 
    cdef char * _cur_str
96
 
    cdef char * _end_str
 
73
    cdef char * cur_str
 
74
    cdef char * end_str
97
75
    # The current start point for parsing
98
 
    cdef char * _start
 
76
    cdef char * start
99
77
 
100
 
    cdef int _header_found
 
78
    cdef int header_found
101
79
 
102
80
    def __init__(self, bytes, key_length, ref_list_length):
103
81
        self.bytes = bytes
104
82
        self.key_length = key_length
105
83
        self.ref_list_length = ref_list_length
106
84
        self.keys = []
107
 
        self._cur_str = NULL
108
 
        self._end_str = NULL
109
 
        self._header_found = 0
 
85
        self.cur_str = NULL
 
86
        self.end_str = NULL
 
87
        self.header_found = 0
110
88
 
111
89
    cdef extract_key(self, char * last):
112
90
        """Extract a key.
113
91
 
114
 
        :param last: points at the byte after the last byte permitted for the
115
 
            key.
 
92
        :param last: points at the byte after the last byte permitted for the key.
116
93
        """
117
94
        cdef char *temp_ptr
118
95
        cdef int loop_counter
122
99
        while loop_counter < self.key_length:
123
100
            loop_counter = loop_counter + 1
124
101
            # grab a key segment
125
 
            temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
 
102
            temp_ptr = <char*>memchr(self.start, c'\0', last - self.start)
126
103
            if temp_ptr == NULL:
127
104
                if loop_counter == self.key_length:
128
105
                    # capture to last
130
107
                else:
131
108
                    # Invalid line
132
109
                    failure_string = ("invalid key, wanted segment from " +
133
 
                        repr(safe_string_from_size(self._start,
134
 
                                                   last - self._start)))
 
110
                        repr(PyString_FromStringAndSize(self.start, last-self.start)))
135
111
                    raise AssertionError(failure_string)
136
112
            # capture the key string
137
 
            # TODO: Consider using PyIntern_FromString, the only caveat is that
138
 
            # it assumes a NULL-terminated string, so we have to check if
139
 
            # temp_ptr[0] == c'\0' or some other char.
140
 
            key_element = safe_string_from_size(self._start,
141
 
                                                temp_ptr - self._start)
 
113
            key_element = PyString_FromStringAndSize(self.start, temp_ptr - self.start)
142
114
            # advance our pointer
143
 
            self._start = temp_ptr + 1
 
115
            self.start = temp_ptr + 1
144
116
            PyList_Append(key_segments, key_element)
145
117
        return tuple(key_segments)
146
118
 
152
124
        cdef char *next_start
153
125
        cdef int loop_counter
154
126
 
155
 
        self._start = self._cur_str
 
127
        self.start = self.cur_str
156
128
        # Find the next newline
157
 
        last = <char*>memchr(self._start, c'\n', self._end_str - self._start)
 
129
        last = <char*>memchr(self.start, c'\n', self.end_str - self.start)
158
130
        if last == NULL:
159
131
            # Process until the end of the file
160
 
            last = self._end_str
161
 
            self._cur_str = self._end_str
 
132
            last = self.end_str
 
133
            self.cur_str = self.end_str
162
134
        else:
163
135
            # And the next string is right after it
164
 
            self._cur_str = last + 1
 
136
            self.cur_str = last + 1
165
137
            # The last character is right before the '\n'
166
138
            last = last
167
139
 
168
 
        if last == self._start:
 
140
        if last == self.start:
169
141
            # parsed it all.
170
142
            return 0
171
 
        if last < self._start:
 
143
        if last < self.start:
172
144
            # Unexpected error condition - fail
173
145
            return -1
174
 
        if 0 == self._header_found:
175
 
            # The first line in a leaf node is the header "type=leaf\n"
176
 
            if strncmp("type=leaf", self._start, last - self._start) == 0:
177
 
                self._header_found = 1
 
146
        if 0 == self.header_found:
 
147
            if strncmp("type=leaf", self.start, last-self.start) == 0:
 
148
                self.header_found = 1
178
149
                return 0
179
150
            else:
180
 
                raise AssertionError('Node did not start with "type=leaf": %r'
181
 
                    % (safe_string_from_size(self._start, last - self._start)))
 
151
                print "failed strncmp", repr(PyString_FromStringAndSize(self.start, last-self.start))
182
152
                return -1
183
153
 
184
154
        key = self.extract_key(last)
185
155
        # find the value area
186
 
        temp_ptr = <char*>_my_memrchr(self._start, c'\0', last - self._start)
 
156
        temp_ptr = <char*>_my_memrchr(self.start, c'\0', last - self.start)
187
157
        if temp_ptr == NULL:
188
158
            # Invalid line
189
159
            return -1
190
160
        else:
191
161
            # capture the value string
192
 
            value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
 
162
            value = PyString_FromStringAndSize(temp_ptr + 1, last - temp_ptr - 1)
193
163
            # shrink the references end point
194
164
            last = temp_ptr
195
165
        if self.ref_list_length:
199
169
                ref_list = []
200
170
                # extract a reference list
201
171
                loop_counter = loop_counter + 1
202
 
                if last < self._start:
 
172
                if last < self.start:
203
173
                    return -1
204
174
                # find the next reference list end point:
205
 
                temp_ptr = <char*>memchr(self._start, c'\t', last - self._start)
 
175
                temp_ptr = <char*>memchr(self.start, c'\t', last - self.start)
206
176
                if temp_ptr == NULL:
207
177
                    # Only valid for the last list
208
178
                    if loop_counter != self.ref_list_length:
218
188
                    ref_ptr = temp_ptr
219
189
                    next_start = temp_ptr + 1
220
190
                # Now, there may be multiple keys in the ref list.
221
 
                while self._start < ref_ptr:
 
191
                while self.start < ref_ptr:
222
192
                    # loop finding keys and extracting them
223
 
                    temp_ptr = <char*>memchr(self._start, c'\r',
224
 
                                             ref_ptr - self._start)
 
193
                    temp_ptr = <char*>memchr(self.start, c'\r', ref_ptr - self.start)
225
194
                    if temp_ptr == NULL:
226
195
                        # key runs to the end
227
196
                        temp_ptr = ref_ptr
228
197
                    PyList_Append(ref_list, self.extract_key(temp_ptr))
229
198
                PyList_Append(ref_lists, tuple(ref_list))
230
199
                # prepare for the next reference list
231
 
                self._start = next_start
 
200
                self.start = next_start
232
201
            ref_lists = tuple(ref_lists)
233
202
            node_value = (value, ref_lists)
234
203
        else:
235
 
            if last != self._start:
 
204
            if last != self.start:
236
205
                # unexpected reference data present
237
206
                return -1
238
207
            node_value = (value, ())
240
209
        return 0
241
210
 
242
211
    def parse(self):
243
 
        cdef Py_ssize_t byte_count
244
 
        if not PyString_CheckExact(self.bytes):
245
 
            raise AssertionError('self.bytes is not a string.')
 
212
        cdef int byte_count
246
213
        byte_count = PyString_Size(self.bytes)
247
 
        self._cur_str = PyString_AsString(self.bytes)
 
214
        self.cur_str = PyString_AsString(self.bytes)
248
215
        # This points to the last character in the string
249
 
        self._end_str = self._cur_str + byte_count
250
 
        while self._cur_str < self._end_str:
 
216
        self.end_str = self.cur_str + byte_count
 
217
        while self.cur_str < self.end_str:
251
218
            self.process_line()
252
219
        return self.keys
253
220
 
255
222
def _parse_leaf_lines(bytes, key_length, ref_list_length):
256
223
    parser = BTreeLeafParser(bytes, key_length, ref_list_length)
257
224
    return parser.parse()
258
 
 
259
 
 
260
 
def _flatten_node(node, reference_lists):
261
 
    """Convert a node into the serialized form.
262
 
 
263
 
    :param node: A tuple representing a node:
264
 
        (index, key_tuple, value, references)
265
 
    :param reference_lists: Does this index have reference lists?
266
 
    :return: (string_key, flattened)
267
 
        string_key  The serialized key for referencing this node
268
 
        flattened   A string with the serialized form for the contents
269
 
    """
270
 
    cdef int have_reference_lists
271
 
    cdef Py_ssize_t flat_len
272
 
    cdef Py_ssize_t key_len
273
 
    cdef Py_ssize_t node_len
274
 
    cdef PyObject * val
275
 
    cdef char * value
276
 
    cdef Py_ssize_t value_len
277
 
    cdef char * out
278
 
    cdef Py_ssize_t refs_len
279
 
    cdef Py_ssize_t next_len
280
 
    cdef int first_ref_list
281
 
    cdef int first_reference
282
 
    cdef int i
283
 
    cdef PyObject *ref_bit
284
 
    cdef Py_ssize_t ref_bit_len
285
 
 
286
 
    if not PyTuple_CheckExact(node):
287
 
        raise TypeError('We expected a tuple() for node not: %s'
288
 
            % type(node))
289
 
    node_len = PyTuple_GET_SIZE(node)
290
 
    have_reference_lists = reference_lists
291
 
    if have_reference_lists:
292
 
        if node_len != 4:
293
 
            raise ValueError('With ref_lists, we expected 4 entries not: %s'
294
 
                % len(node))
295
 
    elif node_len < 3:
296
 
        raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
297
 
            % len(node))
298
 
    # I don't expect that we can do faster than string.join()
299
 
    string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
300
 
 
301
 
    # TODO: instead of using string joins, precompute the final string length,
302
 
    #       and then malloc a single string and copy everything in.
303
 
 
304
 
    # TODO: We probably want to use PySequenceFast, because we have lists and
305
 
    #       tuples, but we aren't sure which we will get.
306
 
 
307
 
    # line := string_key NULL flat_refs NULL value LF
308
 
    # string_key := BYTES (NULL BYTES)*
309
 
    # flat_refs := ref_list (TAB ref_list)*
310
 
    # ref_list := ref (CR ref)*
311
 
    # ref := BYTES (NULL BYTES)*
312
 
    # value := BYTES
313
 
    refs_len = 0
314
 
    if have_reference_lists:
315
 
        # Figure out how many bytes it will take to store the references
316
 
        ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
317
 
        next_len = len(ref_lists) # TODO: use a Py function
318
 
        if next_len > 0:
319
 
            # If there are no nodes, we don't need to do any work
320
 
            # Otherwise we will need (len - 1) '\t' characters to separate
321
 
            # the reference lists
322
 
            refs_len = refs_len + (next_len - 1)
323
 
            for ref_list in ref_lists:
324
 
                next_len = len(ref_list)
325
 
                if next_len > 0:
326
 
                    # We will need (len - 1) '\r' characters to separate the
327
 
                    # references
328
 
                    refs_len = refs_len + (next_len - 1)
329
 
                    for reference in ref_list:
330
 
                        if not PyTuple_CheckExact(reference):
331
 
                            raise TypeError(
332
 
                                'We expect references to be tuples not: %s'
333
 
                                % type(reference))
334
 
                        next_len = PyTuple_GET_SIZE(reference)
335
 
                        if next_len > 0:
336
 
                            # We will need (len - 1) '\x00' characters to
337
 
                            # separate the reference key
338
 
                            refs_len = refs_len + (next_len - 1)
339
 
                            for i from 0 <= i < next_len:
340
 
                                ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
341
 
                                if not PyString_CheckExact_ptr(ref_bit):
342
 
                                    raise TypeError('We expect reference bits'
343
 
                                        ' to be strings not: %s'
344
 
                                        % type(<object>ref_bit))
345
 
                                refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
346
 
 
347
 
    # So we have the (key NULL refs NULL value LF)
348
 
    key_len = PyString_Size(string_key)
349
 
    val = PyTuple_GET_ITEM_ptr_object(node, 2)
350
 
    if not PyString_CheckExact_ptr(val):
351
 
        raise TypeError('Expected a plain str for value not: %s'
352
 
                        % type(<object>val))
353
 
    value = PyString_AS_STRING_ptr(val)
354
 
    value_len = PyString_GET_SIZE_ptr(val)
355
 
    flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
356
 
    line = PyString_FromStringAndSize(NULL, flat_len)
357
 
    # Get a pointer to the new buffer
358
 
    out = PyString_AsString(line)
359
 
    memcpy(out, PyString_AsString(string_key), key_len)
360
 
    out = out + key_len
361
 
    out[0] = c'\0'
362
 
    out = out + 1
363
 
    if refs_len > 0:
364
 
        first_ref_list = 1
365
 
        for ref_list in ref_lists:
366
 
            if first_ref_list == 0:
367
 
                out[0] = c'\t'
368
 
                out = out + 1
369
 
            first_ref_list = 0
370
 
            first_reference = 1
371
 
            for reference in ref_list:
372
 
                if first_reference == 0:
373
 
                    out[0] = c'\r'
374
 
                    out = out + 1
375
 
                first_reference = 0
376
 
                next_len = PyTuple_GET_SIZE(reference)
377
 
                for i from 0 <= i < next_len:
378
 
                    if i != 0:
379
 
                        out[0] = c'\x00'
380
 
                        out = out + 1
381
 
                    ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
382
 
                    ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
383
 
                    memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
384
 
                    out = out + ref_bit_len
385
 
    out[0] = c'\0'
386
 
    out = out  + 1
387
 
    memcpy(out, value, value_len)
388
 
    out = out + value_len
389
 
    out[0] = c'\n'
390
 
    return string_key, line