← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/chk_map.py

  • Committer: Martin Pool
  • Date: 2009-06-19 09:06:56 UTC
  • mfrom: (4463 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4464.
  • Revision ID: mbp@sourcefrog.net-20090619090656-d5weqeecyscv8kqp
merge news

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/chk_map.py
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)
203
203
            multiple pages.
204
204
        :return: The root chk of the resulting CHKMap.
205
205
        """
206
 
        result = CHKMap(store, None, search_key_func=search_key_func)
 
206
        root_key = klass._create_directly(store, initial_value,
 
207
            maximum_size=maximum_size, key_width=key_width,
 
208
            search_key_func=search_key_func)
 
209
        return root_key
 
210
 
 
211
    @classmethod
 
212
    def _create_via_map(klass, store, initial_value, maximum_size=0,
 
213
                        key_width=1, search_key_func=None):
 
214
        result = klass(store, None, search_key_func=search_key_func)
207
215
        result._root_node.set_maximum_size(maximum_size)
208
216
        result._root_node._key_width = key_width
209
217
        delta = []
210
218
        for key, value in initial_value.items():
211
219
            delta.append((None, key, value))
212
 
        return result.apply_delta(delta)
 
220
        root_key = result.apply_delta(delta)
 
221
        return root_key
 
222
 
 
223
    @classmethod
 
224
    def _create_directly(klass, store, initial_value, maximum_size=0,
 
225
                         key_width=1, search_key_func=None):
 
226
        node = LeafNode(search_key_func=search_key_func)
 
227
        node.set_maximum_size(maximum_size)
 
228
        node._key_width = key_width
 
229
        node._items = dict(initial_value)
 
230
        node._raw_size = sum([node._key_value_len(key, value)
 
231
                              for key,value in initial_value.iteritems()])
 
232
        node._len = len(node._items)
 
233
        node._compute_search_prefix()
 
234
        node._compute_serialised_prefix()
 
235
        if (node._len > 1
 
236
            and maximum_size
 
237
            and node._current_size() > maximum_size):
 
238
            prefix, node_details = node._split(store)
 
239
            if len(node_details) == 1:
 
240
                raise AssertionError('Failed to split using node._split')
 
241
            node = InternalNode(prefix, search_key_func=search_key_func)
 
242
            node.set_maximum_size(maximum_size)
 
243
            node._key_width = key_width
 
244
            for split, subnode in node_details:
 
245
                node.add_node(split, subnode)
 
246
        keys = list(node.serialise(store))
 
247
        return keys[-1]
213
248
 
214
249
    def iter_changes(self, basis):
215
250
        """Iterate over the changes between basis and self.
465
500
 
466
501
    def _node_key(self, node):
467
502
        """Get the key for a node whether it's a tuple or node."""
468
 
        if type(node) == tuple:
 
503
        if type(node) is tuple:
469
504
            return node
470
505
        else:
471
506
            return node._key
491
526
 
492
527
        :return: The key of the root node.
