/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: Robert Collins
  • Date: 2007-07-15 15:40:37 UTC
  • mto: (2592.3.33 repository)
  • mto: This revision was merged to the branch mainline in revision 2624.
  • Revision ID: robertc@robertcollins.net-20070715154037-3ar8g89decddc9su
Make GraphIndex accept nodes as key, value, references, so that the method
signature is closer to what a simple key->value index delivers. Also
change the behaviour when the reference list count is zero to accept
key, value as nodes, and emit key, value to make it identical in that case
to a simple key->value index. This may not be a good idea, but for now it
seems ok.

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