143
145
if self._nodes_by_key is None:
144
146
nodes_by_key = {}
145
147
if self.reference_lists:
146
for key, (absent, references, value) in self._nodes.iteritems():
148
for key, (absent, references, value) in viewitems(self._nodes):
149
151
key_dict = nodes_by_key
151
153
key_dict = key_dict.setdefault(subkey, {})
152
154
key_dict[key[-1]] = key, value, references
154
for key, (absent, references, value) in self._nodes.iteritems():
156
for key, (absent, references, value) in viewitems(self._nodes):
157
159
key_dict = nodes_by_key
275
277
# forward sorted by key. In future we may consider topological sorting,
276
278
# at the cost of table scans for direct lookup, or a second index for
278
nodes = sorted(self._nodes.items())
280
nodes = sorted(viewitems(self._nodes))
279
281
# if we do not prepass, we don't know how long it will be up front.
280
282
expected_bytes = None
281
283
# we only need to pre-pass if we have reference lists at all.
480
482
_, _, _, trailers = self._parse_lines(lines, pos)
481
for key, absent, references, value in self._keys_by_offset.itervalues():
483
for key, absent, references, value in viewvalues(self._keys_by_offset):
484
486
# resolve references:
509
511
% (ref_list_num, self.node_ref_lists))
511
513
nodes = self._nodes
512
for key, (value, ref_lists) in nodes.iteritems():
514
for key, (value, ref_lists) in viewitems(nodes):
513
515
ref_list = ref_lists[ref_list_num]
514
516
refs.update([ref for ref in ref_list if ref not in nodes])
518
520
if self._nodes_by_key is None:
519
521
nodes_by_key = {}
520
522
if self.node_ref_lists:
521
for key, (value, references) in self._nodes.iteritems():
523
for key, (value, references) in viewitems(self._nodes):
522
524
key_dict = nodes_by_key
523
525
for subkey in key[:-1]:
524
526
key_dict = key_dict.setdefault(subkey, {})
525
527
key_dict[key[-1]] = key, value, references
527
for key, value in self._nodes.iteritems():
529
for key, value in viewitems(self._nodes):
528
530
key_dict = nodes_by_key
529
531
for subkey in key[:-1]:
530
532
key_dict = key_dict.setdefault(subkey, {})
547
549
if self._nodes is None:
548
550
self._buffer_all()
549
551
if self.node_ref_lists:
550
for key, (value, node_ref_lists) in self._nodes.iteritems():
552
for key, (value, node_ref_lists) in viewitems(self._nodes):
551
553
yield self, key, value, node_ref_lists
553
for key, value in self._nodes.iteritems():
555
for key, value in viewitems(self._nodes):
554
556
yield self, key, value
556
558
def _read_prefix(self, stream):
716
718
self._buffer_all()
717
719
if self._key_length == 1:
721
raise errors.BadIndexKey(key)
722
if len(key) != self._key_length:
723
raise errors.BadIndexKey(key)
721
_sanity_check_key(self, key)
724
722
if self.node_ref_lists:
725
723
value, node_refs = self._nodes[key]
726
724
yield self, key, value, node_refs
728
726
yield self, key, self._nodes[key]
730
728
nodes_by_key = self._get_nodes_by_key()
734
raise errors.BadIndexKey(key)
735
if len(key) != self._key_length:
736
raise errors.BadIndexKey(key)
737
# find what it refers to:
738
key_dict = nodes_by_key
740
# find the subdict whose contents should be returned.
742
while len(elements) and elements[0] is not None:
743
key_dict = key_dict[elements[0]]
746
# a non-existant lookup.
751
key_dict = dicts.pop(-1)
752
# can't be empty or would not exist
753
item, value = next(key_dict.iteritems())
754
if isinstance(value, dict):
756
dicts.extend(key_dict.itervalues())
759
for value in key_dict.itervalues():
760
# each value is the key:value:node refs tuple
762
yield (self, ) + value
764
# the last thing looked up was a terminal element
765
yield (self, ) + key_dict
729
for entry in _iter_entries_prefix(self, nodes_by_key, keys):
767
732
def _find_ancestors(self, keys, ref_list_num, parent_map, missing_keys):
768
733
"""See BTreeIndex._find_ancestors."""
1635
1600
trace.mutter_callsite(3,
1636
1601
"iter_all_entries scales with size of history.")
1637
1602
if self.reference_lists:
1638
for key, (absent, references, value) in self._nodes.iteritems():
1603
for key, (absent, references, value) in viewitems(self._nodes):
1640
1605
yield self, key, value, references
1642
for key, (absent, references, value) in self._nodes.iteritems():
1607
for key, (absent, references, value) in viewitems(self._nodes):
1644
1609
yield self, key, value
1683
1648
will be returned, and every match that is in the index will be
1686
# XXX: To much duplication with the GraphIndex class; consider finding
1687
# a good place to pull out the actual common logic.
1688
1651
keys = set(keys)
1691
1654
if self._key_length == 1:
1692
1655
for key in keys:
1695
raise errors.BadIndexKey(key)
1696
if len(key) != self._key_length:
1697
raise errors.BadIndexKey(key)
1656
_sanity_check_key(self, key)
1698
1657
node = self._nodes[key]
1704
1663
yield self, key, node[2]
1706
1665
nodes_by_key = self._get_nodes_by_key()
1710
raise errors.BadIndexKey(key)
1711
if len(key) != self._key_length:
1712
raise errors.BadIndexKey(key)
1713
# find what it refers to:
1714
key_dict = nodes_by_key
1715
elements = list(key)
1716
# find the subdict to return
1718
while len(elements) and elements[0] is not None:
1719
key_dict = key_dict[elements[0]]
1722
# a non-existant lookup.
1727
key_dict = dicts.pop(-1)
1728
# can't be empty or would not exist
1729
item, value = next(key_dict.iteritems())
1730
if isinstance(value, dict):
1732
dicts.extend(key_dict.itervalues())
1735
for value in key_dict.itervalues():
1736
yield (self, ) + value
1738
yield (self, ) + key_dict
1666
for entry in _iter_entries_prefix(self, nodes_by_key, keys):
1740
1669
def key_count(self):
1741
1670
"""Return an estimate of the number of keys in this index.
1873
1802
def validate(self):
1874
1803
"""Call the adapted's validate."""
1875
1804
self.adapted.validate()
1807
def _sanity_check_key(index_or_builder, key):
1808
"""Raise BadIndexKey if key cannot be used for prefix matching."""
1810
raise errors.BadIndexKey(key)
1811
if len(key) != index_or_builder._key_length:
1812
raise errors.BadIndexKey(key)
1815
def _iter_entries_prefix(index_or_builder, nodes_by_key, keys):
1816
"""Helper for implementing prefix matching iterators."""
1818
_sanity_check_key(index_or_builder, key)
1819
# find what it refers to:
1820
key_dict = nodes_by_key
1821
elements = list(key)
1822
# find the subdict whose contents should be returned.
1824
while len(elements) and elements[0] is not None:
1825
key_dict = key_dict[elements[0]]
1828
# a non-existant lookup.
1833
values_view = viewvalues(dicts.pop())
1834
# can't be empty or would not exist
1835
value = next(iter(values_view))
1836
if isinstance(value, dict):
1837
# still descending, push values
1838
dicts.extend(values_view)
1840
# at leaf tuples, yield values
1841
for value in values_view:
1842
# each value is the key:value:node refs tuple
1844
yield (index_or_builder, ) + value
1846
# the last thing looked up was a terminal element
1847
yield (index_or_builder, ) + key_dict
added
removed
breezy/index.py
