← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

(vila) Fix test failures blocking package builds. (Vincent Ladeuil)

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 bisect import bisect_right
 
20
from __future__ import absolute_import
 
21
 
 
22
import cStringIO
 
23
 
 
24
from bzrlib.lazy_import import lazy_import
 
25
lazy_import(globals(), """
 
26
import bisect
21
27
import math
22
28
import tempfile
23
29
import zlib
 
30
""")
24
31
 
25
32
from bzrlib import (
26
33
    chunk_writer,
30
37
    index,
31
38
    lru_cache,
32
39
    osutils,
 
40
    static_tuple,
33
41
    trace,
 
42
    transport,
34
43
    )
35
44
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
36
 
from bzrlib.transport import get_transport
37
45
 
38
46
 
39
47
_BTSIGNATURE = "B+Tree Graph Index 2\n"
60
68
    def __init__(self):
61
69
        """Create a _BuilderRow."""
62
70
        self.nodes = 0
63
 
        self.spool = tempfile.TemporaryFile()
 
71
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
64
72
        self.writer = None
65
73
 
66
74
    def finish_node(self, pad=True):
67
75
        byte_lines, _, padding = self.writer.finish()
68
76
        if self.nodes == 0:
 
77
            self.spool = cStringIO.StringIO()
69
78
            # padded note:
70
79
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
 
80
        elif self.nodes == 1:
 
81
            # We got bigger than 1 node, switch to a temp file
 
82
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
 
83
            spool.write(self.spool.getvalue())
 
84
            self.spool = spool
71
85
        skipped_bytes = 0
72
86
        if not pad and padding:
73
87
            del byte_lines[-1]
150
164
        :param references: An iterable of iterables of keys. Each is a
151
165
            reference to another key.
152
166
        :param value: The value to associate with the key. It may be any
153
 
            bytes as long as it does not contain \0 or \n.
 
167
            bytes as long as it does not contain \\0 or \\n.
154
168
        """
 
169
        # Ensure that 'key' is a StaticTuple
 
170
        key = static_tuple.StaticTuple.from_sequence(key).intern()
155
171
        # we don't care about absent_references
156
172
        node_refs, _ = self._check_key_ref_value(key, references, value)
157
173
        if key in self._nodes:
158
174
            raise errors.BadIndexDuplicateKey(key, self)
159
 
        self._nodes[key] = (node_refs, value)
160
 
        self._keys.add(key)
 
175
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
161
176
        if self._nodes_by_key is not None and self._key_length > 1:
162
177
            self._update_nodes_by_key(key, value, node_refs)
163
 
        if len(self._keys) < self._spill_at:
 
178
        if len(self._nodes) < self._spill_at:
164
179
            return
165
180
        self._spill_mem_keys_to_disk()
166
181
 
182
197
             backing_pos) = self._spill_mem_keys_and_combine()
183
198
        else:
184
199
            new_backing_file, size = self._spill_mem_keys_without_combining()
185
 
        dir_path, base_name = osutils.split(new_backing_file.name)
186
200
        # Note: The transport here isn't strictly needed, because we will use
187
201
        #       direct access to the new_backing._file object
188
 
        new_backing = BTreeGraphIndex(get_transport(dir_path),
189
 
                                      base_name, size)
 
202
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
 
203
                                      '<temp>', size)
190
204
        # GC will clean up the file
191
205
        new_backing._file = new_backing_file
192
206
        if self._combine_backing_indices:
197
211
                self._backing_indices[backing_pos] = None
198
212
        else:
199
213
            self._backing_indices.append(new_backing)
200
 
        self._keys = set()
201
214
        self._nodes = {}
202
215
        self._nodes_by_key = None
203
216
 
283
296
            flag when writing out. This is used by the _spill_mem_keys_to_disk
284
297
            functionality.
285
298
        """
 
299
        new_leaf = False
286
300
        if rows[-1].writer is None:
287
301
            # opening a new leaf chunk;
 
302
            new_leaf = True
288
303
            for pos, internal_row in enumerate(rows[:-1]):
289
304
                # flesh out any internal nodes that are needed to
290
305
                # preserve the height of the tree
309
324
                optimize_for_size=self._optimize_for_size)
310
325
            rows[-1].writer.write(_LEAF_FLAG)
311
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)
312
332
            # this key did not fit in the node:
313
333
            rows[-1].finish_node()
314
334
            key_line = string_key + "\n"
379
399
        for row in reversed(rows):
380
400
            pad = (type(row) != _LeafBuilderRow)
