/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Robert Collins
  • Date: 2010-05-06 11:08:10 UTC
  • mto: This revision was merged to the branch mainline in revision 5223.
  • Revision ID: robertc@robertcollins.net-20100506110810-h3j07fh5gmw54s25
Cleaner matcher matching revised unlocking protocol.

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
17
17
 
18
18
"""B+Tree indices"""
19
19
 
 
20
import cStringIO
20
21
from bisect import bisect_right
21
22
import math
22
23
import tempfile
30
31
    index,
31
32
    lru_cache,
32
33
    osutils,
 
34
    static_tuple,
33
35
    trace,
34
36
    )
35
37
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
60
62
    def __init__(self):
61
63
        """Create a _BuilderRow."""
62
64
        self.nodes = 0
63
 
        self.spool = tempfile.TemporaryFile()
 
65
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
64
66
        self.writer = None
65
67
 
66
68
    def finish_node(self, pad=True):
67
69
        byte_lines, _, padding = self.writer.finish()
68
70
        if self.nodes == 0:
 
71
            self.spool = cStringIO.StringIO()
69
72
            # padded note:
70
73
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
 
74
        elif self.nodes == 1:
 
75
            # We got bigger than 1 node, switch to a temp file
 
76
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
 
77
            spool.write(self.spool.getvalue())
 
78
            self.spool = spool
71
79
        skipped_bytes = 0
72
80
        if not pad and padding:
73
81
            del byte_lines[-1]
152
160
        :param value: The value to associate with the key. It may be any
153
161
            bytes as long as it does not contain \0 or \n.
154
162
        """
 
163
        # Ensure that 'key' is a StaticTuple
 
164
        key = static_tuple.StaticTuple.from_sequence(key).intern()
155
165
        # we don't care about absent_references
156
166
        node_refs, _ = self._check_key_ref_value(key, references, value)
157
167
        if key in self._nodes:
158
168
            raise errors.BadIndexDuplicateKey(key, self)
159
 
        self._nodes[key] = (node_refs, value)
160
 
        self._keys.add(key)
 
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
161
170
        if self._nodes_by_key is not None and self._key_length > 1:
162
171
            self._update_nodes_by_key(key, value, node_refs)
163
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
164
173
            return
165
174
        self._spill_mem_keys_to_disk()
166
175
 
182
191
             backing_pos) = self._spill_mem_keys_and_combine()
183
192
        else:
184
193
            new_backing_file, size = self._spill_mem_keys_without_combining()
185
 
        dir_path, base_name = osutils.split(new_backing_file.name)
186
194
        # Note: The transport here isn't strictly needed, because we will use
187
195
        #       direct access to the new_backing._file object
188
 
        new_backing = BTreeGraphIndex(get_transport(dir_path),
189
 
                                      base_name, size)
 
196
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
190
197
        # GC will clean up the file
191
198
        new_backing._file = new_backing_file
192
199
        if self._combine_backing_indices:
197
204
                self._backing_indices[backing_pos] = None
198
205
        else:
199
206
            self._backing_indices.append(new_backing)
200
 
        self._keys = set()
201
207
        self._nodes = {}
202
208
        self._nodes_by_key = None
203
209
 
379
385
        for row in reversed(rows):
380
386
            pad = (type(row) != _LeafBuilderRow)
381
387
            row.finish_node(pad=pad)
382
 
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
383
388
        lines = [_BTSIGNATURE]
384
389
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
385
390
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
386
391
        lines.append(_OPTION_LEN + str(key_count) + '\n')
387
392
        row_lengths = [row.nodes for row in rows]
388
393
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
 
394
        if row_lengths and row_lengths[-1] > 1:
 
395
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
 
396
        else:
 
397
            result = cStringIO.StringIO()
389
398
        result.writelines(lines)
390
399
        position = sum(map(len, lines))
391
400
        root_row = True
402
411
            # Special case the first node as it may be prefixed
403
412
            node = row.spool.read(_PAGE_SIZE)
404
413
            result.write(node[reserved:])
405
 
            result.write("\x00" * (reserved - position))
 
414
            if len(node) == _PAGE_SIZE:
 
415
                result.write("\x00" * (reserved - position))
406
416
            position = 0 # Only the root row actually has an offset
407
417
            copied_len = osutils.pumpfile(row.spool, result)
408
418
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
453
463
            efficient order for the index (keys iteration order in this case).
454
464
        """
455
465
        keys = set(keys)
456
 
        local_keys = keys.intersection(self._keys)
 
466
        # Note: We don't use keys.intersection() here. If you read the C api,
 
467
        #       set.intersection(other) special cases when other is a set and
 
468
        #       will iterate the smaller of the two and lookup in the other.
 
469
        #       It does *not* do this for any other type (even dict, unlike
 
470
        #       some other set functions.) Since we expect keys is generally <<
 
471
        #       self._nodes, it is faster to iterate over it in a list
 
472
        #       comprehension
 
473
        nodes = self._nodes
 
474
        local_keys = [key for key in keys if key in nodes]
457
475
        if self.reference_lists:
458
476
            for key in local_keys:
459
 
                node = self._nodes[key]
 
477
                node = nodes[key]
460
478
                yield self, key, node[1], node[0]
461
479
        else:
462
480
            for key in local_keys:
463
 
                node = self._nodes[key]
 
481
                node = nodes[key]
464
482
                yield self, key, node[1]
465
483
        # Find things that are in backing indices that have not been handled
466
484
        # yet.
549
567
                    else:
550
568
                        # yield keys
551
569
                        for value in key_dict.itervalues():
552
 
                            yield (self, ) + value
 
570
                            yield (self, ) + tuple(value)
553
571
            else:
554
572
                yield (self, ) + key_dict
