← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-10-13 06:08:53 UTC
  • mfrom: (4737.1.1 merge-2.0-into-devel)
  • Revision ID: pqm@pqm.ubuntu.com-20091013060853-erk2aaj80fnkrv25
(andrew) Merge lp:bzr/2.0 into lp:bzr, including fixes for #322807,
        #389413, #402623 and documentation improvements.

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 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,
37
31
    index,
38
32
    lru_cache,
39
33
    osutils,
40
 
    static_tuple,
41
34
    trace,
42
 
    transport,
43
35
    )
44
36
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
37
from bzrlib.transport import get_transport
45
38
 
46
39
 
47
40
_BTSIGNATURE = "B+Tree Graph Index 2\n"
164
157
        :param references: An iterable of iterables of keys. Each is a
165
158
            reference to another key.
166
159
        :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.
 
160
            bytes as long as it does not contain \0 or \n.
168
161
        """
169
 
        # Ensure that 'key' is a StaticTuple
170
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
171
162
        # we don't care about absent_references
172
163
        node_refs, _ = self._check_key_ref_value(key, references, value)
173
164
        if key in self._nodes:
174
165
            raise errors.BadIndexDuplicateKey(key, self)
175
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
166
        self._nodes[key] = (node_refs, value)
 
167
        self._keys.add(key)
176
168
        if self._nodes_by_key is not None and self._key_length > 1:
177
169
            self._update_nodes_by_key(key, value, node_refs)
178
 
        if len(self._nodes) < self._spill_at:
 
170
        if len(self._keys) < self._spill_at:
179
171
            return
180
172
        self._spill_mem_keys_to_disk()
181
173
 
199
191
            new_backing_file, size = self._spill_mem_keys_without_combining()
200
192
        # Note: The transport here isn't strictly needed, because we will use
201
193
        #       direct access to the new_backing._file object
202
 
        new_backing = BTreeGraphIndex(transport.get_transport_from_path('.'),
203
 
                                      '<temp>', size)
 
194
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
204
195
        # GC will clean up the file
205
196
        new_backing._file = new_backing_file
206
197
        if self._combine_backing_indices:
211
202
                self._backing_indices[backing_pos] = None
212
203
        else:
213
204
            self._backing_indices.append(new_backing)
 
205
        self._keys = set()
214
206
        self._nodes = {}
215
207
        self._nodes_by_key = None
216
208
 
296
288
            flag when writing out. This is used by the _spill_mem_keys_to_disk
297
289
            functionality.
298
290
        """
299
 
        new_leaf = False
300
291
        if rows[-1].writer is None:
301
292
            # opening a new leaf chunk;
302
 
            new_leaf = True
303
293
            for pos, internal_row in enumerate(rows[:-1]):
304
294
                # flesh out any internal nodes that are needed to
305
295
                # preserve the height of the tree
324
314
                optimize_for_size=self._optimize_for_size)
325
315
            rows[-1].writer.write(_LEAF_FLAG)
326
316
        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
317
            # this key did not fit in the node:
333
318
            rows[-1].finish_node()
334
319
            key_line = string_key + "\n"
425
410
            # Special case the first node as it may be prefixed
426
411
            node = row.spool.read(_PAGE_SIZE)
427
412
            result.write(node[reserved:])
428
 
            if len(node) == _PAGE_SIZE:
429
 
                result.write("\x00" * (reserved - position))
 
413
            result.write("\x00" * (reserved - position))
430
414
            position = 0 # Only the root row actually has an offset
431
415
            copied_len = osutils.pumpfile(row.spool, result)
432
416
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
477
461
            efficient order for the index (keys iteration order in this case).
478
462
        """
479
463
        keys = set(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]
 
464
        local_keys = keys.intersection(self._keys)
489
465
        if self.reference_lists:
490
466
            for key in local_keys:
491
 
                node = nodes[key]
 
467
                node = self._nodes[key]
492
468
                yield self, key, node[1], node[0]
493
469
        else:
494
470
            for key in local_keys:
495
 
                node = nodes[key]
 
471
                node = self._nodes[key]
496
472
                yield self, key, node[1]
497
473
        # Find things that are in backing indices that have not been handled
498
474
        # yet.
581
557
                    else:
582
558
                        # yield keys
583
559
                        for value in key_dict.itervalues():
584
 
                            yield (self, ) + tuple(value)
 
560
                            yield (self, ) + value
585
561
            else:
586
562
                yield (self, ) + key_dict
587
563
 
608
584
 
609
585
        For InMemoryGraphIndex the estimate is exact.
610
586
        """
