← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

Merge bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007-2011 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
31
31
 
32
32
from bzrlib.lazy_import import lazy_import
33
33
lazy_import(globals(), """
34
 
from bzrlib import (
35
 
    bisect_multi,
36
 
    revision as _mod_revision,
37
 
    trace,
38
 
    )
 
34
from bzrlib import trace
 
35
from bzrlib.bisect_multi import bisect_multi_bytes
 
36
from bzrlib.revision import NULL_REVISION
 
37
from bzrlib.trace import mutter
39
38
""")
40
39
from bzrlib import (
41
40
    debug,
42
41
    errors,
 
42
    symbol_versioning,
43
43
    )
44
 
from bzrlib.static_tuple import StaticTuple
45
44
 
46
45
_HEADER_READV = (0, 200)
47
46
_OPTION_KEY_ELEMENTS = "key_elements="
94
93
        :param key_elements: The number of bytestrings in each key.
95
94
        """
96
95
        self.reference_lists = reference_lists
 
96
        self._keys = set()
97
97
        # A dict of {key: (absent, ref_lists, value)}
98
98
        self._nodes = {}
99
 
        # Keys that are referenced but not actually present in this index
100
 
        self._absent_keys = set()
101
99
        self._nodes_by_key = None
102
100
        self._key_length = key_elements
103
101
        self._optimize_for_size = False
105
103
 
106
104
    def _check_key(self, key):
107
105
        """Raise BadIndexKey if key is not a valid key for this index."""
108
 
        if type(key) not in (tuple, StaticTuple):
 
106
        if type(key) != tuple:
109
107
            raise errors.BadIndexKey(key)
110
108
        if self._key_length != len(key):
111
109
            raise errors.BadIndexKey(key)
167
165
            return
168
166
        key_dict = self._nodes_by_key
169
167
        if self.reference_lists:
170
 
            key_value = StaticTuple(key, value, node_refs)
 
168
            key_value = key, value, node_refs
171
169
        else:
172
 
            key_value = StaticTuple(key, value)
 
170
            key_value = key, value
173
171
        for subkey in key[:-1]:
174
172
            key_dict = key_dict.setdefault(subkey, {})
175
173
        key_dict[key[-1]] = key_value
191
189
                                This may contain duplicates if the same key is
192
190
                                referenced in multiple lists.
193
191
        """
194
 
        as_st = StaticTuple.from_sequence
195
192
        self._check_key(key)
196
193
        if _newline_null_re.search(value) is not None:
197
194
            raise errors.BadIndexValue(value)
206
203
                if reference not in self._nodes:
207
204
                    self._check_key(reference)
208
205
                    absent_references.append(reference)
209
 
            reference_list = as_st([as_st(ref).intern()
210
 
                                    for ref in reference_list])
211
 
            node_refs.append(reference_list)
212
 
        return as_st(node_refs), absent_references
 
206
            node_refs.append(tuple(reference_list))
 
207
        return tuple(node_refs), absent_references
213
208
 
214
209
    def add_node(self, key, value, references=()):
215
210
        """Add a node to the index.
230
225
            # There may be duplicates, but I don't think it is worth worrying
231
226
            # about
232
227
            self._nodes[reference] = ('a', (), '')
233
 
        self._absent_keys.update(absent_references)
234
 
        self._absent_keys.discard(key)
235
228
        self._nodes[key] = ('', node_refs, value)
 
229
        self._keys.add(key)
236
230
        if self._nodes_by_key is not None and self._key_length > 1:
237
231
            self._update_nodes_by_key(key, value, node_refs)
238
232
 
239
 
    def clear_cache(self):
240
 
        """See GraphIndex.clear_cache()
241
 
 
242
 
        This is a no-op, but we need the api to conform to a generic 'Index'
243
 
        abstraction.
