702
702
# the last thing looked up was a terminal element
703
703
yield (self, ) + key_dict
705
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
706
"""See BTreeIndex._find_ancestors."""
707
# The api can be implemented as a trivial overlay on top of
708
# iter_entries, it is not an efficient implementation, but it at least
712
for index, key, value, refs in self.iter_entries(keys):
713
parent_keys = refs[ref_list_num]
715
parent_map[key] = parent_keys
716
search_keys.update(parent_keys)
717
# Figure out what, if anything, was missing
718
missing_keys.update(set(keys).difference(found_keys))
719
search_keys = search_keys.difference(parent_map)
705
722
def key_count(self):
706
723
"""Return an estimate of the number of keys in this index.
1297
1314
except errors.NoSuchFile:
1298
1315
self._reload_or_raise()
1317
def find_ancestry(self, keys, ref_list_num):
1318
"""Find the complete ancestry for the given set of keys.
1320
Note that this is a whole-ancestry request, so it should be used
1323
:param keys: An iterable of keys to look for
1324
:param ref_list_num: The reference list which references the parents
1326
:return: (parent_map, missing_keys)
1328
missing_keys = set()
1330
keys_to_lookup = set(keys)
1332
while keys_to_lookup:
1333
# keys that *all* indexes claim are missing, stop searching them
1335
all_index_missing = None
1336
# print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
1337
# print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
1339
# len(missing_keys))
1340
for index_idx, index in enumerate(self._indices):
1341
# TODO: we should probably be doing something with
1342
# 'missing_keys' since we've already determined that
1343
# those revisions have not been found anywhere
1344
index_missing_keys = set()
1345
# Find all of the ancestry we can from this index
1346
# keep looking until the search_keys set is empty, which means
1347
# things we didn't find should be in index_missing_keys
1348
search_keys = keys_to_lookup
1350
# print ' \t%2d\t\t%4d\t%5d\t%5d' % (
1351
# index_idx, len(search_keys),
1352
# len(parent_map), len(index_missing_keys))
1355
# TODO: ref_list_num should really be a parameter, since
1356
# CombinedGraphIndex does not know what the ref lists
1358
search_keys = index._find_ancestors(search_keys,
1359
ref_list_num, parent_map, index_missing_keys)
1360
# print ' \t \t%2d\t%4d\t%5d\t%5d' % (
1361
# sub_generation, len(search_keys),
1362
# len(parent_map), len(index_missing_keys))
1363
# Now set whatever was missing to be searched in the next index
1364
keys_to_lookup = index_missing_keys
1365
if all_index_missing is None:
1366
all_index_missing = set(index_missing_keys)
1368
all_index_missing.intersection_update(index_missing_keys)
1369
if not keys_to_lookup:
1371
if all_index_missing is None:
1372
# There were no indexes, so all search keys are 'missing'
1373
missing_keys.update(keys_to_lookup)
1374
keys_to_lookup = None
1376
missing_keys.update(all_index_missing)
1377
keys_to_lookup.difference_update(all_index_missing)
1378
return parent_map, missing_keys
1300
1380
def key_count(self):
1301
1381
"""Return an estimate of the number of keys in this index.
added
removed
bzrlib/index.py
