← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Jelmer Vernooij
  • Date: 2011-05-01 21:02:50 UTC
  • mto: This revision was merged to the branch mainline in revision 5842.
  • Revision ID: jelmer@samba.org-20110501210250-24jq6hrxxc9psvzf
Actually use branch format 5 in branch format 5 test.

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"
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