381
401
            row.finish_node(pad=pad)
382
 
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
383
402
        lines = [_BTSIGNATURE]
384
403
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
385
404
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
386
405
        lines.append(_OPTION_LEN + str(key_count) + '\n')
387
406
        row_lengths = [row.nodes for row in rows]
388
407
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
 
408
        if row_lengths and row_lengths[-1] > 1:
 
409
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
 
410
        else:
 
411
            result = cStringIO.StringIO()
389
412
        result.writelines(lines)
390
413
        position = sum(map(len, lines))
391
414
        root_row = True
402
425
            # Special case the first node as it may be prefixed
403
426
            node = row.spool.read(_PAGE_SIZE)
404
427
            result.write(node[reserved:])
405
 
            result.write("\x00" * (reserved - position))
 
428
            if len(node) == _PAGE_SIZE:
 
429
                result.write("\x00" * (reserved - position))
406
430
            position = 0 # Only the root row actually has an offset
407
431
            copied_len = osutils.pumpfile(row.spool, result)
408
432
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
453
477
            efficient order for the index (keys iteration order in this case).
454
478
        """
455
479
        keys = set(keys)
456
 
        local_keys = keys.intersection(self._keys)
 
480
        # Note: We don't use keys.intersection() here. If you read the C api,
 
481
        #       set.intersection(other) special cases when other is a set and
 
482
        #       will iterate the smaller of the two and lookup in the other.
 
483
        #       It does *not* do this for any other type (even dict, unlike
 
484
        #       some other set functions.) Since we expect keys is generally <<
 
485
        #       self._nodes, it is faster to iterate over it in a list
 
486
        #       comprehension
 
487
        nodes = self._nodes
 
488
        local_keys = [key for key in keys if key in nodes]
457
489
        if self.reference_lists:
458
490
            for key in local_keys:
459
 
                node = self._nodes[key]
 
491
                node = nodes[key]
460
492
                yield self, key, node[1], node[0]
461
493
        else:
462
494
            for key in local_keys:
463
 
                node = self._nodes[key]
 
495
                node = nodes[key]
464
496
                yield self, key, node[1]
465
497
        # Find things that are in backing indices that have not been handled
466
498
        # yet.
549
581
                    else:
550
582
                        # yield keys
551
583
                        for value in key_dict.itervalues():
552
 
                            yield (self, ) + value
 
584
                            yield (self, ) + tuple(value)
553
585
            else:
554
586
                yield (self, ) + key_dict
555
587
 
576
608
 
577
609
        For InMemoryGraphIndex the estimate is exact.
578
610
        """
579
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
611
        return len(self._nodes) + sum(backing.key_count() for backing in
580
612
            self._backing_indices if backing is not None)
581
613
 
582
614
    def validate(self):
583
615
        """In memory index's have no known corruption at the moment."""
584
616
 
585
617
 
586
 
class _LeafNode(object):
 
618
class _LeafNode(dict):
587
619
    """A leaf node for a serialised B+Tree index."""
588
620
 
589
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
621
    __slots__ = ('min_key', 'max_key', '_keys')
590
622
 
591
623
    def __init__(self, bytes, key_length, ref_list_length):
592
624
        """Parse bytes to create a leaf node object."""
598
630
            self.max_key = key_list[-1][0]
599
631
        else:
600
632
            self.min_key = self.max_key = None
601
 
        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
602
647
 
603
648
 
604
649
class _InternalNode(object):
614
659
    def _parse_lines(self, lines):
615
660
        nodes = []
616
661
        self.offset = int(lines[1][7:])
 
662
        as_st = static_tuple.StaticTuple.from_sequence
617
663
        for line in lines[2:]:
618
664
            if line == '':
619
665
                break
620
 
            nodes.append(tuple(map(intern, line.split('\0'))))
 
666
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
621
667
        return nodes
622
668
 
623
669
 
628
674
    memory except when very large walks are done.
629
675
    """
630
676
 
631
 
    def __init__(self, transport, name, size):
 
677
    def __init__(self, transport, name, size, unlimited_cache=False,
 
678
                 offset=0):
632
679
        """Create a B+Tree index object on the index name.
633
680
 
634
681
        :param transport: The transport to read data for the index from.
638
685
            the initial read (to read the root node header) can be done
639
686
            without over-reading even on empty indices, and on small indices
640
687
            allows single-IO to read the entire index.
 
688
        :param unlimited_cache: If set to True, then instead of using an
 
