KFileItemModel::insertItems(QList<ItemData*>& items): guarantee O(N) run time complexity
Review Request #110355 - Created May 8, 2013 and submitted
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.