/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
31
31
    index,
32
32
    lru_cache,
33
33
    osutils,
 
34
    static_tuple,
34
35
    trace,
35
36
    )
36
37
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
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
 
        self._nodes[key] = (node_refs, value)
167
 
        self._keys.add(key)
 
169
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
168
170
        if self._nodes_by_key is not None and self._key_length > 1:
169
171
            self._update_nodes_by_key(key, value, node_refs)
170
 
        if len(self._keys) < self._spill_at:
 
172
        if len(self._nodes) < self._spill_at:
171
173
            return
172
174
        self._spill_mem_keys_to_disk()
173
175
 
202
204
                self._backing_indices[backing_pos] = None
203
205
        else:
204
206
            self._backing_indices.append(new_backing)
205
 
        self._keys = set()
206
207
        self._nodes = {}
207
208
        self._nodes_by_key = None
208
209
 
410
411
            # Special case the first node as it may be prefixed
411
412
            node = row.spool.read(_PAGE_SIZE)
412
413
            result.write(node[reserved:])
413
 
            result.write("\x00" * (reserved - position))
 
414
            if len(node) == _PAGE_SIZE:
 
415
                result.write("\x00" * (reserved - position))
414
416
            position = 0 # Only the root row actually has an offset
415
417
            copied_len = osutils.pumpfile(row.spool, result)
416
418
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
461
463
            efficient order for the index (keys iteration order in this case).
462
464
        """
463
465
        keys = set(keys)
464
 
        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]
465
475
        if self.reference_lists:
466
476
            for key in local_keys:
467
 
                node = self._nodes[key]
 
477
                node = nodes[key]
468
478
                yield self, key, node[1], node[0]
469
479
        else:
470
480
            for key in local_keys:
471
 
                node = self._nodes[key]
 
481
                node = nodes[key]
472
482
                yield self, key, node[1]
473
483
        # Find things that are in backing indices that have not been handled
474
484
        # yet.
557
567
                    else:
558
568
                        # yield keys
559
569
                        for value in key_dict.itervalues():
560
 
                            yield (self, ) + value
 
570
                            yield (self, ) + tuple(value)
561
571
            else:
562
572
                yield (self, ) + key_dict
563
573
 
584
594
 
585
595
        For InMemoryGraphIndex the estimate is exact.
586
596
        """
587
 
        return len(self._keys) + sum(backing.key_count() for backing in
 
597
        return len(self._nodes) + sum(backing.key_count() for backing in
588
598
            self._backing_indices if backing is not None)
589
599
 
590
600
    def validate(self):
622
632
    def _parse_lines(self, lines):
623
633
        nodes = []
624
634
        self.offset = int(lines[1][7:])
 
635
        as_st = static_tuple.StaticTuple.from_sequence
625
636
        for line in lines[2:]:
626
637
            if line == '':
627
638
                break
628
 
            nodes.append(tuple(map(intern, line.split('\0'))))
 
639
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
629
640
        return nodes
630
641
 
631
642
 
636
647
    memory except when very large walks are done.
637
648
    """
638
649
 
639
 
    def __init__(self, transport, name, size, unlimited_cache=False):
 
650
    def __init__(self, transport, name, size, unlimited_cache=False,
 
651
                 offset=0):
640
652
        """Create a B+Tree index object on the index name.
641
653
 
642
654
        :param transport: The transport to read data for the index from.
649
661
        :param unlimited_cache: If set to True, then instead of using an
650
662
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
651
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.
652
666
        """
653
667
        self._transport = transport
654
668
        self._name = name
656
670
        self._file = None
657
671
        self._recommended_pages = self._compute_recommended_pages()
658
672
        self._root_node = None
 
673
        self._base_offset = offset
659
674
        # Default max size is 100,000 leave values
660
675
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
661
676
        if unlimited_cache:
851
866
            new_tips = next_tips
852
867
        return final_offsets
853
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
 
854
882
    def external_references(self, ref_list_num):
855
883
        if self._root_node is None:
856
884
            self._get_root_node()
1470
1498
        # list of (offset, length) regions of the file that should, evenually
1471
1499
        # be read in to data_ranges, either from 'bytes' or from the transport
1472
1500
        ranges = []
 
1501
        base_offset = self._base_offset
1473
1502
        for index in nodes:
1474
 
            offset = index * _PAGE_SIZE
 
1503
            offset = (index * _PAGE_SIZE)
1475
1504
            size = _PAGE_SIZE
1476
1505
            if index == 0:
1477
1506
                # Root node - special case
1481
1510
                    # The only case where we don't know the size, is for very
1482
1511
                    # small indexes. So we read the whole thing
1483
1512
                    bytes = self._transport.get_bytes(self._name)
1484
 
                    self._size = len(bytes)
 
1513
                    num_bytes = len(bytes)
 
1514
                    self._size = num_bytes - base_offset
1485
1515
                    # the whole thing should be parsed out of 'bytes'
1486
 
                    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)]
1487
1518
                    break
1488
1519
            else:
1489
1520
                if offset > self._size:
1491
1522
                                         ' of the file %s > %s'
1492
1523
                                         % (offset, self._size))
1493
1524
                size = min(size, self._size - offset)
1494
 
            ranges.append((offset, size))
 
1525
            ranges.append((base_offset + offset, size))
1495
1526
        if not ranges:
1496
1527
            return
1497
1528
        elif bytes is not None:
1498
1529
            # already have the whole file
1499
 
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
1500
 
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
 
1530
            data_ranges = [(start, bytes[start:start+size])
 
1531
                           for start, size in ranges]
1501
1532
        elif self._file is None:
1502
1533
            data_ranges = self._transport.readv(self._name, ranges)
1503
1534
        else:
1506
1537
                self._file.seek(offset)
1507
1538
                data_ranges.append((offset, self._file.read(size)))
1508
1539
        for offset, data in data_ranges:
 
1540
            offset -= base_offset
1509
1541
            if offset == 0:
1510
1542
                # extract the header
1511
1543
                offset, data = self._parse_header_from_bytes(data)