← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_btree_serializer_pyx.pyx

(jameinel) Allow 'bzr serve' to interpret SIGHUP as a graceful shutdown.
 (bug #795025) (John A Meinel)

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."""
32
32
 
33
33
    char *PyString_AsString(object p) except NULL
34
34
    object PyString_FromStringAndSize(char *, Py_ssize_t)
 
35
    PyObject *PyString_FromStringAndSize_ptr "PyString_FromStringAndSize" (char *, Py_ssize_t)
 
36
    object PyString_FromFormat(char *, ...)
35
37
    int PyString_CheckExact(object s)
36
38
    int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *)
37
39
    Py_ssize_t PyString_Size(object p)
38
40
    Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
39
41
    char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
 
42
    char * PyString_AS_STRING(object)
 
43
    Py_ssize_t PyString_GET_SIZE(object)
40
44
    int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
 
45
    void PyString_InternInPlace(PyObject **)
41
46
    int PyTuple_CheckExact(object t)
 
47
    object PyTuple_New(Py_ssize_t n_entries)
 
48
    void PyTuple_SET_ITEM(object, Py_ssize_t offset, object) # steals the ref
42
49
    Py_ssize_t PyTuple_GET_SIZE(object t)
43
50
    PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
 
51
    void Py_INCREF(object)
 
52
    void Py_DECREF_ptr "Py_DECREF" (PyObject *)
 
53
    void *PyMem_Malloc(size_t nbytes)
 
54
    void PyMem_Free(void *)
 
55
    void memset(void *, int, size_t)
44
56
 
45
57
cdef extern from "string.h":
46
58
    void *memcpy(void *dest, void *src, size_t n)
47
59
    void *memchr(void *s, int c, size_t n)
 
60
    int memcmp(void *s1, void *s2, size_t n)
48
61
    # GNU extension
49
62
    # void *memrchr(void *s, int c, size_t n)
50
63
    int strncmp(char *s1, char *s2, size_t n)
 
64
    unsigned long strtoul(char *s1, char **out, int base)
 
65
    long long strtoll(char *s1, char **out, int base)
 
66
 
 
67
 
 
68
# It seems we need to import the definitions so that the pyrex compiler has
 
69
# local names to access them.
 
70
from _static_tuple_c cimport StaticTuple, \
 
71
    import_static_tuple_c, StaticTuple_New, \
 
72
    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact, \
 
73
    StaticTuple_GET_SIZE, StaticTuple_GET_ITEM
 
74
# This tells the test infrastructure that StaticTuple is a class, so we don't
 
75
# have to worry about exception checking.
 
76
## extern cdef class StaticTuple
 
77
import sys
51
78
 
52
79
 
53
80
# TODO: Find some way to import this from _dirstate_helpers
54
 
cdef void* _my_memrchr(void *s, int c, size_t n):
 
81
cdef void* _my_memrchr(void *s, int c, size_t n): # cannot_raise
55
82
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
56
83
    # It is not present in any win32 standard library
57
84
    cdef char *pos
65
92
        pos = pos - 1
66
93
    return NULL
67
94
 
 
95
 
68
96
# TODO: Import this from _dirstate_helpers when it is merged
69
97
cdef object safe_string_from_size(char *s, Py_ssize_t size):
70
98
    if size < 0:
74
102
    return PyString_FromStringAndSize(s, size)
75
103
 
76
104
 
 
105
cdef object safe_interned_string_from_size(char *s, Py_ssize_t size):
 
106
    cdef PyObject *py_str
 
107
    if size < 0:
 
108
        raise AssertionError(
 
109
            'tried to create a string with an invalid size: %d @0x%x'
 
110
            % (size, <int>s))
 
111
    py_str = PyString_FromStringAndSize_ptr(s, size)
 
112
    PyString_InternInPlace(&py_str)
 
113
    result = <object>py_str
 
114
    # Casting a PyObject* to an <object> triggers an INCREF from Pyrex, so we
 
115
    # DECREF it to avoid geting immortal strings
 
116
    Py_DECREF_ptr(py_str)
 
117
    return result
 
118
 
 
119
# This sets up the StaticTuple C_API functionality
 
120
import_static_tuple_c()
 
121
 
 
122
 
77
123
cdef class BTreeLeafParser:
78
124
    """Parse the leaf nodes of a BTree index.
79
125
 
112
158
        self._cur_str = NULL
113
159
        self._end_str = NULL
114
160
        self._header_found = 0
 
161
        # keys are tuples
115
162
 
116
163
    cdef extract_key(self, char * last):
117
164
        """Extract a key.
121
168
        """
122
169
        cdef char *temp_ptr
123
170
        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
 
171
        cdef StaticTuple key
 
172
 
 
173
        key = StaticTuple_New(self.key_length)
 
174
        for loop_counter from 0 <= loop_counter < self.key_length:
129
175
            # grab a key segment
130
176
            temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
131
177
            if temp_ptr == NULL:
132
 
                if loop_counter == self.key_length:
 
178
                if loop_counter + 1 == self.key_length:
133
179
                    # capture to last
134
180
                    temp_ptr = last
135
181
                else:
139
185
                                                   last - self._start)))
