Review Request 110355: KFileItemModel::insertItems(QList<ItemData*>& items): guarantee O(N) run time complexity

[Commit Hook]

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/110355/
-----------------------------------------------------------

(Updated May 22, 2013, 4:31 p.m.)


Status
------

This change has been marked as submitted.


Review request for Dolphin.


Description
-------

This is a follow-up to https://git.reviewboard.kde.org/r/108540/.

There are still a few situations where KFileItemModel::insertItems(QList<ItemData*>& items) has quadratic complexity, such as when many items are inserted at the beginning of the list. This patch fixes that by creating the merged ItemData* list in reverse order, such that every item is moved only once. The solution is a bit simpler than the one I proposed in the first version of the earlier review request: Creation of the list of inserted ranges and the actual merging of the ItemData* lists are done simultaneously. The only little drawback is that the list of item ranges has to be reversed in the end.

Some more modifications:

(a) Renamed 'items' to 'newItems' to improve readability.

(b) Added an optimization for the case that the model is still empty. This is probably the most common case (happens when entering a directory).

(c) When updating the hash m_items, only update those indices that have really changed.


Diffs
-----

  dolphin/src/kitemviews/kfileitemmodel.cpp 9be891a 

Diff: http://git.reviewboard.kde.org/r/110355/diff/


Testing
-------

Unit tests still work, benchmark does not show any situations with quadratic runtime behaviour any more.


Thanks,

Frank Reininghaus

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.kde.org/mailman/private/kfm-devel/attachments/20130522/4dbf877f/attachment.htm>