/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: John Arbash Meinel
  • Date: 2009-08-17 22:08:21 UTC
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090817220821-wzul2cdupe88xi7t
a few more implementations of the interface.

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
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
import cStringIO
21
20
from bisect import bisect_right
22
21
import math
23
22
import tempfile
31
30
    index,
32
31
    lru_cache,
33
32
    osutils,
34
 
    static_tuple,
35
33
    trace,
36
34
    )
37
35
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
62
60
    def __init__(self):
63
61
        """Create a _BuilderRow."""
64
62
        self.nodes = 0
65
 
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
 
63
        self.spool = tempfile.TemporaryFile()
66
64
        self.writer = None
67
65
 
68
66
    def finish_node(self, pad=True):
69
67
        byte_lines, _, padding = self.writer.finish()
70
68
        if self.nodes == 0:
71
 
            self.spool = cStringIO.StringIO()
72
69
            # padded note:
73
70
            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
79
71
        skipped_bytes = 0
80
72
        if not pad and padding:
81
73
            del byte_lines[-1]
160
152
        :param value: The value to associate with the key. It may be any
161
153
            bytes as long as it does not contain \0 or \n.
162
154
        """
163
 
        # Ensure that 'key' is a StaticTuple
164
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
165
155
        # we don't care about absent_references
166
156
        node_refs, _ = self._check_key_ref_value(key, references, value)
167
157
        if key in self._nodes:
168
158
            raise errors.BadIndexDuplicateKey(key, self)
169
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
159
        self._nodes[key] = (node_refs, value)
 
160
        self._keys.add(key)
170
161
        if self._nodes_by_key is not None and self._key_length > 1:
171
162
            self._update_nodes_by_key(key, value, node_refs)
172
 
        if len(self._nodes) < self._spill_at:
 
163
        if len(self._keys) < self._spill_at:
173
164
            return
174
165
        self._spill_mem_keys_to_disk()
175
166
 
191
182
             backing_pos) = self._spill_mem_keys_and_combine()
192
183
        else:
193
184
            new_backing_file, size = self._spill_mem_keys_without_combining()
 
185
        dir_path, base_name = osutils.split(new_backing_file.name)
194
186
        # Note: The transport here isn't strictly needed, because we will use
195
187
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(get_transport('.'), '<temp>', size)
 
188
        new_backing = BTreeGraphIndex(get_transport(dir_path),
 
189
                                      base_name, size)
197
190
        # GC will clean up the file
198
191
        new_backing._file = new_backing_file
199
192
        if self._combine_backing_indices:
204
197
                self._backing_indices[backing_pos] = None
205
198
        else:
206
199
            self._backing_indices.append(new_backing)
 
200
        self._keys = set()
207
201
        self._nodes = {}
208
202
        self._nodes_by_key = None
209
203
 
385
379
        for row in reversed(rows):
386
380
            pad = (type(row) != _LeafBuilderRow)
387
381
            row.finish_node(pad=pad)
 
382
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
388
383
        lines = [_BTSIGNATURE]
389
384
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
390
385
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
391
386
        lines.append(_OPTION_LEN + str(key_count) + '\n')
392
387
        row_lengths = [row.nodes for row in rows]
393
388
        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()
398
389
        result.writelines(lines)
399
390
        position = sum(map(len, lines))
400
391
        root_row = True
411
402
            # Special case the first node as it may be prefixed
412
403
            node = row.spool.read(_PAGE_SIZE)
413
404
            result.write(node[reserved:])
414
 
            if len(node) == _PAGE_SIZE:
415
 
                result.write("\x00" * (reserved - position))
 
405
            result.write("\x00" * (reserved - position))
416
406
            position = 0 # Only the root row actually has an offset
417
407
            copied_len = osutils.pumpfile(row.spool, result)
418
408
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
454
444
            return iterators[0]
455
445
        return self._iter_smallest(iterators)
456
446
 
 
447
    def find_ancestry(self, keys, ref_list_num):
 
448
        """See CombinedGraphIndex.find_ancestry()"""
 
449
        pending = set(keys)
 
450
        parent_map = {}
 
451
        missing_keys = set()
 
452
        while pending:
 
453
            next_pending = set()
 
454
            for _, key, value, ref_lists in self.iter_entries(pending):
 
455
                parent_keys = ref_lists[ref_list_num]
 
456
                parent_map[key] = parent_keys
 
457
                next_pending.update([p for p in parent_keys if p not in
 
458
                                     parent_map])
 
459
                missing_keys.update(pending.difference(parent_map))
 
460
            pending = next_pending
 
461
        return parent_map, missing_keys
 
462
 
457
463
    def iter_entries(self, keys):
458
464
        """Iterate over keys within the index.
459
465
 
463
469
            efficient order for the index (keys iteration order in this case).
464
470
        """
465
471
        keys = set(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]
 
472
        local_keys = keys.intersection(self._keys)
475
473
        if self.reference_lists:
476
474
            for key in local_keys:
477
 
                node = nodes[key]
 
475
                node = self._nodes[key]
478
476
                yield self, key, node[1], node[0]
479
477
        else:
480
478
            for key in local_keys:
481
 
                node = nodes[key]
 
479
                node = self._nodes[key]
482
480
                yield self, key, node[1]
483
481
        # Find things that are in backing indices that have not been handled
484
482
        # yet.
567
565
                    else:
568
566
                        # yield keys
569
567
                        for value in key_dict.itervalues():
570
 
                            yield (self, ) + tuple(value)
 
568
                            yield (self, ) + value
571
569
            else:
572
570
                yield (self, ) + key_dict
573
571
 
594
592
 
595
593
        For InMemoryGraphIndex the estimate is exact.
596
594
        """
