← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Andrew Bennetts
  • Date: 2007-08-30 08:11:54 UTC
  • mfrom: (2766 +trunk)
  • mto: (2535.3.55 repo-refactor)
  • mto: This revision was merged to the branch mainline in revision 2772.
  • Revision ID: andrew.bennetts@canonical.com-20070830081154-16hebp2xwr15x2hc
Merge from bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
27
27
from cStringIO import StringIO
28
28
import re
29
29
 
30
 
from bzrlib import errors
 
30
from bzrlib.lazy_import import lazy_import
 
31
lazy_import(globals(), """
 
32
from bzrlib import trace
 
33
from bzrlib.trace import mutter
 
34
""")
 
35
from bzrlib import debug, errors
31
36
 
32
37
_OPTION_KEY_ELEMENTS = "key_elements="
 
38
_OPTION_LEN = "len="
33
39
_OPTION_NODE_REFS = "node_ref_lists="
34
40
_SIGNATURE = "Bazaar Graph Index 1\n"
35
41
 
65
71
        :param key_elements: The number of bytestrings in each key.
66
72
        """
67
73
        self.reference_lists = reference_lists
 
74
        self._keys = set()
68
75
        self._nodes = {}
69
76
        self._nodes_by_key = {}
70
77
        self._key_length = key_elements
105
112
        if key in self._nodes and self._nodes[key][0] == '':
106
113
            raise errors.BadIndexDuplicateKey(key, self)
107
114
        self._nodes[key] = ('', tuple(node_refs), value)
 
115
        self._keys.add(key)
108
116
        if self._key_length > 1:
109
117
            key_dict = self._nodes_by_key
110
118
            if self.reference_lists:
123
131
        lines = [_SIGNATURE]
124
132
        lines.append(_OPTION_NODE_REFS + str(self.reference_lists) + '\n')
125
133
        lines.append(_OPTION_KEY_ELEMENTS + str(self._key_length) + '\n')
 
134
        lines.append(_OPTION_LEN + str(len(self._keys)) + '\n')
126
135
        prefix_length = sum(len(x) for x in lines)
127
136
        # references are byte offsets. To avoid having to do nasty
128
137
        # polynomial work to resolve offsets (references to later in the 
232
241
        self._transport = transport
233
242
        self._name = name
234
243
        self._nodes = None
 
244
        self._key_count = None
235
245
        self._keys_by_offset = None
236
246
        self._nodes_by_key = None
237
247
 
240
250
 
241
251
        Mutates self._nodes and self.keys_by_offset.
242
252
        """
 
253
        if 'index' in debug.debug_flags:
 
254
            mutter('Reading entire index %s', self._transport.abspath(self._name))
243
255
        stream = self._transport.get(self._name)
244
256
        self._read_prefix(stream)
245
257
        expected_elements = 3 + self._key_length
296
308
                for subkey in key[:-1]:
297
309
                    key_dict = key_dict.setdefault(subkey, {})
298
310
                key_dict[key[-1]] = key_value
 
311
        # cache the keys for quick set intersections
299
312
        self._keys = set(self._nodes)
300
313
        if trailers != 1:
301
314
            # there must be one line - the empty trailer line.
310
323
            There is no defined order for the result iteration - it will be in
311
324
            the most efficient order for the index.
312
325
        """
 
326
        if 'evil' in debug.debug_flags:
 
327
            trace.mutter_callsite(2,
 
328
                "iter_all_entries scales with size of history.")
313
329
        if self._nodes is None:
314
330
            self._buffer_all()
315
331
        if self.node_ref_lists:
337
353
            self._key_length = int(options_line[len(_OPTION_KEY_ELEMENTS):-1])
338
354
        except ValueError:
339
355
            raise errors.BadIndexOptions(self)
 
356
        options_line = stream.readline()
 
357
        if not options_line.startswith(_OPTION_LEN):
 
358
            raise errors.BadIndexOptions(self)
 
359
        try:
 
360
            self._key_count = int(options_line[len(_OPTION_LEN):-1])
 
361
        except ValueError:
 
362
            raise errors.BadIndexOptions(self)
340
363
 
341
364
    def iter_entries(self, keys):
342
365
        """Iterate over keys within the index.
432
455
                # the last thing looked up was a terminal element
433
456
                yield (self, ) + key_dict
434
457
 
 
458
    def key_count(self):
 
459
        """Return an estimate of the number of keys in this index.
 
460
        
 
461
        For GraphIndex the estimate is exact.
 
462
        """
 
463
        if self._key_count is None:
 
464
            # really this should just read the prefix
 
465
            self._buffer_all()
 
466
        return self._key_count
 
467
 
435
468
    def _signature(self):
436
469
        """The file signature for this index type."""
437
470
        return _SIGNATURE
538
571
                seen_keys.add(node[1])
539
572
                yield node
540
573
 
 
574
    def key_count(self):
 
575
        """Return an estimate of the number of keys in this index.
 
576
        
 
577
        For CombinedGraphIndex this is approximated by the sum of the keys of
 
578
        the child indices. As child indices may have duplicate keys this can
 
579
        have a maximum error of the number of child indices * largest number of
 
580
        keys in any index.
 
581
        """
 
582
        return sum((index.key_count() for index in self._indices), 0)
 
583
 
541
584
    def validate(self):
542
585
        """Validate that everything in the index can be accessed."""
543
586
        for index in self._indices:
571
614
            defined order for the result iteration - it will be in the most
572
615
            efficient order for the index (in this case dictionary hash order).