611
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
587
        return len(self._keys) + sum(backing.key_count() for backing in
612
588
            self._backing_indices if backing is not None)
613
589
 
614
590
    def validate(self):
615
591
        """In memory index's have no known corruption at the moment."""
616
592
 
617
593
 
618
 
class _LeafNode(dict):
 
594
class _LeafNode(object):
619
595
    """A leaf node for a serialised B+Tree index."""
620
596
 
621
 
    __slots__ = ('min_key', 'max_key', '_keys')
 
597
    __slots__ = ('keys', 'min_key', 'max_key')
622
598
 
623
599
    def __init__(self, bytes, key_length, ref_list_length):
624
600
        """Parse bytes to create a leaf node object."""
630
606
            self.max_key = key_list[-1][0]
631
607
        else:
632
608
            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
 
609
        self.keys = dict(key_list)
647
610
 
648
611
 
649
612
class _InternalNode(object):
659
622
    def _parse_lines(self, lines):
660
623
        nodes = []
661
624
        self.offset = int(lines[1][7:])
662
 
        as_st = static_tuple.StaticTuple.from_sequence
663
625
        for line in lines[2:]:
664
626
            if line == '':
665
627
                break
666
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
628
            nodes.append(tuple(map(intern, line.split('\0'))))
667
629
        return nodes
668
630
 
669
631
 
674
636
    memory except when very large walks are done.
675
637
    """
676
638
 
677
 
    def __init__(self, transport, name, size, unlimited_cache=False,
678
 
                 offset=0):
 
639
    def __init__(self, transport, name, size, unlimited_cache=False):
679
640
        """Create a B+Tree index object on the index name.
680
641
 
681
642
        :param transport: The transport to read data for the index from.
688
649
        :param unlimited_cache: If set to True, then instead of using an
689
650
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
690
651
            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.
