← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

Move all features to bzrlib.tests.features in 2.5

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2008-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
18
18
"""B+Tree indices"""
19
19
 
20
20
import cStringIO
21
 
from bisect import bisect_right
 
21
 
 
22
from bzrlib.lazy_import import lazy_import
 
23
lazy_import(globals(), """
 
24
import bisect
22
25
import math
23
26
import tempfile
24
27
import zlib
 
28
""")
25
29
 
26
30
from bzrlib import (
27
31
    chunk_writer,
33
37
    osutils,
34
38
    static_tuple,
35
39
    trace,
 
40
    transport,
36
41
    )
37
42
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
38
 
from bzrlib.transport import get_transport
39
43
 
40
44
 
41
45
_BTSIGNATURE = "B+Tree Graph Index 2\n"
158
162
        :param references: An iterable of iterables of keys. Each is a
159
163
            reference to another key.
160
164
        :param value: The value to associate with the key. It may be any
161
 
            bytes as long as it does not contain \0 or \n.
 
165
            bytes as long as it does not contain \\0 or \\n.
162
166
        """
163
167
        # Ensure that 'key' is a StaticTuple
164
168
        key = static_tuple.StaticTuple.from_sequence(key).intern()
193
197
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
198
        # Note: The transport here isn't strictly needed, because we will use
195
199
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
200
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
201
                                      '<temp>', size)
197
202
        # GC will clean up the file
198
203
        new_backing._file = new_backing_file
199
204
        if self._combine_backing_indices:
601
606
        """In memory index's have no known corruption at the moment."""
602
607
 
603
608
 
604
 
class _LeafNode(object):
 
609
class _LeafNode(dict):
605
610
    """A leaf node for a serialised B+Tree index."""
606
611
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
612
    __slots__ = ('min_key', 'max_key', '_keys')
608
613
 
609
614
    def __init__(self, bytes, key_length, ref_list_length):
610
615
        """Parse bytes to create a leaf node object."""
616
621
            self.max_key = key_list[-1][0]
617
622
        else:
618
623
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
624
        super(_LeafNode, self).__init__(key_list)
 
625
        self._keys = dict(self)
 
626
 
 
627
    def all_items(self):
 
628
        """Return a sorted list of (key, (value, refs)) items"""
 
629
        items = self.items()
 
630
        items.sort()
 
631
        return items
 
632
 
 
633
    def all_keys(self):
 
634
        """Return a sorted list of all keys."""
 
635
        keys = self.keys()
 
636
        keys.sort()
 
637
        return keys
620
638
 
621
639
 
622
640
class _InternalNode(object):
671
689
        self._recommended_pages = self._compute_recommended_pages()
672
690
        self._root_node = None
673
691
        self._base_offset = offset
 
692
        self._leaf_factory = _LeafNode
674
693
        # Default max size is 100,000 leave values
675
694
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
695
        if unlimited_cache:
949
968
        """Cache directly from key => value, skipping the btree."""
950
969
        if self._leaf_value_cache is not None:
951
970
            for node in nodes.itervalues():
952
 
                for key, value in node.keys.iteritems():
 
971
                for key, value in node.all_items():
953
972
                    if key in self._leaf_value_cache:
954
973
                        # Don't add the rest of the keys, we've seen this node
955
974
                        # before.
979
998
        if self._row_offsets[-1] == 1:
980
999
            # There is only the root node, and we read that via key_count()
981
1000
            if self.node_ref_lists:
982
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1001
                for key, (value, refs) in self._root_node.all_items():
983
1002
                    yield (self, key, value, refs)
984
1003
            else:
985
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1004
                for key, (value, refs) in self._root_node.all_items():
986
1005
                    yield (self, key, value)
987
1006
            return
988
1007
        start_of_leaves = self._row_offsets[-2]
998
1017
        # for spilling index builds to disk.
999
1018
        if self.node_ref_lists:
1000
1019
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1020
                for key, (value, refs) in node.all_items():
1002
1021
                    yield (self, key, value, refs)
1003
1022
        else:
1004
1023
            for _, node in nodes:
1005
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1024
                for key, (value, refs) in node.all_items():
1006
1025
                    yield (self, key, value)
1007
1026
 
1008
1027
    @staticmethod
1032
1051
        # iter_steps = len(in_keys) + len(fixed_keys)
1033
1052
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1034
1053
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1035
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1054
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1036
1055
        # elif bisect_steps < iter_steps:
1037
1056
        #     offsets = {}
1038
1057
        #     for key in in_keys:
1169
1188
                continue
1170
1189
            node = nodes[node_index]
1171
1190
            for next_sub_key in sub_keys:
1172
 
                if next_sub_key in node.keys:
1173
 
                    value, refs = node.keys[next_sub_key]
 
1191
                if next_sub_key in node:
 
1192
                    value, refs = node[next_sub_key]
1174
1193
                    if self.node_ref_lists:
1175
1194
                        yield (self, next_sub_key, value, refs)
1176
1195
                    else:
1244
1263
            # sub_keys is all of the keys we are looking for that should exist
1245
1264
            # on this page, if they aren't here, then they won't be found
1246
1265
            node = nodes[node_index]
1247
 
            node_keys = node.keys
1248
1266
            parents_to_check = set()
1249
1267
            for next_sub_key in sub_keys:
1250
 
                if next_sub_key not in node_keys:
 
1268
                if next_sub_key not in node:
1251
1269
                    # This one is just not present in the index at all
1252
1270
                    missing_keys.add(next_sub_key)
1253
1271
                else:
1254
 
                    value, refs = node_keys[next_sub_key]
 
1272
                    value, refs = node[next_sub_key]
1255
1273
                    parent_keys = refs[ref_list_num]
1256
1274
                    parent_map[next_sub_key] = parent_keys
1257
1275
                    parents_to_check.update(parent_keys)
1264
1282
            while parents_to_check:
1265
1283
                next_parents_to_check = set()
1266
1284
                for key in parents_to_check:
1267
 
                    if key in node_keys:
1268
 
                        value, refs = node_keys[key]
 
1285
                    if key in node:
 
1286
                        value, refs = node[key]
1269
1287
                        parent_keys = refs[ref_list_num]
1270
1288
                        parent_map[key] = parent_keys
1271
1289
                        next_parents_to_check.update(parent_keys)
1545
1563
                    continue
1546
1564
            bytes = zlib.decompress(data)
1547
1565
            if bytes.startswith(_LEAF_FLAG):
1548
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1566
                node = self._leaf_factory(bytes, self._key_length,
 
1567
                                          self.node_ref_lists)
1549
1568
            elif bytes.startswith(_INTERNAL_FLAG):
1550
1569
                node = _InternalNode(bytes)
1551
1570
            else:
1570
1589
            pass
1571
1590
 
1572
1591
 
 
1592
_gcchk_factory = _LeafNode
 
1593
 
1573
1594
try:
1574
1595
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1596
    _gcchk_factory = _btree_serializer._parse_into_chk
1575
1597
except ImportError, e:
1576
1598
    osutils.failed_to_load_extension(e)
1577
1599
    from bzrlib import _btree_serializer_py as _btree_serializer