← 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: 2010-08-28 11:19:49 UTC
  • mto: This revision was merged to the branch mainline in revision 5418.
  • Revision ID: jelmer@samba.org-20100828111949-6ke9opiop2oomr4f
Move get_config to ControlDir.

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,
606
602
        """In memory index's have no known corruption at the moment."""
607
603
 
608
604
 
609
 
class _LeafNode(dict):
 
605
class _LeafNode(object):
610
606
    """A leaf node for a serialised B+Tree index."""
611
607
 
612
 
    __slots__ = ('min_key', 'max_key', '_keys')
 
608
    __slots__ = ('keys', 'min_key', 'max_key')
613
609
 
614
610
    def __init__(self, bytes, key_length, ref_list_length):
615
611
        """Parse bytes to create a leaf node object."""
621
617
            self.max_key = key_list[-1][0]
622
618
        else:
623
619
            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
 
620
        self.keys = dict(key_list)
638
621
 
639
622
 
640
623
class _InternalNode(object):
689
672
        self._recommended_pages = self._compute_recommended_pages()
690
673
        self._root_node = None
691
674
        self._base_offset = offset
692
 
        self._leaf_factory = _LeafNode
693
675
        # Default max size is 100,000 leave values
694
676
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
695
677
        if unlimited_cache:
968
950
        """Cache directly from key => value, skipping the btree."""
969
951
        if self._leaf_value_cache is not None:
970
952
            for node in nodes.itervalues():
971
 
                for key, value in node.all_items():
 
953
                for key, value in node.keys.iteritems():
972
954
                    if key in self._leaf_value_cache:
973
955
                        # Don't add the rest of the keys, we've seen this node
974
956
                        # before.
998
980
        if self._row_offsets[-1] == 1:
999
981
            # There is only the root node, and we read that via key_count()
1000
982
            if self.node_ref_lists:
1001
 
                for key, (value, refs) in self._root_node.all_items():
 
983
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1002
984
                    yield (self, key, value, refs)
1003
985
            else:
1004
 
                for key, (value, refs) in self._root_node.all_items():
 
986
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1005
987
                    yield (self, key, value)
1006
988
            return
1007
989
        start_of_leaves = self._row_offsets[-2]
1017
999
        # for spilling index builds to disk.
1018
1000
        if self.node_ref_lists:
1019
1001
            for _, node in nodes:
1020
 
                for key, (value, refs) in node.all_items():
 
1002
                for key, (value, refs) in sorted(node.keys.items()):
1021
1003
                    yield (self, key, value, refs)
1022
1004
        else:
1023
1005
            for _, node in nodes:
1024
 
                for key, (value, refs) in node.all_items():
 
1006
                for key, (value, refs) in sorted(node.keys.items()):
1025
1007
                    yield (self, key, value)
1026
1008
 
1027
1009
    @staticmethod
1051
1033
        # iter_steps = len(in_keys) + len(fixed_keys)
1052
1034
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1053
1035
        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)]
 
1036
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1055
1037
        # elif bisect_steps < iter_steps:
1056
1038
        #     offsets = {}
1057
1039
        #     for key in in_keys:
1188
1170
                continue
1189
1171
            node = nodes[node_index]
1190
1172
            for next_sub_key in sub_keys:
1191
 
                if next_sub_key in node:
1192
 
                    value, refs = node[next_sub_key]
 
1173
                if next_sub_key in node.keys:
 
1174
                    value, refs = node.keys[next_sub_key]
1193
1175
                    if self.node_ref_lists:
1194
1176
                        yield (self, next_sub_key, value, refs)
1195
1177
                    else:
1263
1245
            # sub_keys is all of the keys we are looking for that should exist
1264
1246
            # on this page, if they aren't here, then they won't be found
1265
1247
            node = nodes[node_index]
 
1248
            node_keys = node.keys
1266
1249
            parents_to_check = set()
1267
1250
            for next_sub_key in sub_keys:
1268
 
                if next_sub_key not in node:
 
1251
                if next_sub_key not in node_keys:
1269
1252
                    # This one is just not present in the index at all
1270
1253
                    missing_keys.add(next_sub_key)
1271
1254
                else:
1272
 
                    value, refs = node[next_sub_key]
 
1255
                    value, refs = node_keys[next_sub_key]
1273
1256
                    parent_keys = refs[ref_list_num]
1274
1257
                    parent_map[next_sub_key] = parent_keys
1275
1258
                    parents_to_check.update(parent_keys)
1282
1265
            while parents_to_check:
1283
1266
                next_parents_to_check = set()
1284
1267
                for key in parents_to_check:
1285
 
                    if key in node:
1286
 
                        value, refs = node[key]
 
1268
                    if key in node_keys:
 
1269
                        value, refs = node_keys[key]
1287
1270
                        parent_keys = refs[ref_list_num]
1288
1271
                        parent_map[key] = parent_keys
1289
1272
                        next_parents_to_check.update(parent_keys)
1563
1546
                    continue
1564
1547
            bytes = zlib.decompress(data)
1565
1548
            if bytes.startswith(_LEAF_FLAG):
1566
 
                node = self._leaf_factory(bytes, self._key_length,
1567
 
                                          self.node_ref_lists)
 
1549
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1568
1550
            elif bytes.startswith(_INTERNAL_FLAG):
1569
1551
                node = _InternalNode(bytes)
1570
1552
            else:
1589
1571
            pass
1590
1572
 
1591
1573
 
1592
 
_gcchk_factory = _LeafNode
1593
 
 
1594
1574
try:
1595
1575
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1596
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1597
1576
except ImportError, e:
1598
1577
    osutils.failed_to_load_extension(e)
1599
1578
    from bzrlib import _btree_serializer_py as _btree_serializer