~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_btree_serializer_pyx.pyx

  • Committer: Danny van Heumen
  • Date: 2010-03-09 16:38:10 UTC
  • mto: (4634.139.5 2.0)
  • mto: This revision was merged to the branch mainline in revision 5160.
  • Revision ID: danny@dannyvanheumen.nl-20100309163810-ujn8hcx08f75nlf1
Refined test to make use of locking hooks and also validate if lock is truly a checkout-lock.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
33
33
    char *PyString_AsString(object p) except NULL
34
34
    object PyString_FromStringAndSize(char *, Py_ssize_t)
35
35
    PyObject *PyString_FromStringAndSize_ptr "PyString_FromStringAndSize" (char *, Py_ssize_t)
36
 
    object PyString_FromFormat(char *, ...)
37
36
    int PyString_CheckExact(object s)
38
37
    int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *)
39
38
    Py_ssize_t PyString_Size(object p)
40
39
    Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *)
41
40
    char * PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *)
42
 
    char * PyString_AS_STRING(object)
43
 
    Py_ssize_t PyString_GET_SIZE(object)
44
41
    int PyString_AsStringAndSize_ptr(PyObject *, char **buf, Py_ssize_t *len)
45
42
    void PyString_InternInPlace(PyObject **)
46
43
    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
49
44
    Py_ssize_t PyTuple_GET_SIZE(object t)
50
45
    PyObject *PyTuple_GET_ITEM_ptr_object "PyTuple_GET_ITEM" (object tpl, int index)
51
 
    void Py_INCREF(object)
52
46
    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)
56
47
 
57
48
cdef extern from "string.h":
58
49
    void *memcpy(void *dest, void *src, size_t n)
59
50
    void *memchr(void *s, int c, size_t n)
60
 
    int memcmp(void *s1, void *s2, size_t n)
61
51
    # GNU extension
62
52
    # void *memrchr(void *s, int c, size_t n)
63
53
    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
78
54
 
79
55
 
80
56
# TODO: Find some way to import this from _dirstate_helpers
92
68
        pos = pos - 1
93
69
    return NULL
94
70
 
95
 
 
96
71
# TODO: Import this from _dirstate_helpers when it is merged
97
72
cdef object safe_string_from_size(char *s, Py_ssize_t size):
98
73
    if size < 0:
116
91
    Py_DECREF_ptr(py_str)
117
92
    return result
118
93
 
119
 
# This sets up the StaticTuple C_API functionality
120
 
import_static_tuple_c()
121
 
 
122
94
 
123
95
cdef class BTreeLeafParser:
124
96
    """Parse the leaf nodes of a BTree index.
158
130
        self._cur_str = NULL
159
131
        self._end_str = NULL
160
132
        self._header_found = 0
161
 
        # keys are tuples
162
133
 
163
134
    cdef extract_key(self, char * last):
164
135
        """Extract a key.
