← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: John Arbash Meinel
  • Date: 2010-02-17 17:11:16 UTC
  • mfrom: (4797.2.17 2.1)
  • mto: (4797.2.18 2.1)
  • mto: This revision was merged to the branch mainline in revision 5055.
  • Revision ID: john@arbash-meinel.com-20100217171116-h7t9223ystbnx5h8
merge bzr.2.1 in preparation for NEWS entry.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
1
 
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2007-2010 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
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
            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
210
212
 
211
213
    def add_node(self, key, value, references=()):
212
214
        """Add a node to the index.
227
229
            # There may be duplicates, but I don't think it is worth worrying
228
230
            # about
229
231
            self._nodes[reference] = ('a', (), '')
 
232
        self._absent_keys.update(absent_references)
 
233
        self._absent_keys.discard(key)
230
234
        self._nodes[key] = ('', node_refs, value)
231
 
        self._keys.add(key)
232
235
        if self._nodes_by_key is not None and self._key_length > 1:
233
236
            self._update_nodes_by_key(key, value, node_refs)
234
237
 
243
246
        lines = [_SIGNATURE]
244
247
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
245
248
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
246
 
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
 
249
        key_count = len(self._nodes) - len(self._absent_keys)
 
250
        lines.append(_OPTION_LEN + str(key_count) + '\n')
247
251
        prefix_length = sum(len(x) for x in lines)
248
252
        # references are byte offsets. To avoid having to do nasty
249
253
        # polynomial work to resolve offsets (references to later in the
451
455
        trailers = 0
452
456
        pos = stream.tell()
453
457
        lines = stream.read().split('\n')
 
458
        stream.close()
454
459
        del lines[-1]
455
460
        _, _, _, trailers = self._parse_lines(lines, pos)
456
461
        for key, absent, references, value in self._keys_by_offset.itervalues():
463
468
                node_value = value
464
469
            self._nodes[key] = node_value
465
470
        # cache the keys for quick set intersections
466
 
        self._keys = set(self._nodes)
467
471
        if trailers != 1:
468
472
            # there must be one line - the empty trailer line.
469
473
            raise errors.BadIndexData(self)
484
488
            raise ValueError('No ref list %d, index has %d ref lists'
485
489
                % (ref_list_num, self.node_ref_lists))
486
490
        refs = set()
487
 
        for key, (value, ref_lists) in self._nodes.iteritems():
 
491
        nodes = self._nodes
 
492
        for key, (value, ref_lists) in nodes.iteritems():
488
493
            ref_list = ref_lists[ref_list_num]
489
 
            refs.update(ref_list)
490
 
        return refs - self._keys
 
494
            refs.update([ref for ref in ref_list if ref not in nodes])
 
495
        return refs
491
496
 
492
497
    def _get_nodes_by_key(self):
493
498
        if self._nodes_by_key is None:
620
625
 
621
626
    def _iter_entries_from_total_buffer(self, keys):
622
627
        """Iterate over keys when the entire index is parsed."""
623
 
        keys = keys.intersection(self._keys)
 
628
        # Note: See the note in BTreeBuilder.iter_entries for why we don't use
 
629
        #       .intersection() here
 
630
        nodes = self._nodes
 
631
        keys = [key for key in keys if key in nodes]
624
632
        if self.node_ref_lists:
625
633
            for key in keys:
626
 
                value, node_refs = self._nodes[key]
 
634
                value, node_refs = nodes[key]
627
635
                yield self, key, value, node_refs
628
636
        else:
629
637
            for key in keys:
630
 
                yield self, key, self._nodes[key]
 
638
                yield self, key, nodes[key]
631
639
 
632
640
    def iter_entries(self, keys):
633
641
        """Iterate over keys within the index.
1170
1178
            self._parsed_key_map.insert(index + 1, new_key)
1171
1179
 
1172
1180
    def _read_and_parse(self, readv_ranges):
1173
 
        """Read the the ranges and parse the resulting data.
 
1181
        """Read the ranges and parse the resulting data.
1174
1182
 
1175
1183
        :param readv_ranges: A prepared readv range list.
1176
1184
        """
1507
1515
            defined order for the result iteration - it will be in the most
1508
1516
            efficient order for the index (keys iteration order in this case).
1509
1517
        """
1510
 
        keys = set(keys)
 
1518
        # Note: See BTreeBuilder.iter_entries for an explanation of why we
 
1519
        #       aren't using set().intersection() here
 
1520
        nodes = self._nodes
 
1521
        keys = [key for key in keys if key in nodes]
1511
1522
        if self.reference_lists:
1512
 
            for key in keys.intersection(self._keys):
1513
 
                node = self._nodes[key]
 
1523
            for key in keys:
 
1524
                node = nodes[key]
1514
1525
                if not node[0]:
1515
1526
                    yield self, key, node[2], node[1]
1516
1527
        else:
1517
 
            for key in keys.intersection(self._keys):
1518
 
                node = self._nodes[key]
 
1528
            for key in keys:
 
1529
                node = nodes[key]
1519
1530
                if not node[0]:
1520
1531
                    yield self, key, node[2]
1521
1532
 
1595
1606
 
1596
1607
        For InMemoryGraphIndex the estimate is exact.
1597
1608
        """
1598
 
        return len(self._keys)
 
1609
        return len(self._nodes) - len(self._absent_keys)
1599
1610
 
1600
1611
    def validate(self):
1601
1612
        """In memory index's have no known corruption at the moment."""