555
573
 
576
594
 
577
595
        For InMemoryGraphIndex the estimate is exact.
578
596
        """
579
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
597
        return len(self._nodes) + sum(backing.key_count() for backing in
580
598
            self._backing_indices if backing is not None)
581
599
 
582
600
    def validate(self):
614
632
    def _parse_lines(self, lines):
615
633
        nodes = []
616
634
        self.offset = int(lines[1][7:])
 
635
        as_st = static_tuple.StaticTuple.from_sequence
617
636
        for line in lines[2:]:
618
637
            if line == '':
619
638
                break
620
 
            nodes.append(tuple(map(intern, line.split('\0'))))
 
639
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
621
640
        return nodes
622
641
 
623
642
 
628
647
    memory except when very large walks are done.
629
648
    """
630
649
 
631
 
    def __init__(self, transport, name, size):
 
650
    def __init__(self, transport, name, size, unlimited_cache=False,
 
651
                 offset=0):
632
652
        """Create a B+Tree index object on the index name.
633
653
 
634
654
        :param transport: The transport to read data for the index from.
638
658
            the initial read (to read the root node header) can be done
639
659
            without over-reading even on empty indices, and on small indices
640
660
            allows single-IO to read the entire index.
 
661
        :param unlimited_cache: If set to True, then instead of using an
 
662
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
 
663
            cache all leaf nodes.
 
664
        :param offset: The start of the btree index data isn't byte 0 of the
 
665
            file. Instead it starts at some point later.
641
666
        """
642
667
        self._transport = transport
643
668
        self._name = name
645
670
        self._file = None
646
671
        self._recommended_pages = self._compute_recommended_pages()
647
672
        self._root_node = None
 
673
        self._base_offset = offset
648
674
        # Default max size is 100,000 leave values
649
675
        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)
 
676
        if unlimited_cache:
 
677
            self._leaf_node_cache = {}
 
678
            self._internal_node_cache = {}
 
679
        else:
 
680
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
681
            # We use a FIFO here just to prevent possible blowout. However, a
 
682
            # 300k record btree has only 3k leaf nodes, and only 20 internal
 
683
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
 
684
            self._internal_node_cache = fifo_cache.FIFOCache(100)
656
685
        self._key_count = None
657
686
        self._row_lengths = None
658
687
        self._row_offsets = None # Start of each row, [-1] is the end
690
719
                if start_of_leaves is None:
691
720
                    start_of_leaves = self._row_offsets[-2]
692
721
                if node_pos < start_of_leaves:
693
 
                    self._internal_node_cache.add(node_pos, node)
 
722
                    self._internal_node_cache[node_pos] = node
694
723
                else:
695
 
                    self._leaf_node_cache.add(node_pos, node)
 
724
                    self._leaf_node_cache[node_pos] = node
696
725
            found[node_pos] = node
697
726
        return found
698
727
 
837
866
            new_tips = next_tips
838
867
        return final_offsets
839
868
 
 
869
    def clear_cache(self):
 
870
        """Clear out any cached/memoized values.
 
871
 
 
872
        This can be called at any time, but generally it is used when we have
 
873
        extracted some information, but don't expect to be requesting any more
 
874
        from this index.
 
875
        """
 
876
        # Note that we don't touch self._root_node or self._internal_node_cache
 
877
        # We don't expect either of those to be big, and it can save
 
878
        # round-trips in the future. We may re-evaluate this if InternalNode
 
879
        # memory starts to be an issue.
 
880
        self._leaf_node_cache.clear()
 
881
 
840
882
    def external_references(self, ref_list_num):
841
883
        if self._root_node is None:
842
884
            self._get_root_node()
1456
1498
        # list of (offset, length) regions of the file that should, evenually
1457
1499
        # be read in to data_ranges, either from 'bytes' or from the transport
1458
1500
        ranges = []
 
1501
        base_offset = self._base_offset
1459
1502
        for index in nodes:
1460
 
            offset = index * _PAGE_SIZE
 
1503
            offset = (index * _PAGE_SIZE)
1461
1504
            size = _PAGE_SIZE
1462
1505
            if index == 0:
1463
1506
                # Root node - special case
1467
1510
                    # The only case where we don't know the size, is for very
1468
1511
                    # small indexes. So we read the whole thing
1469
1512
                    bytes = self._transport.get_bytes(self._name)
1470
 
                    self._size = len(bytes)
 
1513
                    num_bytes = len(bytes)
 
1514
                    self._size = num_bytes - base_offset
1471
1515
                    # the whole thing should be parsed out of 'bytes'
1472
 
                    ranges.append((0, len(bytes)))
 
1516
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
 
1517
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
1473
1518
                    break
1474
1519
            else:
1475
1520
                if offset > self._size:
1477
1522
                                         ' of the file %s > %s'
1478
1523
                                         % (offset, self._size))
1479
1524
                size = min(size, self._size - offset)
1480
 
            ranges.append((offset, size))
 
1525
            ranges.append((base_offset + offset, size))
1481
1526
        if not ranges:
1482
1527
            return
1483
1528
        elif bytes is not None:
1484
1529
            # already have the whole file
1485
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1486
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1530
            data_ranges = [(start, bytes[start:start+size])
 
1531
                           for start, size in ranges]
1487
1532
        elif self._file is None:
1488
1533
            data_ranges = self._transport.readv(self._name, ranges)
1489
1534
        else:
1492
1537
                self._file.seek(offset)
1493
1538
                data_ranges.append((offset, self._file.read(size)))
1494
1539
        for offset, data in data_ranges:
 
1540
            offset -= base_offset
1495
1541
            if offset == 0:
1496
1542
                # extract the header
1497
1543
                offset, data = self._parse_header_from_bytes(data)