/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: Vincent Ladeuil
  • Date: 2009-09-02 08:26:27 UTC
  • mto: (4669.1.1 integration)
  • mto: This revision was merged to the branch mainline in revision 4670.
  • Revision ID: v.ladeuil+lp@free.fr-20090902082627-cit8vm6tefu9hwk2
Cleanup emacs-bzr-send-XXXXXX.el leaks in /tmp during selftest.

* tests/test_mail_client.py:
(TestEmacsMail.test_commandline,
TestEmacsMail.test_commandline_is_8bit): Cleanup the generated tmp
file.

* mail_client.py:
(EmacsMail.__init__, EmacsMail._get_compose_commandline): Keep
track of the tmp file to ease cleanup during testing.

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
17
17
 
18
18
"""B+Tree indices"""
19
19
 
20
 
import cStringIO
21
20
from bisect import bisect_right
22
21
import math
23
22
import tempfile
31
30
    index,
32
31
    lru_cache,
33
32
    osutils,
34
 
    static_tuple,
35
33
    trace,
36
 
    transport,
37
34
    )
38
35
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
 
36
from bzrlib.transport import get_transport
39
37
 
40
38
 
41
39
_BTSIGNATURE = "B+Tree Graph Index 2\n"
62
60
    def __init__(self):
63
61
        """Create a _BuilderRow."""
64
62
        self.nodes = 0
65
 
        self.spool = None# tempfile.TemporaryFile(prefix='bzr-index-row-')
 
63
        self.spool = tempfile.TemporaryFile()
66
64
        self.writer = None
67
65
 
68
66
    def finish_node(self, pad=True):
69
67
        byte_lines, _, padding = self.writer.finish()
70
68
        if self.nodes == 0:
71
 
            self.spool = cStringIO.StringIO()
72
69
            # padded note:
73
70
            self.spool.write("\x00" * _RESERVED_HEADER_BYTES)
74
 
        elif self.nodes == 1:
75
 
            # We got bigger than 1 node, switch to a temp file
76
 
            spool = tempfile.TemporaryFile(prefix='bzr-index-row-')
77
 
            spool.write(self.spool.getvalue())
78
 
            self.spool = spool
79
71
        skipped_bytes = 0
80
72
        if not pad and padding:
81
73
            del byte_lines[-1]
160
152
        :param value: The value to associate with the key. It may be any
161
153
            bytes as long as it does not contain \0 or \n.
162
154
        """
163
 
        # Ensure that 'key' is a StaticTuple
164
 
        key = static_tuple.StaticTuple.from_sequence(key).intern()
165
155
        # we don't care about absent_references
166
156
        node_refs, _ = self._check_key_ref_value(key, references, value)
167
157
        if key in self._nodes:
168
158
            raise errors.BadIndexDuplicateKey(key, self)
169
 
        self._nodes[key] = static_tuple.StaticTuple(node_refs, value)
 
159
        self._nodes[key] = (node_refs, value)
 
160
        self._keys.add(key)
170
161
        if self._nodes_by_key is not None and self._key_length > 1:
171
162
            self._update_nodes_by_key(key, value, node_refs)
172
 
        if len(self._nodes) < self._spill_at:
 
163
        if len(self._keys) < self._spill_at:
173
164
            return
174
165
        self._spill_mem_keys_to_disk()
175
166
 
191
182
             backing_pos) = self._spill_mem_keys_and_combine()
192
183
        else:
193
184
            new_backing_file, size = self._spill_mem_keys_without_combining()
 
185
        dir_path, base_name = osutils.split(new_backing_file.name)
194
186
        # Note: The transport here isn't strictly needed, because we will use
195
187
        #       direct access to the new_backing._file object
196
 
        new_backing = BTreeGraphIndex(transport.get_transport('.'),
197
 
                                      '<temp>', size)
 
188
        new_backing = BTreeGraphIndex(get_transport(dir_path),
 
189
                                      base_name, size)
198
190
        # GC will clean up the file
199
191
        new_backing._file = new_backing_file
200
192
        if self._combine_backing_indices:
205
197
                self._backing_indices[backing_pos] = None
206
198
        else:
207
199
            self._backing_indices.append(new_backing)
 
200
        self._keys = set()
208
201
        self._nodes = {}
209
202
        self._nodes_by_key = None
210
203
 
386
379
        for row in reversed(rows):
387
380
            pad = (type(row) != _LeafBuilderRow)
388
381
            row.finish_node(pad=pad)
 
382
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
389
383
        lines = [_BTSIGNATURE]
390
384
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
391
385
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
392
386
        lines.append(_OPTION_LEN + str(key_count) + '\n')
393
387
        row_lengths = [row.nodes for row in rows]
394
388
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
395
 
        if row_lengths and row_lengths[-1] > 1:
396
 
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
397
 
        else:
398
 
            result = cStringIO.StringIO()
399
389
        result.writelines(lines)
400
390
        position = sum(map(len, lines))
401
391
        root_row = True
412
402
            # Special case the first node as it may be prefixed
413
403
            node = row.spool.read(_PAGE_SIZE)
414
404
            result.write(node[reserved:])
415
 
            if len(node) == _PAGE_SIZE:
416
 
                result.write("\x00" * (reserved - position))
 
405
            result.write("\x00" * (reserved - position))
417
406
            position = 0 # Only the root row actually has an offset
418
407
            copied_len = osutils.pumpfile(row.spool, result)
419
408
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
464
453
            efficient order for the index (keys iteration order in this case).
465
454
        """
