/brz/remove-bazaar

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

« back to all changes in this revision

Viewing changes to bzrlib/_chk_map_py.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-18 18:18:36 UTC
  • mto: This revision was merged to the branch mainline in revision 4461.
  • Revision ID: john@arbash-meinel.com-20090618181836-biodfkat9a8eyzjz
The new add_inventory_by_delta is returning a CHKInventory when mapping from NULL
Which is completely valid, but 'broke' one of the tests.
So to fix it, changed the test to use CHKInventories on both sides, and add an __eq__
member. The nice thing is that CHKInventory.__eq__ is fairly cheap, since it only
has to check the root keys.

Show diffs side-by-side

added added

removed removed

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