13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
17
"""Indexing facilities."""
56
56
def _has_key_from_parent_map(self, key):
57
57
"""Check if this index has one key.
59
If it's possible to check for multiple keys at once through
59
If it's possible to check for multiple keys at once through
60
60
calling get_parent_map that should be faster.
62
62
return (key in self.get_parent_map([key]))
69
69
class GraphIndexBuilder(object):
70
70
"""A builder that can build a GraphIndex.
72
72
The resulting graph has the structure:
74
74
_SIGNATURE OPTIONS NODES NEWLINE
75
75
_SIGNATURE := 'Bazaar Graph Index 1' NEWLINE
76
76
OPTIONS := 'node_ref_lists=' DIGITS NEWLINE
99
99
self._nodes_by_key = None
100
100
self._key_length = key_elements
101
101
self._optimize_for_size = False
102
self._combine_backing_indices = True
103
104
def _check_key(self, key):
104
105
"""Raise BadIndexKey if key is not a valid key for this index."""
246
247
# one to pad all the data with reference-length and determine entry
248
249
# One to serialise.
250
251
# forward sorted by key. In future we may consider topological sorting,
251
252
# at the cost of table scans for direct lookup, or a second index for
315
316
(len(result.getvalue()), expected_bytes))
318
def set_optimize(self, for_size=True):
319
def set_optimize(self, for_size=None, combine_backing_indices=None):
319
320
"""Change how the builder tries to optimize the result.
321
322
:param for_size: Tell the builder to try and make the index as small as
324
:param combine_backing_indices: If the builder spills to disk to save
325
memory, should the on-disk indices be combined. Set to True if you
326
are going to be probing the index, but to False if you are not. (If
327
you are not querying, then the time spent combining is wasted.)
325
330
# GraphIndexBuilder itself doesn't pay attention to the flag yet, but
326
331
# other builders do.
327
self._optimize_for_size = for_size
332
if for_size is not None:
333
self._optimize_for_size = for_size
334
if combine_backing_indices is not None:
335
self._combine_backing_indices = combine_backing_indices
330
338
class GraphIndex(object):
331
339
"""An index for data with embedded graphs.
333
341
The index maps keys to a list of key reference lists, and a value.
334
342
Each node has the same number of key reference lists. Each key reference
335
343
list can be empty or an arbitrary length. The value is an opaque NULL
336
terminated string without any newlines. The storage of the index is
344
terminated string without any newlines. The storage of the index is
337
345
hidden in the interface: keys and key references are always tuples of
338
346
bytestrings, never the internal representation (e.g. dictionary offsets).
516
524
def _resolve_references(self, references):
517
525
"""Return the resolved key references for references.
519
527
References are resolved by looking up the location of the key in the
520
528
_keys_by_offset map and substituting the key name, preserving ordering.
522
:param references: An iterable of iterables of key locations. e.g.
530
:param references: An iterable of iterables of key locations. e.g.
523
531
[[123, 456], [123]]
524
532
:return: A tuple of tuples of keys.
734
742
# We have the key parsed.
736
744
index = self._parsed_key_index(key)
737
if (len(self._parsed_key_map) and
745
if (len(self._parsed_key_map) and
738
746
self._parsed_key_map[index][0] <= key and
739
747
(self._parsed_key_map[index][1] >= key or
740
748
# end of the file has been parsed
745
753
# - if we have examined this part of the file already - yes
746
754
index = self._parsed_byte_index(location)
747
if (len(self._parsed_byte_map) and
755
if (len(self._parsed_byte_map) and
748
756
self._parsed_byte_map[index][0] <= location and
749
757
self._parsed_byte_map[index][1] > location):
750
758
# the byte region has been parsed, so no read is needed.
1005
1013
# adjust offset and data to the parseable data.
1006
1014
trimmed_data = data[trim_start:trim_end]
1007
1015
if not (trimmed_data):
1008
raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
1016
raise AssertionError('read unneeded data [%d:%d] from [%d:%d]'
1009
1017
% (trim_start, trim_end, offset, offset + len(data)))
1011
1019
offset += trim_start
1183
1191
self.__class__.__name__,
1184
1192
', '.join(map(repr, self._indices)))
1186
@symbol_versioning.deprecated_method(symbol_versioning.one_one)
1187
def get_parents(self, revision_ids):
1188
"""See graph._StackedParentsProvider.get_parents.
1190
This implementation thunks the graph.Graph.get_parents api across to
1193
:param revision_ids: An iterable of graph keys for this graph.
1194
:return: A list of parent details for each key in revision_ids.
1195
Each parent details will be one of:
1196
* None when the key was missing
1197
* (NULL_REVISION,) when the key has no parents.
1198
* (parent_key, parent_key...) otherwise.
1200
parent_map = self.get_parent_map(revision_ids)
1201
return [parent_map.get(r, None) for r in revision_ids]
1203
1194
def get_parent_map(self, keys):
1204
1195
"""See graph._StackedParentsProvider.get_parent_map"""
1205
1196
search_keys = set(keys)
1498
1489
Queries against this will emit queries against the adapted Graph with the
1499
1490
prefix added, queries for all items use iter_entries_prefix. The returned
1500
nodes will have their keys and node references adjusted to remove the
1491
nodes will have their keys and node references adjusted to remove the
1501
1492
prefix. Finally, an add_nodes_callback can be supplied - when called the
1502
1493
nodes and references being added will have prefix prepended.
1530
1521
adjusted_references))
1531
1522
except ValueError:
1532
1523
# XXX: TODO add an explicit interface for getting the reference list
1533
# status, to handle this bit of user-friendliness in the API more
1524
# status, to handle this bit of user-friendliness in the API more
1535
1526
for (key, value) in nodes:
1536
1527
translated_nodes.append((self.prefix + key, value))
added
removed
bzrlib/index.py