466
455
        keys = set(keys)
467
 
        # Note: We don't use keys.intersection() here. If you read the C api,
468
 
        #       set.intersection(other) special cases when other is a set and
469
 
        #       will iterate the smaller of the two and lookup in the other.
470
 
        #       It does *not* do this for any other type (even dict, unlike
471
 
        #       some other set functions.) Since we expect keys is generally <<
472
 
        #       self._nodes, it is faster to iterate over it in a list
473
 
        #       comprehension
474
 
        nodes = self._nodes
475
 
        local_keys = [key for key in keys if key in nodes]
 
456
        local_keys = keys.intersection(self._keys)
476
457
        if self.reference_lists:
477
458
            for key in local_keys:
478
 
                node = nodes[key]
 
459
                node = self._nodes[key]
479
460
                yield self, key, node[1], node[0]
480
461
        else:
481
462
            for key in local_keys:
482
 
                node = nodes[key]
 
463
                node = self._nodes[key]
483
464
                yield self, key, node[1]
484
465
        # Find things that are in backing indices that have not been handled
485
466
        # yet.
568
549
                    else:
569
550
                        # yield keys
570
551
                        for value in key_dict.itervalues():
571
 
                            yield (self, ) + tuple(value)
 
552
                            yield (self, ) + value
572
553
            else:
573
554
                yield (self, ) + key_dict
574
555
 
595
576
 
596
577
        For InMemoryGraphIndex the estimate is exact.
597
578
        """
598
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
579
        return len(self._keys) + sum(backing.key_count() for backing in
599
580
            self._backing_indices if backing is not None)
600
581
 
601
582
    def validate(self):
633
614
    def _parse_lines(self, lines):
634
615
        nodes = []
635
616
        self.offset = int(lines[1][7:])
636
 
        as_st = static_tuple.StaticTuple.from_sequence
637
617
        for line in lines[2:]:
638
618
            if line == '':
639
619
                break
640
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
620
            nodes.append(tuple(map(intern, line.split('\0'))))
641
621
        return nodes
642
622
 
643
623
 
648
628
    memory except when very large walks are done.
649
629
    """
650
630
 
651
 
    def __init__(self, transport, name, size, unlimited_cache=False,
652
 
                 offset=0):
 
631
    def __init__(self, transport, name, size):
653
632
        """Create a B+Tree index object on the index name.
654
633
 
655
634
        :param transport: The transport to read data for the index from.
659
638
            the initial read (to read the root node header) can be done
660
639
            without over-reading even on empty indices, and on small indices
661
640
            allows single-IO to read the entire index.
662
 
        :param unlimited_cache: If set to True, then instead of using an
663
 
            LRUCache with size _NODE_CACHE_SIZE, we will use a dict and always
664
 
            cache all leaf nodes.
665
 
        :param offset: The start of the btree index data isn't byte 0 of the
666
 
            file. Instead it starts at some point later.
667
641
        """
668
642
        self._transport = transport
669
643
        self._name = name
671
645
        self._file = None
672
646
        self._recommended_pages = self._compute_recommended_pages()
673
647
        self._root_node = None
674
 
        self._base_offset = offset
675
648
        # Default max size is 100,000 leave values
676
649
        self._leaf_value_cache = None # lru_cache.LRUCache(100*1000)
677
 
        if unlimited_cache:
678
 
            self._leaf_node_cache = {}
679
 
            self._internal_node_cache = {}
680
 
        else:
681
 
            self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
682
 
            # We use a FIFO here just to prevent possible blowout. However, a
683
 
            # 300k record btree has only 3k leaf nodes, and only 20 internal
684
 
            # nodes. A value of 100 scales to ~100*100*100 = 1M records.