140
186
                    raise AssertionError(failure_string)
141
187
            # 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)
 
188
            if (self.key_length == 1
 
189
                and (temp_ptr - self._start) == 45
 
190
                and strncmp(self._start, 'sha1:', 5) == 0):
 
191
                key_element = safe_string_from_size(self._start,
 
192
                                                    temp_ptr - self._start)
 
193
            else:
 
194
                key_element = safe_interned_string_from_size(self._start,
 
195
                                                         temp_ptr - self._start)
147
196
            # advance our pointer
148
197
            self._start = temp_ptr + 1
149
 
            PyList_Append(key_segments, key_element)
150
 
        return tuple(key_segments)
 
198
            Py_INCREF(key_element)
 
199
            StaticTuple_SET_ITEM(key, loop_counter, key_element)
 
200
        key = StaticTuple_Intern(key)
 
201
        return key
151
202
 
152
203
    cdef int process_line(self) except -1:
153
204
        """Process a line in the bytes."""
156
207
        cdef char *ref_ptr
157
208
        cdef char *next_start
158
209
        cdef int loop_counter
 
210
        cdef Py_ssize_t str_len
159
211
 
160
212
        self._start = self._cur_str
161
213
        # Find the next newline
168
220
            # And the next string is right after it
169
221
            self._cur_str = last + 1
170
222
            # The last character is right before the '\n'
171
 
            last = last
172
223
 
173
224
        if last == self._start:
174
225
            # parsed it all.
175
226
            return 0
176
227
        if last < self._start:
177
228
            # Unexpected error condition - fail
178
 
            return -1
 
229
            raise AssertionError("last < self._start")
179
230
        if 0 == self._header_found:
180
231
            # The first line in a leaf node is the header "type=leaf\n"
181
232
            if strncmp("type=leaf", self._start, last - self._start) == 0:
184
235
            else:
185
236
                raise AssertionError('Node did not start with "type=leaf": %r'
186
237
                    % (safe_string_from_size(self._start, last - self._start)))
187
 
                return -1
188
238
 
189
239
        key = self.extract_key(last)
190
240
        # find the value area
191
241
        temp_ptr = <char*>_my_memrchr(self._start, c'\0', last - self._start)
192
242
        if temp_ptr == NULL:
193
243
            # Invalid line
194
 
            return -1
 
244
            raise AssertionError("Failed to find the value area")
195
245
        else:
196
 
            # capture the value string
197
 
            value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
 
246
            # Because of how conversions were done, we ended up with *lots* of
 
247
            # values that are identical. These are all of the 0-length nodes
 
248
            # that are referred to by the TREE_ROOT (and likely some other
 
249
            # directory nodes.) For example, bzr has 25k references to
 
250
            # something like '12607215 328306 0 0', which ends up consuming 1MB
 
251
            # of memory, just for those strings.
 
252
            str_len = last - temp_ptr - 1
 
253
            if (str_len > 4
 
254
                and strncmp(" 0 0", last - 4, 4) == 0):
 
255
                # This drops peak mem for bzr.dev from 87.4MB => 86.2MB
 
256
                # For Launchpad 236MB => 232MB
 
257
                value = safe_interned_string_from_size(temp_ptr + 1, str_len)
 
258
            else:
 
259
                value = safe_string_from_size(temp_ptr + 1, str_len)
198
260
            # shrink the references end point
199
261
            last = temp_ptr
 
262
 
200
263
        if self.ref_list_length:
201
 
            ref_lists = []
 
264
            ref_lists = StaticTuple_New(self.ref_list_length)
202
265
            loop_counter = 0
203
266
            while loop_counter < self.ref_list_length:
204
267
                ref_list = []
205
268
                # extract a reference list
206
269
                loop_counter = loop_counter + 1
207
270
                if last < self._start:
208
 
                    return -1
 
271
                    raise AssertionError("last < self._start")
209
272
                # find the next reference list end point:
210
273
                temp_ptr = <char*>memchr(self._start, c'\t', last - self._start)
211
274
                if temp_ptr == NULL:
212
275
                    # Only valid for the last list
213
276
                    if loop_counter != self.ref_list_length:
214
277
                        # Invalid line
215
 
                        return -1
216
 
                        raise AssertionError("invalid key")
 
278
                        raise AssertionError(
 
279
                            "invalid key, loop_counter != self.ref_list_length")
217
280
                    else:
218
281
                        # scan to the end of the ref list area
219
282
                        ref_ptr = last
230
293
                    if temp_ptr == NULL:
231
294
                        # key runs to the end
232
295
                        temp_ptr = ref_ptr
 
296
 
233
297
                    PyList_Append(ref_list, self.extract_key(temp_ptr))
234
 
                PyList_Append(ref_lists, tuple(ref_list))
 
298
                ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
 
299
                Py_INCREF(ref_list)
 
300
                StaticTuple_SET_ITEM(ref_lists, loop_counter - 1, ref_list)
235
301
                # prepare for the next reference list
236
302
                self._start = next_start
237
 
            ref_lists = tuple(ref_lists)
238
 
            node_value = (value, ref_lists)
 
303
            node_value = StaticTuple(value, ref_lists)