244
 
        """
245
 
        
246
233
    def finish(self):
247
234
        lines = [_SIGNATURE]
248
235
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
249
236
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
250
 
        key_count = len(self._nodes) - len(self._absent_keys)
251
 
        lines.append(_OPTION_LEN + str(key_count) + '\n')
 
237
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
252
238
        prefix_length = sum(len(x) for x in lines)
253
239
        # references are byte offsets. To avoid having to do nasty
254
240
        # polynomial work to resolve offsets (references to later in the
348
334
        if combine_backing_indices is not None:
349
335
            self._combine_backing_indices = combine_backing_indices
350
336
 
351
 
    def find_ancestry(self, keys, ref_list_num):
352
 
        """See CombinedGraphIndex.find_ancestry()"""
353
 
        pending = set(keys)
354
 
        parent_map = {}
355
 
        missing_keys = set()
356
 
        while pending:
357
 
            next_pending = set()
358
 
            for _, key, value, ref_lists in self.iter_entries(pending):
359
 
                parent_keys = ref_lists[ref_list_num]
360
 
                parent_map[key] = parent_keys
361
 
                next_pending.update([p for p in parent_keys if p not in
362
 
                                     parent_map])
363
 
                missing_keys.update(pending.difference(parent_map))
364
 
            pending = next_pending
365
 
        return parent_map, missing_keys
366
 
 
367
337
 
368
338
class GraphIndex(object):
369
339
    """An index for data with embedded graphs.
383
353
    suitable for production use. :XXX
384
354
    """
385
355
 
386
 
    def __init__(self, transport, name, size, unlimited_cache=False, offset=0):
 
356
    def __init__(self, transport, name, size):
387
357
        """Open an index called name on transport.
388
358
 
389
359
        :param transport: A bzrlib.transport.Transport.
395
365
            avoided by having it supplied. If size is None, then bisection
396
366
            support will be disabled and accessing the index will just stream
397
367
            all the data.
398
 
        :param offset: Instead of starting the index data at offset 0, start it
399
 
            at an arbitrary offset.
400
368
        """
401
369
        self._transport = transport
402
370
        self._name = name
419
387
        self._size = size
420
388
        # The number of bytes we've read so far in trying to process this file
421
389
        self._bytes_read = 0
422
 
        self._base_offset = offset
423
390
 
424
391
    def __eq__(self, other):
425
392
        """Equal when self and other were created with the same parameters."""
445
412
            # We already did this
446
413
            return
447
414
        if 'index' in debug.debug_flags:
448
 
            trace.mutter('Reading entire index %s',
449
 
                          self._transport.abspath(self._name))
 
415
            mutter('Reading entire index %s', self._transport.abspath(self._name))
450
416
        if stream is None:
451
417
            stream = self._transport.get(self._name)
452
 
            if self._base_offset != 0:
453
 
                # This is wasteful, but it is better than dealing with
454
 
                # adjusting all the offsets, etc.
455
 
                stream = StringIO(stream.read()[self._base_offset:])
456
418
        self._read_prefix(stream)
457
419
        self._expected_elements = 3 + self._key_length
458
420
        line_count = 0
464
426
        trailers = 0
465
427
        pos = stream.tell()
466
428
        lines = stream.read().split('\n')
467
 
        # GZ 2009-09-20: Should really use a try/finally block to ensure close
468
 
        stream.close()
469
429
        del lines[-1]
470
430
        _, _, _, trailers = self._parse_lines(lines, pos)
471
431
        for key, absent, references, value in self._keys_by_offset.itervalues():
478
438
                node_value = value
479
439
            self._nodes[key] = node_value
480
440
        # cache the keys for quick set intersections
 
441
        self._keys = set(self._nodes)
481
442
        if trailers != 1:
482
443
            # there must be one line - the empty trailer line.
483
444
            raise errors.BadIndexData(self)
484
445
 
485
 
    def clear_cache(self):
486
 
        """Clear out any cached/memoized values.
487
 
 
488
 
        This can be called at any time, but generally it is used when we have
489
 
        extracted some information, but don't expect to be requesting any more
490
 
        from this index.
491
 
        """
492
 
 
493
446
    def external_references(self, ref_list_num):
494
447
        """Return references that are not present in this index.
495
448
        """
498
451
            raise ValueError('No ref list %d, index has %d ref lists'
499
452
                % (ref_list_num, self.node_ref_lists))
500
453
        refs = set()
501
 
        nodes = self._nodes
502
 
        for key, (value, ref_lists) in nodes.iteritems():
 
454
        for key, (value, ref_lists) in self._nodes.iteritems():
503
455
            ref_list = ref_lists[ref_list_num]
504
 
            refs.update([ref for ref in ref_list if ref not in nodes])
505
 
        return refs
 
456
            refs.update(ref_list)
 
457
        return refs - self._keys
506
458
 
507
459
    def _get_nodes_by_key(self):
508
460
        if self._nodes_by_key is None:
635
587
 
636
588
    def _iter_entries_from_total_buffer(self, keys):
637
589
        """Iterate over keys when the entire index is parsed."""
638
 
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
639
 
        #       .intersection() here
640
 
        nodes = self._nodes
641
 
        keys = [key for key in keys if key in nodes]
 
590
        keys = keys.intersection(self._keys)
642
591
        if self.node_ref_lists:
643
592
            for key in keys:
644
 
                value, node_refs = nodes[key]
 
593
                value, node_refs = self._nodes[key]
645
594
                yield self, key, value, node_refs
646
595
        else:
647
596
            for key in keys:
648
 
                yield self, key, nodes[key]
 
597
                yield self, key, self._nodes[key]
649
598
 
650
599
    def iter_entries(self, keys):
651
600
        """Iterate over keys within the index.