168
139
        """
169
140
        cdef char *temp_ptr
170
141
        cdef int loop_counter
171
 
        cdef StaticTuple key
172
 
 
173
 
        key = StaticTuple_New(self.key_length)
174
 
        for loop_counter from 0 <= loop_counter < self.key_length:
 
142
        # keys are tuples
 
143
        loop_counter = 0
 
144
        key_segments = []
 
145
        while loop_counter < self.key_length:
 
146
            loop_counter = loop_counter + 1
175
147
            # grab a key segment
176
148
            temp_ptr = <char*>memchr(self._start, c'\0', last - self._start)
177
149
            if temp_ptr == NULL:
178
 
                if loop_counter + 1 == self.key_length:
 
150
                if loop_counter == self.key_length:
179
151
                    # capture to last
180
152
                    temp_ptr = last
181
153
                else:
185
157
                                                   last - self._start)))
186
158
                    raise AssertionError(failure_string)
187
159
            # capture the key string
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,
 
160
            # TODO: Consider using PyIntern_FromString, the only caveat is that
 
161
            # it assumes a NULL-terminated string, so we have to check if
 
162
            # temp_ptr[0] == c'\0' or some other char.
 
163
            key_element = safe_interned_string_from_size(self._start,
195
164
                                                         temp_ptr - self._start)
196
165
            # advance our pointer
197
166
            self._start = temp_ptr + 1
198
 
            Py_INCREF(key_element)
199
 
            StaticTuple_SET_ITEM(key, loop_counter, key_element)
200
 
        key = StaticTuple_Intern(key)
201
 
        return key
 
167
            PyList_Append(key_segments, key_element)
 
168
        return tuple(key_segments)
202
169
 
203
170
    cdef int process_line(self) except -1:
204
171
        """Process a line in the bytes."""
207
174
        cdef char *ref_ptr
208
175
        cdef char *next_start
209
176
        cdef int loop_counter
210
 
        cdef Py_ssize_t str_len
211
177
 
212
178
        self._start = self._cur_str
213
179
        # Find the next newline
243
209
            # Invalid line
244
210
            raise AssertionError("Failed to find the value area")
245
211
        else:
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)
 
212
            # capture the value string
 
213
            value = safe_string_from_size(temp_ptr + 1, last - temp_ptr - 1)
260
214
            # shrink the references end point
261
215
            last = temp_ptr
262
 
 
263
216
        if self.ref_list_length:
264
 
            ref_lists = StaticTuple_New(self.ref_list_length)
 
217
            ref_lists = []
265
218
            loop_counter = 0
266
219
            while loop_counter < self.ref_list_length:
267
220
                ref_list = []
293
246
                    if temp_ptr == NULL:
294
247
                        # key runs to the end
295
248
                        temp_ptr = ref_ptr
296
 
 
297
249
                    PyList_Append(ref_list, self.extract_key(temp_ptr))
298
 
                ref_list = StaticTuple_Intern(StaticTuple(*ref_list))
299
 
                Py_INCREF(ref_list)
300
 
                StaticTuple_SET_ITEM(ref_lists, loop_counter - 1, ref_list)
 
250
                PyList_Append(ref_lists, tuple(ref_list))
301
251
                # prepare for the next reference list
302
252
                self._start = next_start
303
 
            node_value = StaticTuple(value, ref_lists)
 
253
            ref_lists = tuple(ref_lists)
 
254
            node_value = (value, ref_lists)
304
255
        else:
305
256
            if last != self._start:
306
257
                # unexpected reference data present
307
258
                raise AssertionError("unexpected reference data present")
308
 
            node_value = StaticTuple(value, StaticTuple())
309
 
        PyList_Append(self.keys, StaticTuple(key, node_value))
 
259
            node_value = (value, ())
 
260
        PyList_Append(self.keys, (key, node_value))
310
261
        return 0
311
262
 
312
263
    def parse(self):
327
278
    return parser.parse()
328
279
 
329
280
 
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_py24(gc_chk_sha1_record *record):
500
 
    """Python2.4 PyString_FromFormat doesn't have %u.
501
 
 
502
 
    It only has %d and %ld. We would really like to even have %llu, which
503
 
    is only in python2.7. So we go back into casting to regular objects.
