/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Robert Collins
  • Date: 2007-08-07 05:44:30 UTC
  • mto: (2592.3.96 repository)
  • mto: This revision was merged to the branch mainline in revision 2742.
  • Revision ID: robertc@robertcollins.net-20070807054430-65ige2n2869mp7t4
Add a key_count method to GraphIndex and friends, allowing optimisation of length calculations by the index.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
34
34
from bzrlib import debug, errors
35
35
 
36
36
_OPTION_KEY_ELEMENTS = "key_elements="
 
37
_OPTION_LEN = "len="
37
38
_OPTION_NODE_REFS = "node_ref_lists="
38
39
_SIGNATURE = "Bazaar Graph Index 1\n"
39
40
 
69
70
        :param key_elements: The number of bytestrings in each key.
70
71
        """
71
72
        self.reference_lists = reference_lists
 
73
        self._keys = set()
72
74
        self._nodes = {}
73
75
        self._nodes_by_key = {}
74
76
        self._key_length = key_elements
109
111
        if key in self._nodes and self._nodes[key][0] == '':
110
112
            raise errors.BadIndexDuplicateKey(key, self)
111
113
        self._nodes[key] = ('', tuple(node_refs), value)
 
114
        self._keys.add(key)
112
115
        if self._key_length > 1:
113
116
            key_dict = self._nodes_by_key
114
117
            if self.reference_lists:
127
130
        lines = [_SIGNATURE]
128
131
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
129
132
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
 
133
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
130
134
        prefix_length = sum(len(x) for x in lines)
131
135
        # references are byte offsets. To avoid having to do nasty
132
136
        # polynomial work to resolve offsets (references to later in the 
236
240
        self._transport = transport
237
241
        self._name = name
238
242
        self._nodes = None
 
243
        self._key_count = None
239
244
        self._keys_by_offset = None
240
245
        self._nodes_by_key = None
241
246
 
302
307
                for subkey in key[:-1]:
303
308
                    key_dict = key_dict.setdefault(subkey, {})
304
309
                key_dict[key[-1]] = key_value
 
310
        # cache the keys for quick set intersections
305
311
        self._keys = set(self._nodes)
306
312
        if trailers != 1:
307
313
            # there must be one line - the empty trailer line.
343
349
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
344
350
        except ValueError:
345
351
            raise errors.BadIndexOptions(self)
 
352
        options_line = stream.readline()
 
353
        if not options_line.startswith(_OPTION_LEN):
 
354
            raise errors.BadIndexOptions(self)
 
355
        try:
 
356
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
 
357
        except ValueError:
 
358
            raise errors.BadIndexOptions(self)
346
359
 
347
360
    def iter_entries(self, keys):
348
361
        """Iterate over keys within the index.
438
451
                # the last thing looked up was a terminal element
439
452
                yield (self, ) + key_dict
440
453
 
 
454
    def key_count(self):
 
455
        """Return an estimate of the number of keys in this index.
 
456
        
 
457
        For GraphIndex the estimate is exact.
 
458
        """
 
459
        if self._key_count is None:
 
460
            # really this should just read the prefix
 
461
            self._buffer_all()
 
462
        return self._key_count
 
463
 
441
464
    def _signature(self):
442
465
        """The file signature for this index type."""
443
466
        return _SIGNATURE
544
567
                seen_keys.add(node[1])
545
568
                yield node
546
569
 
 
570
    def key_count(self):
 
571
        """Return an estimate of the number of keys in this index.
 
572
        
 
573
        For CombinedGraphIndex this is approximated by the sum of the keys of
 
574
        the child indices. As child indices may have duplicate keys this can
 
575
        have a maximum error of the number of child indices * largest number of
 
576
        keys in any index.
 
577
        """
 
578
        return sum((index.key_count() for index in self._indices), 0)
 
579
 
547
580
    def validate(self):
548
581
        """Validate that everything in the index can be accessed."""
549
582
        for index in self._indices:
596
629
        """
597
630
        keys = set(keys)
598
631
        if self.reference_lists:
599
 
            for key in keys.intersection(self._nodes):
 
632
            for key in keys.intersection(self._keys):
600
633
                node = self._nodes[key]
601
634
                if not node[0]:
602
635
                    yield self, key, node[2], node[1]
603
636
        else:
604
 
            for key in keys.intersection(self._nodes):
 
637
            for key in keys.intersection(self._keys):
605
638
                node = self._nodes[key]
606
639
                if not node[0]:
607
640
                    yield self, key, node[2]
676
709
            else:
677
710
                yield (self, ) + key_dict
678
711
 
 
712
    def key_count(self):
 
713
        """Return an estimate of the number of keys in this index.
 
714
        
 
715
        For InMemoryGraphIndex the estimate is exact.
 
716
        """
 
717
        return len(self._keys)
 
718
 
679
719
    def validate(self):
680
720
        """In memory index's have no known corruption at the moment."""
681
721
 
791
831
        return self._strip_prefix(self.adapted.iter_entries_prefix(
792
832
            self.prefix_key + key for key in keys))
793
833
 
 
834
    def key_count(self):
 
835
        """Return an estimate of the number of keys in this index.
 
836
        
 
837
        For GraphIndexPrefixAdapter this is relatively expensive - key
 
838
        iteration with the prefix is done.
 
839
        """
 
840
        return len(list(self.iter_all_entries()))
 
841
 
794
842
    def validate(self):
795
843
        """Call the adapted's validate."""
796
844
        self.adapted.validate()