673
622
        if self._nodes is not None:
674
623
            return self._iter_entries_from_total_buffer(keys)
675
624
        else:
676
 
            return (result[1] for result in bisect_multi.bisect_multi_bytes(
 
625
            return (result[1] for result in bisect_multi_bytes(
677
626
                self._lookup_keys_via_location, self._size, keys))
678
627
 
679
628
    def iter_entries_prefix(self, keys):
754
703
                # the last thing looked up was a terminal element
755
704
                yield (self, ) + key_dict
756
705
 
757
 
    def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
758
 
        """See BTreeIndex._find_ancestors."""
759
 
        # The api can be implemented as a trivial overlay on top of
760
 
        # iter_entries, it is not an efficient implementation, but it at least
761
 
        # gets the job done.
762
 
        found_keys = set()
763
 
        search_keys = set()
764
 
        for index, key, value, refs in self.iter_entries(keys):
765
 
            parent_keys = refs[ref_list_num]
766
 
            found_keys.add(key)
767
 
            parent_map[key] = parent_keys
768
 
            search_keys.update(parent_keys)
769
 
        # Figure out what, if anything, was missing
770
 
        missing_keys.update(set(keys).difference(found_keys))
771
 
        search_keys = search_keys.difference(parent_map)
772
 
        return search_keys
773
 
 
774
706
    def key_count(self):
775
707
        """Return an estimate of the number of keys in this index.
776
708
 
1188
1120
            self._parsed_key_map.insert(index + 1, new_key)
1189
1121
 
1190
1122
    def _read_and_parse(self, readv_ranges):
1191
 
        """Read the ranges and parse the resulting data.
 
1123
        """Read the the ranges and parse the resulting data.
1192
1124
 
1193
1125
        :param readv_ranges: A prepared readv range list.
1194
1126
        """
1200
1132
            self._buffer_all()
1201
1133
            return
1202
1134
 
1203
 
        base_offset = self._base_offset
1204
 
        if base_offset != 0:
1205
 
            # Rewrite the ranges for the offset
1206
 
            readv_ranges = [(start+base_offset, size)
1207
 
                            for start, size in readv_ranges]
1208
1135
        readv_data = self._transport.readv(self._name, readv_ranges, True,
1209
 
            self._size + self._base_offset)
 
1136
            self._size)
1210
1137
        # parse
1211
1138
        for offset, data in readv_data:
1212
 
            offset -= base_offset
1213
1139
            self._bytes_read += len(data)
1214
 
            if offset < 0:
1215
 
                # transport.readv() expanded to extra data which isn't part of
1216
 
                # this index
1217
 
                data = data[-offset:]
1218
 
                offset = 0
1219
1140
            if offset == 0 and len(data) == self._size:
1220
1141
                # We read the whole range, most likely because the
1221
1142
                # Transport upcast our readv ranges into one long request
1248
1169
    static data.
1249
1170
 
1250
1171
    Queries against the combined index will be made against the first index,
1251
 
    and then the second and so on. The order of indices can thus influence
 
1172
    and then the second and so on. The order of index's can thus influence
1252
1173
    performance significantly. For example, if one index is on local disk and a
1253
1174
    second on a remote server, the local disk index should be before the other
1254
1175
    in the index list.
1255
 
    
1256
 
    Also, queries tend to need results from the same indices as previous
1257
 
    queries.  So the indices will be reordered after every query to put the
1258
 
    indices that had the result(s) of that query first (while otherwise
1259
 
    preserving the relative ordering).
1260
1176
    """
1261
1177
 
1262
1178
    def __init__(self, indices, reload_func=None):
1269
1185
        """
1270
1186
        self._indices = indices
1271
1187
        self._reload_func = reload_func
1272
 
        # Sibling indices are other CombinedGraphIndex that we should call
1273
 
        # _move_to_front_by_name on when we auto-reorder ourself.
1274
 
        self._sibling_indices = []
1275
 
        # A list of names that corresponds to the instances in self._indices,
1276
 
        # so _index_names[0] is always the name for _indices[0], etc.  Sibling
1277
 
        # indices must all use the same set of names as each other.
1278
 
        self._index_names = [None] * len(self._indices)
1279
1188
 
1280
1189
    def __repr__(self):
1281
1190
        return "%s(%s)" % (
1282
1191
                self.__class__.__name__,
1283
1192
                ', '.join(map(repr, self._indices)))
1284
1193
 
1285
 
    def clear_cache(self):
1286
 
        """See GraphIndex.clear_cache()"""
1287
 
        for index in self._indices:
1288
 
            index.clear_cache()
1289
 
 
1290
1194
    def get_parent_map(self, keys):
1291
 
        """See graph.StackedParentsProvider.get_parent_map"""
 
1195
        """See graph._StackedParentsProvider.get_parent_map"""
1292
1196
        search_keys = set(keys)
1293
 
        if _mod_revision.NULL_REVISION in search_keys:
1294
 
            search_keys.discard(_mod_revision.NULL_REVISION)
1295
 
            found_parents = {_mod_revision.NULL_REVISION:[]}
 
1197
        if NULL_REVISION in search_keys:
 
1198
            search_keys.discard(NULL_REVISION)
 
1199
            found_parents = {NULL_REVISION:[]}
1296
1200
        else:
1297
1201
            found_parents = {}
1298
1202
        for index, key, value, refs in self.iter_entries(search_keys):
1299
1203
            parents = refs[0]
1300
1204
            if not parents:
1301
 
                parents = (_mod_revision.NULL_REVISION,)
 
1205
                parents = (NULL_REVISION,)
1302
1206
            found_parents[key] = parents
1303
1207
        return found_parents
1304
1208
 
1305
1209
    has_key = _has_key_from_parent_map
1306
1210
 
1307
 
    def insert_index(self, pos, index, name=None):
 
1211
    def insert_index(self, pos, index):
1308
1212
        """Insert a new index in the list of indices to query.
1309
1213
 
1310
1214
        :param pos: The position to insert the index.
1311
1215
        :param index: The index to insert.
1312
 
        :param name: a name for this index, e.g. a pack name.  These names can
1313
 
            be used to reflect index reorderings to related CombinedGraphIndex
1314
 
            instances that use the same names.  (see set_sibling_indices)
1315
1216
        """
1316
1217
        self._indices.insert(pos, index)
1317
 
        self._index_names.insert(pos, name)
1318
1218
 
1319
1219
    def iter_all_entries(self):
1320
1220
        """Iterate over all keys within the index
1345
1245
        value and are only reported once.
1346
1246
 
1347
1247
        :param keys: An iterable providing the keys to be retrieved.
1348
 
        :return: An iterable of (index, key, reference_lists, value). There is
1349
 
            no defined order for the result iteration - it will be in the most
 
1248
        :return: An iterable of (index, key, reference_lists, value). There is no
 
1249
            defined order for the result iteration - it will be in the most
1350
1250
            efficient order for the index.
1351
1251
        """
1352
1252
        keys = set(keys)
1353
 
        hit_indices = []
1354
1253
        while True:
1355
1254
            try:
1356
1255
                for index in self._indices:
1357
1256
                    if not keys:
1358
 
                        break
1359
 
                    index_hit = False
 
1257
                        return
1360
1258
                    for node in index.iter_entries(keys):
1361
1259
                        keys.remove(node[1])
1362
1260
                        yield node
1363
 
                        index_hit = True
1364
 
                    if index_hit:
1365
 
                        hit_indices.append(index)
1366
 
                break
 
1261
                return
1367
1262
            except errors.NoSuchFile:
1368
1263
                self._reload_or_raise()
1369
 
        self._move_to_front(hit_indices)
1370
1264
 
1371
1265
    def iter_entries_prefix(self, keys):
1372
1266
        """Iterate over keys within the index using prefix matching.
1392
1286
        if not keys:
1393
1287
            return
1394
1288
        seen_keys = set()
1395
 
        hit_indices = []
1396
1289
        while True:
1397
1290
            try:
1398
1291
                for index in self._indices:
1399
 
                    index_hit = False
1400
1292
                    for node in index.iter_entries_prefix(keys):
1401
1293
                        if node[1] in seen_keys:
1402
1294
                            continue
1403
1295
                        seen_keys.add(node[1])
1404
1296
                        yield node
1405
 
                        index_hit = True
1406
 
                    if index_hit:
1407
 
                        hit_indices.append(index)
1408
 
                break
 
1297
                return
1409
1298
            except errors.NoSuchFile:
1410
1299
                self._reload_or_raise()
1411
 
        self._move_to_front(hit_indices)
1412
 
 
1413
 
    def _move_to_front(self, hit_indices):
1414
 
        """Rearrange self._indices so that hit_indices are first.
1415
 
 
1416
 
        Order is maintained as much as possible, e.g. the first unhit index
1417
 
        will be the first index in _indices after the hit_indices, and the
1418
 
        hit_indices will be present in exactly the order they are passed to
1419
 
        _move_to_front.
1420
 
 
1421
 
        _move_to_front propagates to all objects in self._sibling_indices by
1422
 
        calling _move_to_front_by_name.
1423
 
        """
1424
 
        if self._indices[:len(hit_indices)] == hit_indices:
1425
 
            # The 'hit_indices' are already at the front (and in the same
1426
 
            # order), no need to re-order
1427
 
            return
1428
 
        hit_names = self._move_to_front_by_index(hit_indices)
1429
 
        for sibling_idx in self._sibling_indices:
1430
 
            sibling_idx._move_to_front_by_name(hit_names)
1431
 
 
1432
 
    def _move_to_front_by_index(self, hit_indices):
1433
 
        """Core logic for _move_to_front.
1434
 
        
1435
 
        Returns a list of names corresponding to the hit_indices param.
1436
 
        """
1437
 
        indices_info = zip(self._index_names, self._indices)
1438
 
        if 'index' in debug.debug_flags:
1439
 
            trace.mutter('CombinedGraphIndex reordering: currently %r, '
1440
 
                         'promoting %r', indices_info, hit_indices)
1441
 
        hit_names = []
1442
 
        unhit_names = []
1443
 
        new_hit_indices = []
1444
 
        unhit_indices = []
1445
 
 
1446
 
        for offset, (name, idx) in enumerate(indices_info):
1447
 
            if idx in hit_indices:
1448
 
                hit_names.append(name)
1449
 
                new_hit_indices.append(idx)
1450
 
                if len(new_hit_indices) == len(hit_indices):
1451
 
                    # We've found all of the hit entries, everything else is
1452
 
                    # unhit
1453
 
                    unhit_names.extend(self._index_names[offset+1:])
1454
 
                    unhit_indices.extend(self._indices[offset+1:])
1455
 
                    break
1456
 
            else:
1457
 
                unhit_names.append(name)
1458
 
                unhit_indices.append(idx)
1459
 
 
1460
 
        self._indices = new_hit_indices + unhit_indices
1461
 
        self._index_names = hit_names + unhit_names
1462
 
        if 'index' in debug.debug_flags:
1463
 
            trace.mutter('CombinedGraphIndex reordered: %r', self._indices)
1464
 
        return hit_names
1465
 
 
1466
 
    def _move_to_front_by_name(self, hit_names):
1467
 
        """Moves indices named by 'hit_names' to front of the search order, as
1468
 
        described in _move_to_front.
1469
 
        """
1470
 
        # Translate names to index instances, and then call
1471
 
        # _move_to_front_by_index.
1472
 
        indices_info = zip(self._index_names, self._indices)
1473
 
        hit_indices = []
1474
 
        for name, idx in indices_info:
1475
 
            if name in hit_names:
1476
 
                hit_indices.append(idx)
1477
 
        self._move_to_front_by_index(hit_indices)
1478
 
 
1479
 
    def find_ancestry(self, keys, ref_list_num):
1480
 
        """Find the complete ancestry for the given set of keys.
1481
 
 
1482
 
        Note that this is a whole-ancestry request, so it should be used
1483
 
        sparingly.
1484
 
 
1485
 
        :param keys: An iterable of keys to look for
1486
 
        :param ref_list_num: The reference list which references the parents
1487
 
            we care about.
1488
 
        :return: (parent_map, missing_keys)
1489
 
        """
1490
 
        # XXX: make this call _move_to_front?
1491
 
        missing_keys = set()
1492
 
        parent_map = {}
1493
 
        keys_to_lookup = set(keys)
1494
 
        generation = 0
1495
 
        while keys_to_lookup:
1496
 
            # keys that *all* indexes claim are missing, stop searching them
1497
 
            generation += 1
1498
 
            all_index_missing = None
1499
 
            # print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
1500
 
            # print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
1501
 
            #                                   len(parent_map),
1502
 
            #                                   len(missing_keys))
1503
 
            for index_idx, index in enumerate(self._indices):
1504
 
                # TODO: we should probably be doing something with
1505
 
                #       'missing_keys' since we've already determined that
1506
 
                #       those revisions have not been found anywhere
1507
 
                index_missing_keys = set()
1508
 
                # Find all of the ancestry we can from this index
1509
 
                # keep looking until the search_keys set is empty, which means
1510
 
                # things we didn't find should be in index_missing_keys
1511
 
                search_keys = keys_to_lookup
1512
 
                sub_generation = 0
1513
 
                # print '    \t%2d\t\t%4d\t%5d\t%5d' % (
1514
 
                #     index_idx, len(search_keys),
1515
 
                #     len(parent_map), len(index_missing_keys))
1516
 
                while search_keys:
1517
 
                    sub_generation += 1
1518
 
                    # TODO: ref_list_num should really be a parameter, since
1519
 
                    #       CombinedGraphIndex does not know what the ref lists
1520
 
                    #       mean.
1521
 
                    search_keys = index._find_ancestors(search_keys,
1522
 
                        ref_list_num, parent_map, index_missing_keys)
1523
 
                    # print '    \t  \t%2d\t%4d\t%5d\t%5d' % (
1524
 
                    #     sub_generation, len(search_keys),
1525
 
                    #     len(parent_map), len(index_missing_keys))
1526
 
                # Now set whatever was missing to be searched in the next index
1527
 
                keys_to_lookup = index_missing_keys
1528
 
                if all_index_missing is None:
1529
 
                    all_index_missing = set(index_missing_keys)
1530
 
                else:
1531
 
                    all_index_missing.intersection_update(index_missing_keys)
1532
 
                if not keys_to_lookup:
1533
 
                    break
1534
 
            if all_index_missing is None:
1535
 
                # There were no indexes, so all search keys are 'missing'
1536
 
                missing_keys.update(keys_to_lookup)
1537
 
                keys_to_lookup = None
1538
 
            else:
1539
 
                missing_keys.update(all_index_missing)
1540
 
                keys_to_lookup.difference_update(all_index_missing)
1541
 
        return parent_map, missing_keys
1542
1300
 
1543
1301
    def key_count(self):
1544
1302
        """Return an estimate of the number of keys in this index.
1573
1331
                         ' Raising original exception.')
