← 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: Canonical.com Patch Queue Manager
  • Date: 2007-03-28 06:58:22 UTC
  • mfrom: (2379.2.3 hpss-chroot)
  • Revision ID: pqm@pqm.ubuntu.com-20070328065822-999550a858a3ced3
(robertc) Fix chroot urls to not expose the url of the transport they are protecting, allowing regular url operations to work on them. (Robert Collins, Andrew Bennetts)

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