← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Ferlito
  • Date: 2009-09-02 04:31:45 UTC
  • mto: (4665.7.1 serve-init)
  • mto: This revision was merged to the branch mainline in revision 4913.
  • Revision ID: johnf@inodes.org-20090902043145-gxdsfw03ilcwbyn5
Add a debian init script for bzr --serve

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
 
import cStringIO
21
 
 
22
 
from bzrlib.lazy_import import lazy_import
23
 
lazy_import(globals(), """
24
 
import bisect
 
20
from bisect import bisect_right
25
21
import math
26
22
import tempfile
27
23
import zlib
28
 
""")
29
24
 
30
25
from bzrlib import (
31
26
    chunk_writer,
35
30
    index,
36
31
    lru_cache,
37
32
    osutils,
38
 
    static_tuple,
39
33
    trace,
40
 
    transport,
41
34
    )
42
35
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
36
from bzrlib.transport import get_transport
43
37
 
44
38
 
45
39
_BTSIGNATURE = "B+Tree Graph Index 2\n"
66
60
    def __init__(self):
67
61
        """Create a _BuilderRow."""
68
62
        self.nodes = 0
69
 
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
 
63
        self.spool = tempfile.TemporaryFile()
70
64
        self.writer = None
71
65
 
72
66
    def finish_node(self, pad=True):
73
67
        byte_lines, _, padding = self.writer.finish()
74
68
        if self.nodes == 0:
75
 
            self.spool = cStringIO.StringIO()
76
69
            # padded note:
77
70
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
78
 
        elif self.nodes == 1:
79
 
            # We got bigger than 1 node, switch to a temp file
80
 
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
81
 
            spool.write(self.spool.getvalue())
82
 
            self.spool = spool
83
71
        skipped_bytes = 0
84
72
        if not pad and padding:
85
73
            del byte_lines[-1]
164
152
        :param value: The value to associate with the key. It may be any
165
153
            bytes as long as it does not contain \0 or \n.
166
154
        """
167
 
        # Ensure that 'key' is a StaticTuple
168
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
169
155
        # we don't care about absent_references
170
156
        node_refs, _ = self._check_key_ref_value(key, references, value)
171
157
        if key in self._nodes:
172
158
            raise errors.BadIndexDuplicateKey(key, self)
173
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
159
        self._nodes[key] = (node_refs, value)
 
160
        self._keys.add(key)
174
161
        if self._nodes_by_key is not None and self._key_length > 1:
175
162
            self._update_nodes_by_key(key, value, node_refs)
176
 
        if len(self._nodes) < self._spill_at:
 
163
        if len(self._keys) < self._spill_at:
177
164
            return
178
165
        self._spill_mem_keys_to_disk()
179
166
 
195
182
             backing_pos) = self._spill_mem_keys_and_combine()
196
183
        else:
197
184
            new_backing_file, size = self._spill_mem_keys_without_combining()
 
185
        dir_path, base_name = osutils.split(new_backing_file.name)
198
186
        # Note: The transport here isn't strictly needed, because we will use
199
187
        #       direct access to the new_backing._file object
200
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
201
 
                                      '<temp>', size)
 
188
        new_backing = BTreeGraphIndex(get_transport(dir_path),
 
189
                                      base_name, size)
202
190
        # GC will clean up the file
203
191
        new_backing._file = new_backing_file
204
192
        if self._combine_backing_indices:
209
197
                self._backing_indices[backing_pos] = None
210
198
        else:
211
199
            self._backing_indices.append(new_backing)
 
200
        self._keys = set()
212
201
        self._nodes = {}
213
202
        self._nodes_by_key = None
214
203
 
390
379
        for row in reversed(rows):
391
380
            pad = (type(row) != _LeafBuilderRow)
392
381
            row.finish_node(pad=pad)
 
382
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
393
383
        lines = [_BTSIGNATURE]
394
384
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
395
385
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
396
386
        lines.append(_OPTION_LEN + str(key_count) + '\n')
397
387
        row_lengths = [row.nodes for row in rows]
398
388
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
399
 
        if row_lengths and row_lengths[-1] > 1:
400
 
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
401
 
        else:
402
 
            result = cStringIO.StringIO()
403
389
        result.writelines(lines)
404
390
        position = sum(map(len, lines))
405
391
        root_row = True
416
402
            # Special case the first node as it may be prefixed
417
403
            node = row.spool.read(_PAGE_SIZE)
418
404
            result.write(node[reserved:])
419
 
            if len(node) == _PAGE_SIZE:
420
 
                result.write("\x00" * (reserved - position))
 
405
            result.write("\x00" * (reserved - position))
421
406
            position = 0 # Only the root row actually has an offset
422
407
            copied_len = osutils.pumpfile(row.spool, result)
423
408
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
468
453
            efficient order for the index (keys iteration order in this case).
469
454
        """