1574
1332
            raise exc_type, exc_value, exc_traceback
1575
1333
 
1576
 
    def set_sibling_indices(self, sibling_combined_graph_indices):
1577
 
        """Set the CombinedGraphIndex objects to reorder after reordering self.
1578
 
        """
1579
 
        self._sibling_indices = sibling_combined_graph_indices
1580
 
 
1581
1334
    def validate(self):
1582
1335
        """Validate that everything in the index can be accessed."""
1583
1336
        while True:
1636
1389
            defined order for the result iteration - it will be in the most
1637
1390
            efficient order for the index (keys iteration order in this case).
1638
1391
        """
1639
 
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
1640
 
        #       aren't using set().intersection() here
1641
 
        nodes = self._nodes
1642
 
        keys = [key for key in keys if key in nodes]
 
1392
        keys = set(keys)
1643
1393
        if self.reference_lists:
1644
 
            for key in keys:
1645
 
                node = nodes[key]
 
1394
            for key in keys.intersection(self._keys):
 
1395
                node = self._nodes[key]
1646
1396
                if not node[0]:
1647
1397
                    yield self, key, node[2], node[1]
1648
1398
        else:
1649
 
            for key in keys:
1650
 
                node = nodes[key]
 
1399
            for key in keys.intersection(self._keys):
 
1400
                node = self._nodes[key]
1651
1401
                if not node[0]:
1652
1402
                    yield self, key, node[2]
1653
1403
 
1727
1477
 
1728
1478
        For InMemoryGraphIndex the estimate is exact.
1729
1479
        """
1730
 
        return len(self._nodes) - len(self._absent_keys)
 
1480
        return len(self._keys)
1731
1481
 
1732
1482
    def validate(self):
1733
1483
        """In memory index's have no known corruption at the moment."""