/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-12-22 16:28:47 UTC
  • mto: This revision was merged to the branch mainline in revision 4922.
  • Revision ID: john@arbash-meinel.com-20091222162847-tvnsc69to4l4uf5r
Implement a permute_for_extension helper.

Use it for all of the 'simple' extension permutations.
It basically permutes all tests in the current module, by setting TestCase.module.
Which works well for most of our extension tests. Some had more advanced
handling of permutations (extra permutations, custom vars, etc.)

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
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