470
455
        keys = set(keys)
471
 
        # Note: We don't use keys.intersection() here. If you read the C api,
472
 
        #       set.intersection(other) special cases when other is a set and
473
 
        #       will iterate the smaller of the two and lookup in the other.
474
 
        #       It does *not* do this for any other type (even dict, unlike
475
 
        #       some other set functions.) Since we expect keys is generally <<
476
 
        #       self._nodes, it is faster to iterate over it in a list
477
 
        #       comprehension
478
 
        nodes = self._nodes
479
 
        local_keys = [key for key in keys if key in nodes]
 
456
        local_keys = keys.intersection(self._keys)
480
457
        if self.reference_lists:
481
458
            for key in local_keys:
482
 
                node = nodes[key]
 
459
                node = self._nodes[key]
483
460
                yield self, key, node[1], node[0]
484
461
        else:
485
462
            for key in local_keys:
486
 
                node = nodes[key]
 
463
                node = self._nodes[key]
487
464
                yield self, key, node[1]
488
465
        # Find things that are in backing indices that have not been handled
489
466
        # yet.
572
549
                    else:
573
550
                        # yield keys
574
551
                        for value in key_dict.itervalues():
575
 
                            yield (self, ) + tuple(value)
 
552
                            yield (self, ) + value
576
553
            else:
577
554
                yield (self, ) + key_dict
578
555
 
599
576
 
600
577
        For InMemoryGraphIndex the estimate is exact.
601
578
        """
602
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
579
        return len(self._keys) + sum(backing.key_count() for backing in
603
580
            self._backing_indices if backing is not None)
604
581
 
605
582
    def validate(self):
606
583
        """In memory index's have no known corruption at the moment."""
607
584
 
608
585
 
609
 
class _LeafNode(dict):
 
586
class _LeafNode(object):
610
587
    """A leaf node for a serialised B+Tree index."""
611
588
 
612
 
    __slots__ = ('min_key', 'max_key', '_keys')
 
589
    __slots__ = ('keys', 'min_key', 'max_key')
613
590
 
614
591
    def __init__(self, bytes, key_length, ref_list_length):
615
592
        """Parse bytes to create a leaf node object."""
621
598
            self.max_key = key_list[-1][0]
622
599
        else:
623
600
            self.min_key = self.max_key = None
624
 
        super(_LeafNode, self).__init__(key_list)
625
 
        self._keys = dict(self)
626
 
 
627
 
    def all_items(self):
628
 
        """Return a sorted list of (key, (value, refs)) items"""
629
 
        items = self.items()
630
 
        items.sort()
631
 
        return items
632
 
 
633
 
    def all_keys(self):
634
 
        """Return a sorted list of all keys."""
635
 
        keys = self.keys()
636
 
        keys.sort()
637
 
        return keys
 
601
        self.keys = dict(key_list)
638
602
 
639
603
 
640
604
class _InternalNode(object):
650
614
    def _parse_lines(self, lines):
651
615
        nodes = []
652
616
        self.offset = int(lines[1][7:])
653
 
        as_st = static_tuple.StaticTuple.from_sequence
654
617
        for line in lines[2:]:
655
618
            if line == '':
656
619
                break
657
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
620
            nodes.append(tuple(map(intern, line.split('\0'))))
658
621
        return nodes
659
622
 
660
623
 
665
628
    memory except when very large walks are done.
666
629
    """
667
630
 
668
 
    def __init__(self, transport, name, size, unlimited_cache=False,
669
 
                 offset=0):
 
631
    def __init__(self, transport, name, size):
670
632
        """Create a B+Tree index object on the index name.
671
633
 
672
634
        :param transport: The transport to read data for the index from.
676
638
            the initial read (to read the root node header) can be done
677
639
            without over-reading even on empty indices, and on small indices
678
640
            allows single-IO to read the entire index.
679
 
        :param unlimited_cache: If set to True, then instead of using an
680
 
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
681
 
            cache all leaf nodes.
682
 
        :param offset: The start of the btree index data isn't byte 0 of the
683
 
            file. Instead it starts at some point later.
