m_urlsToExpand()
{
m_dirLister = new KFileItemModelDirLister(this);
- m_dirLister->setAutoUpdate(true);
m_dirLister->setDelayedMimeTypes(true);
const QWidget* parentWidget = qobject_cast<QWidget*>(parent);
m_items.clear();
// Resort the items
- KFileItemModelSortAlgorithm::sort(this, m_itemData.begin(), m_itemData.end());
+ sort(m_itemData.begin(), m_itemData.end());
for (int i = 0; i < itemCount; ++i) {
m_items.insert(m_itemData.at(i)->item.url(), i);
}
m_groups.clear();
QList<ItemData*> sortedItems = createItemDataList(items);
- KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
+ sort(sortedItems.begin(), sortedItems.end());
#ifdef KFILEITEMMODEL_DEBUG
kDebug() << "[TIME] Sorting:" << timer.elapsed();
#endif
}
+static KItemRangeList sortedIndexesToKItemRangeList(const QList<int> sortedNumbers)
+{
+ if (sortedNumbers.empty()) {
+ return KItemRangeList();
+ }
+
+ KItemRangeList result;
+
+ QList<int>::const_iterator it = sortedNumbers.begin();
+ int index = *it;
+ int count = 1;
+
+ ++it;
+
+ QList<int>::const_iterator end = sortedNumbers.end();
+ while (it != end) {
+ if (*it == index + count) {
+ ++count;
+ } else {
+ result << KItemRange(index, count);
+ index = *it;
+ count = 1;
+ }
+ ++it;
+ }
+
+ result << KItemRange(index, count);
+ return result;
+}
+
void KFileItemModel::removeItems(const KFileItemList& items)
{
if (items.isEmpty()) {
m_groups.clear();
- QList<ItemData*> sortedItems;
- sortedItems.reserve(items.count());
- foreach (const KFileItem& item, items) {
- const int index = m_items.value(item.url(), -1);
- if (index >= 0) {
- sortedItems.append(m_itemData.at(index));
- }
- }
- KFileItemModelSortAlgorithm::sort(this, sortedItems.begin(), sortedItems.end());
-
+ // Step 1: Determine the indexes of the removed items, remove them from
+ // the hash m_items, and free the ItemData.
QList<int> indexesToRemove;
indexesToRemove.reserve(items.count());
+ foreach (const KFileItem& item, items) {
+ const KUrl url = item.url();
+ const int index = m_items.value(url, -1);
+ if (index >= 0) {
+ indexesToRemove.append(index);
- // Calculate the item ranges that will get deleted
- KItemRangeList itemRanges;
- int removedAtIndex = -1;
- int removedCount = 0;
- int targetIndex = 0;
- foreach (const ItemData* itemData, sortedItems) {
- const KFileItem& itemToRemove = itemData->item;
+ // Prevent repeated expensive rehashing by using QHash::erase(),
+ // rather than QHash::remove().
+ QHash<KUrl, int>::iterator it = m_items.find(url);
+ m_items.erase(it);
- const int previousTargetIndex = targetIndex;
- while (targetIndex < m_itemData.count()) {
- if (m_itemData.at(targetIndex)->item.url() == itemToRemove.url()) {
- break;
- }
- ++targetIndex;
- }
- if (targetIndex >= m_itemData.count()) {
+ ItemData* data = m_itemData.at(index);
+ delete data;
+ m_itemData[index] = 0;
+ } else {
kWarning() << "Item that should be deleted has not been found!";
- return;
- }
-
- if (targetIndex - previousTargetIndex > 0 && removedAtIndex >= 0) {
- itemRanges << KItemRange(removedAtIndex, removedCount);
- removedAtIndex = targetIndex;
- removedCount = 0;
- }
-
- indexesToRemove.append(targetIndex);
- if (removedAtIndex < 0) {
- removedAtIndex = targetIndex;
}
- ++removedCount;
- ++targetIndex;
}
- // Delete the items
- for (int i = indexesToRemove.count() - 1; i >= 0; --i) {
- const int indexToRemove = indexesToRemove.at(i);
- ItemData* data = m_itemData.at(indexToRemove);
+ std::sort(indexesToRemove.begin(), indexesToRemove.end());
- m_items.remove(data->item.url());
+ // Step 2: Remove the ItemData pointers from the list m_itemData.
+ const KItemRangeList itemRanges = sortedIndexesToKItemRangeList(indexesToRemove);
+ int target = itemRanges.at(0).index;
+ int source = itemRanges.at(0).index + itemRanges.at(0).count;
+ int nextRange = 1;
- delete data;
- m_itemData.removeAt(indexToRemove);
+ const int oldItemDataCount = m_itemData.count();
+ while (source < oldItemDataCount) {
+ if (nextRange < itemRanges.count() - 1 && source == itemRanges.at(nextRange).index) {
+ // Skip the items in the next removed range.
+ source += itemRanges.at(nextRange).count;
+ ++nextRange;
+ }
+ m_itemData[target] = m_itemData[source];
+ ++target;
+ ++source;
}
- // The indexes of all m_items must be adjusted, not only the index
- // of the removed items
- const int itemDataCount = m_itemData.count();
- for (int i = 0; i < itemDataCount; ++i) {
+ m_itemData.erase(m_itemData.end() - indexesToRemove.count(), m_itemData.end());
+
+ // Step 3: Adjust indexes in the hash m_items. Note that all indexes
+ // might have been changed by the removal of the items.
+ const int newItemDataCount = m_itemData.count();
+ for (int i = 0; i < newItemDataCount; ++i) {
m_items.insert(m_itemData.at(i)->item.url(), i);
}
m_expandedParentsCountRoot = UninitializedExpandedParentsCountRoot;
}
- itemRanges << KItemRange(removedAtIndex, removedCount);
emit itemsRemoved(itemRanges);
}
return (sortOrder() == Qt::AscendingOrder) ? result < 0 : result > 0;
}
+/**
+ * Helper class for KFileItemModel::sort().
+ */
+class KFileItemModelLessThan
+{
+public:
+ KFileItemModelLessThan(const KFileItemModel* model) :
+ m_model(model)
+ {
+ }
+
+ bool operator()(const KFileItemModel::ItemData* a, const KFileItemModel::ItemData* b) const
+ {
+ return m_model->lessThan(a, b);
+ }
+
+private:
+ const KFileItemModel* m_model;
+};
+
+void KFileItemModel::sort(QList<KFileItemModel::ItemData*>::iterator begin,
+ QList<KFileItemModel::ItemData*>::iterator end) const
+{
+ KFileItemModelLessThan lessThan(this);
+
+ if (m_sortRole == NameRole) {
+ // Sorting by name can be expensive, in particular if natural sorting is
+ // enabled. Use all CPU cores to speed up the sorting process.
+ static const int numberOfThreads = QThread::idealThreadCount();
+ parallelMergeSort(begin, end, lessThan, numberOfThreads);
+ } else {
+ // Sorting by other roles is quite fast. Use only one thread to prevent
+ // problems caused by non-reentrant comparison functions, see
+ // https://bugs.kde.org/show_bug.cgi?id=312679
+ mergeSort(begin, end, lessThan);
+ }
+}
+
int KFileItemModel::sortRoleCompare(const ItemData* a, const ItemData* b) const
{
const KFileItem& itemA = a->item;
if (index > maxIndex) {
index = maxIndex;
}
- while ((pathA.at(index) != QLatin1Char('/') || pathB.at(index) != QLatin1Char('/')) && index > 0) {
+ while (index > 0 && (pathA.at(index) != QLatin1Char('/') || pathB.at(index) != QLatin1Char('/'))) {
--index;
}
}
}
+bool KFileItemModel::isConsistent() const
+{
+ // Check that m_items and m_itemData are consistent, and that the items are sorted.
+ if (m_items.count() != m_itemData.count()) {
+ return false;
+ }
+
+ for (int i = 0; i < count(); ++i) {
+ const KFileItem item = fileItem(i);
+ if (item.isNull()) {
+ qWarning() << "Item" << i << "is null";
+ return false;
+ }
+
+ const int itemIndex = index(item);
+ if (itemIndex != i) {
+ qWarning() << "Item" << i << "has a wrong index:" << itemIndex;
+ return false;
+ }
+
+ if (i > 0 && !lessThan(m_itemData.at(i - 1), m_itemData.at(i))) {
+ qWarning() << "The order of items" << i - 1 << "and" << i << "is wrong:"
+ << fileItem(i - 1) << fileItem(i);
+ return false;
+ }
+ }
+
+ return true;
+}
+
#include "kfileitemmodel.moc"
projects / dolphin.git / blobdiff