← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-05-28 00:25:32 UTC
  • mfrom: (5264.1.2 command-help-bug-177500)
  • Revision ID: pqm@pqm.ubuntu.com-20100528002532-9bzj1fajyxckd1rg
(lifeless) Stop raising at runtime when a command has no help,
 instead have a test in the test suite that checks all known command objects.
 (Robert Collins)

Show diffs side-by-side

added added

removed removed

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