~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/chk_map.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-15 17:02:13 UTC
  • mfrom: (4442 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090615170213-3sgtjlvsr50v9r12
Merge bzr.dev 4442, in preparation for NEWS entry.

Show diffs side-by-side

added added

removed removed

Lines of Context:
121
121
 
122
122
    def _ensure_root(self):
123
123
        """Ensure that the root node is an object not a key."""
124
 
        if type(self._root_node) == tuple:
 
124
        if type(self._root_node) is tuple:
125
125
            # Demand-load the root
126
126
            self._root_node = self._get_node(self._root_node)
127
127
 
135
135
        :param node: A tuple key or node object.
136
136
        :return: A node object.
137
137
        """
138
 
        if type(node) == tuple:
 
138
        if type(node) is tuple:
139
139
            bytes = self._read_bytes(node)
140
140
            return _deserialise(bytes, node,
141
141
                search_key_func=self._search_key_func)
465
465
 
466
466
    def _node_key(self, node):
467
467
        """Get the key for a node whether it's a tuple or node."""
468
 
        if type(node) == tuple:
 
468
        if type(node) is tuple:
469
469
            return node
470
470
        else:
471
471
            return node._key
491
491
 
492
492
        :return: The key of the root node.
493
493
        """
494
 
        if type(self._root_node) == tuple:
 
494
        if type(self._root_node) is tuple:
495
495
            # Already saved.
496
496
            return self._root_node
497
497
        keys = list(self._root_node.serialise(self._store))
955
955
        # prefix is the key in self._items to use, key_filter is the key_filter
956
956
        # entries that would match this node
957
957
        keys = {}
 
958
        shortcut = False
958
959
        if key_filter is None:
 
960
            # yielding all nodes, yield whatever we have, and queue up a read
 
961
            # for whatever we are missing
 
962
            shortcut = True
959
963
            for prefix, node in self._items.iteritems():
960
 
                if type(node) == tuple:
 
964
                if node.__class__ is tuple:
961
965
                    keys[node] = (prefix, None)
962
966
                else:
963
967
                    yield node, None
964
 
        else:
965
 
            # XXX defaultdict ?
 
968
        elif len(key_filter) == 1:
 
969
            # Technically, this path could also be handled by the first check
 
970
            # in 'self._node_width' in length_filters. However, we can handle
 
971
            # this case without spending any time building up the
 
972
            # prefix_to_keys, etc state.
 
973
 
 
974
            # This is a bit ugly, but TIMEIT showed it to be by far the fastest
 
975
            # 0.626us   list(key_filter)[0]
 
976
            #       is a func() for list(), 2 mallocs, and a getitem
 
977
            # 0.489us   [k for k in key_filter][0]
 
978
            #       still has the mallocs, avoids the func() call
 
979
            # 0.350us   iter(key_filter).next()
 
980
            #       has a func() call, and mallocs an iterator
 
981
            # 0.125us   for key in key_filter: pass
 
982
            #       no func() overhead, might malloc an iterator
 
983
            # 0.105us   for key in key_filter: break
 
984
            #       no func() overhead, might malloc an iterator, probably
 
985
            #       avoids checking an 'else' clause as part of the for
 
986
            for key in key_filter:
 
987
                break
 
988
            search_prefix = self._search_prefix_filter(key)
 
989
            if len(search_prefix) == self._node_width:
 
990
                # This item will match exactly, so just do a dict lookup, and
 
991
                # see what we can return
 
992
                shortcut = True
 
993
                try:
 
994
                    node = self._items[search_prefix]
 
995
                except KeyError:
 
996
                    # A given key can only match 1 child node, if it isn't
 
997
                    # there, then we can just return nothing
 
998
                    return
 
999
                if node.__class__ is tuple:
 
1000
                    keys[node] = (search_prefix, [key])
 
1001
                else:
 
1002
                    # This is loaded, and the only thing that can match,
 
1003
                    # return
 
1004
                    yield node, [key]
 
1005
                    return
 
1006
        if not shortcut:
 
1007
            # First, convert all keys into a list of search prefixes
 
1008
            # Aggregate common prefixes, and track the keys they come from
966
1009
            prefix_to_keys = {}
967
1010
            length_filters = {}
968
1011
            for key in key_filter:
969
 
                search_key = self._search_prefix_filter(key)
 
1012
                search_prefix = self._search_prefix_filter(key)
970
1013
                length_filter = length_filters.setdefault(
971
 
                                    len(search_key), set())
972
 
                length_filter.add(search_key)
973
 
                prefix_to_keys.setdefault(search_key, []).append(key)
974
 
            length_filters = length_filters.items()
975
 
            for prefix, node in self._items.iteritems():
976
 
                node_key_filter = []
977
 
                for length, length_filter in length_filters:
978
 
                    sub_prefix = prefix[:length]
979
 
                    if sub_prefix in length_filter:
980
 
                        node_key_filter.extend(prefix_to_keys[sub_prefix])
981
 
                if node_key_filter: # this key matched something, yield it
982
 
                    if type(node) == tuple:
983
 
                        keys[node] = (prefix, node_key_filter)
 
1014
                                    len(search_prefix), set())
 
1015
                length_filter.add(search_prefix)
 
1016
                prefix_to_keys.setdefault(search_prefix, []).append(key)
 
1017
 
 
1018
            if (self._node_width in length_filters
 
1019
                and len(length_filters) == 1):
 
1020
                # all of the search prefixes match exactly _node_width. This
 
1021
                # means that everything is an exact match, and we can do a
 
1022
                # lookup into self._items, rather than iterating over the items
 
1023
                # dict.
 
1024
                search_prefixes = length_filters[self._node_width]
 
1025
                for search_prefix in search_prefixes:
 
1026
                    try:
 
1027
                        node = self._items[search_prefix]
 
1028
                    except KeyError:
 
1029
                        # We can ignore this one
 
1030
                        continue
 
1031
                    node_key_filter = prefix_to_keys[search_prefix]
 
1032
                    if node.__class__ is tuple:
 
1033
                        keys[node] = (search_prefix, node_key_filter)
984
1034
                    else:
985
1035
                        yield node, node_key_filter
 
1036
            else:
 
1037
                # The slow way. We walk every item in self._items, and check to
 
1038
                # see if there are any matches
 
1039
                length_filters = length_filters.items()
 
1040
                for prefix, node in self._items.iteritems():
 
1041
                    node_key_filter = []
 
1042
                    for length, length_filter in length_filters:
 
1043
                        sub_prefix = prefix[:length]
 
1044
                        if sub_prefix in length_filter:
 
1045
                            node_key_filter.extend(prefix_to_keys[sub_prefix])
 
1046
                    if node_key_filter: # this key matched something, yield it
 
1047
                        if node.__class__ is tuple:
 
1048
                            keys[node] = (prefix, node_key_filter)
 
1049
                        else:
 
1050
                            yield node, node_key_filter
986
1051
        if keys:
987
1052
            # Look in the page cache for some more bytes
988
1053
            found_keys = set()
1117
1182
        :return: An iterable of the keys inserted by this operation.
1118
1183
        """
1119
1184
        for node in self._items.itervalues():
1120
 
            if type(node) == tuple:
 
1185
            if type(node) is tuple:
1121
1186
                # Never deserialised.
1122
1187
                continue
1123
1188
            if node._key is not None:
1134
1199
        lines.append('%s\n' % (self._search_prefix,))
1135
1200
        prefix_len = len(self._search_prefix)
1136
1201
        for prefix, node in sorted(self._items.items()):
1137
 
            if type(node) == tuple:
 
1202
            if type(node) is tuple:
1138
1203
                key = node[0]
1139
1204
            else:
1140
1205
                key = node._key[0]
1179
1244
            raise AssertionError("unserialised nodes have no refs.")
1180
1245
        refs = []
1181
1246
        for value in self._items.itervalues():
1182
 
            if type(value) == tuple:
 
1247
            if type(value) is tuple:
1183
1248
                refs.append(value)
1184
1249
            else:
1185
1250
                refs.append(value.key())