← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Andrew Bennetts
  • Date: 2009-10-08 01:55:33 UTC
  • mto: This revision was merged to the branch mainline in revision 4732.
  • Revision ID: andrew.bennetts@canonical.com-20091008015533-pfzig4dpr3kqt2cc
Add NEWS entry.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
1
 
# Copyright (C) 2008, 2009, 2010 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
31
31
    index,
32
32
    lru_cache,
33
33
    osutils,
34
 
    static_tuple,
35
34
    trace,
36
 
    transport,
37
35
    )
38
36
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
37
from bzrlib.transport import get_transport
39
38
 
40
39
 
41
40
_BTSIGNATURE = "B+Tree Graph Index 2\n"
160
159
        :param value: The value to associate with the key. It may be any
161
160
            bytes as long as it does not contain \0 or \n.
162
161
        """
163
 
        # Ensure that 'key' is a StaticTuple
164
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
165
162
        # we don't care about absent_references
166
163
        node_refs, _ = self._check_key_ref_value(key, references, value)
167
164
        if key in self._nodes:
168
165
            raise errors.BadIndexDuplicateKey(key, self)
169
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
166
        self._nodes[key] = (node_refs, value)
 
167
        self._keys.add(key)
170
168
        if self._nodes_by_key is not None and self._key_length > 1:
171
169
            self._update_nodes_by_key(key, value, node_refs)
172
 
        if len(self._nodes) < self._spill_at:
 
170
        if len(self._keys) < self._spill_at:
173
171
            return
174
172
        self._spill_mem_keys_to_disk()
175
173
 
193
191
            new_backing_file, size = self._spill_mem_keys_without_combining()
194
192
        # Note: The transport here isn't strictly needed, because we will use
195
193
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
197
 
                                      '<temp>', size)
 
194
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
198
195
        # GC will clean up the file
199
196
        new_backing._file = new_backing_file
200
197
        if self._combine_backing_indices:
205
202
                self._backing_indices[backing_pos] = None
206
203
        else:
207
204
            self._backing_indices.append(new_backing)
 
205
        self._keys = set()
208
206
        self._nodes = {}
209
207
        self._nodes_by_key = None
210
208
 
412
410
            # Special case the first node as it may be prefixed
413
411
            node = row.spool.read(_PAGE_SIZE)
414
412
            result.write(node[reserved:])
415
 
            if len(node) == _PAGE_SIZE:
416
 
                result.write("\x00" * (reserved - position))
 
413
            result.write("\x00" * (reserved - position))
417
414
            position = 0 # Only the root row actually has an offset
418
415
            copied_len = osutils.pumpfile(row.spool, result)
419
416
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
464
461
            efficient order for the index (keys iteration order in this case).
465
462
        """
466
463
        keys = set(keys)
467
 
        # Note: We don't use keys.intersection() here. If you read the C api,
468
 
        #       set.intersection(other) special cases when other is a set and
469
 
        #       will iterate the smaller of the two and lookup in the other.
470
 
        #       It does *not* do this for any other type (even dict, unlike
471
 
        #       some other set functions.) Since we expect keys is generally <<
472
 
        #       self._nodes, it is faster to iterate over it in a list
473
 
        #       comprehension
474
 
        nodes = self._nodes
475
 
        local_keys = [key for key in keys if key in nodes]
 
464
        local_keys = keys.intersection(self._keys)
476
465
        if self.reference_lists:
477
466
            for key in local_keys:
478
 
                node = nodes[key]
 
467
                node = self._nodes[key]
479
468
                yield self, key, node[1], node[0]
480
469
        else:
481
470
            for key in local_keys:
482
 
                node = nodes[key]
 
471
                node = self._nodes[key]
483
472
                yield self, key, node[1]
484
473
        # Find things that are in backing indices that have not been handled
485
474
        # yet.
568
557
                    else:
569
558
                        # yield keys
570
559
                        for value in key_dict.itervalues():