239
304
        else:
240
305
            if last != self._start:
241
306
                # unexpected reference data present
242
 
                return -1
243
 
            node_value = (value, ())
244
 
        PyList_Append(self.keys, (key, node_value))
 
307
                raise AssertionError("unexpected reference data present")
 
308
            node_value = StaticTuple(value, StaticTuple())
 
309
        PyList_Append(self.keys, StaticTuple(key, node_value))
245
310
        return 0
246
311
 
247
312
    def parse(self):
262
327
    return parser.parse()
263
328
 
264
329
 
 
330
# TODO: We can go from 8 byte offset + 4 byte length to a simple lookup,
 
331
#       because the block_offset + length is likely to be repeated. However,
 
332
#       the big win there is to cache across pages, and not just one page
 
333
#       Though if we did cache in a page, we could certainly use a short int.
 
334
#       And this goes from 40 bytes to 30 bytes.
 
335
#       One slightly ugly option would be to cache block offsets in a global.
 
336
#       However, that leads to thread-safety issues, etc.
 
337
ctypedef struct gc_chk_sha1_record:
 
338
    long long block_offset
 
339
    unsigned int block_length
 
340
    unsigned int record_start
 
341
    unsigned int record_end
 
342
    char sha1[20]
 
343
 
 
344
 
 
345
cdef int _unhexbuf[256]
 
346
cdef char *_hexbuf
 
347
_hexbuf = '0123456789abcdef'
 
348
 
 
349
cdef _populate_unhexbuf():
 
350
    cdef int i
 
351
    for i from 0 <= i < 256:
 
352
        _unhexbuf[i] = -1
 
353
    for i from 0 <= i < 10: # 0123456789 => map to the raw number
 
354
        _unhexbuf[(i + c'0')] = i
 
355
    for i from 10 <= i < 16: # abcdef => 10, 11, 12, 13, 14, 15, 16
 
356
        _unhexbuf[(i - 10 + c'a')] = i
 
357
    for i from 10 <= i < 16: # ABCDEF => 10, 11, 12, 13, 14, 15, 16
 
358
        _unhexbuf[(i - 10 + c'A')] = i
 
359
_populate_unhexbuf()
 
360
 
 
361
 
 
362
cdef int _unhexlify_sha1(char *as_hex, char *as_bin): # cannot_raise
 
363
    """Take the hex sha1 in as_hex and make it binary in as_bin
 
364
    
 
365
    Same as binascii.unhexlify, but working on C strings, not Python objects.
 
366
    """
 
367
    cdef int top
 
368
    cdef int bot
 
369
    cdef int i, j
 
370
    cdef char *cur
 
371
    
 
372
    # binascii does this using isupper() and tolower() and ?: syntax. I'm
 
373
    # guessing a simple lookup array should be faster.
 
374
    j = 0
 
375
    for i from 0 <= i < 20:
 
376
        top = _unhexbuf[<unsigned char>(as_hex[j])]
 
377
        j = j + 1
 
378
        bot = _unhexbuf[<unsigned char>(as_hex[j])]
 
379
        j = j + 1
 
380
        if top == -1 or bot == -1:
 
381
            return 0
 
382
        as_bin[i] = <unsigned char>((top << 4) + bot);
 
383
    return 1
 
384
 
 
385
 
 
386
def _py_unhexlify(as_hex):
 
387
    """For the test infrastructure, just thunks to _unhexlify_sha1"""
 
388
    if len(as_hex) != 40 or not PyString_CheckExact(as_hex):
 
389
        raise ValueError('not a 40-byte hex digest')
 
390
    as_bin = PyString_FromStringAndSize(NULL, 20)
 
391
    if _unhexlify_sha1(PyString_AS_STRING(as_hex), PyString_AS_STRING(as_bin)):
 
392
        return as_bin
 
393
    return None
 
394
 
 
395
 
 
396
cdef void _hexlify_sha1(char *as_bin, char *as_hex): # cannot_raise
 
397
    cdef int i, j
 
398
    cdef char c
 
399
 
 
400
    j = 0
 
401
    for i from 0 <= i < 20:
 
402
        c = as_bin[i]
 
403
        as_hex[j] = _hexbuf[(c>>4)&0xf]
 
404
        j = j + 1
 
405
        as_hex[j] = _hexbuf[(c)&0xf]
 
406
        j = j + 1
 
407
 
 
408
 
 
409
def _py_hexlify(as_bin):
 
410
    """For test infrastructure, thunk to _hexlify_sha1"""
 
411
    if len(as_bin) != 20 or not PyString_CheckExact(as_bin):
 
412
        raise ValueError('not a 20-byte binary digest')
 
413
    as_hex = PyString_FromStringAndSize(NULL, 40)
 
414
    _hexlify_sha1(PyString_AS_STRING(as_bin), PyString_AS_STRING(as_hex))
 
415
    return as_hex
 
416
 
 
417
 
 
418
cdef int _key_to_sha1(key, char *sha1): # cannot_raise
 
419
    """Map a key into its sha1 content.
 
420
 
 
421
    :param key: A tuple of style ('sha1:abcd...',)
 
422
    :param sha1: A char buffer of 20 bytes
 
423
    :return: 1 if this could be converted, 0 otherwise
 
424
    """
 
