← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Gordon Tyler
  • Date: 2009-11-11 21:38:02 UTC
  • mto: This revision was merged to the branch mainline in revision 4801.
  • Revision ID: gordon@doxxx.net-20091111213802-wj8d2fgirjd7saqn
Fixed globbing.normalize_pattern to not strip '/' down to '' and normalize multiple slashes.

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
 
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):
632
624
    def _parse_lines(self, lines):
633
625
        nodes = []
634
626
        self.offset = int(lines[1][7:])
635
 
        as_st = static_tuple.StaticTuple.from_sequence
636
627
        for line in lines[2:]:
637
628
            if line == '':
638
629
                break
639
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
630
            # TODO: Switch to StaticTuple here.
 
631
            nodes.append(tuple(map(intern, line.split('\0'))))
640
632
        return nodes
641
633
 
642
634
 
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)