229
225
# There may be duplicates, but I don't think it is worth worrying
231
227
self._nodes[reference] = ('a', (), '')
232
self._absent_keys.update(absent_references)
233
self._absent_keys.discard(key)
234
228
self._nodes[key] = ('', node_refs, value)
235
230
if self._nodes_by_key is not None and self._key_length > 1:
236
231
self._update_nodes_by_key(key, value, node_refs)
238
def clear_cache(self):
239
"""See GraphIndex.clear_cache()
241
This is a no-op, but we need the api to conform to a generic 'Index'
245
233
def finish(self):
246
234
lines = [_SIGNATURE]
247
235
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
248
236
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')
237
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
251
238
prefix_length = sum(len(x) for x in lines)
252
239
# references are byte offsets. To avoid having to do nasty
253
240
# polynomial work to resolve offsets (references to later in the
752
703
# the last thing looked up was a terminal element
753
704
yield (self, ) + key_dict
755
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
756
"""See BTreeIndex._find_ancestors."""
757
# The api can be implemented as a trivial overlay on top of
758
# iter_entries, it is not an efficient implementation, but it at least
762
for index, key, value, refs in self.iter_entries(keys):
763
parent_keys = refs[ref_list_num]
765
parent_map[key] = parent_keys
766
search_keys.update(parent_keys)
767
# Figure out what, if anything, was missing
768
missing_keys.update(set(keys).difference(found_keys))
769
search_keys = search_keys.difference(parent_map)
772
706
def key_count(self):
773
707
"""Return an estimate of the number of keys in this index.
1268
1186
self._indices = indices
1269
1187
self._reload_func = reload_func
1270
# Sibling indices are other CombinedGraphIndex that we should call
1271
# _move_to_front_by_name on when we auto-reorder ourself.
1272
self._sibling_indices = []
1273
# A list of names that corresponds to the instances in self._indices,
1274
# so _index_names[0] is always the name for _indices[0], etc. Sibling
1275
# indices must all use the same set of names as each other.
1276
self._index_names = [None] * len(self._indices)
1278
1189
def __repr__(self):
1279
1190
return "%s(%s)" % (
1280
1191
self.__class__.__name__,
1281
1192
', '.join(map(repr, self._indices)))
1283
def clear_cache(self):
1284
"""See GraphIndex.clear_cache()"""
1285
for index in self._indices:
1288
1194
def get_parent_map(self, keys):
1289
"""See graph.StackedParentsProvider.get_parent_map"""
1195
"""See graph._StackedParentsProvider.get_parent_map"""
1290
1196
search_keys = set(keys)
1291
1197
if NULL_REVISION in search_keys:
1292
1198
search_keys.discard(NULL_REVISION)
1392
1288
seen_keys = set()
1396
1291
for index in self._indices:
1398
1292
for node in index.iter_entries_prefix(keys):
1399
1293
if node[1] in seen_keys:
1401
1295
seen_keys.add(node[1])
1405
hit_indices.append(index)
1407
1298
except errors.NoSuchFile:
1408
1299
self._reload_or_raise()
1409
self._move_to_front(hit_indices)
1411
def _move_to_front(self, hit_indices):
1412
"""Rearrange self._indices so that hit_indices are first.
1414
Order is maintained as much as possible, e.g. the first unhit index
1415
will be the first index in _indices after the hit_indices, and the
1416
hit_indices will be present in exactly the order they are passed to
1419
_move_to_front propagates to all objects in self._sibling_indices by
1420
calling _move_to_front_by_name.
1422
if self._indices[:len(hit_indices)] == hit_indices:
1423
# The 'hit_indices' are already at the front (and in the same
1424
# order), no need to re-order
1426
hit_names = self._move_to_front_by_index(hit_indices)
1427
for sibling_idx in self._sibling_indices:
1428
sibling_idx._move_to_front_by_name(hit_names)
1430
def _move_to_front_by_index(self, hit_indices):
1431
"""Core logic for _move_to_front.
1433
Returns a list of names corresponding to the hit_indices param.
1435
indices_info = zip(self._index_names, self._indices)
1436
if 'index' in debug.debug_flags:
1437
mutter('CombinedGraphIndex reordering: currently %r, promoting %r',
1438
indices_info, hit_indices)
1441
new_hit_indices = []
1444
for offset, (name, idx) in enumerate(indices_info):
1445
if idx in hit_indices:
1446
hit_names.append(name)
1447
new_hit_indices.append(idx)
1448
if len(new_hit_indices) == len(hit_indices):
1449
# We've found all of the hit entries, everything else is
1451
unhit_names.extend(self._index_names[offset+1:])
1452
unhit_indices.extend(self._indices[offset+1:])
1455
unhit_names.append(name)
1456
unhit_indices.append(idx)
1458
self._indices = new_hit_indices + unhit_indices
1459
self._index_names = hit_names + unhit_names
1460
if 'index' in debug.debug_flags:
1461
mutter('CombinedGraphIndex reordered: %r', self._indices)
1464
def _move_to_front_by_name(self, hit_names):
1465
"""Moves indices named by 'hit_names' to front of the search order, as
1466
described in _move_to_front.
1468
# Translate names to index instances, and then call
1469
# _move_to_front_by_index.
1470
indices_info = zip(self._index_names, self._indices)
1472
for name, idx in indices_info:
1473
if name in hit_names:
1474
hit_indices.append(idx)
1475
self._move_to_front_by_index(hit_indices)
1477
def find_ancestry(self, keys, ref_list_num):
1478
"""Find the complete ancestry for the given set of keys.
1480
Note that this is a whole-ancestry request, so it should be used
1483
:param keys: An iterable of keys to look for
1484
:param ref_list_num: The reference list which references the parents
1486
:return: (parent_map, missing_keys)
1488
# XXX: make this call _move_to_front?
1489
missing_keys = set()
1491
keys_to_lookup = set(keys)
1493
while keys_to_lookup:
1494
# keys that *all* indexes claim are missing, stop searching them
1496
all_index_missing = None
1497
# print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
1498
# print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
1500
# len(missing_keys))
1501
for index_idx, index in enumerate(self._indices):
1502
# TODO: we should probably be doing something with
1503
# 'missing_keys' since we've already determined that
1504
# those revisions have not been found anywhere
1505
index_missing_keys = set()
1506
# Find all of the ancestry we can from this index
1507
# keep looking until the search_keys set is empty, which means
1508
# things we didn't find should be in index_missing_keys
1509
search_keys = keys_to_lookup
1511
# print ' \t%2d\t\t%4d\t%5d\t%5d' % (
1512
# index_idx, len(search_keys),
1513
# len(parent_map), len(index_missing_keys))
1516
# TODO: ref_list_num should really be a parameter, since
1517
# CombinedGraphIndex does not know what the ref lists
1519
search_keys = index._find_ancestors(search_keys,
1520
ref_list_num, parent_map, index_missing_keys)
1521
# print ' \t \t%2d\t%4d\t%5d\t%5d' % (
1522
# sub_generation, len(search_keys),
1523
# len(parent_map), len(index_missing_keys))
1524
# Now set whatever was missing to be searched in the next index
1525
keys_to_lookup = index_missing_keys
1526
if all_index_missing is None:
1527
all_index_missing = set(index_missing_keys)
1529
all_index_missing.intersection_update(index_missing_keys)
1530
if not keys_to_lookup:
1532
if all_index_missing is None:
1533
# There were no indexes, so all search keys are 'missing'
1534
missing_keys.update(keys_to_lookup)
1535
keys_to_lookup = None
1537
missing_keys.update(all_index_missing)
1538
keys_to_lookup.difference_update(all_index_missing)
1539
return parent_map, missing_keys
1541
1301
def key_count(self):
1542
1302
"""Return an estimate of the number of keys in this index.