93
93
:param key_elements: The number of bytestrings in each key.
95
95
self.reference_lists = reference_lists
96
97
# 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()
100
99
self._nodes_by_key = None
101
100
self._key_length = key_elements
102
101
self._optimize_for_size = False
167
166
key_dict = self._nodes_by_key
168
167
if self.reference_lists:
169
key_value = StaticTuple(key, value, node_refs)
168
key_value = key, value, node_refs
171
key_value = StaticTuple(key, value)
170
key_value = key, value
172
171
for subkey in key[:-1]:
173
172
key_dict = key_dict.setdefault(subkey, {})
174
173
key_dict[key[-1]] = key_value
205
203
if reference not in self._nodes:
206
204
self._check_key(reference)
207
205
absent_references.append(reference)
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
206
node_refs.append(tuple(reference_list))
207
return tuple(node_refs), absent_references
213
209
def add_node(self, key, value, references=()):
214
210
"""Add a node to the index.
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
347
334
if combine_backing_indices is not None:
348
335
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
367
338
class GraphIndex(object):
368
339
"""An index for data with embedded graphs.
382
353
suitable for production use. :XXX
385
def __init__(self, transport, name, size, unlimited_cache=False):
356
def __init__(self, transport, name, size):
386
357
"""Open an index called name on transport.
388
359
:param transport: A bzrlib.transport.Transport.
468
438
node_value = value
469
439
self._nodes[key] = node_value
470
440
# cache the keys for quick set intersections
441
self._keys = set(self._nodes)
471
442
if trailers != 1:
472
443
# there must be one line - the empty trailer line.
473
444
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
483
446
def external_references(self, ref_list_num):
484
447
"""Return references that are not present in this index.
488
451
raise ValueError('No ref list %d, index has %d ref lists'
489
452
% (ref_list_num, self.node_ref_lists))
492
for key, (value, ref_lists) in nodes.iteritems():
454
for key, (value, ref_lists) in self._nodes.iteritems():
493
455
ref_list = ref_lists[ref_list_num]
494
refs.update([ref for ref in ref_list if ref not in nodes])
456
refs.update(ref_list)
457
return refs - self._keys
497
459
def _get_nodes_by_key(self):
498
460
if self._nodes_by_key is None:
626
588
def _iter_entries_from_total_buffer(self, keys):
627
589
"""Iterate over keys when the entire index is parsed."""
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]
590
keys = keys.intersection(self._keys)
632
591
if self.node_ref_lists:
634
value, node_refs = nodes[key]
593
value, node_refs = self._nodes[key]
635
594
yield self, key, value, node_refs
638
yield self, key, nodes[key]
597
yield self, key, self._nodes[key]
640
599
def iter_entries(self, keys):
641
600
"""Iterate over keys within the index.
744
703
# the last thing looked up was a terminal element
745
704
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)
764
706
def key_count(self):
765
707
"""Return an estimate of the number of keys in this index.
1249
1191
self.__class__.__name__,
1250
1192
', '.join(map(repr, self._indices)))
1252
def clear_cache(self):
1253
"""See GraphIndex.clear_cache()"""
1254
for index in self._indices:
1257
1194
def get_parent_map(self, keys):
1258
"""See graph.StackedParentsProvider.get_parent_map"""
1195
"""See graph._StackedParentsProvider.get_parent_map"""
1259
1196
search_keys = set(keys)
1260
1197
if NULL_REVISION in search_keys:
1261
1198
search_keys.discard(NULL_REVISION)
1361
1298
except errors.NoSuchFile:
1362
1299
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
1427
1301
def key_count(self):
1428
1302
"""Return an estimate of the number of keys in this index.
1515
1389
defined order for the result iteration - it will be in the most
1516
1390
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]
1522
1393
if self.reference_lists:
1394
for key in keys.intersection(self._keys):
1395
node = self._nodes[key]
1525
1396
if not node[0]:
1526
1397
yield self, key, node[2], node[1]
1399
for key in keys.intersection(self._keys):
1400
node = self._nodes[key]
1530
1401
if not node[0]:
1531
1402
yield self, key, node[2]
added
removed
bzrlib/index.py
