← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

Also add iter_key_prefix support to InMemoryGraphIndex.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
65
65
        """
66
66
        self.reference_lists = reference_lists
67
67
        self._nodes = {}
 
68
        self._nodes_by_key = {}
68
69
        self._key_length = key_elements
69
70
 
70
71
    def _check_key(self, key):
103
104
        if key in self._nodes and self._nodes[key][0] == '':
104
105
            raise errors.BadIndexDuplicateKey(key, self)
105
106
        self._nodes[key] = ('', tuple(node_refs), value)
 
107
        if self._key_length > 1:
 
108
            key_dict = self._nodes_by_key
 
109
            if self.reference_lists:
 
110
                key_value = key, value, tuple(node_refs)
 
111
            else:
 
112
                key_value = key, value
 
113
            # possibly should do this on-demand, but it seems likely it is 
 
114
            # always wanted
 
115
            subkey = list(reversed(key[:-1]))
 
116
            while len(subkey):
 
117
                if subkey[-1] not in key_dict:
 
118
                    key_dict[subkey[-1]] = {}
 
119
                key_dict = key_dict[subkey[-1]]
 
120
                subkey.pop(-1)
 
121
            key_dict[key[-1]] = key_value
106
122
 
107
123
    def finish(self):
108
124
        lines = [_SIGNATURE]
580
596
                if not node[0]:
581
597
                    yield key, node[2]
582
598
 
 
599
    def iter_entries_prefix(self, keys):
 
600
        """Iterate over keys within the index using prefix matching.
 
601
 
 
602
        Prefix matching is applied within the tuple of a key, not to within
 
603
        the bytestring of each key element. e.g. if you have the keys ('foo',
 
604
        'bar'), ('foobar', 'gam') and do a prefix search for ('foo', None) then
 
605
        only the former key is returned.
 
606
 
 
607
        :param keys: An iterable providing the key prefixes to be retrieved.
 
608
            Each key prefix takes the form of a tuple the length of a key, but
 
609
            with the last N elements 'None' rather than a regular bytestring.
 
610
            The first element cannot be 'None'.
 
611
        :return: An iterable as per iter_all_entries, but restricted to the
 
612
            keys with a matching prefix to those supplied. No additional keys
 
613
            will be returned, and every match that is in the index will be
 
614
            returned.
 
615
        """
 
616
        # XXX: To much duplication with the GraphIndex class; consider finding
 
617
        # a good place to pull out the actual common logic.
 
618
        keys = set(keys)
 
619
        if not keys:
 
620
            return
 
621
        if self._key_length == 1:
 
622
            for key in keys:
 
623
                # sanity check
 
624
                if key[0] is None:
 
625
                    raise errors.BadIndexKey(key)
 
626
                if len(key) != self._key_length:
 
627
                    raise errors.BadIndexKey(key)
 
628
                node = self._nodes[key]
 
629
                if node[0]:
 
630
                    continue 
 
631
                if self.reference_lists:
 
632
                    yield key, node[2], node[1]
 
633
                else:
 
634
                    yield key, node[2]
 
635
            return
 
636
        for key in keys:
 
637
            # sanity check
 
638
            if key[0] is None:
 
639
                raise errors.BadIndexKey(key)
 
640
            if len(key) != self._key_length:
 
641
                raise errors.BadIndexKey(key)
 
642
            # find what it refers to:
 
643
            key_dict = self._nodes_by_key
 
644
            elements = list(key)
 
645
            # find the subdict to return
 
646
            try:
 
647
                while len(elements) and elements[0] is not None:
 
648
                    key_dict = key_dict[elements[0]]
 
649
                    elements.pop(0)
 
650
            except KeyError:
 
651
                # a non-existant lookup.
 
652
                continue
 
653
            if len(elements):
 
654
                dicts = [key_dict]
 
655
                while dicts:
 
656
                    key_dict = dicts.pop(-1)
 
657
                    # can't be empty or would not exist
 
658
                    item, value = key_dict.iteritems().next()
 
659
                    if type(value) == dict:
 
660
                        # push keys 
 
661
                        dicts.extend(key_dict.itervalues())
 
662
                    else:
 
663
                        # yield keys
 
664
                        for value in key_dict.itervalues():
 
665
                            yield value
 
666
            else:
 
667
                yield key_dict
 
668
 
583
669
    def validate(self):
584
670
        """In memory index's have no known corruption at the moment."""