571
 
                            yield (self, ) + tuple(value)
 
560
                            yield (self, ) + value
572
561
            else:
573
562
                yield (self, ) + key_dict
574
563
 
595
584
 
596
585
        For InMemoryGraphIndex the estimate is exact.
597
586
        """
598
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
587
        return len(self._keys) + sum(backing.key_count() for backing in
599
588
            self._backing_indices if backing is not None)
600
589
 
601
590
    def validate(self):
602
591
        """In memory index's have no known corruption at the moment."""
603
592
 
604
593
 
605
 
class _LeafNode(dict):
 
594
class _LeafNode(object):
606
595
    """A leaf node for a serialised B+Tree index."""
607
596
 
608
 
    __slots__ = ('min_key', 'max_key', '_keys')
 
597
    __slots__ = ('keys', 'min_key', 'max_key')
609
598
 
610
599
    def __init__(self, bytes, key_length, ref_list_length):
611
600
        """Parse bytes to create a leaf node object."""
617
606
            self.max_key = key_list[-1][0]
618
607
        else:
619
608
            self.min_key = self.max_key = None
620
 
        super(_LeafNode, self).__init__(key_list)
621
 
        self._keys = dict(self)
622
 
 
623
 
    def all_items(self):
624
 
        """Return a sorted list of (key, (value, refs)) items"""
625
 
        items = self.items()
626
 
        items.sort()
627
 
        return items
628
 
 
629
 
    def all_keys(self):
630
 
        """Return a sorted list of all keys."""
631
 
        keys = self.keys()
632
 
        keys.sort()
633
 
        return keys
 
609
        self.keys = dict(key_list)
634
610
 
635
611
 
636
612
class _InternalNode(object):
646
622
    def _parse_lines(self, lines):
647
623
        nodes = []
648
624
        self.offset = int(lines[1][7:])
649
 
        as_st = static_tuple.StaticTuple.from_sequence
650
625
        for line in lines[2:]:
651
626
            if line == '':
652
627
                break
653
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
628
            nodes.append(tuple(map(intern, line.split('\0'))))
654
629
        return nodes
655
630
 
656
631
 
661
636
    memory except when very large walks are done.
662
637
    """
663
638
 
664
 
    def __init__(self, transport, name, size, unlimited_cache=False,
665
 
                 offset=0):
 
639
    def __init__(self, transport, name, size):
666
640
        """Create a B+Tree index object on the index name.
667
641
 
668
642
        :param transport: The transport to read data for the index from.
672
646
            the initial read (to read the root node header) can be done
673
647
            without over-reading even on empty indices, and on small indices
674
648
            allows single-IO to read the entire index.
675
 
        :param unlimited_cache: If set to True, then instead of using an
676
 
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
677
 
            cache all leaf nodes.
678
 
        :param offset: The start of the btree index data isn't byte 0 of the
679
 
            file. Instead it starts at some point later.
680
649
        """
681
650
        self._transport = transport
682
651
        self._name = name
684
653
        self._file = None
685
654
        self._recommended_pages = self._compute_recommended_pages()
686
655
        self._root_node = None
687
 
        self._base_offset = offset
688
 
        self._leaf_factory = _LeafNode
689
656
        # Default max size is 100,000 leave values
690
657
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
691
 
        if unlimited_cache:
692
 
            self._leaf_node_cache = {}
693
 
            self._internal_node_cache = {}
694
 
        else:
695
 
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
696
 
            # We use a FIFO here just to prevent possible blowout. However, a
697
 
            # 300k record btree has only 3k leaf nodes, and only 20 internal
698
 
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
699
 
            self._internal_node_cache = fifo_cache.FIFOCache(100)
 
658
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
659
        # We could limit this, but even a 300k record btree has only 3k leaf
 
660
        # nodes, and only 20 internal nodes. So the default of 100 nodes in an
 
661
        # LRU would mean we always cache everything anyway, no need to pay the
 
662
        # overhead of LRU
 
663
        self._internal_node_cache = fifo_cache.FIFOCache(100)
700
664
        self._key_count = None
701
665
        self._row_lengths = None
702
666
        self._row_offsets = None # Start of each row, [-1] is the end
734
698
                if start_of_leaves is None:
735
699
                    start_of_leaves = self._row_offsets[-2]
736
700
                if node_pos < start_of_leaves:
737
 
                    self._internal_node_cache[node_pos] = node
 
701
                    self._internal_node_cache.add(node_pos, node)
738
702
                else:
739
 
                    self._leaf_node_cache[node_pos] = node
 
703
                    self._leaf_node_cache.add(node_pos, node)
740
704
            found[node_pos] = node
741
705
        return found
742
706
 
881
845
            new_tips = next_tips
882
846
        return final_offsets
883
847
 
884
 
    def clear_cache(self):
885
 
        """Clear out any cached/memoized values.
