/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Robert Collins
  • Date: 2010-05-06 11:08:10 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506110810-h3j07fh5gmw54s25
Cleaner matcher matching revised unlocking protocol.

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
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
from __future__ import absolute_import
21
 
 
22
20
import cStringIO
23
 
 
24
 
from bzrlib.lazy_import import lazy_import
25
 
lazy_import(globals(), """
26
 
import bisect
 
21
from bisect import bisect_right
27
22
import math
28
23
import tempfile
29
24
import zlib
30
 
""")
31
25
 
32
26
from bzrlib import (
33
27
    chunk_writer,
39
33
    osutils,
40
34
    static_tuple,
41
35
    trace,
42
 
    transport,
43
36
    )
44
37
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
38
from bzrlib.transport import get_transport
45
39
 
46
40
 
47
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
164
158
        :param references: An iterable of iterables of keys. Each is a
165
159
            reference to another key.
166
160
        :param value: The value to associate with the key. It may be any
167
 
            bytes as long as it does not contain \\0 or \\n.
 
161
            bytes as long as it does not contain \0 or \n.
168
162
        """
169
163
        # Ensure that 'key' is a StaticTuple
170
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
199
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
200
194
        # Note: The transport here isn't strictly needed, because we will use
201
195
        #       direct access to the new_backing._file object
202
 
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
203
 
                                      '<temp>', size)
 
196
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
204
197
        # GC will clean up the file
205
198
        new_backing._file = new_backing_file
206
199
        if self._combine_backing_indices:
296
289
            flag when writing out. This is used by the _spill_mem_keys_to_disk
297
290
            functionality.
298
291
        """
299
 
        new_leaf = False
300
292
        if rows[-1].writer is None:
301
293
            # opening a new leaf chunk;
302
 
            new_leaf = True
303
294
            for pos, internal_row in enumerate(rows[:-1]):
304
295
                # flesh out any internal nodes that are needed to
305
296
                # preserve the height of the tree
324
315
                optimize_for_size=self._optimize_for_size)
325
316
            rows[-1].writer.write(_LEAF_FLAG)
326
317
        if rows[-1].writer.write(line):
327
 
            # if we failed to write, despite having an empty page to write to,
328
 
            # then line is too big. raising the error avoids infinite recursion
329
 
            # searching for a suitably large page that will not be found.
330
 
            if new_leaf:
331
 
                raise errors.BadIndexKey(string_key)
332
318
            # this key did not fit in the node:
333
319
            rows[-1].finish_node()
334
320
            key_line = string_key + "\n"
615
601
        """In memory index's have no known corruption at the moment."""
616
602
 
617
603
 
618
 
class _LeafNode(dict):
 
604
class _LeafNode(object):
619
605
    """A leaf node for a serialised B+Tree index."""
620
606
 
621
 
    __slots__ = ('min_key', 'max_key', '_keys')
 
607
    __slots__ = ('keys', 'min_key', 'max_key')
622
608
 
623
609
    def __init__(self, bytes, key_length, ref_list_length):
624
610
        """Parse bytes to create a leaf node object."""
630
616
            self.max_key = key_list[-1][0]
631
617
        else:
632
618
            self.min_key = self.max_key = None
633
 
        super(_LeafNode, self).__init__(key_list)
634
 
        self._keys = dict(self)
635
 
 
636
 
    def all_items(self):
637
 
        """Return a sorted list of (key, (value, refs)) items"""
638
 
        items = self.items()
639
 
        items.sort()
640
 
        return items
641
 
 
642
 
    def all_keys(self):
643
 
        """Return a sorted list of all keys."""
644
 
        keys = self.keys()
645
 
        keys.sort()
646
 
        return keys
 
619
        self.keys = dict(key_list)
647
620
 
648
621
 
649
622
class _InternalNode(object):
698
671
        self._recommended_pages = self._compute_recommended_pages()
699
672
        self._root_node = None
700
673
        self._base_offset = offset
701
 
        self._leaf_factory = _LeafNode
702
674
        # Default max size is 100,000 leave values
703
675
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
704
676
        if unlimited_cache:
977
949
        """Cache directly from key => value, skipping the btree."""
978
950
        if self._leaf_value_cache is not None:
979
951
            for node in nodes.itervalues():
980
 
                for key, value in node.all_items():
 