684
641
        """
685
642
        self._transport = transport
686
643
        self._name = name
688
645
        self._file = None
689
646
        self._recommended_pages = self._compute_recommended_pages()
690
647
        self._root_node = None
691
 
        self._base_offset = offset
692
 
        self._leaf_factory = _LeafNode
693
648
        # Default max size is 100,000 leave values
694
649
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
695
 
        if unlimited_cache:
696
 
            self._leaf_node_cache = {}
697
 
            self._internal_node_cache = {}
698
 
        else:
699
 
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
700
 
            # We use a FIFO here just to prevent possible blowout. However, a
701
 
            # 300k record btree has only 3k leaf nodes, and only 20 internal
702
 
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
703
 
            self._internal_node_cache = fifo_cache.FIFOCache(100)
 
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
656
        self._key_count = None
705
657
        self._row_lengths = None
706
658
        self._row_offsets = None # Start of each row, [-1] is the end
738
690
                if start_of_leaves is None:
739
691
                    start_of_leaves = self._row_offsets[-2]
740
692
                if node_pos < start_of_leaves:
741
 
                    self._internal_node_cache[node_pos] = node
 
693
                    self._internal_node_cache.add(node_pos, node)
742
694
                else:
743
 
                    self._leaf_node_cache[node_pos] = node
 
695
                    self._leaf_node_cache.add(node_pos, node)
744
696
            found[node_pos] = node
745
697
        return found
746
698
 
885
837
            new_tips = next_tips
886
838
        return final_offsets
887
839
 
888
 
    def clear_cache(self):
889
 
        """Clear out any cached/memoized values.
890
 
 
891
 
        This can be called at any time, but generally it is used when we have
892
 
        extracted some information, but don't expect to be requesting any more
893
 
        from this index.