597
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
595
        return len(self._keys) + sum(backing.key_count() for backing in
598
596
            self._backing_indices if backing is not None)
599
597
 
600
598
    def validate(self):
632
630
    def _parse_lines(self, lines):
633
631
        nodes = []
634
632
        self.offset = int(lines[1][7:])
635
 
        as_st = static_tuple.StaticTuple.from_sequence
636
633
        for line in lines[2:]:
637
634
            if line == '':
638
635
                break
639
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
636
            nodes.append(tuple(map(intern, line.split('\0'))))
640
637
        return nodes
641
638
 
642
639
 
647
644
    memory except when very large walks are done.
648
645
    """
649
646
 
650
 
    def __init__(self, transport, name, size, unlimited_cache=False,
651
 
                 offset=0):
 
647
    def __init__(self, transport, name, size):
652
648
        """Create a B+Tree index object on the index name.
653
649
 
654
650
        :param transport: The transport to read data for the index from.
658
654
            the initial read (to read the root node header) can be done
659
655
            without over-reading even on empty indices, and on small indices
660
656
            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.
666
657
        """
667
658
        self._transport = transport
668
659
        self._name = name
670
661
        self._file = None
671
662
        self._recommended_pages = self._compute_recommended_pages()
672
663
        self._root_node = None
673
 
        self._base_offset = offset
674
664
        # Default max size is 100,000 leave values
675
665
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
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)
 
666
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
667
        # We could limit this, but even a 300k record btree has only 3k leaf
 
668
        # nodes, and only 20 internal nodes. So the default of 100 nodes in an
 
669
        # LRU would mean we always cache everything anyway, no need to pay the
 
670
        # overhead of LRU
 
671
        self._internal_node_cache = fifo_cache.FIFOCache(100)
685
672
        self._key_count = None
686
673
        self._row_lengths = None
687
674
        self._row_offsets = None # Start of each row, [-1] is the end
719
706
                if start_of_leaves is None:
720
707
                    start_of_leaves = self._row_offsets[-2]
721
708
                if node_pos < start_of_leaves:
722
 
                    self._internal_node_cache[node_pos] = node
 
709
                    self._internal_node_cache.add(node_pos, node)
723
710
                else:
724
 
                    self._leaf_node_cache[node_pos] = node
 
711
                    self._leaf_node_cache.add(node_pos, node)
725
712
            found[node_pos] = node
726
713
        return found
727
714
 
866
853
            new_tips = next_tips
867
854
        return final_offsets
868
855
 
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
 
 
882
856
    def external_references(self, ref_list_num):
883
857
        if self._root_node is None:
884
858
            self._get_root_node()
1498
1472
        # list of (offset, length) regions of the file that should, evenually
1499
1473
        # be read in to data_ranges, either from 'bytes' or from the transport
1500
1474
        ranges = []
1501
 
        base_offset = self._base_offset
1502
1475
        for index in nodes:
1503
 
            offset = (index * _PAGE_SIZE)
 
1476
            offset = index * _PAGE_SIZE
1504
1477
            size = _PAGE_SIZE
1505
1478
            if index == 0:
1506
1479
                # Root node - special case
1510
1483
                    # The only case where we don't know the size, is for very
1511
1484
                    # small indexes. So we read the whole thing
1512
1485
                    bytes = self._transport.get_bytes(self._name)
1513
 
                    num_bytes = len(bytes)
1514
 
                    self._size = num_bytes - base_offset
 
1486
                    self._size = len(bytes)
1515
1487
                    # the whole thing should be parsed out of 'bytes'
1516
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1517
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1488
                    ranges.append((0, len(bytes)))
1518
1489
                    break
1519
1490
            else:
1520
1491
                if offset > self._size:
1522
1493
                                         ' of the file %s > %s'
1523
1494
                                         % (offset, self._size))
1524
1495
                size = min(size, self._size - offset)
1525
 
            ranges.append((base_offset + offset, size))
 
1496
            ranges.append((offset, size))
1526
1497
        if not ranges:
1527
1498
            return
1528
1499
        elif bytes is not None:
1529
1500
            # already have the whole file
1530
 
            data_ranges = [(start, bytes[start:start+size])
1531
 
                           for start, size in ranges]
 
1501
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1502
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1532
1503
        elif self._file is None:
1533
1504
            data_ranges = self._transport.readv(self._name, ranges)
1534
1505
        else:
1537
1508
                self._file.seek(offset)
1538
1509
                data_ranges.append((offset, self._file.read(size)))
1539
1510
        for offset, data in data_ranges:
1540
 
            offset -= base_offset
1541
1511
            if offset == 0:
1542
1512
                # extract the header
1543
1513
                offset, data = self._parse_header_from_bytes(data)
1572
1542
 
1573
1543
try:
1574
1544
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1575
 
except ImportError, e:
1576
 
    osutils.failed_to_load_extension(e)
 
1545
except ImportError:
1577
1546
    from bzrlib import _btree_serializer_py as _btree_serializer