886
 
 
887
 
        This can be called at any time, but generally it is used when we have
888
 
        extracted some information, but don't expect to be requesting any more
889
 
        from this index.
890
 
        """
891
 
        # Note that we don't touch self._root_node or self._internal_node_cache
892
 
        # We don't expect either of those to be big, and it can save
893
 
        # round-trips in the future. We may re-evaluate this if InternalNode
894
 
        # memory starts to be an issue.
895
 
        self._leaf_node_cache.clear()
896
 
 
897
848
    def external_references(self, ref_list_num):
898
849
        if self._root_node is None:
899
850
            self._get_root_node()
964
915
        """Cache directly from key => value, skipping the btree."""
965
916
        if self._leaf_value_cache is not None:
966
917
            for node in nodes.itervalues():
967
 
                for key, value in node.all_items():
 
918
                for key, value in node.keys.iteritems():
968
919
                    if key in self._leaf_value_cache:
969
920
                        # Don't add the rest of the keys, we've seen this node
970
921
                        # before.
994
945
        if self._row_offsets[-1] == 1:
995
946
            # There is only the root node, and we read that via key_count()
996
947
            if self.node_ref_lists:
997
 
                for key, (value, refs) in self._root_node.all_items():
 
948
                for key, (value, refs) in sorted(self._root_node.keys.items()):
998
949
                    yield (self, key, value, refs)
999
950
            else:
1000
 
                for key, (value, refs) in self._root_node.all_items():
 
951
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1001
952
                    yield (self, key, value)
1002
953
            return
1003
954
        start_of_leaves = self._row_offsets[-2]
1013
964
        # for spilling index builds to disk.
1014
965
        if self.node_ref_lists:
1015
966
            for _, node in nodes:
1016
 
                for key, (value, refs) in node.all_items():
 
967
                for key, (value, refs) in sorted(node.keys.items()):
1017
968
                    yield (self, key, value, refs)
1018
969
        else:
1019
970
            for _, node in nodes:
1020
 
                for key, (value, refs) in node.all_items():
 
971
                for key, (value, refs) in sorted(node.keys.items()):
1021
972
                    yield (self, key, value)
1022
973
 
1023
974
    @staticmethod
1184
1135
                continue
1185
1136
            node = nodes[node_index]
1186
1137
            for next_sub_key in sub_keys:
1187
 
                if next_sub_key in node:
1188
 
                    value, refs = node[next_sub_key]
 
1138
                if next_sub_key in node.keys:
 
1139
                    value, refs = node.keys[next_sub_key]
1189
1140
                    if self.node_ref_lists:
1190
1141
                        yield (self, next_sub_key, value, refs)
1191
1142
                    else:
1259
1210
            # sub_keys is all of the keys we are looking for that should exist
1260
1211
            # on this page, if they aren't here, then they won't be found
1261
1212
            node = nodes[node_index]
 
1213
            node_keys = node.keys
1262
1214
            parents_to_check = set()
1263
1215
            for next_sub_key in sub_keys:
1264
 
                if next_sub_key not in node:
 
1216
                if next_sub_key not in node_keys:
1265
1217
                    # This one is just not present in the index at all
1266
1218
                    missing_keys.add(next_sub_key)
1267
1219
                else:
1268
 
                    value, refs = node[next_sub_key]
 
1220
                    value, refs = node_keys[next_sub_key]
1269
1221
                    parent_keys = refs[ref_list_num]
1270
1222
                    parent_map[next_sub_key] = parent_keys
1271
1223
                    parents_to_check.update(parent_keys)
1278
1230
            while parents_to_check:
1279
1231
                next_parents_to_check = set()
1280
1232
                for key in parents_to_check:
1281
 
                    if key in node:
1282
 
                        value, refs = node[key]
 
1233
                    if key in node_keys:
 
1234
                        value, refs = node_keys[key]
1283
1235
                        parent_keys = refs[ref_list_num]
1284
1236
                        parent_map[key] = parent_keys
1285
1237
                        next_parents_to_check.update(parent_keys)
1512
1464
        # list of (offset, length) regions of the file that should, evenually
1513
1465
        # be read in to data_ranges, either from 'bytes' or from the transport
1514
1466
        ranges = []
1515
 
        base_offset = self._base_offset
1516
1467
        for index in nodes:
1517
 
            offset = (index * _PAGE_SIZE)
 
1468
            offset = index * _PAGE_SIZE
1518
1469
            size = _PAGE_SIZE
1519
1470
            if index == 0:
1520
1471
                # Root node - special case
1524
1475
                    # The only case where we don't know the size, is for very
1525
1476
                    # small indexes. So we read the whole thing
1526
1477
                    bytes = self._transport.get_bytes(self._name)
1527
 
                    num_bytes = len(bytes)
1528
 
                    self._size = num_bytes - base_offset
 
1478
                    self._size = len(bytes)
1529
1479
                    # the whole thing should be parsed out of 'bytes'
1530
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1531
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1480
                    ranges.append((0, len(bytes)))
1532
1481
                    break
1533
1482
            else:
1534
1483
                if offset > self._size:
1536
1485
                                         ' of the file %s > %s'
1537
1486
                                         % (offset, self._size))
1538
1487
                size = min(size, self._size - offset)
1539
 
            ranges.append((base_offset + offset, size))
 
1488
            ranges.append((offset, size))
1540
1489
        if not ranges:
1541
1490
            return
1542
1491
        elif bytes is not None:
1543
1492
            # already have the whole file
1544
 
            data_ranges = [(start, bytes[start:start+size])
1545
 
                           for start, size in ranges]
 
1493
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1494
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1546
1495
        elif self._file is None:
1547
1496
            data_ranges = self._transport.readv(self._name, ranges)
1548
1497
        else:
1551
1500
                self._file.seek(offset)
1552
1501
                data_ranges.append((offset, self._file.read(size)))
1553
1502
        for offset, data in data_ranges:
1554
 
            offset -= base_offset
1555
1503
            if offset == 0:
1556
1504
                # extract the header
1557
1505
                offset, data = self._parse_header_from_bytes(data)
1559
1507
                    continue
1560
1508
            bytes = zlib.decompress(data)
1561
1509
            if bytes.startswith(_LEAF_FLAG):
1562
 
                node = self._leaf_factory(bytes, self._key_length,
1563
 
                                          self.node_ref_lists)
 
1510
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1564
1511
            elif bytes.startswith(_INTERNAL_FLAG):
1565
1512
                node = _InternalNode(bytes)
1566
1513
            else:
1585
1532
            pass
1586
1533
 
1587
1534
 
1588
 
_gcchk_factory = _LeafNode
1589
 
 
1590
1535
try:
1591
1536
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1592
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1593
1537
except ImportError, e:
1594
1538
    osutils.failed_to_load_extension(e)
1595
1539
    from bzrlib import _btree_serializer_py as _btree_serializer