685
 
            self._internal_node_cache = fifo_cache.FIFOCache(100)
 
650
        self._leaf_node_cache = lru_cache.LRUCache(_NODE_CACHE_SIZE)
 
651
        # We could limit this, but even a 300k record btree has only 3k leaf
 
652
        # nodes, and only 20 internal nodes. So the default of 100 nodes in an
 
653
        # LRU would mean we always cache everything anyway, no need to pay the
 
654
        # overhead of LRU
 
655
        self._internal_node_cache = fifo_cache.FIFOCache(100)
686
656
        self._key_count = None
687
657
        self._row_lengths = None
688
658
        self._row_offsets = None # Start of each row, [-1] is the end
720
690
                if start_of_leaves is None:
721
691
                    start_of_leaves = self._row_offsets[-2]
722
692
                if node_pos < start_of_leaves:
723
 
                    self._internal_node_cache[node_pos] = node
 
693
                    self._internal_node_cache.add(node_pos, node)
724
694
                else:
725
 
                    self._leaf_node_cache[node_pos] = node
 
695
                    self._leaf_node_cache.add(node_pos, node)
726
696
            found[node_pos] = node
727
697
        return found
728
698
 
867
837
            new_tips = next_tips
868
838
        return final_offsets
869
839
 
870
 
    def clear_cache(self):
871
 
        """Clear out any cached/memoized values.
872
 
 
873
 
        This can be called at any time, but generally it is used when we have
874
 
        extracted some information, but don't expect to be requesting any more
875
 
        from this index.
876
 
        """
877
 
        # Note that we don't touch self._root_node or self._internal_node_cache
878
 
        # We don't expect either of those to be big, and it can save
879
 
        # round-trips in the future. We may re-evaluate this if InternalNode
880
 
        # memory starts to be an issue.
881
 
        self._leaf_node_cache.clear()
882
 
 
883
840
    def external_references(self, ref_list_num):
884
841
        if self._root_node is None:
885
842
            self._get_root_node()
1499
1456
        # list of (offset, length) regions of the file that should, evenually
1500
1457
        # be read in to data_ranges, either from 'bytes' or from the transport
1501
1458
        ranges = []
1502
 
        base_offset = self._base_offset
1503
1459
        for index in nodes:
1504
 
            offset = (index * _PAGE_SIZE)
 
1460
            offset = index * _PAGE_SIZE
1505
1461
            size = _PAGE_SIZE
1506
1462
            if index == 0:
1507
1463
                # Root node - special case
1511
1467
                    # The only case where we don't know the size, is for very
1512
1468
                    # small indexes. So we read the whole thing
1513
1469
                    bytes = self._transport.get_bytes(self._name)
1514
 
                    num_bytes = len(bytes)
1515
 
                    self._size = num_bytes - base_offset
 
1470
                    self._size = len(bytes)
1516
1471
                    # the whole thing should be parsed out of 'bytes'
1517
 
                    ranges = [(start, min(_PAGE_SIZE, num_bytes - start))
1518
 
                        for start in xrange(base_offset, num_bytes, _PAGE_SIZE)]
 
1472
                    ranges.append((0, len(bytes)))
1519
1473
                    break
1520
1474
            else:
1521
1475
                if offset > self._size:
1523
1477
                                         ' of the file %s > %s'
1524
1478
                                         % (offset, self._size))
1525
1479
                size = min(size, self._size - offset)
1526
 
            ranges.append((base_offset + offset, size))
 
1480
            ranges.append((offset, size))
1527
1481
        if not ranges:
1528
1482
            return
1529
1483
        elif bytes is not None:
1530
1484
            # already have the whole file
1531
 
            data_ranges = [(start, bytes[start:start+size])
1532
 
                           for start, size in ranges]
 
1485
            data_ranges = [(start, bytes[start:start+_PAGE_SIZE])
 
1486
                           for start in xrange(0, len(bytes), _PAGE_SIZE)]
1533
1487
        elif self._file is None:
1534
1488
            data_ranges = self._transport.readv(self._name, ranges)
1535
1489
        else:
1538
1492
                self._file.seek(offset)
1539
1493
                data_ranges.append((offset, self._file.read(size)))
1540
1494
        for offset, data in data_ranges:
1541
 
            offset -= base_offset
1542
1495
            if offset == 0:
1543
1496
                # extract the header
1544
1497
                offset, data = self._parse_header_from_bytes(data)
1573
1526
 
1574
1527
try:
1575
1528
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1576
 
except ImportError, e:
1577
 
    osutils.failed_to_load_extension(e)
 
1529
except ImportError:
1578
1530
    from bzrlib import _btree_serializer_py as _btree_serializer