← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/chk_map.py

Merge the pyrex chk implementations into brisbane-core.
Update the test suite for 'multiply_tests'.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/chk_map.py
38
38
"""
39
39
 
40
40
import heapq
 
41
import time
41
42
 
42
43
from bzrlib import lazy_import
43
44
lazy_import.lazy_import(globals(), """
44
 
import zlib
45
 
import struct
46
 
 
47
45
from bzrlib import versionedfile
48
46
""")
49
47
from bzrlib import (
74
72
    return '\x00'.join(key)
75
73
 
76
74
 
77
 
def _crc32(bit):
78
 
    # Depending on python version and platform, zlib.crc32 will return either a
79
 
    # signed (<= 2.5 >= 3.0) or an unsigned (2.5, 2.6).
80
 
    # http://docs.python.org/library/zlib.html recommends using a mask to force
81
 
    # an unsigned value to ensure the same numeric value (unsigned) is obtained
82
 
    # across all python versions and platforms.
83
 
    # Note: However, on 32-bit platforms this causes an upcast to PyLong, which
84
 
    #       are generally slower than PyInts. However, if performance becomes
85
 
    #       critical, we should probably write the whole thing as an extension
86
 
    #       anyway.
87
 
    #       Though we really don't need that 32nd bit of accuracy. (even 2**24
88
 
    #       is probably enough node fan out for realistic trees.)
89
 
    return zlib.crc32(bit)&0xFFFFFFFF
90
 
 
91
 
 
92
 
def _search_key_16(key):
93
 
    """Map the key tuple into a search key string which has 16-way fan out."""
94
 
    return '\x00'.join(['%08X' % _crc32(bit) for bit in key])
95
 
 
96
 
 
97
 
def _search_key_255(key):
98
 
    """Map the key tuple into a search key string which has 255-way fan out.
99
 
 
100
 
    We use 255-way because '\n' is used as a delimiter, and causes problems
101
 
    while parsing.
102
 
    """
103
 
    bytes = '\x00'.join([struct.pack('>L', _crc32(bit)) for bit in key])
104
 
    return bytes.replace('\n', '_')
105
 
 
106
 
 
107
75
search_key_registry = registry.Registry()
108
76
search_key_registry.register('plain', _search_key_plain)
109
 
search_key_registry.register('hash-16-way', _search_key_16)
110
 
search_key_registry.register('hash-255-way', _search_key_255)
111
77
 
112
78
 
113
79
class CHKMap(object):
676
642
        :param bytes: The bytes of the node.
677
643
        :param key: The key that the serialised node has.
678
644
        """
679
 
        result = LeafNode(search_key_func=search_key_func)
680
 
        # Splitlines can split on '\r' so don't use it, split('\n') adds an
681
 
        # extra '' if the bytes ends in a final newline.
682
 
        lines = bytes.split('\n')
683
 
        trailing = lines.pop()
684
 
        if trailing != '':
685
 
            raise AssertionError('We did not have a final newline for %s'
686
 
                                 % (key,))
687
 
        items = {}
688
 
        if lines[0] != 'chkleaf:':
689
 
            raise ValueError("not a serialised leaf node: %r" % bytes)
690
 
        maximum_size = int(lines[1])
691
 
        width = int(lines[2])
692
 
        length = int(lines[3])
693
 
        prefix = lines[4]
694
 
        pos = 5
695
 
        while pos < len(lines):
696
 
            line = prefix + lines[pos]
697
 
            elements = line.split('\x00')
698
 
            pos += 1
699
 
            if len(elements) != width + 1:
700
 
                raise AssertionError(
701
 
                    'Incorrect number of elements (%d vs %d) for: %r'
702
 
                    % (len(elements), width + 1, line))
703
 
            num_value_lines = int(elements[-1])
704
 
            value_lines = lines[pos:pos+num_value_lines]
705
 
            pos += num_value_lines
706
 
            value = '\n'.join(value_lines)
707
 
            items[tuple(elements[:-1])] = value
708
 
        if len(items) != length:
709
 
            raise AssertionError("item count (%d) mismatch for key %s,"
710
 
                " bytes %r" % (length, key, bytes))
711
 
        result._items = items
712
 
        result._len = length
713
 
        result._maximum_size = maximum_size
714
 
        result._key = key
715
 
        result._key_width = width