493
528
        """
494
 
        if type(self._root_node) == tuple:
 
529
        if type(self._root_node) is tuple:
495
530
            # Already saved.
496
531
            return self._root_node
497
532
        keys = list(self._root_node.serialise(self._store))
764
799
                result[prefix] = node
765
800
            else:
766
801
                node = result[prefix]
767
 
            node.map(store, key, value)
 
802
            sub_prefix, node_details = node.map(store, key, value)
 
803
            if len(node_details) > 1:
 
804
                if prefix != sub_prefix:
 
805
                    # This node has been split and is now found via a different
 
806
                    # path
 
807
                    result.pop(prefix)
 
808
                new_node = InternalNode(sub_prefix,
 
809
                    search_key_func=self._search_key_func)
 
810
                new_node.set_maximum_size(self._maximum_size)
 
811
                new_node._key_width = self._key_width
 
812
                for split, node in node_details:
 
813
                    new_node.add_node(split, node)
 
814
                result[prefix] = new_node
768
815
        return common_prefix, result.items()
769
816
 
770
817
    def map(self, store, key, value):
955
1002
        # prefix is the key in self._items to use, key_filter is the key_filter
956
1003
        # entries that would match this node
957
1004
        keys = {}
 
1005
        shortcut = False
958
1006
        if key_filter is None:
 
1007
            # yielding all nodes, yield whatever we have, and queue up a read
 
1008
            # for whatever we are missing
 
1009
            shortcut = True
959
1010
            for prefix, node in self._items.iteritems():
960
 
                if type(node) == tuple:
 
1011
                if node.__class__ is tuple:
961
1012
                    keys[node] = (prefix, None)
962
1013
                else:
963
1014
                    yield node, None
964
 
        else:
965
 
            # XXX defaultdict ?
 
1015
        elif len(key_filter) == 1:
 
1016
            # Technically, this path could also be handled by the first check
 
1017
            # in 'self._node_width' in length_filters. However, we can handle
 
1018
            # this case without spending any time building up the
 
1019
            # prefix_to_keys, etc state.
 
1020
 
 
1021
            # This is a bit ugly, but TIMEIT showed it to be by far the fastest
 
1022
            # 0.626us   list(key_filter)[0]
 
1023
            #       is a func() for list(), 2 mallocs, and a getitem
 
1024
            # 0.489us   [k for k in key_filter][0]
 
1025
            #       still has the mallocs, avoids the func() call
 
1026
            # 0.350us   iter(key_filter).next()
 
1027
            #       has a func() call, and mallocs an iterator
 
1028
            # 0.125us   for key in key_filter: pass
 
1029
            #       no func() overhead, might malloc an iterator
 
1030
            # 0.105us   for key in key_filter: break
 
1031
            #       no func() overhead, might malloc an iterator, probably
 
1032
            #       avoids checking an 'else' clause as part of the for
 
1033
            for key in key_filter:
 
1034
                break
 
1035
            search_prefix = self._search_prefix_filter(key)
 
1036
            if len(search_prefix) == self._node_width:
 
1037
                # This item will match exactly, so just do a dict lookup, and
 
1038
                # see what we can return
 
1039
                shortcut = True
 
1040
                try:
 
1041
                    node = self._items[search_prefix]
 
1042
                except KeyError:
 
1043
                    # A given key can only match 1 child node, if it isn't
 
1044
                    # there, then we can just return nothing
 
1045
                    return
 
1046
                if node.__class__ is tuple:
 
1047
                    keys[node] = (search_prefix, [key])
 
1048
                else:
 
1049
                    # This is loaded, and the only thing that can match,
 
1050
                    # return
 
1051
                    yield node, [key]
 
1052
                    return
 
1053
        if not shortcut:
 
1054
            # First, convert all keys into a list of search prefixes
 
1055
            # Aggregate common prefixes, and track the keys they come from
966
1056
            prefix_to_keys = {}
967
1057
            length_filters = {}
968
1058
            for key in key_filter:
969
 
                search_key = self._search_prefix_filter(key)
 
1059
                search_prefix = self._search_prefix_filter(key)
970
1060
                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)
 
1061
                                    len(search_prefix), set())
 
1062
                length_filter.add(search_prefix)
 
1063
                prefix_to_keys.setdefault(search_prefix, []).append(key)
 
1064
 
 
1065
            if (self._node_width in length_filters
 
1066
                and len(length_filters) == 1):
 
1067
                # all of the search prefixes match exactly _node_width. This
 
1068
                # means that everything is an exact match, and we can do a
 
1069
                # lookup into self._items, rather than iterating over the items
 
1070
                # dict.
 
1071
                search_prefixes = length_filters[self._node_width]
 
1072
                for search_prefix in search_prefixes:
 
1073
                    try:
 
1074
                        node = self._items[search_prefix]
 
1075
                    except KeyError:
 
1076
                        # We can ignore this one
 
1077
                        continue
 
1078
                    node_key_filter = prefix_to_keys[search_prefix]
 
1079
                    if node.__class__ is tuple:
 
1080
                        keys[node] = (search_prefix, node_key_filter)
984
1081
                    else:
985
1082
                        yield node, node_key_filter
 
1083
            else:
 
1084
                # The slow way. We walk every item in self._items, and check to
 
1085
                # see if there are any matches
 
1086
                length_filters = length_filters.items()
 
1087
                for prefix, node in self._items.iteritems():
 
1088
                    node_key_filter = []
 
1089
                    for length, length_filter in length_filters:
 
1090
                        sub_prefix = prefix[:length]
 
1091
                        if sub_prefix in length_filter:
 
1092
                            node_key_filter.extend(prefix_to_keys[sub_prefix])
 
1093
                    if node_key_filter: # this key matched something, yield it
 
1094
                        if node.__class__ is tuple:
 
1095
                            keys[node] = (prefix, node_key_filter)
 
1096
                        else:
 
1097
                            yield node, node_key_filter
986
1098
        if keys:
987
1099
            # Look in the page cache for some more bytes
988
1100
            found_keys = set()
1117
1229
        :return: An iterable of the keys inserted by this operation.
1118
1230
        """
1119
1231
        for node in self._items.itervalues():
1120
 
            if type(node) == tuple:
 
1232
            if type(node) is tuple:
1121
1233
                # Never deserialised.
1122
1234
                continue
1123
1235
            if node._key is not None:
1134
1246
        lines.append('%s\n' % (self._search_prefix,))
1135
1247
        prefix_len = len(self._search_prefix)
1136
1248
        for prefix, node in sorted(self._items.items()):
1137
 
            if type(node) == tuple:
 
1249
            if type(node) is tuple:
1138
1250
                key = node[0]
1139
1251
            else:
1140
1252
                key = node._key[0]
1179
1291
            raise AssertionError("unserialised nodes have no refs.")
1180
1292
        refs = []
1181
1293
        for value in self._items.itervalues():
1182
 
            if type(value) == tuple:
 
1294
            if type(value) is tuple:
1183
1295
                refs.append(value)
1184
1296
            else:
1185
1297
                refs.append(value.key())