← 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: John Arbash Meinel
  • Author(s): Mark Hammond
  • Date: 2008-09-09 17:02:21 UTC
  • mto: This revision was merged to the branch mainline in revision 3697.
  • Revision ID: john@arbash-meinel.com-20080909170221-svim3jw2mrz0amp3
An updated transparent icon for bzr.

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