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

Review Request #110355 - Created May 8, 2013 and submitted

Frank Reininghaus
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.
Unit tests still work, benchmark does not show any situations with quadratic runtime behaviour any more.
Commit Hook
Frank Reininghaus
Review request changed

Status: Closed (submitted)