689
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
 
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.
641
693
        """
642
694
        self._transport = transport
643
695
        self._name = name
645
697
        self._file = None
646
698
        self._recommended_pages = self._compute_recommended_pages()
647
699
        self._root_node = None
 
700
        self._base_offset = offset
 
701
        self._leaf_factory = _LeafNode
648
702
        # Default max size is 100,000 leave values
649
703
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
650
 
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
651
 
        # We could limit this, but even a 300k record btree has only 3k leaf
652
 
        # nodes, and only 20 internal nodes. So the default of 100 nodes in an
653
 
        # LRU would mean we always cache everything anyway, no need to pay the
654
 
        # overhead of LRU
655
 
        self._internal_node_cache = fifo_cache.FIFOCache(100)
 
704
        if unlimited_cache:
 
705
            self._leaf_node_cache = {}
 
706
            self._internal_node_cache = {}
 
707
        else:
 
708
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
709
            # We use a FIFO here just to prevent possible blowout. However, a
 
710
            # 300k record btree has only 3k leaf nodes, and only 20 internal
 
711
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
 
712
            self._internal_node_cache = fifo_cache.FIFOCache(100)
656
713
        self._key_count = None
657
714
        self._row_lengths = None
658
715
        self._row_offsets = None # Start of each row, [-1] is the end
690
747
                if start_of_leaves is None:
691
748
                    start_of_leaves = self._row_offsets[-2]
692
749
                if node_pos < start_of_leaves:
693
 
                    self._internal_node_cache.add(node_pos, node)
 
750
                    self._internal_node_cache[node_pos] = node
694
751
                else:
695
 
                    self._leaf_node_cache.add(node_pos, node)
 
752
                    self._leaf_node_cache[node_pos] = node
696
753
            found[node_pos] = node
697
754
        return found
698
755
 
837
894
            new_tips = next_tips
838
895
        return final_offsets
839
896
 
 
897
    def clear_cache(self):
 
898
        """Clear out any cached/memoized values.
 
899
 
 
900
        This can be called at any time, but generally it is used when we have
 
901
        extracted some information, but don't expect to be requesting any more
 
902
        from this index.
 