573
616
        """
 
617
        if 'evil' in debug.debug_flags:
 
618
            trace.mutter_callsite(2,
 
619
                "iter_all_entries scales with size of history.")
574
620
        if self.reference_lists:
575
621
            for key, (absent, references, value) in self._nodes.iteritems():
576
622
                if not absent:
590
636
        """
591
637
        keys = set(keys)
592
638
        if self.reference_lists:
593
 
            for key in keys.intersection(self._nodes):
 
639
            for key in keys.intersection(self._keys):
594
640
                node = self._nodes[key]
595
641
                if not node[0]:
596
642
                    yield self, key, node[2], node[1]
597
643
        else:
598
 
            for key in keys.intersection(self._nodes):
 
644
            for key in keys.intersection(self._keys):
599
645
                node = self._nodes[key]
600
646
                if not node[0]:
601
647
                    yield self, key, node[2]
635
681
                if self.reference_lists:
636
682
                    yield self, key, node[2], node[1]
637
683
                else:
638
 
                    yield self ,key, node[2]
 
684
                    yield self, key, node[2]
639
685
            return
640
686
        for key in keys:
641
687
            # sanity check
670
716
            else:
671
717
                yield (self, ) + key_dict
672
718
 
 
719
    def key_count(self):
 
720
        """Return an estimate of the number of keys in this index.
 
721
        
 
722
        For InMemoryGraphIndex the estimate is exact.
 
723
        """
 
724
        return len(self._keys)
 
725
 
673
726
    def validate(self):
674
727
        """In memory index's have no known corruption at the moment."""
675
728
 
684
737
    nodes and references being added will have prefix prepended.
685
738
    """
686
739
 
687
 
    def __init__(self, adapted, prefix, missing_key_length, add_nodes_callback=None):
 
740
    def __init__(self, adapted, prefix, missing_key_length,
 
741
        add_nodes_callback=None):
688
742
        """Construct an adapter against adapted with prefix."""
689
743
        self.adapted = adapted
690
 
        self.prefix = prefix + (None,)*missing_key_length
691
 
        self.prefix_key = prefix
 
744
        self.prefix_key = prefix + (None,)*missing_key_length
 
745
        self.prefix = prefix
692
746
        self.prefix_len = len(prefix)
693
747
        self.add_nodes_callback = add_nodes_callback
694
748
 
701
755
        nodes = tuple(nodes)
702
756
        translated_nodes = []
703
757
        try:
 
758
            # Add prefix_key to each reference node_refs is a tuple of tuples,
 
759
            # so split it apart, and add prefix_key to the internal reference
704
760
            for (key, value, node_refs) in nodes:
705
761
                adjusted_references = (
706
 
                    tuple(tuple(self.prefix_key + ref_node for ref_node in ref_list)
 
762
                    tuple(tuple(self.prefix + ref_node for ref_node in ref_list)
707
763
                        for ref_list in node_refs))
708
 
                translated_nodes.append((self.prefix_key + key, value,
 
764
                translated_nodes.append((self.prefix + key, value,
709
765
                    adjusted_references))
710
766
        except ValueError:
711
767
            # XXX: TODO add an explicit interface for getting the reference list
712
768
            # status, to handle this bit of user-friendliness in the API more 
713
769
            # explicitly.
714
770
            for (key, value) in nodes:
715
 
                translated_nodes.append((self.prefix_key + key, value))
 
771
                translated_nodes.append((self.prefix + key, value))
716
772
        self.add_nodes_callback(translated_nodes)
717
773
 
718
774
    def add_node(self, key, value, references=()):
732
788
        """Strip prefix data from nodes and return it."""
733
789
        for node in an_iter:
734
790
            # cross checks
735
 
            if node[1][:self.prefix_len] != self.prefix_key:
 
791
            if node[1][:self.prefix_len] != self.prefix:
736
792
                raise errors.BadIndexData(self)
737
793
            for ref_list in node[3]:
738
794
                for ref_node in ref_list:
739
 
                    if ref_node[:self.prefix_len] != self.prefix_key:
 
795
                    if ref_node[:self.prefix_len] != self.prefix:
740
796
                        raise errors.BadIndexData(self)
741
797
            yield node[0], node[1][self.prefix_len:], node[2], (
742
798
                tuple(tuple(ref_node[self.prefix_len:] for ref_node in ref_list)
752
808
            defined order for the result iteration - it will be in the most
753
809
            efficient order for the index (in this case dictionary hash order).
754
810
        """
755
 
        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix]))
 
811
        return self._strip_prefix(self.adapted.iter_entries_prefix([self.prefix_key]))
756
812
 
757
813
    def iter_entries(self, keys):
758
814
        """Iterate over keys within the index.
763
819
            efficient order for the index (keys iteration order in this case).
764
820
        """
765
821
        return self._strip_prefix(self.adapted.iter_entries(
766
 
            self.prefix_key + key for key in keys))
 
822
            self.prefix + key for key in keys))
767
823
 
768
824
    def iter_entries_prefix(self, keys):
769
825
        """Iterate over keys within the index using prefix matching.
783
839
            returned.
784
840
        """
785
841
        return self._strip_prefix(self.adapted.iter_entries_prefix(
786
 
            self.prefix_key + key for key in keys))
 
842
            self.prefix + key for key in keys))
 
843
 
 
844
    def key_count(self):
 
845
        """Return an estimate of the number of keys in this index.
 
846
        
 
847
        For GraphIndexPrefixAdapter this is relatively expensive - key
 
848
        iteration with the prefix is done.
 
849
        """
 
850
        return len(list(self.iter_all_entries()))
787
851
 
788
852
    def validate(self):
789
853
        """Call the adapted's validate."""