← 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-12-01 09:41:08 UTC
  • mfrom: (4845.1.1 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20091201094108-g1zkahrmast6h08b
(spiv) Fix crash involving static_tuple when C extensions are not
        built

Show diffs side-by-side

added added

removed removed

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