425
    cdef char *c_val
 
426
    cdef PyObject *p_val
 
427
 
 
428
    if StaticTuple_CheckExact(key) and StaticTuple_GET_SIZE(key) == 1:
 
429
        p_val = <PyObject *>StaticTuple_GET_ITEM(key, 0)
 
430
    elif (PyTuple_CheckExact(key) and PyTuple_GET_SIZE(key) == 1):
 
431
        p_val = PyTuple_GET_ITEM_ptr_object(key, 0)
 
432
    else:
 
433
        # Not a tuple or a StaticTuple
 
434
        return 0
 
435
    if (PyString_CheckExact_ptr(p_val) and PyString_GET_SIZE_ptr(p_val) == 45):
 
436
        c_val = PyString_AS_STRING_ptr(p_val)
 
437
    else:
 
438
        return 0
 
439
    if strncmp(c_val, 'sha1:', 5) != 0:
 
440
        return 0
 
441
    if not _unhexlify_sha1(c_val + 5, sha1):
 
442
        return 0
 
443
    return 1
 
444
 
 
445
 
 
446
def _py_key_to_sha1(key):
 
447
    """Map a key to a simple sha1 string.
 
448
 
 
449
    This is a testing thunk to the C function.
 
450
    """
 
451
    as_bin_sha = PyString_FromStringAndSize(NULL, 20)
 
452
    if _key_to_sha1(key, PyString_AS_STRING(as_bin_sha)):
 
453
        return as_bin_sha
 
454
    return None
 
455
 
 
456
 
 
457
cdef StaticTuple _sha1_to_key(char *sha1):
 
458
    """Compute a ('sha1:abcd',) key for a given sha1."""
 
459
    cdef StaticTuple key
 
460
    cdef object hexxed
 
461
    cdef char *c_buf
 
462
    hexxed = PyString_FromStringAndSize(NULL, 45)
 
463
    c_buf = PyString_AS_STRING(hexxed)
 
464
    memcpy(c_buf, 'sha1:', 5)
 
465
    _hexlify_sha1(sha1, c_buf+5)
 
466
    key = StaticTuple_New(1)
 
467
    Py_INCREF(hexxed)
 
468
    StaticTuple_SET_ITEM(key, 0, hexxed)
 
469
    # This is a bit expensive. To parse 120 keys takes 48us, to return them all
 
470
    # can be done in 66.6us (so 18.6us to build them all).
 
471
    # Adding simple hash() here brings it to 76.6us (so computing the hash
 
472
    # value of 120keys is 10us), Intern is 86.9us (another 10us to look and add
 
473
    # them to the intern structure.)
 
474
    # However, since we only intern keys that are in active use, it is probably
 
475
    # a win. Since they would have been read from elsewhere anyway.
 
476
    # We *could* hang the PyObject form off of the gc_chk_sha1_record for ones
 
477
    # that we have deserialized. Something to think about, at least.
 
478
    key = StaticTuple_Intern(key)
 
479
    return key
 
480
 
 
481
 
 
482
def _py_sha1_to_key(sha1_bin):
 
483
    """Test thunk to check the sha1 mapping."""
 
484
    if not PyString_CheckExact(sha1_bin) or PyString_GET_SIZE(sha1_bin) != 20:
 
485
        raise ValueError('sha1_bin must be a str of exactly 20 bytes')
 
486
    return _sha1_to_key(PyString_AS_STRING(sha1_bin))
 
487
 
 
488
 
 
489
cdef unsigned int _sha1_to_uint(char *sha1): # cannot_raise
 
490
    cdef unsigned int val
 
491
    # Must be in MSB, because that is how the content is sorted
 
492
    val = (((<unsigned int>(sha1[0]) & 0xff) << 24)
 
493
           | ((<unsigned int>(sha1[1]) & 0xff) << 16)
 
494
           | ((<unsigned int>(sha1[2]) & 0xff) << 8)
 
495
           | ((<unsigned int>(sha1[3]) & 0xff) << 0))
 
496
    return val
 
497
 
 
498
 
 
499
cdef _format_record(gc_chk_sha1_record *record):
 
500
    # This is inefficient to go from a logical state back to a
 
501
    # string, but it makes things work a bit better internally for now.
 
502
    if record.block_offset >= 0xFFFFFFFF:
 
503
        # %llu is what we really want, but unfortunately it was only added
 
504
        # in python 2.7... :(
 
505
        block_offset_str = str(record.block_offset)
 
506
        value = PyString_FromFormat('%s %u %u %u',
 
507
                                PyString_AS_STRING(block_offset_str),
 
508
                                record.block_length,
 
509
                                record.record_start, record.record_end)
 
510
    else:
 
511
        value = PyString_FromFormat('%lu %u %u %u',
 
512
                                    <unsigned long>record.block_offset,
 
513
                                    record.block_length,
 
514
                                    record.record_start, record.record_end)
 
515
    return value
 
516
 
 
517
 
 
518
cdef class GCCHKSHA1LeafNode:
 
519
    """Track all the entries for a given leaf node."""
 
