← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/chk_map.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-06-18 20:25:52 UTC
  • mfrom: (4413.5.15 1.16-chk-direct)
  • Revision ID: pqm@pqm.ubuntu.com-20090618202552-xyl6tcvbxtm8bupf
(jam) Improve initial commit performance by creating a CHKMap in bulk,
        rather than via O(tree) map() calls.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/chk_map.py
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.
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):