/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_btree_serializer_c.pyx

  • Committer: mernst at mit
  • Date: 2008-10-16 10:57:16 UTC
  • mto: This revision was merged to the branch mainline in revision 3799.
  • Revision ID: mernst@csail.mit.edu-20081016105716-v8x8n5t2pf7f6uds
Improved documentation of stacked and lightweight branches

These patches improve the User Guide's documentation of stacked and
lightweight branches.

Section "1.2.6 Putting the concepts together" should mention stacked
branches and the difference between them and lightweight branches.  It
should also contain links to further details of the common scenarios.

Section "5.3.4 Getting a lightweight checkout" should mention stacked
branches as an option, and should link to all the options, not just some of
them.  It should also clarify that lightweight only applies to checkouts,
not to arbitrary branches.

Show diffs side-by-side

added added

removed removed

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