504
 
    """
505
 
    return "%s %s %s %s" % (record.block_offset, record.block_length,
506
 
                            record.record_start, record.record_end)
507
 
 
508
 
 
509
 
cdef _format_record(gc_chk_sha1_record *record):
510
 
    # This is inefficient to go from a logical state back to a
511
 
    # string, but it makes things work a bit better internally for now.
512
 
    if record.block_offset >= 0xFFFFFFFF:
513
 
        # %llu is what we really want, but unfortunately it was only added
514
 
        # in python 2.7... :(
515
 
        block_offset_str = str(record.block_offset)
516
 
        value = PyString_FromFormat('%s %lu %lu %lu',
517
 
                                PyString_AS_STRING(block_offset_str),
518
 
                                record.block_length,
519
 
                                record.record_start, record.record_end)
520
 
    else:
521
 
        value = PyString_FromFormat('%lu %lu %lu %lu',
522
 
                                    <unsigned long>record.block_offset,
523
 
                                    record.block_length,
524
 
                                    record.record_start, record.record_end)
525
 
    return value
526
 
 
527
 
ctypedef object (*formatproc)(gc_chk_sha1_record *)
528
 
cdef formatproc _record_formatter
529
 
_record_formatter = _format_record
530
 
if sys.version_info[:2] == (2, 4):
531
 
    _record_formatter = _format_record_py24
532
 
 
533
 
 
534
 
cdef class GCCHKSHA1LeafNode:
535
 
    """Track all the entries for a given leaf node."""
536
 
 
537
 
    cdef gc_chk_sha1_record *records
538
 
    cdef public object last_key
539
 
    cdef gc_chk_sha1_record *last_record
540
 
    cdef public int num_records
541
 
    # This is the number of bits to shift to get to the interesting byte. A
542
 
    # value of 24 means that the very first byte changes across all keys.
543
 
    # Anything else means that there is a common prefix of bits that we can
544
 
    # ignore. 0 means that at least the first 3 bytes are identical, though
545
 
    # that is going to be very rare
546
 
    cdef public unsigned char common_shift
547
 
    # This maps an interesting byte to the first record that matches.
548
 
    # Equivalent to bisect.bisect_left(self.records, sha1), though only taking
549
 
    # into account that one byte.
550
 
    cdef unsigned char offsets[257]
551
 
 
552
 
    def __sizeof__(self):
553
 
        # :( Why doesn't Pyrex let me do a simple sizeof(GCCHKSHA1LeafNode)
554
 
        # like Cython? Explicitly enumerating everything here seems to leave my
555
 
        # size off by 2 (286 bytes vs 288 bytes actual). I'm guessing it is an
556
 
        # alignment/padding issue. Oh well- at least we scale properly with
557
 
        # num_records and are very close to correct, which is what I care
558
 
        # about.
559
 
        # If we ever decide to require cython:
560
 
        # return (sizeof(GCCHKSHA1LeafNode)
561
 
        #     + sizeof(gc_chk_sha1_record)*self.num_records)
562
 
        return (sizeof(PyObject) + sizeof(void*) + sizeof(int)
563
 
            + sizeof(gc_chk_sha1_record*) + sizeof(PyObject *)
564
 
            + sizeof(gc_chk_sha1_record*) + sizeof(char)
565
 
            + sizeof(unsigned char)*257
566
 
            + sizeof(gc_chk_sha1_record)*self.num_records)
567
 
 
568
 
    def __dealloc__(self):
569
 
        if self.records != NULL:
570
 
            PyMem_Free(self.records)
571
 
            self.records = NULL
572
 
 
573
 
    def __init__(self, bytes):
574
 
        self._parse_bytes(bytes)
575
 
        self.last_key = None
576
 
        self.last_record = NULL
577
 
 
578
 
    property min_key:
579
 
        def __get__(self):
580
 
            if self.num_records > 0:
581
 
                return _sha1_to_key(self.records[0].sha1)
582
 
            return None
583
 
 
584
 
    property max_key:
585
 
        def __get__(self):
586
 
            if self.num_records > 0:
587
 
                return _sha1_to_key(self.records[self.num_records-1].sha1)
588
 
            return None
589
 
 
590
 
    cdef StaticTuple _record_to_value_and_refs(self,
591
 
                                               gc_chk_sha1_record *record):
592
 
        """Extract the refs and value part of this record."""
593
 
        cdef StaticTuple value_and_refs
594
 
        cdef StaticTuple empty
595
 
        value_and_refs = StaticTuple_New(2)
596
 
        value = _record_formatter(record)
597
 
        Py_INCREF(value)
598
 
        StaticTuple_SET_ITEM(value_and_refs, 0, value)
599
 
        # Always empty refs
600
 
        empty = StaticTuple_New(0)
601
 
        Py_INCREF(empty)
602
 
        StaticTuple_SET_ITEM(value_and_refs, 1, empty)
603
 
        return value_and_refs
604
 
 
605
 
    cdef StaticTuple _record_to_item(self, gc_chk_sha1_record *record):
606
 
        """Turn a given record back into a fully fledged item.