894
 
        """
895
 
        # Note that we don't touch self._root_node or self._internal_node_cache
896
 
        # We don't expect either of those to be big, and it can save
897
 
        # round-trips in the future. We may re-evaluate this if InternalNode
898
 
        # memory starts to be an issue.
899
 
        self._leaf_node_cache.clear()
900
 
 
901
840
    def external_references(self, ref_list_num):
902
841
        if self._root_node is None:
903
842
            self._get_root_node()
968
907
        """Cache directly from key => value, skipping the btree."""
969
908
        if self._leaf_value_cache is not None:
970
909
            for node in nodes.itervalues():
971
 
                for key, value in node.all_items():
 
910
                for key, value in node.keys.iteritems():
972
911
                    if key in self._leaf_value_cache:
973
912
                        # Don't add the rest of the keys, we've seen this node
974
913
                        # before.
998
937
        if self._row_offsets[-1] == 1:
999
938
            # There is only the root node, and we read that via key_count()
1000
939
            if self.node_ref_lists:
1001
 
                for key, (value, refs) in self._root_node.all_items():
 
940
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1002
941
                    yield (self, key, value, refs)
1003
942
            else:
1004
 
                for key, (value, refs) in self._root_node.all_items():
 
943
                for key, (value, refs) in sorted(self._root_node.keys.items()):
1005
944
                    yield (self, key, value)
1006
945
            return
1007
946
        start_of_leaves = self._row_offsets[-2]
1017
956
        # for spilling index builds to disk.
1018
957
        if self.node_ref_lists:
1019
958
            for _, node in nodes:
1020
 
                for key, (value, refs) in node.all_items():
 
959
                for key, (value, refs) in sorted(node.keys.items()):
1021
960
                    yield (self, key, value, refs)
1022
961
        else:
1023
962
            for _, node in nodes:
1024
 
                for key, (value, refs) in node.all_items():
 
963
                for key, (value, refs) in sorted(node.keys.items()):
1025
964
                    yield (self, key, value)
1026
965
 
1027
966
    @staticmethod
1051
990
        # iter_steps = len(in_keys) + len(fixed_keys)
1052
991
        # bisect_steps = len(in_keys) * math.log(len(fixed_keys), 2)
1053
992
        if len(in_keys) == 1: # Bisect will always be faster for M = 1
1054
 
            return [(bisect.bisect_right(fixed_keys, in_keys[0]), in_keys)]
 
993
            return [(bisect_right(fixed_keys, in_keys[0]), in_keys)]
1055
994
        # elif bisect_steps < iter_steps:
1056
995
        #     offsets = {}
1057
996
        #     for key in in_keys:
1188
1127
                continue
1189
1128
            node = nodes[node_index]
1190
1129
            for next_sub_key in sub_keys:
1191
 
                if next_sub_key in node:
1192
 
                    value, refs = node[next_sub_key]
 
1130
                if next_sub_key in node.keys:
 
1131
                    value, refs = node.keys[next_sub_key]
1193
1132
                    if self.node_ref_lists:
1194
1133
                        yield (self, next_sub_key, value, refs)
1195
1134
                    else:
1263
1202
            # sub_keys is all of the keys we are looking for that should exist
1264
1203
            # on this page, if they aren't here, then they won't be found
1265
1204
            node = nodes[node_index]
 
1205
            node_keys = node.keys
1266
1206
            parents_to_check = set()
1267
1207
            for next_sub_key in sub_keys:
1268
 
                if next_sub_key not in node:
 
1208
                if next_sub_key not in node_keys:
1269
1209
                    # This one is just not present in the index at all
1270
1210
                    missing_keys.add(next_sub_key)
1271
1211
                else:
1272
 
                    value, refs = node[next_sub_key]
 
1212
                    value, refs = node_keys[next_sub_key]
1273
1213
                    parent_keys = refs[ref_list_num]
1274
1214
                    parent_map[next_sub_key] = parent_keys
1275
1215
                    parents_to_check.update(parent_keys)
1282
1222
            while parents_to_check:
1283
1223
                next_parents_to_check = set()
1284
1224
                for key in parents_to_check:
1285
 
                    if key in node:
1286
 
                        value, refs = node[key]
 
1225
                    if key in node_keys:
 
1226
                        value, refs = node_keys[key]
1287
1227
                        parent_keys = refs[ref_list_num]
1288
1228
                        parent_map[key] = parent_keys
1289
1229
                        next_parents_to_check.update(parent_keys)
1516
1456
        # list of (offset, length) regions of the file that should, evenually
1517
1457
        # be read in to data_ranges, either from 'bytes' or from the transport
1518
1458
        ranges = []
1519
 
        base_offset = self._base_offset
1520
1459
        for index in nodes:
1521
 
            offset = (index * _PAGE_SIZE)
 
1460
            offset = index * _PAGE_SIZE
1522
1461
            size = _PAGE_SIZE
1523
1462
            if index == 0:
1524
1463
                # Root node - special case
1528
1467
                    # The only case where we don't know the size, is for very
1529
1468
                    # small indexes. So we read the whole thing
1530
1469
                    bytes = self._transport.get_bytes(self._name)
1531
 
                    num_bytes = len(bytes)
1532
 
                    self._size = num_bytes - base_offset
 
1470
                    self._size = len(bytes)
1533
1471
                    # the whole thing should be parsed out of 'bytes'
1534
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1535
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1472
                    ranges.append((0, len(bytes)))
1536
1473
                    break
1537
1474
            else:
1538
1475
                if offset > self._size:
1540
1477
                                         ' of the file %s > %s'
1541
1478
                                         % (offset, self._size))
1542
1479
                size = min(size, self._size - offset)
1543
 
            ranges.append((base_offset + offset, size))
 
1480
            ranges.append((offset, size))
1544
1481
        if not ranges:
1545
1482
            return
1546
1483
        elif bytes is not None:
1547
1484
            # already have the whole file
1548
 
            data_ranges = [(start, bytes[start:start+size])
1549
 
                           for start, size in ranges]
 
1485
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1486
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1550
1487
        elif self._file is None:
1551
1488
            data_ranges = self._transport.readv(self._name, ranges)
1552
1489
        else:
1555
1492
                self._file.seek(offset)
1556
1493
                data_ranges.append((offset, self._file.read(size)))
1557
1494
        for offset, data in data_ranges:
1558
 
            offset -= base_offset
1559
1495
            if offset == 0:
1560
1496
                # extract the header
1561
1497
                offset, data = self._parse_header_from_bytes(data)
1563
1499
                    continue
1564
1500
            bytes = zlib.decompress(data)
1565
1501
            if bytes.startswith(_LEAF_FLAG):
1566
 
                node = self._leaf_factory(bytes, self._key_length,
1567
 
                                          self.node_ref_lists)
 
1502
                node = _LeafNode(bytes, self._key_length, self.node_ref_lists)
1568
1503
            elif bytes.startswith(_INTERNAL_FLAG):
1569
1504
                node = _InternalNode(bytes)
1570
1505
            else:
1589
1524
            pass
1590
1525
 
1591
1526
 
1592
 
_gcchk_factory = _LeafNode
1593
 
 
1594
1527
try:
1595
1528
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1596
 
    _gcchk_factory = _btree_serializer._parse_into_chk
1597
 
except ImportError, e:
1598
 
    osutils.failed_to_load_extension(e)
 
1529
except ImportError:
1599
1530
    from bzrlib import _btree_serializer_py as _btree_serializer