← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/btree_index.py

  • Committer: Joe Julian
  • Date: 2010-01-10 02:25:31 UTC
  • mto: (4634.119.7 2.0)
  • mto: This revision was merged to the branch mainline in revision 4959.
  • Revision ID: joe@julianfamily.org-20100110022531-wqk61rsagz8xsiga
https://launchpad.net/bugs/175839
Added MANIFEST.in to allow bdist_rpm to have all the required include files and tools. bdist_rpm will still fail to build correctly on some distributions due to a disttools bug http://bugs.python.org/issue644744

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/btree_index.py
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
34
    )
37
35
from bzrlib.index import _OPTION_NODE_REFS, _OPTION_KEY_ELEMENTS, _OPTION_LEN
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(get_transport('.'), '<temp>', size)
 
188
        new_backing = BTreeGraphIndex(get_transport(dir_path),
 
189
                                      base_name, size)
197
190
        # GC will clean up the file
198
191
        new_backing._file = new_backing_file
199
192
        if self._combine_backing_indices:
204
197
                self._backing_indices[backing_pos] = None
205
198
        else:
206
199
            self._backing_indices.append(new_backing)
 
200
        self._keys = set()
207
201
        self._nodes = {}
208
202
        self._nodes_by_key = None
209
203
 
385
379
        for row in reversed(rows):
386
380
            pad = (type(row) != _LeafBuilderRow)
387
381
            row.finish_node(pad=pad)
 
382
        result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
388
383
        lines = [_BTSIGNATURE]
389
384
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
390
385
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
391
386
        lines.append(_OPTION_LEN + str(key_count) + '\n')
392
387
        row_lengths = [row.nodes for row in rows]
393
388
        lines.append(_OPTION_ROW_LENGTHS + ','.join(map(str, row_lengths)) + '\n')
394
 
        if row_lengths and row_lengths[-1] > 1:
395
 
            result = tempfile.NamedTemporaryFile(prefix='bzr-index-')
396
 
        else:
397
 
            result = cStringIO.StringIO()
398
389
        result.writelines(lines)
399
390
        position = sum(map(len, lines))
400
391
        root_row = True
411
402
            # Special case the first node as it may be prefixed
412
403
            node = row.spool.read(_PAGE_SIZE)
413
404
            result.write(node[reserved:])
414
 
            if len(node) == _PAGE_SIZE:
415
 
                result.write("\x00" * (reserved - position))
 
405
            result.write("\x00" * (reserved - position))
416
406
            position = 0 # Only the root row actually has an offset
417
407
            copied_len = osutils.pumpfile(row.spool, result)
418
408
            if copied_len != (row.nodes - 1) * _PAGE_SIZE:
463
453
            efficient order for the index (keys iteration order in this case).
464
454
        """
465
455
        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]
 
456
        local_keys = keys.intersection(self._keys)
475
457
        if self.reference_lists:
476
458
            for key in local_keys:
477
 
                node = nodes[key]
 
459
                node = self._nodes[key]
478
460
                yield self, key, node[1], node[0]
479
461
        else:
480
462
            for key in local_keys:
481
 
                node = nodes[key]
 
463
                node = self._nodes[key]
482
464
                yield self, key, node[1]
483
465
        # Find things that are in backing indices that have not been handled
484
466
        # yet.
594
576
 
595
577
        For InMemoryGraphIndex the estimate is exact.
596
578
        """
597
 
        return len(self._nodes) + sum(backing.key_count() for backing in
 
579
        return len(self._keys) + sum(backing.key_count() for backing in
598
580
            self._backing_indices if backing is not None)
599
581
 
600
582
    def validate(self):
632
614
    def _parse_lines(self, lines):
633
615
        nodes = []
634
616
        self.offset = int(lines[1][7:])
635
 
        as_st = static_tuple.StaticTuple.from_sequence
636
617
        for line in lines[2:]:
637
618
            if line == '':
638
619
                break
639
 
            nodes.append(as_st(map(intern, line.split('\0'))).intern())
 
620
            nodes.append(tuple(map(intern, line.split('\0'))))
640
621
        return nodes
641
622
 
642
623
 
862
843
            new_tips = next_tips
863
844
        return final_offsets
864
845
 
865
 
    def clear_cache(self):
866
 
        """Clear out any cached/memoized values.
867
 
 
868
 
        This can be called at any time, but generally it is used when we have
869
 
        extracted some information, but don't expect to be requesting any more
870
 
        from this index.
871
 
        """
872
 
        # Note that we don't touch self._root_node or self._internal_node_cache
873
 
        # We don't expect either of those to be big, and it can save
874
 
        # round-trips in the future. We may re-evaluate this if InternalNode
875
 
        # memory starts to be an issue.
876
 
        self._leaf_node_cache.clear()
877
 
 
878
846
    def external_references(self, ref_list_num):
879
847
        if self._root_node is None:
880
848
            self._get_root_node()
1564
1532
 
1565
1533
try:
1566
1534
    from bzrlib import _btree_serializer_pyx as _btree_serializer
1567
 
except ImportError, e:
1568
 
    osutils.failed_to_load_extension(e)
 
1535
except ImportError:
1569
1536
    from bzrlib import _btree_serializer_py as _btree_serializer