607
 
        """
608
 
        cdef StaticTuple item
609
 
        cdef StaticTuple key
610
 
        cdef StaticTuple value_and_refs
611
 
        cdef object value
612
 
        key = _sha1_to_key(record.sha1)
613
 
        item = StaticTuple_New(2)
614
 
        Py_INCREF(key)
615
 
        StaticTuple_SET_ITEM(item, 0, key)
616
 
        value_and_refs = self._record_to_value_and_refs(record)
617
 
        Py_INCREF(value_and_refs)
618
 
        StaticTuple_SET_ITEM(item, 1, value_and_refs)
619
 
        return item
620
 
 
621
 
    cdef gc_chk_sha1_record* _lookup_record(self, char *sha1) except? NULL:
622
 
        """Find a gc_chk_sha1_record that matches the sha1 supplied."""
623
 
        cdef int lo, hi, mid, the_cmp
624
 
        cdef int offset
625
 
 
626
 
        # TODO: We can speed up misses by comparing this sha1 to the common
627
 
        #       bits, and seeing if the common prefix matches, if not, we don't
628
 
        #       need to search for anything because it cannot match
629
 
        # Use the offset array to find the closest fit for this entry
630
 
        # follow that up with bisecting, since multiple keys can be in one
631
 
        # spot
632
 
        # Bisecting dropped us from 7000 comparisons to 582 (4.8/key), using
633
 
        # the offset array dropped us from 23us to 20us and 156 comparisions
634
 
        # (1.3/key)
635
 
        offset = self._offset_for_sha1(sha1)
636
 
        lo = self.offsets[offset]
637
 
        hi = self.offsets[offset+1]
638
 
        if hi == 255:
639
 
            # if hi == 255 that means we potentially ran off the end of the
640
 
            # list, so push it up to num_records
641
 
            # note that if 'lo' == 255, that is ok, because we can start
642
 
            # searching from that part of the list.
643
 
            hi = self.num_records
644
 
        local_n_cmp = 0
645
 
        while lo < hi:
646
 
            mid = (lo + hi) / 2
647
 
            the_cmp = memcmp(self.records[mid].sha1, sha1, 20)
648
 
            if the_cmp == 0:
649
 
                return &self.records[mid]
650
 
            elif the_cmp < 0:
651
 
                lo = mid + 1
652
 
            else:
653
 
                hi = mid
654
 
        return NULL
655
 
 
656
 
    def __contains__(self, key):
657
 
        cdef char sha1[20]
658
 
        cdef gc_chk_sha1_record *record
659
 
        if _key_to_sha1(key, sha1):
660
 
            # If it isn't a sha1 key, then it won't be in this leaf node
661
 
            record = self._lookup_record(sha1)
662
 
            if record != NULL:
663
 
                self.last_key = key
664
 
                self.last_record = record
665
 
                return True
666
 
        return False
667
 
 
668
 
    def __getitem__(self, key):
669
 
        cdef char sha1[20]
670
 
        cdef gc_chk_sha1_record *record
671
 
        record = NULL
672
 
        if self.last_record != NULL and key is self.last_key:
673
 
            record = self.last_record
674
 
        elif _key_to_sha1(key, sha1):
675
 
            record = self._lookup_record(sha1)
676
 
        if record == NULL:
677
 
            raise KeyError('key %r is not present' % (key,))
678
 
        return self._record_to_value_and_refs(record)
679
 
 
680
 
    def __len__(self):
681
 
        return self.num_records
682
 
 
683
 
    def all_keys(self):
684
 
        cdef int i
685
 
        result = []
686
 
        for i from 0 <= i < self.num_records:
687
 
            PyList_Append(result, _sha1_to_key(self.records[i].sha1))
688
 
        return result
689
 
 
690
 
    def all_items(self):
691
 
        cdef int i
692
 
        result = []
693
 
        for i from 0 <= i < self.num_records:
694
 
            item = self._record_to_item(&self.records[i])
695
 
            PyList_Append(result, item)
696
 
        return result
697
 
 
698
 
    cdef int _count_records(self, char *c_content, char *c_end): # cannot_raise
699
 
        """Count how many records are in this section."""
700
 
        cdef char *c_cur
701
 
        cdef int num_records
702
 
 
703
 
        c_cur = c_content
704
 
        num_records = 0
705
 
        while c_cur != NULL and c_cur < c_end:
706
 
            c_cur = <char *>memchr(c_cur, c'\n', c_end - c_cur);
707
 
            if c_cur == NULL:
708
 
                break
709
 
            c_cur = c_cur + 1
710
 
            num_records = num_records + 1
711
 
        return num_records
712
 
 
713
 
    cdef _parse_bytes(self, bytes):
714
 
        """Parse the string 'bytes' into content."""
715
 
        cdef char *c_bytes
716
 
        cdef char *c_cur
717
 
        cdef char *c_end
718
 
        cdef Py_ssize_t n_bytes
719
 
        cdef int num_records
720
 
        cdef int entry
721
 
        cdef gc_chk_sha1_record *cur_record
722
 
 
723
 
        if not PyString_CheckExact(bytes):
724
 
            raise TypeError('We only support parsing plain 8-bit strings.')
725
 
        # Pass 1, count how many records there will be
726
 
        n_bytes = PyString_GET_SIZE(bytes)
727
 
        c_bytes = PyString_AS_STRING(bytes)
728
 
        c_end = c_bytes + n_bytes
729
 
        if strncmp(c_bytes, 'type=leaf\n', 10):
730
 
            raise ValueError("bytes did not start with 'type=leaf\\n': %r"
731
 
                             % (bytes[:10],))
732
 
        c_cur = c_bytes + 10
733
 
        num_records = self._count_records(c_cur, c_end)
734
 
        # Now allocate the memory for these items, and go to town
735
 
        self.records = <gc_chk_sha1_record*>PyMem_Malloc(num_records *
736
 
            (sizeof(unsigned short) + sizeof(gc_chk_sha1_record)))
737
 
        self.num_records = num_records
738
 
        cur_record = self.records
739
 
        entry = 0
740
 
        while c_cur != NULL and c_cur < c_end and entry < num_records:
741
 
            c_cur = self._parse_one_entry(c_cur, c_end, cur_record)
742
 
            cur_record = cur_record + 1
743
 
            entry = entry + 1
744
 
        if (entry != self.num_records
745
 
            or c_cur != c_end
746
 
            or cur_record != self.records + self.num_records):
747
 
            raise ValueError('Something went wrong while parsing.')
748
 
        # Pass 3: build the offset map
749
 
        self._compute_common()
750
 
 
751
 
    cdef char *_parse_one_entry(self, char *c_cur, char *c_end,
752
 
                                gc_chk_sha1_record *cur_record) except NULL:
753
 
        """Read a single sha record from the bytes.