520
 
 
521
    cdef gc_chk_sha1_record *records
 
522
    cdef public object last_key
 
523
    cdef gc_chk_sha1_record *last_record
 
524
    cdef public int num_records
 
525
    # This is the number of bits to shift to get to the interesting byte. A
 
526
    # value of 24 means that the very first byte changes across all keys.
 
527
    # Anything else means that there is a common prefix of bits that we can
 
528
    # ignore. 0 means that at least the first 3 bytes are identical, though
 
529
    # that is going to be very rare
 
530
    cdef public unsigned char common_shift
 
531
    # This maps an interesting byte to the first record that matches.
 
532
    # Equivalent to bisect.bisect_left(self.records, sha1), though only taking
 
533
    # into account that one byte.
 
534
    cdef unsigned char offsets[257]
 
535
 
 
536
    def __sizeof__(self):
 
537
        # :( Why doesn't Pyrex let me do a simple sizeof(GCCHKSHA1LeafNode)
 
538
        # like Cython? Explicitly enumerating everything here seems to leave my
 
539
        # size off by 2 (286 bytes vs 288 bytes actual). I'm guessing it is an
 
540
        # alignment/padding issue. Oh well- at least we scale properly with
 
541
        # num_records and are very close to correct, which is what I care
 
542
        # about.
 
543
        # If we ever decide to require cython:
 
544
        # return (sizeof(GCCHKSHA1LeafNode)
 
545
        #     + sizeof(gc_chk_sha1_record)*self.num_records)
 
546
        return (sizeof(PyObject) + sizeof(void*) + sizeof(int)
 
547
            + sizeof(gc_chk_sha1_record*) + sizeof(PyObject *)
 
548
            + sizeof(gc_chk_sha1_record*) + sizeof(char)
 
549
            + sizeof(unsigned char)*257
 
550
            + sizeof(gc_chk_sha1_record)*self.num_records)
 
551
 
 
552
    def __dealloc__(self):
 
553
        if self.records != NULL:
 
554
            PyMem_Free(self.records)
 
555
            self.records = NULL
 
556
 
 
557
    def __init__(self, bytes):
 
558
        self._parse_bytes(bytes)
 
559
        self.last_key = None
 
560
        self.last_record = NULL
 
561
 
 
562
    property min_key:
 
563
        def __get__(self):
 
564
            if self.num_records > 0:
 
565
                return _sha1_to_key(self.records[0].sha1)
 
566
            return None
 
567
 
 
568
    property max_key:
 
569
        def __get__(self):
 
570
            if self.num_records > 0:
 
571
                return _sha1_to_key(self.records[self.num_records-1].sha1)
 
572
            return None
 
573
 
 
574
    cdef StaticTuple _record_to_value_and_refs(self,
 
575
                                               gc_chk_sha1_record *record):
 
576
        """Extract the refs and value part of this record."""
 
577
        cdef StaticTuple value_and_refs
 
578
        cdef StaticTuple empty
 
579
        value_and_refs = StaticTuple_New(2)
 
580
        value = _format_record(record)
 
581
        Py_INCREF(value)
 
582
        StaticTuple_SET_ITEM(value_and_refs, 0, value)
 
583
        # Always empty refs
 
584
        empty = StaticTuple_New(0)
 
585
        Py_INCREF(empty)
 
586
        StaticTuple_SET_ITEM(value_and_refs, 1, empty)
 
587
        return value_and_refs
 
588
 
 
589
    cdef StaticTuple _record_to_item(self, gc_chk_sha1_record *record):
 
590
        """Turn a given record back into a fully fledged item.
 
591
        """
 
592
        cdef StaticTuple item
 
593
        cdef StaticTuple key
 
594
        cdef StaticTuple value_and_refs
 
595
        cdef object value
 
596
        key = _sha1_to_key(record.sha1)
 
597
        item = StaticTuple_New(2)
 
598
        Py_INCREF(key)
 
599
        StaticTuple_SET_ITEM(item, 0, key)
 
600
        value_and_refs = self._record_to_value_and_refs(record)
 
601
        Py_INCREF(value_and_refs)
 
602
        StaticTuple_SET_ITEM(item, 1, value_and_refs)
 
603
        return item
 
604
 
 
605
    cdef gc_chk_sha1_record* _lookup_record(self, char *sha1) except? NULL:
 
606
        """Find a gc_chk_sha1_record that matches the sha1 supplied."""
 
607
        cdef int lo, hi, mid, the_cmp
 
608
        cdef int offset
 
609
 
 
610
        # TODO: We can speed up misses by comparing this sha1 to the common
 
611
        #       bits, and seeing if the common prefix matches, if not, we don't
 
612
        #       need to search for anything because it cannot match
 
613
        # Use the offset array to find the closest fit for this entry
 
614
        # follow that up with bisecting, since multiple keys can be in one
 
615
        # spot
 
616
        # Bisecting dropped us from 7000 comparisons to 582 (4.8/key), using
 
617
        # the offset array dropped us from 23us to 20us and 156 comparisions
 
618
        # (1.3/key)
 
619
        offset = self._offset_for_sha1(sha1)
 
620
        lo = self.offsets[offset]
 
