« back to all changes in this revision
Viewing changes to bzrlib/index.py
- browse files at revision 4842
- compare with another revision
- compare with revision 2485.8.58
- download diff
- download tarball
- view history from revision 4842
- Committer: Canonical.com Patch Queue Manager
- Date: 2009-11-30 22:04:45 UTC
- mfrom: (4789.28.4 2.1.0b4-builder-no-keys)
- Revision ID: pqm@pqm.ubuntu.com-20091130220445-vbfmmgocbgcs195q
(jam) Update BTreeBuilder to remove ._keys and use StaticTuple
added
removed
bzrlib/index.py
93
93
:param key_elements: The number of bytestrings in each key.
94
94
"""
95
95
self.reference_lists = reference_lists
96
self._keys = set()
97
96
# A dict of {key: (absent, ref_lists, value)}
98
97
self._nodes = {}
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
165
166
return
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)
169
170
else:
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
189
190
This may contain duplicates if the same key is
190
191
referenced in multiple lists.
191
192
"""
193
as_st = StaticTuple.from_sequence
192
194
self._check_key(key)
193
195
if _newline_null_re.search(value) is not None:
194
196
raise errors.BadIndexValue(value)
203
205
if reference not in self._nodes:
204
206
self._check_key(reference)
205
207
absent_references.append(reference)
206
# TODO: StaticTuple
207
node_refs.append(tuple(reference_list))
208
# TODO: StaticTuple
209
return tuple(node_refs), absent_references
208
node_refs.append(as_st(reference_list))
209
return as_st(node_refs), absent_references
210
210
211
211
def add_node(self, key, value, references=()):
212
212
"""Add a node to the index.
227
227
# There may be duplicates, but I don't think it is worth worrying
228
228
# about
229
229
self._nodes[reference] = ('a', (), '')
230
self._absent_keys.update(absent_references)
231
self._absent_keys.discard(key)
230
232
self._nodes[key] = ('', node_refs, value)
231
self._keys.add(key)
232
233
if self._nodes_by_key is not None and self._key_length > 1:
233
234
self._update_nodes_by_key(key, value, node_refs)
234
235
243
244
lines = [_SIGNATURE]
244
245
lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
245
246
lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
246
lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
247
key_count = len(self._nodes) - len(self._absent_keys)
248
lines.append(_OPTION_LEN + str(key_count) + '\n')
247
249
prefix_length = sum(len(x) for x in lines)
248
250
# references are byte offsets. To avoid having to do nasty
249
251
# polynomial work to resolve offsets (references to later in the
463
465
node_value = value
464
466
self._nodes[key] = node_value
465
467
# cache the keys for quick set intersections
466
self._keys = set(self._nodes)
467
468
if trailers != 1:
468
469
# there must be one line - the empty trailer line.
469
470
raise errors.BadIndexData(self)
484
485
raise ValueError('No ref list %d, index has %d ref lists'
485
486
% (ref_list_num, self.node_ref_lists))
486
487
refs = set()
487
for key, (value, ref_lists) in self._nodes.iteritems():
488
nodes = self._nodes
489
for key, (value, ref_lists) in nodes.iteritems():
488
490
ref_list = ref_lists[ref_list_num]
489
refs.update(ref_list)
490
return refs - self._keys
491
refs.update([ref for ref in ref_list if ref not in nodes])
492
return refs
491
493
492
494
def _get_nodes_by_key(self):
493
495
if self._nodes_by_key is None:
620
622
621
623
def _iter_entries_from_total_buffer(self, keys):
622
624
"""Iterate over keys when the entire index is parsed."""
623
keys = keys.intersection(self._keys)
625
# Note: See the note in BTreeBuilder.iter_entries for why we don't use
626
# .intersection() here
627
nodes = self._nodes
628
keys = [key for key in keys if key in nodes]
624
629
if self.node_ref_lists:
625
630
for key in keys:
626
value, node_refs = self._nodes[key]
631
value, node_refs = nodes[key]
627
632
yield self, key, value, node_refs
628
633
else:
629
634
for key in keys:
630
yield self, key, self._nodes[key]
635
yield self, key, nodes[key]
631
636
632
637
def iter_entries(self, keys):
633
638
"""Iterate over keys within the index.
1507
1512
defined order for the result iteration - it will be in the most
1508
1513
efficient order for the index (keys iteration order in this case).
1509
1514
"""
1510
keys = set(keys)
1515
# Note: See BTreeBuilder.iter_entries for an explanation of why we
1516
# aren't using set().intersection() here
1517
nodes = self._nodes
1518
keys = [key for key in keys if key in nodes]
1511
1519
if self.reference_lists:
1512
for key in keys.intersection(self._keys):
1513
node = self._nodes[key]
1520
for key in keys:
1521
node = nodes[key]
1514
1522
if not node[0]:
1515
1523
yield self, key, node[2], node[1]
1516
1524
else:
1517
for key in keys.intersection(self._keys):
1518
node = self._nodes[key]
1525
for key in keys:
1526
node = nodes[key]
1519
1527
if not node[0]:
1520
1528
yield self, key, node[2]
1521
1529
1595
1603
1596
1604
For InMemoryGraphIndex the estimate is exact.
1597
1605
"""
1598
return len(self._keys)
1606
return len(self._nodes) - len(self._absent_keys)
1599
1607
1600
1608
def validate(self):
1601
1609
"""In memory index's have no known corruption at the moment."""
Loggerhead is a web-based interface for Breezy
Version: 2.0.1