← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Andrew Bennetts
  • Date: 2009-10-26 06:44:40 UTC
  • mfrom: (4634.77.9 2.0)
  • mto: This revision was merged to the branch mainline in revision 4770.
  • Revision ID: andrew.bennetts@canonical.com-20091026064440-06u7tpg7l6sjkh8h
Merge lp:bzr/2.0 into lp:bzr.

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