← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Vincent Ladeuil
  • Date: 2016-01-21 11:42:23 UTC
  • mto: This revision was merged to the branch mainline in revision 6610.
  • Revision ID: v.ladeuil+lp@free.fr-20160121114223-ngcvndi02ydiqs5z
Allow hyphens in option names to unbreak compatibility.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008 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
17
17
 
18
18
"""B+Tree indices"""
19
19
 
 
20
from __future__ import absolute_import
 
21
 
20
22
import cStringIO
21
 
from bisect import bisect_right
 
23
 
 
24
from bzrlib.lazy_import import lazy_import
 
25
lazy_import(globals(), """
 
26
import bisect
22
27
import math
23
28
import tempfile
24
29
import zlib
 
30
""")
25
31
 
26
32
from bzrlib import (
27
33
    chunk_writer,
33
39
    osutils,
34
40
    static_tuple,
35
41
    trace,
 
42
    transport,
36
43
    )
37
44
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
38
 
from bzrlib.transport import get_transport
39
45
 
40
46
 
41
47
_BTSIGNATURE = "B+Tree Graph Index 2\n"
158
164
        :param references: An iterable of iterables of keys. Each is a
159
165
            reference to another key.
160
166
        :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.
 
167
            bytes as long as it does not contain \\0 or \\n.
162
168
        """
163
169
        # Ensure that 'key' is a StaticTuple
164
170
        key = static_tuple.StaticTuple.from_sequence(key).intern()
193
199
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
200
        # Note: The transport here isn't strictly needed, because we will use
195
201
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
202
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
 
203
                                      '<temp>', size)
197
204
        # GC will clean up the file
198
205
        new_backing._file = new_backing_file
199
206
        if self._combine_backing_indices:
289
296
            flag when writing out. This is used by the _spill_mem_keys_to_disk
290
297
            functionality.
291
298
        """
 
299
        new_leaf = False
292
300
        if rows[-1].writer is None:
293
301
            # opening a new leaf chunk;
 
302
            new_leaf = True
294
303
            for pos, internal_row in enumerate(rows[:-1]):
295
304
                # flesh out any internal nodes that are needed to
296
305
                # preserve the height of the tree
315
324
                optimize_for_size=self._optimize_for_size)
316
325
            rows[-1].writer.write(_LEAF_FLAG)
317
326
        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)
318
332
            # this key did not fit in the node:
319
333
            rows[-1].finish_node()
320
334
            key_line = string_key + "\n"
567
581
                    else:
568
582
                        # yield keys
569
583
                        for value in key_dict.itervalues():
570
 
                            yield (self, ) + value
 
584
                            yield (self, ) + tuple(value)
571
585
            else:
572
586
                yield (self, ) + key_dict
573
587
 
601
615
        """In memory index's have no known corruption at the moment."""
602
616
 
603
617
 
604
 
class _LeafNode(object):
 
618
class _LeafNode(dict):
605
619
    """A leaf node for a serialised B+Tree index."""
606
620
 
607
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
621
    __slots__ = ('min_key', 'max_key', '_keys')
608
622
 
609
623
    def __init__(self, bytes, key_length, ref_list_length):
610
624
        """Parse bytes to create a leaf node object."""
616
630
            self.max_key = key_list[-1][0]
617
631
        else:
618
632
            self.min_key = self.max_key = None
619
 
        self.keys = dict(key_list)
 
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
620
647
 
621
648
 
622
649
class _InternalNode(object):
647
674
    memory except when very large walks are done.
648
675
    """
649
676
 
650
 
    def __init__(self, transport, name, size, unlimited_cache=False):
 
677
    def __init__(self, transport, name, size, unlimited_cache=False,
 
678
                 offset=0):
651
679
        """Create a B+Tree index object on the index name.
652
680
 
653
681
        :param transport: The transport to read data for the index from.
660
688
        :param unlimited_cache: If set to True, then instead of using an
661
689
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
662
690
            cache all leaf nodes.
 
691
        :param offset: The start of the btree index data isn't byte 0 of the
 
692
            file. Instead it starts at some point later.
