← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-09-18 03:34:31 UTC
  • mfrom: (4699.1.1 bzr.faster-test-no-assert)
  • Revision ID: pqm@pqm.ubuntu.com-20090918033431-imjyd17yze1okeap
(Harald Meland) Make test_no_asserts 7x faster.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2007, 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
40
40
    debug,
41
41
    errors,
42
42
    )
43
 
from bzrlib.static_tuple import StaticTuple
44
43
 
45
44
_HEADER_READV = (0, 200)
46
45
_OPTION_KEY_ELEMENTS = "key_elements="
93
92
        :param key_elements: The number of bytestrings in each key.
94
93
        """
95
94
        self.reference_lists = reference_lists
 
95
        self._keys = set()
96
96
        # A dict of {key: (absent, ref_lists, value)}
97
97
        self._nodes = {}
98
 
        # Keys that are referenced but not actually present in this index
99
 
        self._absent_keys = set()
100
98
        self._nodes_by_key = None
101
99
        self._key_length = key_elements
102
100
        self._optimize_for_size = False
104
102
 
105
103
    def _check_key(self, key):
106
104
        """Raise BadIndexKey if key is not a valid key for this index."""
107
 
        if type(key) not in (tuple, StaticTuple):
 
105
        if type(key) != tuple:
108
106
            raise errors.BadIndexKey(key)
109
107
        if self._key_length != len(key):
110
108
            raise errors.BadIndexKey(key)
166
164
            return
167
165
        key_dict = self._nodes_by_key
168
166
        if self.reference_lists:
169
 
            key_value = StaticTuple(key, value, node_refs)
 
167
            key_value = key, value, node_refs
170
168
        else:
171
 
            key_value = StaticTuple(key, value)
 
169
            key_value = key, value
172
170
        for subkey in key[:-1]:
173
171
            key_dict = key_dict.setdefault(subkey, {})
174
172
        key_dict[key[-1]] = key_value
190
188
                                This may contain duplicates if the same key is
191
189
                                referenced in multiple lists.
192
190
        """
193
 
        as_st = StaticTuple.from_sequence
194
191
        self._check_key(key)
195
192
        if _newline_null_re.search(value) is not None:
196
193
            raise errors.BadIndexValue(value)
205
202
                if reference not in self._nodes:
206
203
                    self._check_key(reference)
207
204
                    absent_references.append(reference)
208
 
            reference_list = as_st([as_st(ref).intern()
209
 
                                    for ref in reference_list])
210
 
            node_refs.append(reference_list)
211
 
        return as_st(node_refs), absent_references
 
205
            node_refs.append(tuple(reference_list))
 
206
        return tuple(node_refs), absent_references
212
207
 
213
208
    def add_node(self, key, value, references=()):
214
209
        """Add a node to the index.
229
224
            # There may be duplicates, but I don't think it is worth worrying
230
225
            # about
231
226
            self._nodes[reference] = ('a', (), '')
232
 
        self._absent_keys.update(absent_references)
233
 
        self._absent_keys.discard(key)
234
227
        self._nodes[key] = ('', node_refs, value)
 
228
        self._keys.add(key)
235
229
        if self._nodes_by_key is not None and self._key_length > 1:
236
230
            self._update_nodes_by_key(key, value, node_refs)
237
231
 
238
 
    def clear_cache(self):
239
 
        """See GraphIndex.clear_cache()
240
 
 
241
 
        This is a no-op, but we need the api to conform to a generic 'Index'
242
 
        abstraction.
243
 
        """
244
 
        
245
232
    def finish(self):
246
233
        lines = [_SIGNATURE]
247
234
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
248
235
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
249
 
        key_count = len(self._nodes) - len(self._absent_keys)
250
 
        lines.append(_OPTION_LEN + str(key_count) + '\n')
 
236
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
251
237
        prefix_length = sum(len(x) for x in lines)
252
238
        # references are byte offsets. To avoid having to do nasty
253
239
        # polynomial work to resolve offsets (references to later in the
382
368
    suitable for production use. :XXX
383
369
    """
384
370
 
385
 
    def __init__(self, transport, name, size, unlimited_cache=False):
 
371
    def __init__(self, transport, name, size):
