« back to all changes in this revision
Viewing changes to bzrlib/_chk_map_py.py
- browse files at revision 4241.6.1
- compare with another revision
- compare with revision 3873.1.2
- download diff
- download tarball
- view history from revision 4241.6.1
- Committer: Ian Clatworthy
- Date: 2009-04-03 02:29:30 UTC
- mto: This revision was merged to the branch mainline in revision 4259.
- Revision ID: ian.clatworthy@canonical.com-20090403022930-epud0dn5421fp0a0
chk_map code from brisbane-core
added
removed
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
Loggerhead is a web-based interface for Breezy
Version: 2.0.1