← 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: 2010-09-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

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, 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
31
31
    index,
32
32
    lru_cache,
33
33
    osutils,
 
34
    static_tuple,
34
35
    trace,
 
36
    transport,
35
37
    )
36
38
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
37
 
from bzrlib.transport import get_transport
38
39
 
39
40
 
40
41
_BTSIGNATURE = "B+Tree Graph Index 2\n"
159
160
        :param value: The value to associate with the key. It may be any
160
161
            bytes as long as it does not contain \0 or \n.
161
162
        """
 
163
        # Ensure that 'key' is a StaticTuple
 
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
162
165
        # we don't care about absent_references
163
166
        node_refs, _ = self._check_key_ref_value(key, references, value)
164
167
        if key in self._nodes:
165
168
            raise errors.BadIndexDuplicateKey(key, self)
166
 
        # TODO: StaticTuple
167
 
        self._nodes[key] = (node_refs, value)
168
 
        self._keys.add(key)
 
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
169
170
        if self._nodes_by_key is not None and self._key_length > 1:
170
171
            self._update_nodes_by_key(key, value, node_refs)
171
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
172
173
            return
173
174
        self._spill_mem_keys_to_disk()
174
175
 
192
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
193
194
        # Note: The transport here isn't strictly needed, because we will use
194
195
        #       direct access to the new_backing._file object
195
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
196
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
 
197
                                      '<temp>', size)
196
198
        # GC will clean up the file
197
199
        new_backing._file = new_backing_file
198
200
        if self._combine_backing_indices:
203
205
                self._backing_indices[backing_pos] = None
204
206
        else:
205
207
            self._backing_indices.append(new_backing)
206
 
        self._keys = set()
207
208
        self._nodes = {}
208
209
        self._nodes_by_key = None
209
210
 
411
412
            # Special case the first node as it may be prefixed
412
413
            node = row.spool.read(_PAGE_SIZE)
413
414
            result.write(node[reserved:])
414
 
            result.write("\x00" * (reserved - position))
 
415
            if len(node) == _PAGE_SIZE:
 
416
                result.write("\x00" * (reserved - position))
415
417
            position = 0 # Only the root row actually has an offset
416
418
            copied_len = osutils.pumpfile(row.spool, result)
417
419
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
462
464
            efficient order for the index (keys iteration order in this case).
463
465
        """
464
466
        keys = set(keys)
465
 
        local_keys = keys.intersection(self._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]
466
476
        if self.reference_lists:
467
477
            for key in local_keys:
468
 
                node = self._nodes[key]
 
478
                node = nodes[key]
469
479
                yield self, key, node[1], node[0]
470
480
        else:
471
481
            for key in local_keys:
472
 
                node = self._nodes[key]
 
482
                node = nodes[key]
473
483
                yield self, key, node[1]
474
484
        # Find things that are in backing indices that have not been handled
475
485
        # yet.
558
568
                    else:
559
569
                        # yield keys
560
570
                        for value in key_dict.itervalues():
561
 
                            yield (self, ) + value
 
571
                            yield (self, ) + tuple(value)
562
572
            else:
563
573
                yield (self, ) + key_dict
564
574
 
585
595
 
586
596
        For InMemoryGraphIndex the estimate is exact.
587
597
        """
588
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
598
        return len(self._nodes) + sum(backing.key_count() for backing in
589
599
            self._backing_indices if backing is not None)
590
600
 
591
601
    def validate(self):
592
602
        """In memory index's have no known corruption at the moment."""
593
603
 
594
604
 
595
 
class _LeafNode(object):
 
605
class _LeafNode(dict):
596
606
    """A leaf node for a serialised B+Tree index."""
597
607
 
598
 
    __slots__ = ('keys', 'min_key', 'max_key')
 
608
    __slots__ = ('min_key', 'max_key', '_keys')
599
609
 
600
610
    def __init__(self, bytes, key_length, ref_list_length):
601
611
        """Parse bytes to create a leaf node object."""