386
372
        """Open an index called name on transport.
387
373
 
388
374
        :param transport: A bzrlib.transport.Transport.
455
441
        trailers = 0
456
442
        pos = stream.tell()
457
443
        lines = stream.read().split('\n')
458
 
        stream.close()
459
444
        del lines[-1]
460
445
        _, _, _, trailers = self._parse_lines(lines, pos)
461
446
        for key, absent, references, value in self._keys_by_offset.itervalues():
468
453
                node_value = value
469
454
            self._nodes[key] = node_value
470
455
        # cache the keys for quick set intersections
 
456
        self._keys = set(self._nodes)
471
457
        if trailers != 1:
472
458
            # there must be one line - the empty trailer line.
473
459
            raise errors.BadIndexData(self)
474
460
 
475
 
    def clear_cache(self):
476
 
        """Clear out any cached/memoized values.
477
 
 
478
 
        This can be called at any time, but generally it is used when we have
479
 
        extracted some information, but don't expect to be requesting any more
480
 
        from this index.
481
 
        """
482
 
 
483
461
    def external_references(self, ref_list_num):
484
462
        """Return references that are not present in this index.
485
463
        """
488
466
            raise ValueError('No ref list %d, index has %d ref lists'
489
467
                % (ref_list_num, self.node_ref_lists))
490
468
        refs = set()
491
 
        nodes = self._nodes
492
 
        for key, (value, ref_lists) in nodes.iteritems():
 
469
        for key, (value, ref_lists) in self._nodes.iteritems():
493
470
            ref_list = ref_lists[ref_list_num]
494
 
            refs.update([ref for ref in ref_list if ref not in nodes])
495
 
        return refs
 
471
            refs.update(ref_list)
 
472
        return refs - self._keys
496
473
 
497
474
    def _get_nodes_by_key(self):
498
475
        if self._nodes_by_key is None:
625
602
 
626
603
    def _iter_entries_from_total_buffer(self, keys):
627
604
        """Iterate over keys when the entire index is parsed."""
628
 
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
629
 
        #       .intersection() here
630
 
        nodes = self._nodes
631
 
        keys = [key for key in keys if key in nodes]
 
605
        keys = keys.intersection(self._keys)
632
606
        if self.node_ref_lists:
633
607
            for key in keys:
634
 
                value, node_refs = nodes[key]
 
608
                value, node_refs = self._nodes[key]
635
609
                yield self, key, value, node_refs
636
610
        else:
637
611
            for key in keys:
638
 
                yield self, key, nodes[key]
 
612
                yield self, key, self._nodes[key]
639
613
 
640
614
    def iter_entries(self, keys):
641
615
        """Iterate over keys within the index.
1178
1152
            self._parsed_key_map.insert(index + 1, new_key)
1179
1153
 
1180
1154
    def _read_and_parse(self, readv_ranges):
1181
 
        """Read the ranges and parse the resulting data.
 
1155
        """Read the the ranges and parse the resulting data.
1182
1156
 
1183
1157
        :param readv_ranges: A prepared readv range list.
1184
1158
        """
1249
1223
                self.__class__.__name__,
1250
1224
                ', '.join(map(repr, self._indices)))
1251
1225
 
1252
 
    def clear_cache(self):
1253
 
        """See GraphIndex.clear_cache()"""
1254
 
        for index in self._indices:
1255
 
            index.clear_cache()
1256
 
 
1257
1226
    def get_parent_map(self, keys):
1258
1227
        """See graph.StackedParentsProvider.get_parent_map"""
1259
1228
        search_keys = set(keys)
1515
1484
            defined order for the result iteration - it will be in the most
1516
1485
            efficient order for the index (keys iteration order in this case).
1517
1486
        """
1518
 
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
1519
 
        #       aren't using set().intersection() here
1520
 
        nodes = self._nodes
1521
 
        keys = [key for key in keys if key in nodes]
 
1487
        keys = set(keys)
1522
1488
        if self.reference_lists:
1523
 
            for key in keys:
1524
 
                node = nodes[key]
 
1489
            for key in keys.intersection(self._keys):
 
1490
                node = self._nodes[key]
1525
1491
                if not node[0]:
1526
1492
                    yield self, key, node[2], node[1]
1527
1493
        else:
1528
 
            for key in keys:
1529
 
                node = nodes[key]
 
1494
            for key in keys.intersection(self._keys):
 
1495
                node = self._nodes[key]
1530
1496
                if not node[0]:
1531
1497
                    yield self, key, node[2]
1532
1498
 
1606
1572
 
1607
1573
        For InMemoryGraphIndex the estimate is exact.
1608
1574
        """
1609
 
        return len(self._nodes) - len(self._absent_keys)
 
1575
        return len(self._keys)
1610
1576
 
1611
1577
    def validate(self):
1612
1578
        """In memory index's have no known corruption at the moment."""