93
93
:param key_elements: The number of bytestrings in each key.
95
95
self.reference_lists = reference_lists
97
96
# A dict of {key: (absent, ref_lists, value)}
98
# Keys that are referenced but not actually present in this index
99
self._absent_keys = set()
99
100
self._nodes_by_key = None
100
101
self._key_length = key_elements
101
102
self._optimize_for_size = False
166
167
key_dict = self._nodes_by_key
167
168
if self.reference_lists:
168
key_value = key, value, node_refs
169
key_value = StaticTuple(key, value, node_refs)
170
key_value = key, value
171
key_value = StaticTuple(key, value)
171
172
for subkey in key[:-1]:
172
173
key_dict = key_dict.setdefault(subkey, {})
173
174
key_dict[key[-1]] = key_value
203
205
if reference not in self._nodes:
204
206
self._check_key(reference)
205
207
absent_references.append(reference)
206
node_refs.append(tuple(reference_list))
207
return tuple(node_refs), absent_references
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
209
213
def add_node(self, key, value, references=()):
210
214
"""Add a node to the index.
225
229
# There may be duplicates, but I don't think it is worth worrying
227
231
self._nodes[reference] = ('a', (), '')
232
self._absent_keys.update(absent_references)
233
self._absent_keys.discard(key)
228
234
self._nodes[key] = ('', node_refs, value)
230
235
if self._nodes_by_key is not None and self._key_length > 1:
231
236
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'
233
245
def finish(self):
234
246
lines = [_SIGNATURE]
235
247
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
236
248
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
237
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
249
key_count = len(self._nodes) - len(self._absent_keys)
250
lines.append(_OPTION_LEN + str(key_count) + '\n')
238
251
prefix_length = sum(len(x) for x in lines)
239
252
# references are byte offsets. To avoid having to do nasty
240
253
# polynomial work to resolve offsets (references to later in the
334
347
if combine_backing_indices is not None:
335
348
self._combine_backing_indices = combine_backing_indices
350
def find_ancestry(self, keys, ref_list_num):
351
"""See CombinedGraphIndex.find_ancestry()"""
357
for _, key, value, ref_lists in self.iter_entries(pending):
358
parent_keys = ref_lists[ref_list_num]
359
parent_map[key] = parent_keys
360
next_pending.update([p for p in parent_keys if p not in
362
missing_keys.update(pending.difference(parent_map))
363
pending = next_pending
364
return parent_map, missing_keys
338
367
class GraphIndex(object):
339
368
"""An index for data with embedded graphs.
353
382
suitable for production use. :XXX
356
def __init__(self, transport, name, size):
385
def __init__(self, transport, name, size, unlimited_cache=False):
357
386
"""Open an index called name on transport.
359
388
:param transport: A bzrlib.transport.Transport.
438
468
node_value = value
439
469
self._nodes[key] = node_value
440
470
# cache the keys for quick set intersections
441
self._keys = set(self._nodes)
442
471
if trailers != 1:
443
472
# there must be one line - the empty trailer line.
444
473
raise errors.BadIndexData(self)
475
def clear_cache(self):
476
"""Clear out any cached/memoized values.
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
446
483
def external_references(self, ref_list_num):
447
484
"""Return references that are not present in this index.
451
488
raise ValueError('No ref list %d, index has %d ref lists'
452
489
% (ref_list_num, self.node_ref_lists))
454
for key, (value, ref_lists) in self._nodes.iteritems():
492
for key, (value, ref_lists) in nodes.iteritems():
455
493
ref_list = ref_lists[ref_list_num]
456
refs.update(ref_list)
457
return refs - self._keys
494
refs.update([ref for ref in ref_list if ref not in nodes])
459
497
def _get_nodes_by_key(self):
460
498
if self._nodes_by_key is None:
588
626
def _iter_entries_from_total_buffer(self, keys):
589
627
"""Iterate over keys when the entire index is parsed."""
590
keys = keys.intersection(self._keys)
628
# Note: See the note in BTreeBuilder.iter_entries for why we don't use
629
# .intersection() here
631
keys = [key for key in keys if key in nodes]
591
632
if self.node_ref_lists:
593
value, node_refs = self._nodes[key]
634
value, node_refs = nodes[key]
594
635
yield self, key, value, node_refs
597
yield self, key, self._nodes[key]
638
yield self, key, nodes[key]
599
640
def iter_entries(self, keys):
600
641
"""Iterate over keys within the index.
703
744
# the last thing looked up was a terminal element
704
745
yield (self, ) + key_dict
747
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
748
"""See BTreeIndex._find_ancestors."""
749
# The api can be implemented as a trivial overlay on top of
750
# iter_entries, it is not an efficient implementation, but it at least
754
for index, key, value, refs in self.iter_entries(keys):
755
parent_keys = refs[ref_list_num]
757
parent_map[key] = parent_keys
758
search_keys.update(parent_keys)
759
# Figure out what, if anything, was missing
760
missing_keys.update(set(keys).difference(found_keys))
761
search_keys = search_keys.difference(parent_map)
706
764
def key_count(self):
707
765
"""Return an estimate of the number of keys in this index.
1191
1249
self.__class__.__name__,
1192
1250
', '.join(map(repr, self._indices)))
1252
def clear_cache(self):
1253
"""See GraphIndex.clear_cache()"""
1254
for index in self._indices:
1194
1257
def get_parent_map(self, keys):
1195
"""See graph._StackedParentsProvider.get_parent_map"""
1258
"""See graph.StackedParentsProvider.get_parent_map"""
1196
1259
search_keys = set(keys)
1197
1260
if NULL_REVISION in search_keys:
1198
1261
search_keys.discard(NULL_REVISION)
1298
1361
except errors.NoSuchFile:
1299
1362
self._reload_or_raise()
1364
def find_ancestry(self, keys, ref_list_num):
1365
"""Find the complete ancestry for the given set of keys.
1367
Note that this is a whole-ancestry request, so it should be used
1370
:param keys: An iterable of keys to look for
1371
:param ref_list_num: The reference list which references the parents
1373
:return: (parent_map, missing_keys)
1375
missing_keys = set()
1377
keys_to_lookup = set(keys)
1379
while keys_to_lookup:
1380
# keys that *all* indexes claim are missing, stop searching them
1382
all_index_missing = None
1383
# print 'gen\tidx\tsub\tn_keys\tn_pmap\tn_miss'
1384
# print '%4d\t\t\t%4d\t%5d\t%5d' % (generation, len(keys_to_lookup),
1386
# len(missing_keys))
1387
for index_idx, index in enumerate(self._indices):
1388
# TODO: we should probably be doing something with
1389
# 'missing_keys' since we've already determined that
1390
# those revisions have not been found anywhere
1391
index_missing_keys = set()
1392
# Find all of the ancestry we can from this index
1393
# keep looking until the search_keys set is empty, which means
1394
# things we didn't find should be in index_missing_keys
1395
search_keys = keys_to_lookup
1397
# print ' \t%2d\t\t%4d\t%5d\t%5d' % (
1398
# index_idx, len(search_keys),
1399
# len(parent_map), len(index_missing_keys))
1402
# TODO: ref_list_num should really be a parameter, since
1403
# CombinedGraphIndex does not know what the ref lists
1405
search_keys = index._find_ancestors(search_keys,
1406
ref_list_num, parent_map, index_missing_keys)
1407
# print ' \t \t%2d\t%4d\t%5d\t%5d' % (
1408
# sub_generation, len(search_keys),
1409
# len(parent_map), len(index_missing_keys))
1410
# Now set whatever was missing to be searched in the next index
1411
keys_to_lookup = index_missing_keys
1412
if all_index_missing is None:
1413
all_index_missing = set(index_missing_keys)
1415
all_index_missing.intersection_update(index_missing_keys)
1416
if not keys_to_lookup:
1418
if all_index_missing is None:
1419
# There were no indexes, so all search keys are 'missing'
1420
missing_keys.update(keys_to_lookup)
1421
keys_to_lookup = None
1423
missing_keys.update(all_index_missing)
1424
keys_to_lookup.difference_update(all_index_missing)
1425
return parent_map, missing_keys
1301
1427
def key_count(self):
1302
1428
"""Return an estimate of the number of keys in this index.
1389
1515
defined order for the result iteration - it will be in the most
1390
1516
efficient order for the index (keys iteration order in this case).
1518
# Note: See BTreeBuilder.iter_entries for an explanation of why we
1519
# aren't using set().intersection() here
1521
keys = [key for key in keys if key in nodes]
1393
1522
if self.reference_lists:
1394
for key in keys.intersection(self._keys):
1395
node = self._nodes[key]
1396
1525
if not node[0]:
1397
1526
yield self, key, node[2], node[1]
1399
for key in keys.intersection(self._keys):
1400
node = self._nodes[key]
1401
1530
if not node[0]:
1402
1531
yield self, key, node[2]
added
removed
bzrlib/index.py