693
652
        """
694
653
        self._transport = transport
695
654
        self._name = name
697
656
        self._file = None
698
657
        self._recommended_pages = self._compute_recommended_pages()
699
658
        self._root_node = None
700
 
        self._base_offset = offset
701
 
        self._leaf_factory = _LeafNode
702
659
        # Default max size is 100,000 leave values
703
660
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
704
661
        if unlimited_cache:
894
851
            new_tips = next_tips
895
852
        return final_offsets
896
853
 
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
 
 
910
854
    def external_references(self, ref_list_num):
911
855
        if self._root_node is None:
912
856
            self._get_root_node()
977
921
        """Cache directly from key => value, skipping the btree."""
978
922
        if self._leaf_value_cache is not None:
979
923
            for node in nodes.itervalues():
980
 
                for key, value in node.all_items():
 
924
                for key, value in node.keys.iteritems():
981
925
                    if key in self._leaf_value_cache:
982
926
                        # Don't add the rest of the keys, we've seen this node
983
927
                        # before.
1007
951
        if self._row_offsets[-1] == 1:
1008
952
            # There is only the root node, and we read that via key_count()
1009
953
            if self.node_ref_lists:
1010
 
                for key, (value, refs) in self._root_node.all_items():
 
954
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1011
955
                    yield (self, key, value, refs)
1012
956
            else:
1013
 
                for key, (value, refs) in self._root_node.all_items():
 
957
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1014
958
                    yield (self, key, value)
1015
959
            return
1016
960
        start_of_leaves = self._row_offsets[-2]
1026
970
        # for spilling index builds to disk.
1027
971
        if self.node_ref_lists:
1028
972
            for _, node in nodes:
1029
 
                for key, (value, refs) in node.all_items():
 
973
                for key, (value, refs) in sorted(node.keys.items()):
1030
974
                    yield (self, key, value, refs)
1031
975
        else:
1032
976
            for _, node in nodes:
1033
 
                for key, (value, refs) in node.all_items():
 
977
                for key, (value, refs) in sorted(node.keys.items()):
1034
978
                    yield (self, key, value)
1035
979
 
1036
980
    @staticmethod
1060
1004
        # iter_steps = len(in_keys) + len(fixed_keys)
1061
1005
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1062
1006
        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)]
 
1007
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1064
1008
        # elif bisect_steps < iter_steps:
1065
1009
        #     offsets = {}
1066
1010
        #     for key in in_keys:
1197
1141
                continue
1198
1142
            node = nodes[node_index]
1199
1143
            for next_sub_key in sub_keys:
1200
 
                if next_sub_key in node:
1201
 
                    value, refs = node[next_sub_key]
 
1144
                if next_sub_key in node.keys:
 
1145
                    value, refs = node.keys[next_sub_key]
1202
1146
                    if self.node_ref_lists:
1203
1147
                        yield (self, next_sub_key, value, refs)
1204
1148
                    else:
1272
1216
            # sub_keys is all of the keys we are looking for that should exist
1273
1217
            # on this page, if they aren't here, then they won't be found
1274
1218
            node = nodes[node_index]
 
1219
            node_keys = node.keys
1275
1220
            parents_to_check = set()
1276
1221
            for next_sub_key in sub_keys:
1277
 
                if next_sub_key not in node:
 
1222
                if next_sub_key not in node_keys:
1278
1223
                    # This one is just not present in the index at all
1279
1224
                    missing_keys.add(next_sub_key)
1280
1225
                else:
1281
 
                    value, refs = node[next_sub_key]
 
1226
                    value, refs = node_keys[next_sub_key]
1282
1227
                    parent_keys = refs[ref_list_num]
1283
1228
                    parent_map[next_sub_key] = parent_keys
1284
1229
                    parents_to_check.update(parent_keys)
1291
1236
            while parents_to_check:
1292
1237
                next_parents_to_check = set()
1293
1238
                for key in parents_to_check:
1294
 
                    if key in node:
1295
 
                        value, refs = node[key]
 
1239
                    if key in node_keys:
 
1240
                        value, refs = node_keys[key]
1296
1241
                        parent_keys = refs[ref_list_num]
1297
1242
                        parent_map[key] = parent_keys
1298
1243
                        next_parents_to_check.update(parent_keys)
1525
1470
        # list of (offset, length) regions of the file that should, evenually
1526
1471
        # be read in to data_ranges, either from 'bytes' or from the transport
1527
1472
        ranges = []
1528
 
        base_offset = self._base_offset
1529
1473
        for index in nodes:
1530
 
            offset = (index * _PAGE_SIZE)
 
1474
            offset = index * _PAGE_SIZE
1531
1475
            size = _PAGE_SIZE
1532
1476
            if index == 0:
1533
1477
                # Root node - special case
1537
1481
                    # The only case where we don't know the size, is for very
1538
1482
                    # small indexes. So we read the whole thing
1539
1483
                    bytes = self._transport.get_bytes(self._name)
1540
 
                    num_bytes = len(bytes)
1541
 
                    self._size = num_bytes - base_offset
 
1484
                    self._size = len(bytes)
1542
1485
                    # the whole thing should be parsed out of 'bytes'
1543
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1544
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1486
                    ranges.append((0, len(bytes)))
1545
1487
                    break
1546
1488
            else:
1547
1489
                if offset > self._size:
1549
1491
                                         ' of the file %s > %s'
1550
1492
                                         % (offset, self._size))
1551
1493
                size = min(size, self._size - offset)
1552
 
            ranges.append((base_offset + offset, size))
 
1494
            ranges.append((offset, size))
1553
1495
        if not ranges:
1554
1496
            return
1555
1497
        elif bytes is not None:
1556
1498
            # already have the whole file
1557
 
            data_ranges = [(start, bytes[start:start+size])
1558
 
                           for start, size in ranges]
 
1499
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1500
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1559
1501
        elif self._file is None:
1560
1502
            data_ranges = self._transport.readv(self._name, ranges)
1561
1503
        else:
1564
1506
                self._file.seek(offset)
1565
1507
                data_ranges.append((offset, self._file.read(size)))
1566
1508
        for offset, data in data_ranges:
1567
 
            offset -= base_offset
1568
1509
            if offset == 0:
1569
1510
                # extract the header
1570
1511
                offset, data = self._parse_header_from_bytes(data)
1572
1513
                    continue
1573
1514
            bytes = zlib.decompress(data)
1574
1515
            if bytes.startswith(_LEAF_FLAG):
1575
 
                node = self._leaf_factory(bytes, self._key_length,
1576
 
                                          self.node_ref_lists)
 
1516
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1577
1517
            elif bytes.startswith(_INTERNAL_FLAG):
1578
1518
                node = _InternalNode(bytes)
1579
1519
            else:
1598
1538
            pass
1599
1539
 
1600
1540
 
1601
 
_gcchk_factory = _LeafNode
1602
 
 
1603
1541
try:
1604
1542
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1605
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1606
1543
except ImportError, e:
1607
1544
    osutils.failed_to_load_extension(e)
1608
1545
    from bzrlib import _btree_serializer_py as _btree_serializer