/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-11-07 00:28:26 UTC
  • mto: This revision was merged to the branch mainline in revision 4842.
  • Revision ID: john@arbash-meinel.com-20091107002826-umvwb3zl0yajo6rc
Use StaticTuple as part of the builder process.

Also use it in the pure python btree parser, mostly for consistency.

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
160
160
        :param value: The value to associate with the key. It may be any
161
161
            bytes as long as it does not contain \0 or \n.
162
162
        """
163
 
        # Ensure that 'key' is a StaticTuple
164
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
165
163
        # we don't care about absent_references
166
164
        node_refs, _ = self._check_key_ref_value(key, references, value)
167
165
        if key in self._nodes:
168
166
            raise errors.BadIndexDuplicateKey(key, self)
169
167
        self._nodes[key] = static_tuple.StaticTuple(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
 
463
463
            efficient order for the index (keys iteration order in this case).
464
464
        """
465
465
        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]
 
466
        local_keys = keys.intersection(self._keys)
475
467
        if self.reference_lists:
476
468
            for key in local_keys:
477
 
                node = nodes[key]
 
469
                node = self._nodes[key]
478
470
                yield self, key, node[1], node[0]
479
471
        else:
480
472
            for key in local_keys:
481
 
                node = nodes[key]
 
473
                node = self._nodes[key]
482
474
                yield self, key, node[1]
483
475
        # Find things that are in backing indices that have not been handled
484
476
        # yet.
567
559
                    else:
568
560
                        # yield keys
569
561
                        for value in key_dict.itervalues():
570
 
                            yield (self, ) + tuple(value)
 
562
                            yield (self, ) + value
571
563
            else:
572
564
                yield (self, ) + key_dict
573
565
 
594
586
 
595
587
        For InMemoryGraphIndex the estimate is exact.
596
588
        """
597
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
589
        return len(self._keys) + sum(backing.key_count() for backing in
598
590
            self._backing_indices if backing is not None)
599
591
 
600
592
    def validate(self):
647
639
    memory except when very large walks are done.
648
640
    """
649
641
 
650
 
    def __init__(self, transport, name, size, unlimited_cache=False,
651
 
                 offset=0):
 
642
    def __init__(self, transport, name, size, unlimited_cache=False):
652
643
        """Create a B+Tree index object on the index name.
653
644
 
654
645
        :param transport: The transport to read data for the index from.
661
652
        :param unlimited_cache: If set to True, then instead of using an
662
653
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
663
654
            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
655
        """
667
656
        self._transport = transport
668
657
        self._name = name
670
659
        self._file = None
671
660
        self._recommended_pages = self._compute_recommended_pages()
672
661
        self._root_node = None
673
 
        self._base_offset = offset
674
662
        # Default max size is 100,000 leave values
675
663
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
676
664
        if unlimited_cache:
1498
1486
        # list of (offset, length) regions of the file that should, evenually
1499
1487
        # be read in to data_ranges, either from 'bytes' or from the transport
1500
1488
        ranges = []
1501
 
        base_offset = self._base_offset
1502
1489
        for index in nodes:
1503
 
            offset = (index * _PAGE_SIZE)
 
1490
            offset = index * _PAGE_SIZE
1504
1491
            size = _PAGE_SIZE
1505
1492
            if index == 0:
1506
1493
                # Root node - special case
1510
1497
                    # The only case where we don't know the size, is for very
1511
1498
                    # small indexes. So we read the whole thing
1512
1499
                    bytes = self._transport.get_bytes(self._name)
1513
 
                    num_bytes = len(bytes)
1514
 
                    self._size = num_bytes - base_offset
 
1500
                    self._size = len(bytes)
1515
1501
                    # 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)]
 
1502
                    ranges.append((0, len(bytes)))
1518
1503
                    break
1519
1504
            else:
1520
1505
                if offset > self._size:
1522
1507
                                         ' of the file %s > %s'
1523
1508
                                         % (offset, self._size))
1524
1509
                size = min(size, self._size - offset)
1525
 
            ranges.append((base_offset + offset, size))
 
1510
            ranges.append((offset, size))
1526
1511
        if not ranges:
1527
1512
            return
1528
1513
        elif bytes is not None:
1529
1514
            # already have the whole file
1530
 
            data_ranges = [(start, bytes[start:start+size])
1531
 
                           for start, size in ranges]
 
1515
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1516
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1532
1517
        elif self._file is None:
1533
1518
            data_ranges = self._transport.readv(self._name, ranges)
1534
1519
        else:
1537
1522
                self._file.seek(offset)
1538
1523
                data_ranges.append((offset, self._file.read(size)))
1539
1524
        for offset, data in data_ranges:
1540
 
            offset -= base_offset
1541
1525
            if offset == 0:
1542
1526
                # extract the header
1543
1527
                offset, data = self._parse_header_from_bytes(data)