621
        hi = self.offsets[offset+1]
 
622
        if hi == 255:
 
623
            # if hi == 255 that means we potentially ran off the end of the
 
624
            # list, so push it up to num_records
 
625
            # note that if 'lo' == 255, that is ok, because we can start
 
626
            # searching from that part of the list.
 
627
            hi = self.num_records
 
628
        local_n_cmp = 0
 
629
        while lo < hi:
 
630
            mid = (lo + hi) / 2
 
631
            the_cmp = memcmp(self.records[mid].sha1, sha1, 20)
 
632
            if the_cmp == 0:
 
633
                return &self.records[mid]
 
634
            elif the_cmp < 0:
 
635
                lo = mid + 1
 
636
            else:
 
637
                hi = mid
 
638
        return NULL
 
639
 
 
640
    def __contains__(self, key):
 
641
        cdef char sha1[20]
 
642
        cdef gc_chk_sha1_record *record
 
643
        if _key_to_sha1(key, sha1):
 
644
            # If it isn't a sha1 key, then it won't be in this leaf node
 
645
            record = self._lookup_record(sha1)
 
646
            if record != NULL:
 
647
                self.last_key = key
 
648
                self.last_record = record
 
649
                return True
 
650
        return False
 
651
 
 
652
    def __getitem__(self, key):
 
653
        cdef char sha1[20]
 
654
        cdef gc_chk_sha1_record *record
 
655
        record = NULL
 
656
        if self.last_record != NULL and key is self.last_key:
 
657
            record = self.last_record
 
658
        elif _key_to_sha1(key, sha1):
 
659
            record = self._lookup_record(sha1)
 
660
        if record == NULL:
 
661
            raise KeyError('key %r is not present' % (key,))
 
662
        return self._record_to_value_and_refs(record)
 
663
 
 
664
    def __len__(self):
 
665
        return self.num_records
 
666
 
 
667
    def all_keys(self):
 
668
        cdef int i
 
669
        result = []
 
670
        for i from 0 <= i < self.num_records:
 
671
            PyList_Append(result, _sha1_to_key(self.records[i].sha1))
 
672
        return result
 
673
 
 
674
    def all_items(self):
 
675
        cdef int i
 
676
        result = []
 
677
        for i from 0 <= i < self.num_records:
 
678
            item = self._record_to_item(&self.records[i])
 
679
            PyList_Append(result, item)
 
680
        return result
 
681
 
 
682
    cdef int _count_records(self, char *c_content, char *c_end): # cannot_raise
 
683
        """Count how many records are in this section."""
 
684
        cdef char *c_cur
 
685
        cdef int num_records
 
686
 
 
687
        c_cur = c_content
 
688
        num_records = 0
 
689
        while c_cur != NULL and c_cur < c_end:
 
690
            c_cur = <char *>memchr(c_cur, c'\n', c_end - c_cur);
 
691
            if c_cur == NULL:
 
692
                break
 
693
            c_cur = c_cur + 1
 
694
            num_records = num_records + 1
 
695
        return num_records
 
696
 
 
697
    cdef _parse_bytes(self, bytes):
 
698
        """Parse the string 'bytes' into content."""
 
699
        cdef char *c_bytes
 
700
        cdef char *c_cur
 
701
        cdef char *c_end
 
702
        cdef Py_ssize_t n_bytes
 
703
        cdef int num_records
 
704
        cdef int entry
 
705
        cdef gc_chk_sha1_record *cur_record
 
706
 
 
707
        if not PyString_CheckExact(bytes):
 
708
            raise TypeError('We only support parsing plain 8-bit strings.')
 
709
        # Pass 1, count how many records there will be
 
710
        n_bytes = PyString_GET_SIZE(bytes)
 
711
        c_bytes = PyString_AS_STRING(bytes)
 
712
        c_end = c_bytes + n_bytes
 
713
        if strncmp(c_bytes, 'type=leaf\n', 10):
 
714
            raise ValueError("bytes did not start with 'type=leaf\\n': %r"
 
715
                             % (bytes[:10],))
 
716
        c_cur = c_bytes + 10
 
717
        num_records = self._count_records(c_cur, c_end)
 
718
        # Now allocate the memory for these items, and go to town
 
719
        self.records = <gc_chk_sha1_record*>PyMem_Malloc(num_records *
 
720
            (sizeof(unsigned short) + sizeof(gc_chk_sha1_record)))
 
721
        self.num_records = num_records
 
722
        cur_record = self.records
 
723
        entry = 0
 
724
        while c_cur != NULL and c_cur < c_end and entry < num_records:
 
725
            c_cur = self._parse_one_entry(c_cur, c_end, cur_record)
 
726
            cur_record = cur_record + 1
 
727
            entry = entry + 1
 
728
        if (entry != self.num_records
 
729
            or c_cur != c_end
 
730
            or cur_record != self.records + self.num_records):
 
731
            raise ValueError('Something went wrong while parsing.')
 
732
        # Pass 3: build the offset map
 
733
        self._compute_common()
 
734
 
 
735
    cdef char *_parse_one_entry(self, char *c_cur, char *c_end,
 
736
                                gc_chk_sha1_record *cur_record) except NULL:
 