903
        """
 
904
        # Note that we don't touch self._root_node or self._internal_node_cache
 
905
        # We don't expect either of those to be big, and it can save
 
906
        # round-trips in the future. We may re-evaluate this if InternalNode
 
907
        # memory starts to be an issue.
 
908
        self._leaf_node_cache.clear()
 
909
 
840
910
    def external_references(self, ref_list_num):
841
911
        if self._root_node is None:
842
912
            self._get_root_node()
907
977
        """Cache directly from key => value, skipping the btree."""
908
978
        if self._leaf_value_cache is not None:
909
979
            for node in nodes.itervalues():
910
 
                for key, value in node.keys.iteritems():
 
980
                for key, value in node.all_items():
911
981
                    if key in self._leaf_value_cache:
912
982
                        # Don't add the rest of the keys, we've seen this node
913
983
                        # before.
937
1007
        if self._row_offsets[-1] == 1:
938
1008
            # There is only the root node, and we read that via key_count()
939
1009
            if self.node_ref_lists:
940
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1010
                for key, (value, refs) in self._root_node.all_items():
941
1011
                    yield (self, key, value, refs)
942
1012
            else:
943
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1013
                for key, (value, refs) in self._root_node.all_items():
944
1014
                    yield (self, key, value)
945
1015
            return
946
1016
        start_of_leaves = self._row_offsets[-2]
956
1026
        # for spilling index builds to disk.
957
1027
        if self.node_ref_lists:
958
1028
            for _, node in nodes:
959
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1029
                for key, (value, refs) in node.all_items():
960
1030
                    yield (self, key, value, refs)
961
1031
        else:
962
1032
            for _, node in nodes:
963
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1033
                for key, (value, refs) in node.all_items():
964
1034
                    yield (self, key, value)
965
1035
 
966
1036
    @staticmethod
990
1060
        # iter_steps = len(in_keys) + len(fixed_keys)
991
1061
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
992
1062
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
993
 
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
1063
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
994
1064
        # elif bisect_steps < iter_steps:
995
1065
        #     offsets = {}
996
1066
        #     for key in in_keys:
1127
1197
                continue
1128
1198
            node = nodes[node_index]
1129
1199
            for next_sub_key in sub_keys:
1130
 
                if next_sub_key in node.keys:
1131
 
                    value, refs = node.keys[next_sub_key]
 
1200
                if next_sub_key in node:
 
1201
                    value, refs = node[next_sub_key]
1132
1202
                    if self.node_ref_lists:
1133
1203
                        yield (self, next_sub_key, value, refs)
1134
1204
                    else:
1202
1272
            # sub_keys is all of the keys we are looking for that should exist
1203
1273
            # on this page, if they aren't here, then they won't be found
1204
1274
            node = nodes[node_index]
1205
 
            node_keys = node.keys
1206
1275
            parents_to_check = set()
1207
1276
            for next_sub_key in sub_keys:
1208
 
                if next_sub_key not in node_keys:
 
1277
                if next_sub_key not in node:
1209
1278
                    # This one is just not present in the index at all
1210
1279
                    missing_keys.add(next_sub_key)
1211
1280
                else:
1212
 
                    value, refs = node_keys[next_sub_key]
 
1281
                    value, refs = node[next_sub_key]
1213
1282
                    parent_keys = refs[ref_list_num]
1214
1283
                    parent_map[next_sub_key] = parent_keys
1215
1284
                    parents_to_check.update(parent_keys)
1222
1291
            while parents_to_check:
1223
1292
                next_parents_to_check = set()
1224
1293
                for key in parents_to_check:
1225
 
                    if key in node_keys:
1226
 
                        value, refs = node_keys[key]
 
1294
                    if key in node:
 
1295
                        value, refs = node[key]
1227
1296
                        parent_keys = refs[ref_list_num]
1228
1297
                        parent_map[key] = parent_keys
1229
1298
                        next_parents_to_check.update(parent_keys)
1456
1525
        # list of (offset, length) regions of the file that should, evenually
1457
1526
        # be read in to data_ranges, either from 'bytes' or from the transport
1458
1527
        ranges = []
 
1528
        base_offset = self._base_offset
1459
1529
        for index in nodes:
1460
 
            offset = index * _PAGE_SIZE
 
1530
            offset = (index * _PAGE_SIZE)
1461
1531
            size = _PAGE_SIZE
1462
1532
            if index == 0:
1463
1533
                # Root node - special case
1467
1537
                    # The only case where we don't know the size, is for very
1468
1538
                    # small indexes. So we read the whole thing
1469
1539
                    bytes = self._transport.get_bytes(self._name)
1470
 
                    self._size = len(bytes)
 
1540
                    num_bytes = len(bytes)
 
1541
                    self._size = num_bytes - base_offset
1471
1542
                    # the whole thing should be parsed out of 'bytes'
1472
 
                    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)]
1473
1545
                    break
1474
1546
            else:
1475
1547
                if offset > self._size:
1477
1549
                                         ' of the file %s > %s'
1478
1550
                                         % (offset, self._size))
1479
1551
                size = min(size, self._size - offset)
1480
 
            ranges.append((offset, size))
 
1552
            ranges.append((base_offset + offset, size))
1481
1553
        if not ranges:
1482
1554
            return
1483
1555
        elif bytes is not None:
1484
1556
            # already have the whole file
1485
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1486
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1557
            data_ranges = [(start, bytes[start:start+size])
 
1558
                           for start, size in ranges]
1487
1559
        elif self._file is None:
1488
1560
            data_ranges = self._transport.readv(self._name, ranges)
1489
1561
        else:
1492
1564
                self._file.seek(offset)
1493
1565
                data_ranges.append((offset, self._file.read(size)))
1494
1566
        for offset, data in data_ranges:
 
1567
            offset -= base_offset
1495
1568
            if offset == 0:
1496
1569
                # extract the header
1497
1570
                offset, data = self._parse_header_from_bytes(data)
1499
1572
                    continue
1500
1573
            bytes = zlib.decompress(data)
1501
1574
            if bytes.startswith(_LEAF_FLAG):
1502
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1575
                node = self._leaf_factory(bytes, self._key_length,
 
1576
                                          self.node_ref_lists)
1503
1577
            elif bytes.startswith(_INTERNAL_FLAG):
1504
1578
                node = _InternalNode(bytes)
1505
1579
            else:
1524
1598
            pass
1525
1599
 
1526
1600
 
 
1601
_gcchk_factory = _LeafNode
 
1602
 
1527
1603
try:
1528
1604
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1529
 
except ImportError:
 
1605
    _gcchk_factory = _btree_serializer._parse_into_chk
 
1606
except ImportError, e:
 
1607
    osutils.failed_to_load_extension(e)
1530
1608
    from bzrlib import _btree_serializer_py as _btree_serializer