607
617
            self.max_key = key_list[-1][0]
608
618
        else:
609
619
            self.min_key = self.max_key = None
610
 
        self.keys = dict(key_list)
 
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
611
634
 
612
635
 
613
636
class _InternalNode(object):
623
646
    def _parse_lines(self, lines):
624
647
        nodes = []
625
648
        self.offset = int(lines[1][7:])
 
649
        as_st = static_tuple.StaticTuple.from_sequence
626
650
        for line in lines[2:]:
627
651
            if line == '':
628
652
                break
629
 
            # TODO: Switch to StaticTuple here.
630
 
            nodes.append(tuple(map(intern, line.split('\0'))))
 
653
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
631
654
        return nodes
632
655
 
633
656
 
638
661
    memory except when very large walks are done.
639
662
    """
640
663
 
641
 
    def __init__(self, transport, name, size, unlimited_cache=False):
 
664
    def __init__(self, transport, name, size, unlimited_cache=False,
 
665
                 offset=0):
642
666
        """Create a B+Tree index object on the index name.
643
667
 
644
668
        :param transport: The transport to read data for the index from.
651
675
        :param unlimited_cache: If set to True, then instead of using an
652
676
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
653
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.
654
680
        """
655
681
        self._transport = transport
656
682
        self._name = name
658
684
        self._file = None
659
685
        self._recommended_pages = self._compute_recommended_pages()
660
686
        self._root_node = None
 
687
        self._base_offset = offset
 
688
        self._leaf_factory = _LeafNode
661
689
        # Default max size is 100,000 leave values
662
690
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
663
691
        if unlimited_cache:
936
964
        """Cache directly from key => value, skipping the btree."""
937
965
        if self._leaf_value_cache is not None:
938
966
            for node in nodes.itervalues():
939
 
                for key, value in node.keys.iteritems():
 
967
                for key, value in node.all_items():
940
968
                    if key in self._leaf_value_cache:
941
969
                        # Don't add the rest of the keys, we've seen this node
942
970
                        # before.
966
994
        if self._row_offsets[-1] == 1:
967
995
            # There is only the root node, and we read that via key_count()
968
996
            if self.node_ref_lists:
969
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
997
                for key, (value, refs) in self._root_node.all_items():
970
998
                    yield (self, key, value, refs)
971
999
            else:
972
 
                for key, (value, refs) in sorted(self._root_node.keys.items()):
 
1000
                for key, (value, refs) in self._root_node.all_items():
973
1001
                    yield (self, key, value)
974
1002
            return
975
1003
        start_of_leaves = self._row_offsets[-2]
985
1013
        # for spilling index builds to disk.
986
1014
        if self.node_ref_lists:
987
1015
            for _, node in nodes:
988
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1016
                for key, (value, refs) in node.all_items():
989
1017
                    yield (self, key, value, refs)
990
1018
        else:
991
1019
            for _, node in nodes:
992
 
                for key, (value, refs) in sorted(node.keys.items()):
 
1020
                for key, (value, refs) in node.all_items():
993
1021
                    yield (self, key, value)
994
1022
 
995
1023
    @staticmethod
1156
1184
                continue
1157
1185
            node = nodes[node_index]
1158
1186
            for next_sub_key in sub_keys:
1159
 
                if next_sub_key in node.keys:
1160
 
                    value, refs = node.keys[next_sub_key]
 
1187
                if next_sub_key in node:
 
1188
                    value, refs = node[next_sub_key]
1161
1189
                    if self.node_ref_lists:
1162
1190
                        yield (self, next_sub_key, value, refs)
1163
1191
                    else:
1231
1259
            # sub_keys is all of the keys we are looking for that should exist
1232
1260
            # on this page, if they aren't here, then they won't be found
1233
1261
            node = nodes[node_index]
1234
 
            node_keys = node.keys
1235
1262
            parents_to_check = set()
1236
1263
            for next_sub_key in sub_keys:
1237
 
                if next_sub_key not in node_keys:
 
1264
                if next_sub_key not in node:
1238
1265
                    # This one is just not present in the index at all
1239
1266
                    missing_keys.add(next_sub_key)
1240
1267
                else:
1241
 
                    value, refs = node_keys[next_sub_key]
 
1268
                    value, refs = node[next_sub_key]
1242
1269
                    parent_keys = refs[ref_list_num]
1243
1270
                    parent_map[next_sub_key] = parent_keys
1244
1271
                    parents_to_check.update(parent_keys)
1251
1278
            while parents_to_check:
1252
1279
                next_parents_to_check = set()
1253
1280
                for key in parents_to_check:
1254
 
                    if key in node_keys:
1255
 
                        value, refs = node_keys[key]
 
1281
                    if key in node:
 
1282
                        value, refs = node[key]
1256
1283
                        parent_keys = refs[ref_list_num]
1257
1284
                        parent_map[key] = parent_keys
1258
1285
                        next_parents_to_check.update(parent_keys)
1485
1512
        # list of (offset, length) regions of the file that should, evenually
1486
1513
        # be read in to data_ranges, either from 'bytes' or from the transport
1487
1514
        ranges = []
 
1515
        base_offset = self._base_offset
1488
1516
        for index in nodes:
1489
 
            offset = index * _PAGE_SIZE
 
1517
            offset = (index * _PAGE_SIZE)
1490
1518
            size = _PAGE_SIZE
1491
1519
            if index == 0:
1492
1520
                # Root node - special case
1496
1524
                    # The only case where we don't know the size, is for very
1497
1525
                    # small indexes. So we read the whole thing
1498
1526
                    bytes = self._transport.get_bytes(self._name)
1499
 
                    self._size = len(bytes)
 
1527
                    num_bytes = len(bytes)
 
1528
                    self._size = num_bytes - base_offset
1500
1529
                    # the whole thing should be parsed out of 'bytes'
1501
 
                    ranges.append((0, len(bytes)))
 
1530
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
 
1531
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1502
1532
                    break
1503
1533
            else:
1504
1534
                if offset > self._size:
1506
1536
                                         ' of the file %s > %s'
1507
1537
                                         % (offset, self._size))
1508
1538
                size = min(size, self._size - offset)
1509
 
            ranges.append((offset, size))
 
1539
            ranges.append((base_offset + offset, size))
1510
1540
        if not ranges:
1511
1541
            return
1512
1542
        elif bytes is not None:
1513
1543
            # already have the whole file
1514
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1515
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1544
            data_ranges = [(start, bytes[start:start+size])
 
1545
                           for start, size in ranges]
1516
1546
        elif self._file is None:
1517
1547
            data_ranges = self._transport.readv(self._name, ranges)
1518
1548
        else:
1521
1551
                self._file.seek(offset)
1522
1552
                data_ranges.append((offset, self._file.read(size)))
1523
1553
        for offset, data in data_ranges:
 
1554
            offset -= base_offset
1524
1555
            if offset == 0:
1525
1556
                # extract the header
1526
1557
                offset, data = self._parse_header_from_bytes(data)
1528
1559
                    continue
1529
1560
            bytes = zlib.decompress(data)
1530
1561
            if bytes.startswith(_LEAF_FLAG):
1531
 
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
 
1562
                node = self._leaf_factory(bytes, self._key_length,
 
1563
                                          self.node_ref_lists)
1532
1564
            elif bytes.startswith(_INTERNAL_FLAG):
1533
1565
                node = _InternalNode(bytes)
1534
1566
            else:
1553
1585
            pass
1554
1586
 
1555
1587
 
 
1588
_gcchk_factory = _LeafNode
 
1589
 
1556
1590
try:
1557
1591
    from bzrlib import _btree_serializer_pyx as _btree_serializer
 
1592
    _gcchk_factory = _btree_serializer._parse_into_chk
1558
1593
except ImportError, e:
1559
1594
    osutils.failed_to_load_extension(e)
1560
1595
    from bzrlib import _btree_serializer_py as _btree_serializer