754
 
        :param c_cur: The pointer to the start of bytes
755
 
        :param cur_record: 
756
 
        """
757
 
        cdef char *c_next
758
 
        if strncmp(c_cur, 'sha1:', 5):
759
 
            raise ValueError('line did not start with sha1: %r'
760
 
                % (safe_string_from_size(c_cur, 10),))
761
 
        c_cur = c_cur + 5
762
 
        c_next = <char *>memchr(c_cur, c'\0', c_end - c_cur)
763
 
        if c_next == NULL or (c_next - c_cur != 40):
764
 
            raise ValueError('Line did not contain 40 hex bytes')
765
 
        if not _unhexlify_sha1(c_cur, cur_record.sha1):
766
 
            raise ValueError('We failed to unhexlify')
767
 
        c_cur = c_next + 1
768
 
        if c_cur[0] != c'\0':
769
 
            raise ValueError('only 1 null, not 2 as expected')
770
 
        c_cur = c_cur + 1
771
 
        cur_record.block_offset = strtoll(c_cur, &c_next, 10)
772
 
        if c_cur == c_next or c_next[0] != c' ':
773
 
            raise ValueError('Failed to parse block offset')
774
 
        c_cur = c_next + 1
775
 
        cur_record.block_length = strtoul(c_cur, &c_next, 10)
776
 
        if c_cur == c_next or c_next[0] != c' ':
777
 
            raise ValueError('Failed to parse block length')
778
 
        c_cur = c_next + 1
779
 
        cur_record.record_start = strtoul(c_cur, &c_next, 10)
780
 
        if c_cur == c_next or c_next[0] != c' ':
781
 
            raise ValueError('Failed to parse block length')
782
 
        c_cur = c_next + 1
783
 
        cur_record.record_end = strtoul(c_cur, &c_next, 10)
784
 
        if c_cur == c_next or c_next[0] != c'\n':
785
 
            raise ValueError('Failed to parse record end')
786
 
        c_cur = c_next + 1
787
 
        return c_cur
788
 
 
789
 
    cdef int _offset_for_sha1(self, char *sha1) except -1:
790
 
        """Find the first interesting 8-bits of this sha1."""
791
 
        cdef int this_offset
792
 
        cdef unsigned int as_uint
793
 
        as_uint = _sha1_to_uint(sha1)
794
 
        this_offset = (as_uint >> self.common_shift) & 0xFF
795
 
        return this_offset
796
 
 
797
 
    def _get_offset_for_sha1(self, sha1):
798
 
        return self._offset_for_sha1(PyString_AS_STRING(sha1))
799
 
 
800
 
    cdef _compute_common(self):
801
 
        cdef unsigned int first
802
 
        cdef unsigned int this
803
 
        cdef unsigned int common_mask
804
 
        cdef unsigned char common_shift
805
 
        cdef int i
806
 
        cdef int offset, this_offset
807
 
        cdef int max_offset
808
 
        # The idea with the offset map is that we should be able to quickly
809
 
        # jump to the key that matches a gives sha1. We know that the keys are
810
 
        # in sorted order, and we know that a lot of the prefix is going to be
811
 
        # the same across them.
812
 
        # By XORing the records together, we can determine what bits are set in
813
 
        # all of them
814
 
        if self.num_records < 2:
815
 
            # Everything is in common if you have 0 or 1 leaves
816
 
            # So we'll always just shift to the first byte
817
 
            self.common_shift = 24
818
 
        else:
819
 
            common_mask = 0xFFFFFFFF
820
 
            first = _sha1_to_uint(self.records[0].sha1)
821
 
            for i from 0 < i < self.num_records:
822
 
                this = _sha1_to_uint(self.records[i].sha1)
823
 
                common_mask = (~(first ^ this)) & common_mask
824
 
            common_shift = 24
825
 
            while common_mask & 0x80000000 and common_shift > 0:
826
 
                common_mask = common_mask << 1
827
 
                common_shift = common_shift - 1
828
 
            self.common_shift = common_shift
829
 
        offset = 0
830
 
        max_offset = self.num_records
831
 
        # We cap this loop at 254 records. All the other offsets just get
832
 
        # filled with 0xff as the singleton saying 'too many'.
833
 
        # It means that if we have >255 records we have to bisect the second
834
 
        # half of the list, but this is going to be very rare in practice.
835
 
        if max_offset > 255:
836
 
            max_offset = 255
837
 
        for i from 0 <= i < max_offset:
838
 
            this_offset = self._offset_for_sha1(self.records[i].sha1)
839
 
            while offset <= this_offset:
840
 
                self.offsets[offset] = i
841
 
                offset = offset + 1
842
 
        while offset < 257:
843
 
            self.offsets[offset] = max_offset
844
 
            offset = offset + 1
845
 
 
846
 
    def _get_offsets(self):
847
 
        cdef int i
848
 
        result = []
849
 
        for i from 0 <= i < 257:
850
 
            PyList_Append(result, self.offsets[i])
851
 
        return result
852
 
 
853
 
 
854
 
def _parse_into_chk(bytes, key_length, ref_list_length):
855
 
    """Parse into a format optimized for chk records."""
856
 
    assert key_length == 1
857
 
    assert ref_list_length == 0
858
 
    return GCCHKSHA1LeafNode(bytes)
859
 
 
860
 
 
861
281
def _flatten_node(node, reference_lists):
862
282
    """Convert a node into the serialized form.
