← Back to branch summary

~bzr/ubuntu/lucid/bzr/beta-ppa

« back to all changes in this revision

Viewing changes to bzrlib/_chk_map_pyx.pyx

  • Committer: Martin Pool
  • Date: 2010-07-02 07:29:40 UTC
  • mfrom: (129.1.7 packaging-karmic)
  • Revision ID: mbp@sourcefrog.net-20100702072940-hpzq5elg8wjve8rh
http://bugs.debian.org/452024
http://bugs.debian.org/464688
http://bugs.debian.org/523595
http://bugs.debian.org/526233
http://bugs.debian.org/537708
http://bugs.debian.org/555336
http://bugs.debian.org/555343
https://launchpad.net/bugs/249452
https://launchpad.net/bugs/385074
* PPA rebuild.
* PPA rebuild for Karmic.
* PPA rebuild for Jaunty.
* PPA rebuild for Hardy.
* From postinst, actually remove the example bash completion scripts.
  (LP: #249452)
* New upstream release.
* New upstream release.
* New upstream release.
* Revert change to Build-depends: Dapper does not have python-central.
  Should be python-support..
* Target ppa..
* Target ppa..
* Target ppa..
* Target ppa..
* New upstream release.
* Switch to dpkg-source 3.0 (quilt) format.
* Bump standards version to 3.8.4.
* Remove embedded copy of python-configobj. Closes: #555336
* Remove embedded copy of python-elementtree. Closes: #555343
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* Change section from 'Devel' to 'Vcs'..
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* debian/control: Fix obsolete-relation-form-in-source
  lintian warning. 
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split out docs into bzr-doc package.
* New upstream release.
* Added John Francesco Ferlito to Uploaders.
* Fix install path to quick-reference guide
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to doc paths changing
* New upstream release.
* Fix FTBFS due to path changes, again, again.
* Fix FTBFS due to path changes, again.
* Fix FTBFS due to path changes.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Bump standards version to 3.8.3.
* Remove unused patch system.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix copy and paste tab error in .install file
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
 + Fixes compatibility with Python 2.4. Closes: #537708
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream version.
* Bump standards version to 3.8.2.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add python-pyrex to build-deps to ensure C extensions are always build.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* Split documentation into bzr-doc package. ((LP: #385074)
* Multiple packaging changes to make us more linitan clean.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Fix API compatibility version. (Closes: #526233)
* New upstream release.
  + Fixes default format for upgrade command. (Closes: #464688)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add missing dependency on zlib development library. (Closes:
  #523595)
* Add zlib build-depends.
* Add zlib build-depends.
* Add zlib build-depends.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Move to section vcs.
* Bump standards version to 3.8.1.
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* New upstream release.
* Remove temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* Add temporary patch for missing .c files from distribution
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Recommend ca-certificates. (Closes: #452024)
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Update watch file. bazaar now uses launchpad to host its sources.
* Remove patch for inventory root revision copy, applied upstream.
* New upstream release.
* New upstream release.
* New upstream release
* Force removal of files installed in error to /etc/bash_completion.d/
  (LP: #249452)
* New upstream release.
* New upstream release
* New upstream release.
* Bump standards version.
* Include patch for inventory root revision copy, required for bzr-svn.
* New upstream release.
* Remove unused lintian overrides.
* Correct the package version not to be native.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* New upstream release.
* Final 1.5 release.
* New upstream release.
* New upstream release.
* New upstream release.
* Add myself as a co-maintainer.
* Add a Dm-Upload-Allowed: yes header.
* New upstream bugfix release.
* New upstream release.
* Final 1.3 release.
* New upstream release.
* First release candidate of the upcoming 1.3 release.
* Rebuild to fix the problem caused by a build with a broken python-central.
* New upstream release.
* Rebuild for dapper PPA.
* Apply Lamont's patches to fix build-dependencies on dapper.
  (See: https://bugs.launchpad.net/bzr/+bug/189915)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_chk_map_pyx.pyx
 
1
# Copyright (C) 2009, 2010 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
 
 
18
#python2.4 support
 
19
cdef extern from "python-compat.h":
 
20
    pass
 
21
 
 
22
cdef extern from *:
 
23
    ctypedef unsigned int size_t
 
24
    int memcmp(void *, void*, size_t)
 
25
    void memcpy(void *, void*, size_t)
 
26
    void *memchr(void *s, int c, size_t len)
 
27
    long strtol(char *, char **, int)
 
28
    void sprintf(char *, char *, ...)
 
29
 
 
30
cdef extern from "Python.h":
 
31
    ctypedef int Py_ssize_t # Required for older pyrex versions
 
32
    ctypedef struct PyObject:
 
33
        pass
 
34
    int PyTuple_CheckExact(object p)
 
35
    Py_ssize_t PyTuple_GET_SIZE(object t)
 
36
    int PyString_CheckExact(object)
 
37
    char *PyString_AS_STRING(object s)
 
38
    Py_ssize_t PyString_GET_SIZE(object)
 
39
 
 
40
    int PyDict_SetItem(object d, object k, object v) except -1
 
41
 
 
42
    object PyTuple_New(Py_ssize_t count)
 
43
    void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)
 
44
 
 
45
    void Py_INCREF(object)
 
46
 
 
47
    PyObject * PyTuple_GET_ITEM_ptr "PyTuple_GET_ITEM" (object t,
 
48
                                                        Py_ssize_t offset)
 
49
    int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *p)
 
50
    Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *s)
 
51
    char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
 
52
    object PyString_FromStringAndSize(char*, Py_ssize_t)
 
53
 
 
54
# cimport all of the definitions we will need to access
 
55
from _static_tuple_c cimport StaticTuple,\
 
56
    import_static_tuple_c, StaticTuple_New, \
 
57
    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
 
58
 
 
59
cdef extern from "_static_tuple_c.h":
 
60
    # Defined explicitly rather than cimport-ing. Trying to use cimport, the
 
61
    # type for PyObject is a different class that happens to have the same
 
62
    # name...
 
63
    PyObject * StaticTuple_GET_ITEM_ptr "StaticTuple_GET_ITEM" (StaticTuple,
 
64
                                                                Py_ssize_t)
 
65
 
 
66
cdef extern from "zlib.h":
 
67
    ctypedef unsigned long uLong
 
68
    ctypedef unsigned int uInt
 
69
    ctypedef unsigned char Bytef
 
70
 
 
71
    uLong crc32(uLong crc, Bytef *buf, uInt len)
 
72
 
 
73
 
 
74
# Set up the StaticTuple C_API functionality
 
75
import_static_tuple_c()
 
76
 
 
77
cdef object _LeafNode
 
78
_LeafNode = None
 
79
cdef object _InternalNode
 
80
_InternalNode = None
 
81
cdef object _unknown
 
82
_unknown = None
 
83
 
 
84
# We shouldn't just copy this from _dirstate_helpers_pyx
 
85
cdef void* _my_memrchr(void *s, int c, size_t n): # cannot_raise
 
86
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
 
87
    cdef char *pos
 
88
    cdef char *start
 
89
 
 
90
    start = <char*>s
 
91
    pos = start + n - 1
 
92
    while pos >= start:
 
93
        if pos[0] == c:
 
94
            return <void*>pos
 
95
        pos = pos - 1
 
96
    return NULL
 
97
 
 
98
 
 
99
def _search_key_16(key):
 
100
    """See chk_map._search_key_16."""
 
101
    cdef Py_ssize_t num_bits
 
102
    cdef Py_ssize_t i, j
 
103
    cdef Py_ssize_t num_out_bytes
 
104
    cdef Bytef *c_bit
 
105
    cdef uLong c_len
 
106
    cdef uInt crc_val
 
107
    cdef Py_ssize_t out_off
 
108
    cdef char *c_out
 
109
    cdef PyObject *bit
 
110
 
 
111
    if not StaticTuple_CheckExact(key):
 
112
        raise TypeError('key %r is not a StaticTuple' % (key,))
 
113
    num_bits = len(key)
 
114
    # 4 bytes per crc32, and another 1 byte between bits
 
115
    num_out_bytes = (9 * num_bits) - 1
 
116
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
 
117
    c_out = PyString_AS_STRING(out)
 
118
    for i from 0 <= i < num_bits:
 
119
        if i > 0:
 
120
            c_out[0] = c'\x00'
 
121
            c_out = c_out + 1
 
122
        # We use the _ptr variant, because GET_ITEM returns a borrowed
 
123
        # reference, and Pyrex assumes that returned 'object' are a new
 
124
        # reference
 
125
        bit = StaticTuple_GET_ITEM_ptr(key, i)
 
126
        if not PyString_CheckExact_ptr(bit):
 
127
            raise TypeError('Bit %d of %r is not a string' % (i, key))
 
128
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
 
129
        c_len = PyString_GET_SIZE_ptr(bit)
 
130
        crc_val = crc32(0, c_bit, c_len)
 
131
        # Hex(val) order
 
132
        sprintf(c_out, '%08X', crc_val)
 
133
        c_out = c_out + 8
 
134
    return out
 
135
 
 
136
 
 
137
def _search_key_255(key):
 
138
    """See chk_map._search_key_255."""
 
139
    cdef Py_ssize_t num_bits
 
140
    cdef Py_ssize_t i, j
 
141
    cdef Py_ssize_t num_out_bytes
 
142
    cdef Bytef *c_bit
 
143
    cdef uLong c_len
 
144
    cdef uInt crc_val
 
145
    cdef Py_ssize_t out_off
 
146
    cdef char *c_out
 
147
    cdef PyObject *bit
 
148
 
 
149
    if not StaticTuple_CheckExact(key):
 
150
        raise TypeError('key %r is not a StaticTuple' % (key,))
 
151
    num_bits = len(key)
 
152
    # 4 bytes per crc32, and another 1 byte between bits
 
153
    num_out_bytes = (5 * num_bits) - 1
 
154
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
 
155
    c_out = PyString_AS_STRING(out)
 
156
    for i from 0 <= i < num_bits:
 
157
        if i > 0:
 
158
            c_out[0] = c'\x00'
 
159
            c_out = c_out + 1
 
160
        bit = StaticTuple_GET_ITEM_ptr(key, i)
 
161
        if not PyString_CheckExact_ptr(bit):
 
162
            raise TypeError('Bit %d of %r is not a string: %r'
 
163
                            % (i, key, <object>bit))
 
164
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
 
165
        c_len = PyString_GET_SIZE_ptr(bit)
 
166
        crc_val = crc32(0, c_bit, c_len)
 
167
        # MSB order
 
168
        c_out[0] = (crc_val >> 24) & 0xFF
 
169
        c_out[1] = (crc_val >> 16) & 0xFF
 
170
        c_out[2] = (crc_val >> 8) & 0xFF
 
171
        c_out[3] = (crc_val >> 0) & 0xFF
 
172
        for j from 0 <= j < 4:
 
173
            if c_out[j] == c'\n':
 
174
                c_out[j] = c'_'
 
175
        c_out = c_out + 4
 
176
    return out
 
177
 
 
178
 
 
179
cdef int _get_int_from_line(char **cur, char *end, char *message) except -1:
 
180
    """Read a positive integer from the data stream.
 
181
 
 
182
    :param cur: The start of the data, this will be moved to after the
 
183
        trailing newline when done.
 
184
    :param end: Do not parse any data past this byte.
 
185
    :return: The integer stored in those bytes
 
186
    """
 
187
    cdef int value
 
188
    cdef char *next_line, *next
 
189
 
 
190
    next_line = <char *>memchr(cur[0], c'\n', end - cur[0])
 
191
    if next_line == NULL:
 
192
        raise ValueError("Missing %s line\n" % message)
 
193
 
 
194
    value = strtol(cur[0], &next, 10)
 
195
    if next != next_line:
 
196
        raise ValueError("%s line not a proper int\n" % message)
 
197
    cur[0] = next_line + 1
 
198
    return value
 
199
 
 
200
 
 
201
def _deserialise_leaf_node(bytes, key, search_key_func=None):
 
202
    """Deserialise bytes, with key key, into a LeafNode.
 
203
 
 
204
    :param bytes: The bytes of the node.
 
205
    :param key: The key that the serialised node has.
 
206
    """
 
207
    cdef char *c_bytes, *cur, *next, *end
 
208
    cdef char *next_line
 
209
    cdef Py_ssize_t c_bytes_len, prefix_length, items_length
 
210
    cdef int maximum_size, width, length, i, prefix_tail_len
 
211
    cdef int num_value_lines, num_prefix_bits
 
212
    cdef char *prefix, *value_start, *prefix_tail
 
213
    cdef char *next_null, *last_null, *line_start
 
214
    cdef char *c_entry, *entry_start
 
215
    cdef StaticTuple entry_bits
 
216
 
 
217
    if _LeafNode is None:
 
218
        from bzrlib import chk_map
 
219
        _LeafNode = chk_map.LeafNode
 
220
        _InternalNode = chk_map.InternalNode
 
221
        _unknown = chk_map._unknown
 
222
 
 
223
    result = _LeafNode(search_key_func=search_key_func)
 
224
    # Splitlines can split on '\r' so don't use it, split('\n') adds an
 
225
    # extra '' if the bytes ends in a final newline.
 
226
    if not PyString_CheckExact(bytes):
 
227
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
 
228
 
 
229
    c_bytes = PyString_AS_STRING(bytes)
 
230
    c_bytes_len = PyString_GET_SIZE(bytes)
 
231
 
 
232
    if c_bytes_len < 9 or memcmp(c_bytes, "chkleaf:\n", 9) != 0:
 
233
        raise ValueError("not a serialised leaf node: %r" % bytes)
 
234
    if c_bytes[c_bytes_len - 1] != c'\n':
 
235
        raise ValueError("bytes does not end in a newline")
 
236
 
 
237
    end = c_bytes + c_bytes_len
 
238
    cur = c_bytes + 9
 
239
    maximum_size = _get_int_from_line(&cur, end, "maximum_size")
 
240
    width = _get_int_from_line(&cur, end, "width")
 
241
    length = _get_int_from_line(&cur, end, "length")
 
242
 
 
243
    next_line = <char *>memchr(cur, c'\n', end - cur)
 
244
    if next_line == NULL:
 
245
        raise ValueError('Missing the prefix line\n')
 
246
    prefix = cur
 
247
    prefix_length = next_line - cur
 
248
    cur = next_line + 1
 
249
 
 
250
    prefix_bits = []
 
251
    prefix_tail = prefix
 
252
    num_prefix_bits = 0
 
253
    next_null = <char *>memchr(prefix, c'\0', prefix_length)
 
254
    while next_null != NULL:
 
255
        num_prefix_bits = num_prefix_bits + 1
 
256
        prefix_bits.append(
 
257
            PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
 
258
        prefix_tail = next_null + 1
 
259
        next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
 
260
    prefix_tail_len = next_line - prefix_tail
 
261
 
 
262
    if num_prefix_bits >= width:
 
263
        raise ValueError('Prefix has too many nulls versus width')
 
264
 
 
265
    items_length = end - cur
 
266
    items = {}
 
267
    while cur < end:
 
268
        line_start = cur
 
269
        next_line = <char *>memchr(cur, c'\n', end - cur)
 
270
        if next_line == NULL:
 
271
            raise ValueError('null line\n')
 
272
        last_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
 
273
        if last_null == NULL:
 
274
            raise ValueError('fail to find the num value lines null')
 
275
        next_null = last_null + 1 # move past NULL
 
276
        num_value_lines = _get_int_from_line(&next_null, next_line + 1,
 
277
                                             "num value lines")
 
278
        cur = next_line + 1
 
279
        value_start = cur
 
280
        # Walk num_value_lines forward
 
281
        for i from 0 <= i < num_value_lines:
 
282
            next_line = <char *>memchr(cur, c'\n', end - cur)
 
283
            if next_line == NULL:
 
284
                raise ValueError('missing trailing newline')
 
285
            cur = next_line + 1
 
286
        entry_bits = StaticTuple_New(width)
 
287
        for i from 0 <= i < num_prefix_bits:
 
288
            # TODO: Use PyList_GetItem, or turn prefix_bits into a
 
289
            #       tuple/StaticTuple
 
290
            entry = prefix_bits[i]
 
291
            # SET_ITEM 'steals' a reference
 
292
            Py_INCREF(entry)
 
293
            StaticTuple_SET_ITEM(entry_bits, i, entry)
 
294
        value = PyString_FromStringAndSize(value_start, next_line - value_start)
 
295
        # The next entry bit needs the 'tail' from the prefix, and first part
 
296
        # of the line
 
297
        entry_start = line_start
 
298
        next_null = <char *>memchr(entry_start, c'\0',
 
299
                                   last_null - entry_start + 1)
 
300
        if next_null == NULL:
 
301
            raise ValueError('bad no null, bad')
 
302
        entry = PyString_FromStringAndSize(NULL,
 
303
                    prefix_tail_len + next_null - line_start)
 
304
        c_entry = PyString_AS_STRING(entry)
 
305
        if prefix_tail_len > 0:
 
306
            memcpy(c_entry, prefix_tail, prefix_tail_len)
 
307
        if next_null - line_start > 0:
 
308
            memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
 
309
        Py_INCREF(entry)
 
310
        i = num_prefix_bits
 
311
        StaticTuple_SET_ITEM(entry_bits, i, entry)
 
312
        while next_null != last_null: # We have remaining bits
 
313
            i = i + 1
 
314
            if i > width:
 
315
                raise ValueError("Too many bits for entry")
 
316
            entry_start = next_null + 1
 
317
            next_null = <char *>memchr(entry_start, c'\0',
 
318
                                       last_null - entry_start + 1)
 
319
            if next_null == NULL:
 
320
                raise ValueError('bad no null')
 
321
            entry = PyString_FromStringAndSize(entry_start,
 
322
                                               next_null - entry_start)
 
323
            Py_INCREF(entry)
 
324
            StaticTuple_SET_ITEM(entry_bits, i, entry)
 
325
        if len(entry_bits) != width:
 
326
            raise AssertionError(
 
327
                'Incorrect number of elements (%d vs %d)'
 
328
                % (len(entry_bits)+1, width + 1))
 
329
        entry_bits = StaticTuple_Intern(entry_bits)
 
330
        PyDict_SetItem(items, entry_bits, value)
 
331
    if len(items) != length:
 
332
        raise ValueError("item count (%d) mismatch for key %s,"
 
333
                         " bytes %r" % (length, entry_bits, bytes))
 
334
    result._items = items
 
335
    result._len = length
 
336
    result._maximum_size = maximum_size
 
337
    result._key = key
 
338
    result._key_width = width
 
339
    result._raw_size = items_length + length * prefix_length
 
340
    if length == 0:
 
341
        result._search_prefix = None
 
342
        result._common_serialised_prefix = None
 
343
    else:
 
344
        result._search_prefix = _unknown
 
345
        result._common_serialised_prefix = PyString_FromStringAndSize(prefix,
 
346
                                                prefix_length)
 
347
    if c_bytes_len != result._current_size():
 
348
        raise AssertionError('_current_size computed incorrectly %d != %d',
 
349
            c_bytes_len, result._current_size())
 
350
    return result
 
351
 
 
352
 
 
353
def _deserialise_internal_node(bytes, key, search_key_func=None):
 
354
    cdef char *c_bytes, *cur, *next, *end
 
355
    cdef char *next_line
 
356
    cdef Py_ssize_t c_bytes_len, prefix_length
 
357
    cdef int maximum_size, width, length, i, prefix_tail_len
 
358
    cdef char *prefix, *line_prefix, *next_null, *c_item_prefix
 
359
 
 
360
    if _InternalNode is None:
 
361
        from bzrlib import chk_map
 
362
        _LeafNode = chk_map.LeafNode
 
363
        _InternalNode = chk_map.InternalNode
 
364
        _unknown = chk_map._unknown
 
365
    result = _InternalNode(search_key_func=search_key_func)
 
366
 
 
367
    if not StaticTuple_CheckExact(key):
 
368
        raise TypeError('key %r is not a StaticTuple' % (key,))
 
369
    if not PyString_CheckExact(bytes):
 
370
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
 
371
 
 
372
    c_bytes = PyString_AS_STRING(bytes)
 
373
    c_bytes_len = PyString_GET_SIZE(bytes)
 
374
 
 
375
    if c_bytes_len < 9 or memcmp(c_bytes, "chknode:\n", 9) != 0:
 
376
        raise ValueError("not a serialised internal node: %r" % bytes)
 
377
    if c_bytes[c_bytes_len - 1] != c'\n':
 
378
        raise ValueError("bytes does not end in a newline")
 
379
 
 
380
    items = {}
 
381
    cur = c_bytes + 9
 
382
    end = c_bytes + c_bytes_len
 
383
    maximum_size = _get_int_from_line(&cur, end, "maximum_size")
 
384
    width = _get_int_from_line(&cur, end, "width")
 
385
    length = _get_int_from_line(&cur, end, "length")
 
386
 
 
387
    next_line = <char *>memchr(cur, c'\n', end - cur)
 
388
    if next_line == NULL:
 
389
        raise ValueError('Missing the prefix line\n')
 
390
    prefix = cur
 
391
    prefix_length = next_line - cur
 
392
    cur = next_line + 1
 
393
 
 
394
    while cur < end:
 
395
        # Find the null separator
 
396
        next_line = <char *>memchr(cur, c'\n', end - cur)
 
397
        if next_line == NULL:
 
398
            raise ValueError('missing trailing newline')
 
399
        next_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
 
400
        if next_null == NULL:
 
401
            raise ValueError('bad no null')
 
402
        item_prefix = PyString_FromStringAndSize(NULL,
 
403
            prefix_length + next_null - cur)
 
404
        c_item_prefix = PyString_AS_STRING(item_prefix)
 
405
        if prefix_length:
 
406
            memcpy(c_item_prefix, prefix, prefix_length)
 
407
        memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
 
408
        flat_key = PyString_FromStringAndSize(next_null + 1,
 
409
                                              next_line - next_null - 1)
 
410
        flat_key = StaticTuple(flat_key).intern()
 
411
        PyDict_SetItem(items, item_prefix, flat_key)
 
412
        cur = next_line + 1
 
413
    assert len(items) > 0
 
414
    result._items = items
 
415
    result._len = length
 
416
    result._maximum_size = maximum_size
 
417
    result._key = key
 
418
    result._key_width = width
 
419
    # XXX: InternalNodes don't really care about their size, and this will
 
420
    #      change if we add prefix compression
 
421
    result._raw_size = None # len(bytes)
 
422
    result._node_width = len(item_prefix)
 
423
    result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
 
424
    return result