]> cloud.milkyroute.net Git - dolphin.git/blobdiff - src/kitemviews/kfileitemmodel.cpp
Fix O(N^2) complexity issue in KItemListView::slotItemsRemoved()
[dolphin.git] / src / kitemviews / kfileitemmodel.cpp
index d30d9e5be054605e2abef0c19aa0f795e4d4ec1d..d174cf67fd5ab8e72fd86cf35e296c43a9afd024 100644 (file)
@@ -114,6 +114,7 @@ KFileItemModel::~KFileItemModel()
 {
     qDeleteAll(m_itemData);
     qDeleteAll(m_filteredItems.values());
+    qDeleteAll(m_pendingItemsToInsert);
 }
 
 void KFileItemModel::loadDirectory(const KUrl& url)
@@ -124,8 +125,10 @@ void KFileItemModel::loadDirectory(const KUrl& url)
 void KFileItemModel::refreshDirectory(const KUrl& url)
 {
     // Refresh all expanded directories first (Bug 295300)
-    foreach (const KUrl& expandedUrl, m_expandedDirs) {
-        m_dirLister->openUrl(expandedUrl, KDirLister::Reload);
+    QHashIterator<KUrl, KUrl> expandedDirs(m_expandedDirs);
+    while (expandedDirs.hasNext()) {
+        expandedDirs.next();
+        m_dirLister->openUrl(expandedDirs.value(), KDirLister::Reload);
     }
 
     m_dirLister->openUrl(url, KDirLister::Reload);
@@ -167,7 +170,7 @@ bool KFileItemModel::setData(int index, const QHash<QByteArray, QVariant>& value
     QHashIterator<QByteArray, QVariant> it(values);
     while (it.hasNext()) {
         it.next();
-        const QByteArray role = it.key();
+        const QByteArray role = sharedValue(it.key());
         const QVariant value = it.value();
 
         if (currentValues[role] != value) {
@@ -249,7 +252,7 @@ QMimeData* KFileItemModel::createMimeData(const QSet<int>& indexes) const
         const int index = it.next();
         const KFileItem item = fileItem(index);
         if (!item.isNull()) {
-            urls << item.url();
+            urls << item.targetUrl();
 
             bool isLocal;
             mostLocalUrls << item.mostLocalUrl(isLocal);
@@ -425,18 +428,19 @@ bool KFileItemModel::setExpanded(int index, bool expanded)
     }
 
     QHash<QByteArray, QVariant> values;
-    values.insert("isExpanded", expanded);
+    values.insert(sharedValue("isExpanded"), expanded);
     if (!setData(index, values)) {
         return false;
     }
 
     const KFileItem item = m_itemData.at(index)->item;
     const KUrl url = item.url();
+    const KUrl targetUrl = item.targetUrl();
     if (expanded) {
-        m_expandedDirs.insert(url);
+        m_expandedDirs.insert(targetUrl, url);
         m_dirLister->openUrl(url, KDirLister::Keep);
     } else {
-        m_expandedDirs.remove(url);
+        m_expandedDirs.remove(targetUrl);
         m_dirLister->stop(url);
 
         removeFilteredChildren(KFileItemList() << item);
@@ -478,7 +482,7 @@ int KFileItemModel::expandedParentsCount(int index) const
 
 QSet<KUrl> KFileItemModel::expandedDirectories() const
 {
-    return m_expandedDirs;
+    return m_expandedDirs.values().toSet();
 }
 
 void KFileItemModel::restoreExpandedDirectories(const QSet<KUrl>& urls)
@@ -644,11 +648,11 @@ void KFileItemModel::onSortRoleChanged(const QByteArray& current, const QByteArr
     Q_UNUSED(previous);
     m_sortRole = typeForRole(current);
 
-#ifdef KFILEITEMMODEL_DEBUG
     if (!m_requestRole[m_sortRole]) {
-        kWarning() << "The sort-role has been changed to a role that has not been received yet";
+        QSet<QByteArray> newRoles = m_roles;
+        newRoles << current;
+        setRoles(newRoles);
     }
-#endif
 
     resortAllItems();
 }
@@ -755,14 +759,15 @@ void KFileItemModel::slotItemsAdded(const KUrl& directoryUrl, const KFileItemLis
 {
     Q_ASSERT(!items.isEmpty());
 
-    KUrl parentUrl = directoryUrl;
-    parentUrl.adjustPath(KUrl::RemoveTrailingSlash);
+    KUrl parentUrl;
+    if (m_expandedDirs.contains(directoryUrl)) {
+        parentUrl = m_expandedDirs.value(directoryUrl);
+    } else {
+        parentUrl = directoryUrl;
+        parentUrl.adjustPath(KUrl::RemoveTrailingSlash);
+    }
 
     if (m_requestRole[ExpandedParentsCountRole]) {
-        // To be able to compare whether the new items may be inserted as children
-        // of a parent item the pending items must be added to the model first.
-        dispatchPendingItemsToInsert();
-
         KFileItem item = items.first();
 
         // If the expanding of items is enabled, the call
@@ -776,6 +781,12 @@ void KFileItemModel::slotItemsAdded(const KUrl& directoryUrl, const KFileItemLis
             return;
         }
 
+        if (directoryUrl != directory()) {
+            // To be able to compare whether the new items may be inserted as children
+            // of a parent item the pending items must be added to the model first.
+            dispatchPendingItemsToInsert();
+        }
+
         // KDirLister keeps the children of items that got expanded once even if
         // they got collapsed again with KFileItemModel::setExpanded(false). So it must be
         // checked whether the parent for new items is still expanded.
@@ -846,12 +857,12 @@ void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >&
     kDebug() << "Refreshing" << items.count() << "items";
 #endif
 
-    m_groups.clear();
-
     // Get the indexes of all items that have been refreshed
     QList<int> indexes;
     indexes.reserve(items.count());
 
+    QSet<QByteArray> changedRoles;
+
     QListIterator<QPair<KFileItem, KFileItem> > it(items);
     while (it.hasNext()) {
         const QPair<KFileItem, KFileItem>& itemPair = it.next();
@@ -864,9 +875,14 @@ void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >&
             // Keep old values as long as possible if they could not retrieved synchronously yet.
             // The update of the values will be done asynchronously by KFileItemModelRolesUpdater.
             QHashIterator<QByteArray, QVariant> it(retrieveData(newItem, m_itemData.at(index)->parent));
+            QHash<QByteArray, QVariant>& values = m_itemData[index]->values;
             while (it.hasNext()) {
                 it.next();
-                m_itemData[index]->values.insert(it.key(), it.value());
+                const QByteArray& role = it.key();
+                if (values.value(role) != it.value()) {
+                    values.insert(role, it.value());
+                    changedRoles.insert(role);
+                }
             }
 
             m_items.remove(oldItem.url());
@@ -907,9 +923,11 @@ void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >&
         itemRangeList.append(KItemRange(rangeIndex, rangeCount));
     }
 
-    emit itemsChanged(itemRangeList, m_roles);
+    emit itemsChanged(itemRangeList, changedRoles);
 
-    resortAllItems();
+    if (changedRoles.contains(sortRole())) {
+        resortAllItems();
+    }
 }
 
 void KFileItemModel::slotClear()
@@ -924,6 +942,8 @@ void KFileItemModel::slotClear()
 
     m_maximumUpdateIntervalTimer->stop();
     m_resortAllItemsTimer->stop();
+
+    qDeleteAll(m_pendingItemsToInsert);
     m_pendingItemsToInsert.clear();
 
     const int removedCount = m_itemData.count();
@@ -1252,27 +1272,27 @@ QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item,
     // KFileItem::iconName() can be very expensive if the MIME-type is unknown
     // and hence will be retrieved asynchronously by KFileItemModelRolesUpdater.
     QHash<QByteArray, QVariant> data;
-    data.insert("url", item.url());
+    data.insert(sharedValue("url"), item.url());
 
     const bool isDir = item.isDir();
     if (m_requestRole[IsDirRole]) {
-        data.insert("isDir", isDir);
+        data.insert(sharedValue("isDir"), isDir);
     }
 
     if (m_requestRole[IsLinkRole]) {
         const bool isLink = item.isLink();
-        data.insert("isLink", isLink);
+        data.insert(sharedValue("isLink"), isLink);
     }
 
     if (m_requestRole[NameRole]) {
-        data.insert("text", item.text());
+        data.insert(sharedValue("text"), item.text());
     }
 
     if (m_requestRole[SizeRole]) {
         if (isDir) {
-            data.insert("size", QVariant());
+            data.insert(sharedValue("size"), QVariant());
         } else {
-            data.insert("size", item.size());
+            data.insert(sharedValue("size"), item.size());
         }
     }
 
@@ -1281,19 +1301,19 @@ QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item,
         // having several thousands of items. Instead the formatting of the
         // date-time will be done on-demand by the view when the date will be shown.
         const KDateTime dateTime = item.time(KFileItem::ModificationTime);
-        data.insert("date", dateTime.dateTime());
+        data.insert(sharedValue("date"), dateTime.dateTime());
     }
 
     if (m_requestRole[PermissionsRole]) {
-        data.insert("permissions", item.permissionsString());
+        data.insert(sharedValue("permissions"), item.permissionsString());
     }
 
     if (m_requestRole[OwnerRole]) {
-        data.insert("owner", item.user());
+        data.insert(sharedValue("owner"), item.user());
     }
 
     if (m_requestRole[GroupRole]) {
-        data.insert("group", item.group());
+        data.insert(sharedValue("group"), item.group());
     }
 
     if (m_requestRole[DestinationRole]) {
@@ -1301,7 +1321,7 @@ QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item,
         if (destination.isEmpty()) {
             destination = QLatin1String("-");
         }
-        data.insert("destination", destination);
+        data.insert(sharedValue("destination"), destination);
     }
 
     if (m_requestRole[PathRole]) {
@@ -1324,11 +1344,11 @@ QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item,
 
         const int index = path.lastIndexOf(item.text());
         path = path.mid(0, index - 1);
-        data.insert("path", path);
+        data.insert(sharedValue("path"), path);
     }
 
     if (m_requestRole[IsExpandableRole]) {
-        data.insert("isExpandable", item.isDir() && item.url() == item.targetUrl());
+        data.insert(sharedValue("isExpandable"), item.isDir());
     }
 
     if (m_requestRole[ExpandedParentsCountRole]) {
@@ -1337,14 +1357,14 @@ QHash<QByteArray, QVariant> KFileItemModel::retrieveData(const KFileItem& item,
             level = parent->values["expandedParentsCount"].toInt() + 1;
         }
 
-        data.insert("expandedParentsCount", level);
+        data.insert(sharedValue("expandedParentsCount"), level);
     }
 
     if (item.isMimeTypeKnown()) {
-        data.insert("iconName", item.iconName());
+        data.insert(sharedValue("iconName"), item.iconName());
 
         if (m_requestRole[TypeRole]) {
-            data.insert("type", item.mimeComment());
+            data.insert(sharedValue("type"), item.mimeComment());
         }
     }
 
@@ -1961,6 +1981,19 @@ void KFileItemModel::determineMimeTypes(const KFileItemList& items, int timeout)
     }
 }
 
+QByteArray KFileItemModel::sharedValue(const QByteArray& value)
+{
+    static QSet<QByteArray> pool;
+    const QSet<QByteArray>::const_iterator it = pool.constFind(value);
+
+    if (it != pool.constEnd()) {
+        return *it;
+    } else {
+        pool.insert(value);
+        return value;
+    }
+}
+
 bool KFileItemModel::isConsistent() const
 {
     if (m_items.count() != m_itemData.count()) {