863
283
 
872
292
    cdef Py_ssize_t flat_len
873
293
    cdef Py_ssize_t key_len
874
294
    cdef Py_ssize_t node_len
 
295
    cdef PyObject * val
875
296
    cdef char * value
876
297
    cdef Py_ssize_t value_len
877
298
    cdef char * out
880
301
    cdef int first_ref_list
881
302
    cdef int first_reference
882
303
    cdef int i
 
304
    cdef PyObject *ref_bit
883
305
    cdef Py_ssize_t ref_bit_len
884
306
 
885
 
    if not PyTuple_CheckExact(node) and not StaticTuple_CheckExact(node):
886
 
        raise TypeError('We expected a tuple() or StaticTuple() for node not: %s'
 
307
    if not PyTuple_CheckExact(node):
 
308
        raise TypeError('We expected a tuple() for node not: %s'
887
309
            % type(node))
888
 
    node_len = len(node)
 
310
    node_len = PyTuple_GET_SIZE(node)
889
311
    have_reference_lists = reference_lists
890
312
    if have_reference_lists:
891
313
        if node_len != 4:
894
316
    elif node_len < 3:
895
317
        raise ValueError('Without ref_lists, we need at least 3 entries not: %s'
896
318
            % len(node))
897
 
    # TODO: We can probably do better than string.join(), namely
898
 
    #       when key has only 1 item, we can just grab that string
899
 
    #       And when there are 2 items, we could do a single malloc + len() + 1
900
 
    #       also, doing .join() requires a PyObject_GetAttrString call, which
901
 
    #       we could also avoid.
902
 
    # TODO: Note that pyrex 0.9.6 generates fairly crummy code here, using the
903
 
    #       python object interface, versus 0.9.8+ which uses a helper that
904
 
    #       checks if this supports the sequence interface.
905
 
    #       We *could* do more work on our own, and grab the actual items
906
 
    #       lists. For now, just ask people to use a better compiler. :)
907
 
    string_key = '\0'.join(node[1])
 
319
    # I don't expect that we can do faster than string.join()
 
320
    string_key = '\0'.join(<object>PyTuple_GET_ITEM_ptr_object(node, 1))
908
321
 
909
322
    # TODO: instead of using string joins, precompute the final string length,
910
323
    #       and then malloc a single string and copy everything in.
921
334
    refs_len = 0
922
335
    if have_reference_lists:
923
336
        # Figure out how many bytes it will take to store the references
924
 
        ref_lists = node[3]
 
337
        ref_lists = <object>PyTuple_GET_ITEM_ptr_object(node, 3)
925
338
        next_len = len(ref_lists) # TODO: use a Py function
926
339
        if next_len > 0:
927
340
            # If there are no nodes, we don't need to do any work
935
348
                    # references
936
349
                    refs_len = refs_len + (next_len - 1)
937
350
                    for reference in ref_list:
938
 
                        if (not PyTuple_CheckExact(reference)
939
 
                            and not StaticTuple_CheckExact(reference)):
 
351
                        if not PyTuple_CheckExact(reference):
940
352
                            raise TypeError(
941
353
                                'We expect references to be tuples not: %s'
942
354
                                % type(reference))
943
 
                        next_len = len(reference)
 
355
                        next_len = PyTuple_GET_SIZE(reference)
944
356
                        if next_len > 0:
945
357
                            # We will need (len - 1) '\x00' characters to
946
358
                            # separate the reference key
947
359
                            refs_len = refs_len + (next_len - 1)
948
 
                            for ref_bit in reference:
949
 
                                if not PyString_CheckExact(ref_bit):
 
360
                            for i from 0 <= i < next_len:
 
361
                                ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
 
362
                                if not PyString_CheckExact_ptr(ref_bit):
950
363
                                    raise TypeError('We expect reference bits'
951
364
                                        ' to be strings not: %s'
952
365
                                        % type(<object>ref_bit))
953
 
                                refs_len = refs_len + PyString_GET_SIZE(ref_bit)
 
366
                                refs_len = refs_len + PyString_GET_SIZE_ptr(ref_bit)
954
367
 
955
368
    # So we have the (key NULL refs NULL value LF)
956
369
    key_len = PyString_Size(string_key)
957
 
    val = node[2]
958
 
    if not PyString_CheckExact(val):
 
370
    val = PyTuple_GET_ITEM_ptr_object(node, 2)
 
371
    if not PyString_CheckExact_ptr(val):
959
372
        raise TypeError('Expected a plain str for value not: %s'
960
 
                        % type(val))
961
 
    value = PyString_AS_STRING(val)
962
 
    value_len = PyString_GET_SIZE(val)
 
373
                        % type(<object>val))
 
