← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: John Arbash Meinel
  • Date: 2009-10-12 21:44:27 UTC
  • mto: This revision was merged to the branch mainline in revision 4737.
  • Revision ID: john@arbash-meinel.com-20091012214427-zddi1kmc2jlf7v31
Py_ssize_t and its associated function typedefs are not available w/ python 2.4

So we define them in python-compat.h
Even further, gcc issued a warning for:
static int
_workaround_pyrex_096()
So we changed it to:
_workaround_pyrex_096(void)

Also, some python api funcs were incorrectly defined as 'char *' when they meant
'const char *'. Work around that with a (char *) cast, to avoid compiler warnings.

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
        self._nodes[key] = (node_refs, value)
 
167
        self._keys.add(key)
170
168
        if self._nodes_by_key is not None and self._key_length > 1:
171
169
            self._update_nodes_by_key(key, value, node_refs)
172
 
        if len(self._nodes) < self._spill_at:
 
170
        if len(self._keys) < self._spill_at:
173
171
            return
174
172
        self._spill_mem_keys_to_disk()
175
173
 
204
202
                self._backing_indices[backing_pos] = None
205
203
        else:
206
204
            self._backing_indices.append(new_backing)
 
205
        self._keys = set()
207
206
        self._nodes = {}
208
207
        self._nodes_by_key = None
209
208
 
411
410
            # Special case the first node as it may be prefixed
412
411
            node = row.spool.read(_PAGE_SIZE)
413
412
            result.write(node[reserved:])
414
 
            if len(node) == _PAGE_SIZE:
415
 
                result.write("\x00" * (reserved - position))
 
413
            result.write("\x00" * (reserved - position))
416
414
            position = 0 # Only the root row actually has an offset
417
415
            copied_len = osutils.pumpfile(row.spool, result)
418
416
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
463
461
            efficient order for the index (keys iteration order in this case).
464
462
        """
465
463
        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]
 
464
        local_keys = keys.intersection(self._keys)
475
465
        if self.reference_lists:
476
466
            for key in local_keys:
477
 
                node = nodes[key]
 
467
                node = self._nodes[key]
478
468
                yield self, key, node[1], node[0]
479
469
        else:
480
470
            for key in local_keys:
481
 
                node = nodes[key]
 
471
                node = self._nodes[key]
482
472
                yield self, key, node[1]
483
473
        # Find things that are in backing indices that have not been handled
484
474
        # yet.
567
557
                    else:
568
558
                        # yield keys
569
559
                        for value in key_dict.itervalues():
570
 
                            yield (self, ) + tuple(value)
 
560
                            yield (self, ) + value
571
561
            else:
572
562
                yield (self, ) + key_dict
573
563
 
594
584
 
595
585
        For InMemoryGraphIndex the estimate is exact.
596
586
        """
597
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
587
        return len(self._keys) + sum(backing.key_count() for backing in
598
588
            self._backing_indices if backing is not None)
599
589
 
600
590
    def validate(self):
632
622
    def _parse_lines(self, lines):
633
623
        nodes = []
634
624
        self.offset = int(lines[1][7:])
635
 
        as_st = static_tuple.StaticTuple.from_sequence
636
625
        for line in lines[2:]:
637
626
            if line == '':
638
627
                break
639
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
628
            nodes.append(tuple(map(intern, line.split('\0'))))
640
629
        return nodes
641
630
 
642
631
 
647
636
    memory except when very large walks are done.
648
637
    """
649
638
 
650
 
    def __init__(self, transport, name, size, unlimited_cache=False,
651
 
                 offset=0):
 
639
    def __init__(self, transport, name, size):
652
640
        """Create a B+Tree index object on the index name.
653
641
 
654
642
        :param transport: The transport to read data for the index from.
658
646
            the initial read (to read the root node header) can be done
659
647
            without over-reading even on empty indices, and on small indices
660
648
            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
649
        """
667
650
        self._transport = transport
668
651
        self._name = name
670
653
        self._file = None
671
654
        self._recommended_pages = self._compute_recommended_pages()
672
655
        self._root_node = None
673
 
        self._base_offset = offset
674
656
        # Default max size is 100,000 leave values
675
657
        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)
 
658
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
659
        # We could limit this, but even a 300k record btree has only 3k leaf
 
660
        # nodes, and only 20 internal nodes. So the default of 100 nodes in an
 
661
        # LRU would mean we always cache everything anyway, no need to pay the
 
662
        # overhead of LRU
 
663
        self._internal_node_cache = fifo_cache.FIFOCache(100)
685
664
        self._key_count = None
686
665
        self._row_lengths = None
687
666
        self._row_offsets = None # Start of each row, [-1] is the end
719
698
                if start_of_leaves is None:
720
699
                    start_of_leaves = self._row_offsets[-2]
721
700
                if node_pos < start_of_leaves:
722
 
                    self._internal_node_cache[node_pos] = node
 
701
                    self._internal_node_cache.add(node_pos, node)
723
702
                else:
724
 
                    self._leaf_node_cache[node_pos] = node
 
703
                    self._leaf_node_cache.add(node_pos, node)
725
704
            found[node_pos] = node
726
705
        return found
727
706
 
866
845
            new_tips = next_tips
867
846
        return final_offsets
868
847
 
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
848
    def external_references(self, ref_list_num):
883
849
        if self._root_node is None:
884
850
            self._get_root_node()
1498
1464
        # list of (offset, length) regions of the file that should, evenually
1499
1465
        # be read in to data_ranges, either from 'bytes' or from the transport
1500
1466
        ranges = []
1501
 
        base_offset = self._base_offset
1502
1467
        for index in nodes:
1503
 
            offset = (index * _PAGE_SIZE)
 
1468
            offset = index * _PAGE_SIZE
1504
1469
            size = _PAGE_SIZE
1505
1470
            if index == 0:
1506
1471
                # Root node - special case
1510
1475
                    # The only case where we don't know the size, is for very
1511
1476
                    # small indexes. So we read the whole thing
1512
1477
                    bytes = self._transport.get_bytes(self._name)
1513
 
                    num_bytes = len(bytes)
1514
 
                    self._size = num_bytes - base_offset
 
1478
                    self._size = len(bytes)
1515
1479
                    # 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)]
 
1480
                    ranges.append((0, len(bytes)))
1518
1481
                    break
1519
1482
            else:
1520
1483
                if offset > self._size:
1522
1485
                                         ' of the file %s > %s'
1523
1486
                                         % (offset, self._size))
1524
1487
                size = min(size, self._size - offset)
1525
 
            ranges.append((base_offset + offset, size))
 
1488
            ranges.append((offset, size))
1526
1489
        if not ranges:
1527
1490
            return
1528
1491
        elif bytes is not None:
1529
1492
            # already have the whole file
1530
 
            data_ranges = [(start, bytes[start:start+size])
1531
 
                           for start, size in ranges]
 
1493
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1494
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1532
1495
        elif self._file is None:
1533
1496
            data_ranges = self._transport.readv(self._name, ranges)
1534
1497
        else:
1537
1500
                self._file.seek(offset)
1538
1501
                data_ranges.append((offset, self._file.read(size)))
1539
1502
        for offset, data in data_ranges:
1540
 
            offset -= base_offset
1541
1503
            if offset == 0:
1542
1504
                # extract the header
1543
1505
                offset, data = self._parse_header_from_bytes(data)