737
        """Read a single sha record from the bytes.
 
738
        :param c_cur: The pointer to the start of bytes
 
739
        :param cur_record: 
 
740
        """
 
741
        cdef char *c_next
 
742
        if strncmp(c_cur, 'sha1:', 5):
 
743
            raise ValueError('line did not start with sha1: %r'
 
744
                % (safe_string_from_size(c_cur, 10),))
 
745
        c_cur = c_cur + 5
 
746
        c_next = <char *>memchr(c_cur, c'\0', c_end - c_cur)
 
747
        if c_next == NULL or (c_next - c_cur != 40):
 
748
            raise ValueError('Line did not contain 40 hex bytes')
 
749
        if not _unhexlify_sha1(c_cur, cur_record.sha1):
 
750
            raise ValueError('We failed to unhexlify')
 
751
        c_cur = c_next + 1
 
752
        if c_cur[0] != c'\0':
 
753
            raise ValueError('only 1 null, not 2 as expected')
 
754
        c_cur = c_cur + 1
 
755
        cur_record.block_offset = strtoll(c_cur, &c_next, 10)
 
756
        if c_cur == c_next or c_next[0] != c' ':
 
757
            raise ValueError('Failed to parse block offset')
 
758
        c_cur = c_next + 1
 
759
        cur_record.block_length = strtoul(c_cur, &c_next, 10)
 
760
        if c_cur == c_next or c_next[0] != c' ':
 
761
            raise ValueError('Failed to parse block length')
 
762
        c_cur = c_next + 1
 
763
        cur_record.record_start = strtoul(c_cur, &c_next, 10)
 
764
        if c_cur == c_next or c_next[0] != c' ':
 
765
            raise ValueError('Failed to parse block length')
 
766
        c_cur = c_next + 1
 
767
        cur_record.record_end = strtoul(c_cur, &c_next, 10)
 
768
        if c_cur == c_next or c_next[0] != c'\n':
 
769
            raise ValueError('Failed to parse record end')
 
770
        c_cur = c_next + 1
 
771
        return c_cur
 
772
 
 
773
    cdef int _offset_for_sha1(self, char *sha1) except -1:
 
774
        """Find the first interesting 8-bits of this sha1."""
 
775
        cdef int this_offset
 
776
        cdef unsigned int as_uint
 
777
        as_uint = _sha1_to_uint(sha1)
 
778
        this_offset = (as_uint >> self.common_shift) & 0xFF
 
779
        return this_offset
 
780
 
 
781
    def _get_offset_for_sha1(self, sha1):
 
782
        return self._offset_for_sha1(PyString_AS_STRING(sha1))
 
783
 
 
784
    cdef _compute_common(self):
 
785
        cdef unsigned int first
 
786
        cdef unsigned int this
 
787
        cdef unsigned int common_mask
 
788
        cdef unsigned char common_shift
 
789
        cdef int i
 
790
        cdef int offset, this_offset
 
791
        cdef int max_offset
 
792
        # The idea with the offset map is that we should be able to quickly
 
793
        # jump to the key that matches a gives sha1. We know that the keys are
 
794
        # in sorted order, and we know that a lot of the prefix is going to be
 
795
        # the same across them.
 
796
        # By XORing the records together, we can determine what bits are set in
 
797
        # all of them
 
798
        if self.num_records < 2:
 
799
            # Everything is in common if you have 0 or 1 leaves
 
800
            # So we'll always just shift to the first byte
 
801
            self.common_shift = 24
 
802
        else:
 
803
            common_mask = 0xFFFFFFFF
 
804
            first = _sha1_to_uint(self.records[0].sha1)
 
805
            for i from 0 < i < self.num_records:
 
806
                this = _sha1_to_uint(self.records[i].sha1)
 
807
                common_mask = (~(first ^ this)) & common_mask
 
808
            common_shift = 24
 
809
            while common_mask & 0x80000000 and common_shift > 0:
 
810
                common_mask = common_mask << 1
 
811
                common_shift = common_shift - 1
 
812
            self.common_shift = common_shift
 
813
        offset = 0
 
814
        max_offset = self.num_records
 
815
        # We cap this loop at 254 records. All the other offsets just get
 
816
        # filled with 0xff as the singleton saying 'too many'.
 
817
        # It means that if we have >255 records we have to bisect the second
 
818
        # half of the list, but this is going to be very rare in practice.
 
819
        if max_offset > 255:
 
820
            max_offset = 255
 
821
        for i from 0 <= i < max_offset:
 
822
            this_offset = self._offset_for_sha1(self.records[i].sha1)
 
823
            while offset <= this_offset:
 
824
                self.offsets[offset] = i
 
825
                offset = offset + 1
 
826
        while offset < 257:
 
827
            self.offsets[offset] = max_offset
 
828
            offset = offset + 1
 
829
 
 
830
    def _get_offsets(self):
 
831
        cdef int i
 
832
        result = []
 
833
        for i from 0 <= i < 257:
 
834
            PyList_Append(result, self.offsets[i])
 
835
        return result
 
836
 
 
837
 
 
838
def _parse_into_chk(bytes, key_length, ref_list_length):
 
