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/#review32978
-----------------------------------------------------------


This review has been submitted with commit fba053e9844964b9787294efa8a85f0a7aafb91a by Frank Reininghaus to branch master.

- Commit Hook


On May 8, 2013, 6:27 a.m., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/110355/
> -----------------------------------------------------------
> 
> (Updated May 8, 2013, 6:27 a.m.)
> 
> 
> 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/04ec2683/attachment.htm>