94
110
if not element or _whitespace_re.search(element) is not None:
95
111
raise errors.BadIndexKey(element)
97
def add_node(self, key, value, references=()):
98
"""Add a node to the index.
100
:param key: The key. keys are non-empty tuples containing
101
as many whitespace-free utf8 bytestrings as the key length
102
defined for this index.
103
:param references: An iterable of iterables of keys. Each is a
104
reference to another key.
105
:param value: The value to associate with the key. It may be any
106
bytes as long as it does not contain \0 or \n.
113
def _external_references(self):
114
"""Return references that are not present in this index.
118
# TODO: JAM 2008-11-21 This makes an assumption about how the reference
119
# lists are used. It is currently correct for pack-0.92 through
120
# 1.9, which use the node references (3rd column) second
121
# reference list as the compression parent. Perhaps this should
122
# be moved into something higher up the stack, since it
123
# makes assumptions about how the index is used.
124
if self.reference_lists > 1:
125
for node in self.iter_all_entries():
127
refs.update(node[3][1])
130
# If reference_lists == 0 there can be no external references, and
131
# if reference_lists == 1, then there isn't a place to store the
135
def _get_nodes_by_key(self):
136
if self._nodes_by_key is None:
138
if self.reference_lists:
139
for key, (absent, references, value) in self._nodes.iteritems():
142
key_dict = nodes_by_key
143
for subkey in key[:-1]:
144
key_dict = key_dict.setdefault(subkey, {})
145
key_dict[key[-1]] = key, value, references
147
for key, (absent, references, value) in self._nodes.iteritems():
150
key_dict = nodes_by_key
151
for subkey in key[:-1]:
152
key_dict = key_dict.setdefault(subkey, {})
153
key_dict[key[-1]] = key, value
154
self._nodes_by_key = nodes_by_key
155
return self._nodes_by_key
157
def _update_nodes_by_key(self, key, value, node_refs):
158
"""Update the _nodes_by_key dict with a new key.
160
For a key of (foo, bar, baz) create
161
_nodes_by_key[foo][bar][baz] = key_value
163
if self._nodes_by_key is None:
165
key_dict = self._nodes_by_key
166
if self.reference_lists:
167
key_value = key, value, node_refs
169
key_value = key, value
170
for subkey in key[:-1]:
171
key_dict = key_dict.setdefault(subkey, {})
172
key_dict[key[-1]] = key_value
174
def _check_key_ref_value(self, key, references, value):
175
"""Check that 'key' and 'references' are all valid.
177
:param key: A key tuple. Must conform to the key interface (be a tuple,
178
be of the right length, not have any whitespace or nulls in any key
180
:param references: An iterable of reference lists. Something like
181
[[(ref, key)], [(ref, key), (other, key)]]
182
:param value: The value associate with this key. Must not contain
183
newlines or null characters.
184
:return: (node_refs, absent_references)
185
node_refs basically a packed form of 'references' where all
187
absent_references reference keys that are not in self._nodes.
188
This may contain duplicates if the same key is
189
referenced in multiple lists.
108
191
self._check_key(key)
109
192
if _newline_null_re.search(value) is not None:
111
194
if len(references) != self.reference_lists:
112
195
raise errors.BadIndexValue(references)
197
absent_references = []
114
198
for reference_list in references:
115
199
for reference in reference_list:
116
self._check_key(reference)
200
# If reference *is* in self._nodes, then we know it has already
117
202
if reference not in self._nodes:
118
self._nodes[reference] = ('a', (), '')
203
self._check_key(reference)
204
absent_references.append(reference)
119
205
node_refs.append(tuple(reference_list))
120
if key in self._nodes and self._nodes[key][0] == '':
206
return tuple(node_refs), absent_references
208
def add_node(self, key, value, references=()):
209
"""Add a node to the index.
211
:param key: The key. keys are non-empty tuples containing
212
as many whitespace-free utf8 bytestrings as the key length
213
defined for this index.
214
:param references: An iterable of iterables of keys. Each is a
215
reference to another key.
216
:param value: The value to associate with the key. It may be any
217
bytes as long as it does not contain \0 or \n.
220
absent_references) = self._check_key_ref_value(key, references, value)
221
if key in self._nodes and self._nodes[key][0] != 'a':
121
222
raise errors.BadIndexDuplicateKey(key, self)
122
self._nodes[key] = ('', tuple(node_refs), value)
223
for reference in absent_references:
224
# There may be duplicates, but I don't think it is worth worrying
226
self._nodes[reference] = ('a', (), '')
227
self._nodes[key] = ('', node_refs, value)
123
228
self._keys.add(key)
124
if self._key_length > 1:
125
key_dict = self._nodes_by_key
126
if self.reference_lists:
127
key_value = key, value, tuple(node_refs)
129
key_value = key, value
130
# possibly should do this on-demand, but it seems likely it is
132
# For a key of (foo, bar, baz) create
133
# _nodes_by_key[foo][bar][baz] = key_value
134
for subkey in key[:-1]:
135
key_dict = key_dict.setdefault(subkey, {})
136
key_dict[key[-1]] = key_value
229
if self._nodes_by_key is not None and self._key_length > 1:
230
self._update_nodes_by_key(key, value, node_refs)
138
232
def finish(self):
139
233
lines = [_SIGNATURE]
288
395
return "%s(%r)" % (self.__class__.__name__,
289
396
self._transport.abspath(self._name))
291
def _buffer_all(self):
398
def _buffer_all(self, stream=None):
292
399
"""Buffer all the index data.
294
401
Mutates self._nodes and self.keys_by_offset.
403
if self._nodes is not None:
404
# We already did this
296
406
if 'index' in debug.debug_flags:
297
407
mutter('Reading entire index %s', self._transport.abspath(self._name))
298
stream = self._transport.get(self._name)
409
stream = self._transport.get(self._name)
299
410
self._read_prefix(stream)
300
411
self._expected_elements = 3 + self._key_length
319
430
node_value = value
320
431
self._nodes[key] = node_value
321
if self._key_length > 1:
322
subkey = list(reversed(key[:-1]))
323
key_dict = self._nodes_by_key
324
if self.node_ref_lists:
325
key_value = key, node_value[0], node_value[1]
327
key_value = key, node_value
328
# possibly should do this on-demand, but it seems likely it is
330
# For a key of (foo, bar, baz) create
331
# _nodes_by_key[foo][bar][baz] = key_value
332
for subkey in key[:-1]:
333
key_dict = key_dict.setdefault(subkey, {})
334
key_dict[key[-1]] = key_value
335
432
# cache the keys for quick set intersections
336
433
self._keys = set(self._nodes)
337
434
if trailers != 1:
338
435
# there must be one line - the empty trailer line.
339
436
raise errors.BadIndexData(self)
438
def _get_nodes_by_key(self):
439
if self._nodes_by_key is None:
441
if self.node_ref_lists:
442
for key, (value, references) in self._nodes.iteritems():
443
key_dict = nodes_by_key
444
for subkey in key[:-1]:
445
key_dict = key_dict.setdefault(subkey, {})
446
key_dict[key[-1]] = key, value, references
448
for key, value in self._nodes.iteritems():
449
key_dict = nodes_by_key
450
for subkey in key[:-1]:
451
key_dict = key_dict.setdefault(subkey, {})
452
key_dict[key[-1]] = key, value
453
self._nodes_by_key = nodes_by_key
454
return self._nodes_by_key
341
456
def iter_all_entries(self):
342
457
"""Iterate over all keys within the index.
468
583
keys supplied. No additional keys will be returned, and every
469
584
key supplied that is in the index will be returned.
471
# PERFORMANCE TODO: parse and bisect all remaining data at some
472
# threshold of total-index processing/get calling layers that expect to
473
# read the entire index to use the iter_all_entries method instead.
477
589
if self._size is None and self._nodes is None:
478
590
self._buffer_all()
592
# We fit about 20 keys per minimum-read (4K), so if we are looking for
593
# more than 1/20th of the index its likely (assuming homogenous key
594
# spread) that we'll read the entire index. If we're going to do that,
595
# buffer the whole thing. A better analysis might take key spread into
596
# account - but B+Tree indices are better anyway.
597
# We could look at all data read, and use a threshold there, which will
598
# trigger on ancestry walks, but that is not yet fully mapped out.
599
if self._nodes is None and len(keys) * 20 > self.key_count():
479
601
if self._nodes is not None:
480
602
return self._iter_entries_from_total_buffer(keys)
623
746
if self._bisect_nodes is None:
624
747
readv_ranges.append(_HEADER_READV)
625
748
self._read_and_parse(readv_ranges)
750
if self._nodes is not None:
751
# _read_and_parse triggered a _buffer_all because we requested the
753
for location, key in location_keys:
754
if key not in self._nodes: # not present
755
result.append(((location, key), False))
756
elif self.node_ref_lists:
757
value, refs = self._nodes[key]
758
result.append(((location, key),
759
(self, key, value, refs)))
761
result.append(((location, key),
762
(self, key, self._nodes[key])))
626
764
# generate results:
627
765
# - figure out <, >, missing, present
628
766
# - result present references so we can return them.
630
767
# keys that we cannot answer until we resolve references
631
768
pending_references = []
632
769
pending_locations = set()
683
820
readv_ranges.append((location, length))
684
821
self._read_and_parse(readv_ranges)
822
if self._nodes is not None:
823
# The _read_and_parse triggered a _buffer_all, grab the data and
825
for location, key in pending_references:
826
value, refs = self._nodes[key]
827
result.append(((location, key), (self, key, value, refs)))
685
829
for location, key in pending_references:
686
830
# answer key references we had to look-up-late.
687
index = self._parsed_key_index(key)
688
831
value, refs = self._bisect_nodes[key]
689
832
result.append(((location, key), (self, key,
690
833
value, self._resolve_references(refs))))
961
1104
:param readv_ranges: A prepared readv range list.
964
readv_data = self._transport.readv(self._name, readv_ranges, True,
967
for offset, data in readv_data:
968
if self._bisect_nodes is None:
969
# this must be the start
970
if not (offset == 0):
971
raise AssertionError()
972
offset, data = self._parse_header_from_bytes(data)
973
# print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
974
self._parse_region(offset, data)
1106
if not readv_ranges:
1108
if self._nodes is None and self._bytes_read * 2 >= self._size:
1109
# We've already read more than 50% of the file and we are about to
1110
# request more data, just _buffer_all() and be done
1114
readv_data = self._transport.readv(self._name, readv_ranges, True,
1117
for offset, data in readv_data:
1118
self._bytes_read += len(data)
1119
if offset == 0 and len(data) == self._size:
1120
# We read the whole range, most likely because the
1121
# Transport upcast our readv ranges into one long request
1122
# for enough total data to grab the whole index.
1123
self._buffer_all(StringIO(data))
1125
if self._bisect_nodes is None:
1126
# this must be the start
1127
if not (offset == 0):
1128
raise AssertionError()
1129
offset, data = self._parse_header_from_bytes(data)
1130
# print readv_ranges, "[%d:%d]" % (offset, offset + len(data))
1131
self._parse_region(offset, data)
976
1133
def _signature(self):
977
1134
"""The file signature for this index type."""
1111
1284
seen_keys = set()
1112
for index in self._indices:
1113
for node in index.iter_entries_prefix(keys):
1114
if node[1] in seen_keys:
1116
seen_keys.add(node[1])
1287
for index in self._indices:
1288
for node in index.iter_entries_prefix(keys):
1289
if node[1] in seen_keys:
1291
seen_keys.add(node[1])
1294
except errors.NoSuchFile:
1295
self._reload_or_raise()
1119
1297
def key_count(self):
1120
1298
"""Return an estimate of the number of keys in this index.
1122
1300
For CombinedGraphIndex this is approximated by the sum of the keys of
1123
1301
the child indices. As child indices may have duplicate keys this can
1124
1302
have a maximum error of the number of child indices * largest number of
1125
1303
keys in any index.
1127
return sum((index.key_count() for index in self._indices), 0)
1307
return sum((index.key_count() for index in self._indices), 0)
1308
except errors.NoSuchFile:
1309
self._reload_or_raise()
1311
missing_keys = _missing_keys_from_parent_map
1313
def _reload_or_raise(self):
1314
"""We just got a NoSuchFile exception.
1316
Try to reload the indices, if it fails, just raise the current
1319
if self._reload_func is None:
1321
exc_type, exc_value, exc_traceback = sys.exc_info()
1322
trace.mutter('Trying to reload after getting exception: %s',
1324
if not self._reload_func():
1325
# We tried to reload, but nothing changed, so we fail anyway
1326
trace.mutter('_reload_func indicated nothing has changed.'
1327
' Raising original exception.')
1328
raise exc_type, exc_value, exc_traceback
1129
1330
def validate(self):
1130
1331
"""Validate that everything in the index can be accessed."""
1131
for index in self._indices:
1334
for index in self._indices:
1337
except errors.NoSuchFile:
1338
self._reload_or_raise()
1135
1341
class InMemoryGraphIndex(GraphIndexBuilder):
added
removed
bzrlib/index.py
