← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_chk_map_py.py

  • Committer: Robert Collins
  • Date: 2010-04-08 04:34:03 UTC
  • mfrom: (5138 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5139.
  • Revision ID: robertc@robertcollins.net-20100408043403-56z0d07vdqrx7f3t
Update bugfix for 528114 to trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_chk_map_py.py
 
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
"""Python implementation of _search_key functions, etc."""
 
18
 
 
19
import zlib
 
20
import struct
 
21
 
 
22
from bzrlib.static_tuple import StaticTuple
 
23
 
 
24
_LeafNode = None
 
25
_InternalNode = None
 
26
_unknown = None
 
27
 
 
28
def _crc32(bit):
 
29
    # Depending on python version and platform, zlib.crc32 will return either a
 
30
    # signed (<= 2.5 >= 3.0) or an unsigned (2.5, 2.6).
 
31
    # http://docs.python.org/library/zlib.html recommends using a mask to force
 
32
    # an unsigned value to ensure the same numeric value (unsigned) is obtained
 
33
    # across all python versions and platforms.
 
34
    # Note: However, on 32-bit platforms this causes an upcast to PyLong, which
 
35
    #       are generally slower than PyInts. However, if performance becomes
 
36
    #       critical, we should probably write the whole thing as an extension
 
37
    #       anyway.
 
38
    #       Though we really don't need that 32nd bit of accuracy. (even 2**24
 
39
    #       is probably enough node fan out for realistic trees.)
 
40
    return zlib.crc32(bit)&0xFFFFFFFF
 
41
 
 
42
 
 
43
def _search_key_16(key):
 
44
    """Map the key tuple into a search key string which has 16-way fan out."""
 
45
    return '\x00'.join(['%08X' % _crc32(bit) for bit in key])
 
46
 
 
47
 
 
48
def _search_key_255(key):
 
49
    """Map the key tuple into a search key string which has 255-way fan out.
 
50
 
 
51
    We use 255-way because '\n' is used as a delimiter, and causes problems
 
52
    while parsing.
 
53
    """
 
54
    bytes = '\x00'.join([struct.pack('>L', _crc32(bit)) for bit in key])
 
55
    return bytes.replace('\n', '_')
 
56
 
 
57
 
 
58
def _deserialise_leaf_node(bytes, key, search_key_func=None):
 
59
    """Deserialise bytes, with key key, into a LeafNode.
 
60
 
 
61
    :param bytes: The bytes of the node.
 
62
    :param key: The key that the serialised node has.
 
63
    """
 
64
    global _unknown, _LeafNode, _InternalNode
 
65
    if _LeafNode is None:
 
66
        from bzrlib import chk_map
 
67
        _unknown = chk_map._unknown
 
68
        _LeafNode = chk_map.LeafNode
 
69
        _InternalNode = chk_map.InternalNode
 
70
    result = _LeafNode(search_key_func=search_key_func)
 
71
    # Splitlines can split on '\r' so don't use it, split('\n') adds an
 
72
    # extra '' if the bytes ends in a final newline.
 
73
    lines = bytes.split('\n')
 
74
    trailing = lines.pop()
 
75
    if trailing != '':
 
76
        raise AssertionError('We did not have a final newline for %s'
 
77
                             % (key,))
 
78
    items = {}
 
79
    if lines[0] != 'chkleaf:':
 
80
        raise ValueError("not a serialised leaf node: %r" % bytes)
 
81
    maximum_size = int(lines[1])
 
82
    width = int(lines[2])
 
83
    length = int(lines[3])
 
84
    prefix = lines[4]
 
85
    pos = 5
 
86
    while pos < len(lines):
 
87
        line = prefix + lines[pos]
 
88
        elements = line.split('\x00')
 
89
        pos += 1
 
90
        if len(elements) != width + 1:
 
91
            raise AssertionError(
 
92
                'Incorrect number of elements (%d vs %d) for: %r'
 
93
                % (len(elements), width + 1, line))
 
94
        num_value_lines = int(elements[-1])
 
95
        value_lines = lines[pos:pos+num_value_lines]
 
96
        pos += num_value_lines
 
97
        value = '\n'.join(value_lines)
 
98
        items[StaticTuple.from_sequence(elements[:-1])] = value
 
99
    if len(items) != length:
 
100
        raise AssertionError("item count (%d) mismatch for key %s,"
 
101
            " bytes %r" % (length, key, bytes))
 
102
    result._items = items
 
103
    result._len = length
 
104
    result._maximum_size = maximum_size
 
105
    result._key = key
 
106
    result._key_width = width
 
107
    result._raw_size = (sum(map(len, lines[5:])) # the length of the suffix
 
108
        + (length)*(len(prefix))
 
109
        + (len(lines)-5))
 
110
    if not items:
 
111
        result._search_prefix = None
 
112
        result._common_serialised_prefix = None
 
113
    else:
 
114
        result._search_prefix = _unknown
 
115
        result._common_serialised_prefix = prefix
 
116
    if len(bytes) != result._current_size():
 
117
        raise AssertionError('_current_size computed incorrectly')
 
118
    return result
 
119
 
 
120
 
 
121
def _deserialise_internal_node(bytes, key, search_key_func=None):
 
122
    global _unknown, _LeafNode, _InternalNode
 
123
    if _InternalNode is None:
 
124
        from bzrlib import chk_map
 
125
        _unknown = chk_map._unknown
 
126
        _LeafNode = chk_map.LeafNode
 
127
        _InternalNode = chk_map.InternalNode
 
128
    result = _InternalNode(search_key_func=search_key_func)
 
129
    # Splitlines can split on '\r' so don't use it, remove the extra ''
 
130
    # from the result of split('\n') because we should have a trailing
 
131
    # newline
 
132
    lines = bytes.split('\n')
 
133
    if lines[-1] != '':
 
134
        raise ValueError("last line must be ''")
 
135
    lines.pop(-1)
 
136
    items = {}
 
137
    if lines[0] != 'chknode:':
 
138
        raise ValueError("not a serialised internal node: %r" % bytes)
 
139
    maximum_size = int(lines[1])
 
140
    width = int(lines[2])
 
141
    length = int(lines[3])
 
142
    common_prefix = lines[4]
 
143
    for line in lines[5:]:
 
144
        line = common_prefix + line
 
145
        prefix, flat_key = line.rsplit('\x00', 1)
 
146
        items[prefix] = StaticTuple(flat_key,)
 
147
    if len(items) == 0:
 
148
        raise AssertionError("We didn't find any item for %s" % key)
 
149
    result._items = items
 
150
    result._len = length
 
151
    result._maximum_size = maximum_size
 
152
    result._key = key
 
153
    result._key_width = width
 
154
    # XXX: InternalNodes don't really care about their size, and this will
 
155
    #      change if we add prefix compression
 
156
    result._raw_size = None # len(bytes)
 
157
    result._node_width = len(prefix)
 
158
    result._search_prefix = common_prefix
 
159
    return result