952
                for key, value in node.keys.iteritems():
981
953
                    if key in self._leaf_value_cache:
982
954
                        # Don't add the rest of the keys, we've seen this node
983
955
                        # before.
1007
979
        if self._row_offsets[-1] == 1:
1008
980
            # There is only the root node, and we read that via key_count()
1009
981
            if self.node_ref_lists:
1010
 
                for key, (value, refs) in self._root_node.all_items():
 
982
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1011
983
                    yield (self, key, value, refs)
1012
984
            else:
1013
 
                for key, (value, refs) in self._root_node.all_items():
 
985
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1014
986
                    yield (self, key, value)
1015
987
            return
1016
988
        start_of_leaves = self._row_offsets[-2]
1026
998
        # for spilling index builds to disk.
1027
999
        if self.node_ref_lists:
1028
1000
            for _, node in nodes:
1029
 
                for key, (value, refs) in node.all_items():
 
1001
                for key, (value, refs) in sorted(node.keys.items()):
1030
1002
                    yield (self, key, value, refs)
1031
1003
        else:
1032
1004
            for _, node in nodes:
1033
 
                for key, (value, refs) in node.all_items():
 
1005
                for key, (value, refs) in sorted(node.keys.items()):
1034
1006
                    yield (self, key, value)
1035
1007
 
1036
1008
    @staticmethod
1060
1032
        # iter_steps = len(in_keys) + len(fixed_keys)
1061
1033
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1062
1034
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1063
 
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1035
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1064
1036
        # elif bisect_steps < iter_steps:
1065
1037
        #     offsets = {}
1066
1038
        #     for key in in_keys:
1197
1169
                continue
1198
1170
            node = nodes[node_index]
1199
1171
            for next_sub_key in sub_keys:
1200
 
                if next_sub_key in node:
1201
 
                    value, refs = node[next_sub_key]
 
1172
                if next_sub_key in node.keys:
 
1173
                    value, refs = node.keys[next_sub_key]
1202
1174
                    if self.node_ref_lists:
1203
1175
                        yield (self, next_sub_key, value, refs)
1204
1176
                    else:
1272
1244
            # sub_keys is all of the keys we are looking for that should exist
1273
1245
            # on this page, if they aren't here, then they won't be found
1274
1246
            node = nodes[node_index]
 
1247
            node_keys = node.keys
1275
1248
            parents_to_check = set()
1276
1249
            for next_sub_key in sub_keys:
1277
 
                if next_sub_key not in node:
 
1250
                if next_sub_key not in node_keys:
1278
1251
                    # This one is just not present in the index at all
1279
1252
                    missing_keys.add(next_sub_key)
1280
1253
                else:
1281
 
                    value, refs = node[next_sub_key]
 
1254
                    value, refs = node_keys[next_sub_key]
1282
1255
                    parent_keys = refs[ref_list_num]
1283
1256
                    parent_map[next_sub_key] = parent_keys
1284
1257
                    parents_to_check.update(parent_keys)
1291
1264
            while parents_to_check:
1292
1265
                next_parents_to_check = set()
1293
1266
                for key in parents_to_check:
1294
 
                    if key in node:
1295
 
                        value, refs = node[key]
 
1267
                    if key in node_keys:
 
1268
                        value, refs = node_keys[key]
1296
1269
                        parent_keys = refs[ref_list_num]
1297
1270
                        parent_map[key] = parent_keys
1298
1271
                        next_parents_to_check.update(parent_keys)
1572
1545
                    continue
1573
1546
            bytes = zlib.decompress(data)
1574
1547
            if bytes.startswith(_LEAF_FLAG):
1575
 
                node = self._leaf_factory(bytes, self._key_length,
1576
 
                                          self.node_ref_lists)
 
1548
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1577
1549
            elif bytes.startswith(_INTERNAL_FLAG):
1578
1550
                node = _InternalNode(bytes)
1579
1551
            else:
1598
1570
            pass
1599
1571
 
1600
1572
 
1601
 
_gcchk_factory = _LeafNode
1602
 
 
1603
1573
try:
1604
1574
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1605
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1606
1575
except ImportError, e:
1607
1576
    osutils.failed_to_load_extension(e)
1608
1577
    from bzrlib import _btree_serializer_py as _btree_serializer