716
 
        result._raw_size = (sum(map(len, lines[5:])) # the length of the suffix
717
 
            + (length)*(len(prefix))
718
 
            + (len(lines)-5))
719
 
        if not items:
720
 
            result._search_prefix = None
721
 
            result._common_serialised_prefix = None
722
 
        else:
723
 
            result._search_prefix = _unknown
724
 
            result._common_serialised_prefix = prefix
725
 
        if len(bytes) != result._current_size():
726
 
            raise AssertionError('_current_size computed incorrectly')
727
 
        return result
 
645
        return _deserialise_leaf_node(bytes, key,
 
646
                                      search_key_func=search_key_func)
728
647
 
729
648
    def iteritems(self, store, key_filter=None):
730
649
        """Iterate over items in the node.
994
913
        :param key: The key that the serialised node has.
995
914
        :return: An InternalNode instance.
996
915
        """
997
 
        result = InternalNode(search_key_func=search_key_func)
998
 
        # Splitlines can split on '\r' so don't use it, remove the extra ''
999
 
        # from the result of split('\n') because we should have a trailing
1000
 
        # newline
1001
 
        lines = bytes.split('\n')
1002
 
        if lines[-1] != '':
1003
 
            raise AssertionError("last line must be ''")
1004
 
        lines.pop(-1)
1005
 
        items = {}
1006
 
        if lines[0] != 'chknode:':
1007
 
            raise ValueError("not a serialised internal node: %r" % bytes)
1008
 
        maximum_size = int(lines[1])
1009
 
        width = int(lines[2])
1010
 
        length = int(lines[3])
1011
 
        common_prefix = lines[4]
1012
 
        for line in lines[5:]:
1013
 
            line = common_prefix + line
1014
 
            prefix, flat_key = line.rsplit('\x00', 1)
1015
 
            items[prefix] = (flat_key,)
1016
 
        result._items = items
1017
 
        result._len = length
1018
 
        result._maximum_size = maximum_size
1019
 
        result._key = key
1020
 
        result._key_width = width
1021
 
        # XXX: InternalNodes don't really care about their size, and this will
1022
 
        #      change if we add prefix compression
1023
 
        result._raw_size = None # len(bytes)
1024
 
        result._node_width = len(prefix)
1025
 
        assert len(items) > 0
1026
 
        result._search_prefix = common_prefix
1027
 
        return result
 
916
        return _deserialise_internal_node(bytes, key,
 
917
                                          search_key_func=search_key_func)
1028
918
 
1029
919
    def iteritems(self, store, key_filter=None):
1030
920
        for node in self._iter_nodes(store, key_filter=key_filter):
1357
1247
def _deserialise(bytes, key, search_key_func):
1358
1248
    """Helper for repositorydetails - convert bytes to a node."""
1359
1249
    if bytes.startswith("chkleaf:\n"):
1360
 
        return LeafNode.deserialise(bytes, key, search_key_func=search_key_func)
 
1250
        node = LeafNode.deserialise(bytes, key, search_key_func=search_key_func)
1361
1251
    elif bytes.startswith("chknode:\n"):
1362
 
        return InternalNode.deserialise(bytes, key,
 
1252
        node = InternalNode.deserialise(bytes, key,
1363
1253
            search_key_func=search_key_func)
1364
1254
    else:
1365
1255
        raise AssertionError("Unknown node type.")
 
1256
    return node
1366
1257
 
1367
1258
 
1368
1259
def _find_children_info(store, interesting_keys, uninteresting_keys, pb):
1539
1430
                # all_uninteresting_items.update(interesting_items)
1540
1431
            yield {record.key: record}, interesting_items
1541
1432
        chks_to_read = next_chks
 
1433
 
 
1434
 
 
1435
try:
 
1436
    from bzrlib._chk_map_pyx import (
 
1437
        _search_key_16,
 
1438
        _search_key_255,
 
1439
        _deserialise_leaf_node,
 
1440
        _deserialise_internal_node,
 
1441
        )
 
1442
except ImportError:
 
1443
    from bzrlib._chk_map_py import (
 
1444
        _search_key_16,
 
1445
        _search_key_255,
 
1446
        _deserialise_leaf_node,
 
1447
        _deserialise_internal_node,
 
1448
        )
 
1449
search_key_registry.register('hash-16-way', _search_key_16)
 
1450
search_key_registry.register('hash-255-way', _search_key_255)