374
    value = PyString_AS_STRING_ptr(val)
 
375
    value_len = PyString_GET_SIZE_ptr(val)
963
376
    flat_len = (key_len + 1 + refs_len + 1 + value_len + 1)
964
377
    line = PyString_FromStringAndSize(NULL, flat_len)
965
378
    # Get a pointer to the new buffer
981
394
                    out[0] = c'\r'
982
395
                    out = out + 1
983
396
                first_reference = 0
984
 
                next_len = len(reference)
 
397
                next_len = PyTuple_GET_SIZE(reference)
985
398
                for i from 0 <= i < next_len:
986
399
                    if i != 0:
987
400
                        out[0] = c'\x00'
988
401
                        out = out + 1
989
 
                    ref_bit = reference[i]
990
 
                    ref_bit_len = PyString_GET_SIZE(ref_bit)
991
 
                    memcpy(out, PyString_AS_STRING(ref_bit), ref_bit_len)
 
402
                    ref_bit = PyTuple_GET_ITEM_ptr_object(reference, i)
 
403
                    ref_bit_len = PyString_GET_SIZE_ptr(ref_bit)
 
404
                    memcpy(out, PyString_AS_STRING_ptr(ref_bit), ref_bit_len)
992
405
                    out = out + ref_bit_len
993
406
    out[0] = c'\0'
994
407
    out = out  + 1