663
693
        """
664
694
        self._transport = transport
665
695
        self._name = name
667
697
        self._file = None
668
698
        self._recommended_pages = self._compute_recommended_pages()
669
699
        self._root_node = None
 
700
        self._base_offset = offset
 
701
        self._leaf_factory = _LeafNode
670
702
        # Default max size is 100,000 leave values
671
703
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
672
704
        if unlimited_cache:
945
977
        """Cache directly from key => value, skipping the btree."""
946
978
        if self._leaf_value_cache is not None:
947
979
            for node in nodes.itervalues():
948
 
                for key, value in node.keys.iteritems():
 
980
                for key, value in node.all_items():
949
981
                    if key in self._leaf_value_cache:
950
982
                        # Don't add the rest of the keys, we've seen this node
951
983
                        # before.
975
1007
        if self._row_offsets[-1] == 1:
976
1008
            # There is only the root node, and we read that via key_count()
977
1009
            if self.node_ref_lists:
978
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1010
                for key, (value, refs) in self._root_node.all_items():
979
1011
                    yield (self, key, value, refs)
980
1012
            else:
981
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1013
                for key, (value, refs) in self._root_node.all_items():
982
1014
                    yield (self, key, value)
983
1015
            return
984
1016
        start_of_leaves = self._row_offsets[-2]
994
1026
        # for spilling index builds to disk.
995
1027
        if self.node_ref_lists:
996
1028
            for _, node in nodes:
997
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1029
                for key, (value, refs) in node.all_items():
998
1030
                    yield (self, key, value, refs)
999
1031
        else:
1000
1032
            for _, node in nodes:
1001
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1033
                for key, (value, refs) in node.all_items():
1002
1034
                    yield (self, key, value)
1003
1035
 
1004
1036
    @staticmethod
1028
1060
        # iter_steps = len(in_keys) + len(fixed_keys)
1029
1061
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1030
1062
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1031
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1063
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
1032
1064
        # elif bisect_steps < iter_steps:
1033
1065
        #     offsets = {}
1034
1066
        #     for key in in_keys:
1165
1197
                continue
1166
1198
            node = nodes[node_index]
1167
1199
            for next_sub_key in sub_keys:
1168
 
                if next_sub_key in node.keys:
1169
 
                    value, refs = node.keys[next_sub_key]
 
1200
                if next_sub_key in node:
 
1201
                    value, refs = node[next_sub_key]
1170
1202
                    if self.node_ref_lists:
1171
1203
                        yield (self, next_sub_key, value, refs)
1172
1204
                    else:
1240
1272
            # sub_keys is all of the keys we are looking for that should exist
1241
1273
            # on this page, if they aren't here, then they won't be found
1242
1274
            node = nodes[node_index]
1243
 
            node_keys = node.keys
1244
1275
            parents_to_check = set()
1245
1276
            for next_sub_key in sub_keys:
1246
 
                if next_sub_key not in node_keys:
 
1277
                if next_sub_key not in node:
1247
1278
                    # This one is just not present in the index at all
1248
1279
                    missing_keys.add(next_sub_key)
1249
1280
                else:
1250
 
                    value, refs = node_keys[next_sub_key]
 
1281
                    value, refs = node[next_sub_key]
1251
1282
                    parent_keys = refs[ref_list_num]
1252
1283
                    parent_map[next_sub_key] = parent_keys
1253
1284
                    parents_to_check.update(parent_keys)
1260
1291
            while parents_to_check:
1261
1292
                next_parents_to_check = set()
1262
1293
                for key in parents_to_check:
1263
 
                    if key in node_keys:
1264
 
                        value, refs = node_keys[key]
 
1294
                    if key in node:
 
1295
                        value, refs = node[key]
1265
1296
                        parent_keys = refs[ref_list_num]
1266
1297
                        parent_map[key] = parent_keys
1267
1298
                        next_parents_to_check.update(parent_keys)
1494
1525
        # list of (offset, length) regions of the file that should, evenually
1495
1526
        # be read in to data_ranges, either from 'bytes' or from the transport
1496
1527
        ranges = []
 
1528
        base_offset = self._base_offset
1497
1529
        for index in nodes:
1498
 
            offset = index * _PAGE_SIZE
 
1530
            offset = (index * _PAGE_SIZE)
1499
1531
            size = _PAGE_SIZE
1500
1532
            if index == 0:
1501
1533
                # Root node - special case
1505
1537
                    # The only case where we don't know the size, is for very
1506
1538
                    # small indexes. So we read the whole thing
1507
1539
                    bytes = self._transport.get_bytes(self._name)
1508
 
                    self._size = len(bytes)
 
1540
                    num_bytes = len(bytes)
 
1541
                    self._size = num_bytes - base_offset
1509
1542
                    # the whole thing should be parsed out of 'bytes'
1510
 
                    ranges.append((0, len(bytes)))
 
1543
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
 
1544
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1511
1545
                    break
1512
1546
            else:
1513
1547
                if offset > self._size:
1515
1549
                                         ' of the file %s > %s'
1516
1550
                                         % (offset, self._size))
1517
1551
                size = min(size, self._size - offset)
1518
 
            ranges.append((offset, size))
 
1552
            ranges.append((base_offset + offset, size))
1519
1553
        if not ranges:
1520
1554
            return
1521
1555
        elif bytes is not None:
1522
1556
            # already have the whole file
1523
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1524
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1557
            data_ranges = [(start, bytes[start:start+size])
 
1558
                           for start, size in ranges]
1525
1559
        elif self._file is None:
1526
1560
            data_ranges = self._transport.readv(self._name, ranges)
1527
1561
        else:
1530
1564
                self._file.seek(offset)
1531
1565
                data_ranges.append((offset, self._file.read(size)))
1532
1566
        for offset, data in data_ranges:
 
1567
            offset -= base_offset
1533
1568
            if offset == 0:
1534
1569
                # extract the header
1535
1570
                offset, data = self._parse_header_from_bytes(data)
1537
1572
                    continue
1538
1573
            bytes = zlib.decompress(data)
1539
1574
            if bytes.startswith(_LEAF_FLAG):
1540
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1575
                node = self._leaf_factory(bytes, self._key_length,
 
1576
                                          self.node_ref_lists)
1541
1577
            elif bytes.startswith(_INTERNAL_FLAG):
1542
1578
                node = _InternalNode(bytes)
1543
1579
            else:
1562
1598
            pass
1563
1599
 
1564
1600
 
 
1601
_gcchk_factory = _LeafNode
 
1602
 
1565
1603
try:
1566
1604
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1605
    _gcchk_factory = _btree_serializer._parse_into_chk
1567
1606
except ImportError, e:
1568
1607
    osutils.failed_to_load_extension(e)
1569
1608
    from bzrlib import _btree_serializer_py as _btree_serializer