839
    """Parse into a format optimized for chk records."""
 
840
    assert key_length == 1
 
841
    assert ref_list_length == 0
 
842
    return GCCHKSHA1LeafNode(bytes)
 
843
 
 
844
 
265
845
def _flatten_node(node, reference_lists):
266
846
    """Convert a node into the serialized form.
267
847
 
276
856
    cdef Py_ssize_t flat_len
277
857
    cdef Py_ssize_t key_len
278
858
    cdef Py_ssize_t node_len
279
 
    cdef PyObject * val
280
859
    cdef char * value
281
860
    cdef Py_ssize_t value_len
282
861
    cdef char * out
285
864
    cdef int first_ref_list
286
865
    cdef int first_reference
287
866
    cdef int i
288
 
    cdef PyObject *ref_bit
289
867
    cdef Py_ssize_t ref_bit_len
290
868
 
291
 
    if not PyTuple_CheckExact(node):
292
 
        raise TypeError('We expected a tuple() for node not: %s'
 
869
    if not PyTuple_CheckExact(node) and not StaticTuple_CheckExact(node):
 
870
        raise TypeError('We expected a tuple() or StaticTuple() for node not: %s'
293
871
            % type(node))
294
 
    node_len = PyTuple_GET_SIZE(node)
 
872
    node_len = len(node)
295
873
    have_reference_lists = reference_lists
296
874
    if have_reference_lists:
297
875
        if node_len != 4:
300
878
    elif node_len < 3:
301
879
        raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
302
880
            % 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))
 
881
    # TODO: We can probably do better than string.join(), namely
 
882
    #       when key has only 1 item, we can just grab that string
 
883
    #       And when there are 2 items, we could do a single malloc + len() + 1
 
884
    #       also, doing .join() requires a PyObject_GetAttrString call, which
 
885
    #       we could also avoid.
 
886
    # TODO: Note that pyrex 0.9.6 generates fairly crummy code here, using the
 
887
    #       python object interface, versus 0.9.8+ which uses a helper that
 
888
    #       checks if this supports the sequence interface.
 
889
    #       We *could* do more work on our own, and grab the actual items
 
890
    #       lists. For now, just ask people to use a better compiler. :)
 
891
    string_key = '\0'.join(node[1])
305
892
 
306
893
    # TODO: instead of using string joins, precompute the final string length,
307
894
    #       and then malloc a single string and copy everything in.
318
905
    refs_len = 0
319
906
    if have_reference_lists:
320
907
        # Figure out how many bytes it will take to store the references
321
 
        ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
 
908
        ref_lists = node[3]
322
909
        next_len = len(ref_lists) # TODO: use a Py function
323
910
        if next_len > 0:
324
911
            # If there are no nodes, we don't need to do any work
332
919
                    # references
333
920
                    refs_len = refs_len + (next_len - 1)
334
921
                    for reference in ref_list:
335
 
                        if not PyTuple_CheckExact(reference):
 
922
                        if (not PyTuple_CheckExact(reference)
 
923
                            and not StaticTuple_CheckExact(reference)):
336
924
                            raise TypeError(
337
925
                                'We expect references to be tuples not: %s'
338
926
                                % type(reference))
339
 
                        next_len = PyTuple_GET_SIZE(reference)
 
927
                        next_len = len(reference)
340
928
                        if next_len > 0:
341
929
                            # We will need (len - 1) '\x00' characters to
342
930
                            # separate the reference key
343
931
                            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):
 
932
                            for ref_bit in reference:
 
933
                                if not PyString_CheckExact(ref_bit):
347
934
                                    raise TypeError('We expect reference bits'
348
935
                                        ' to be strings not: %s'
349
936
                                        % type(<object>ref_bit))
350
 
                                refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
 
937
                                refs_len = refs_len + PyString_GET_SIZE(ref_bit)
351
938
 
352
939
    # So we have the (key NULL refs NULL value LF)
353
940
    key_len = PyString_Size(string_key)
354
 
    val = PyTuple_GET_ITEM_ptr_object(node, 2)
355
 
    if not PyString_CheckExact_ptr(val):
 
941
    val = node[2]
 
942
    if not PyString_CheckExact(val):
356
943
        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)
 
944
                        % type(val))
 
945
    value = PyString_AS_STRING(val)
 
946
    value_len = PyString_GET_SIZE(val)
360
947
    flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
361
948
    line = PyString_FromStringAndSize(NULL, flat_len)
362
949
    # Get a pointer to the new buffer
378
965
                    out[0] = c'\r'
379
966
                    out = out + 1
380
967
                first_reference = 0
381
 
                next_len = PyTuple_GET_SIZE(reference)
 
968
                next_len = len(reference)
382
969
                for i from 0 <= i < next_len:
383
970
                    if i != 0:
384
971
                        out[0] = c'\x00'
385
972
                        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)
 
973
                    ref_bit = reference[i]
 
974
                    ref_bit_len = PyString_GET_SIZE(ref_bit)
 
975
                    memcpy(out, PyString_AS_STRING(ref_bit), ref_bit_len)
389
976
                    out = out + ref_bit_len
390
977
    out[0] = c'\0'
391
978
    out = out  + 1