From 7baaea978200c82fdf65e3934cfa373edeca6524 Mon Sep 17 00:00:00 2001 From: Gabriel de Dietrich Date: Wed, 10 Mar 2010 16:53:06 +0100 Subject: Slow QTreeView::layout() with many (> 10000) children When updating the QTreeViewItem::total field in layout(), we used to call QTreeViewPrivate::viewIndex() to get the parent item, which is O(n). We have now introduced 'parentItem' in QTreeViewItem wich makes this O(1), with a small penality when inserting and removing elements in QTreeViewPrivate::viewItems. The QTreeViewPrivate::checkViewItems() is left inside the code for further debugging. Reviewed-by: Olivier Task-number: QTBUG-8885 --- src/gui/itemviews/qtreeview.cpp | 57 +++++++++++++++++++++++++++++++---------- src/gui/itemviews/qtreeview_p.h | 9 ++++++- 2 files changed, 51 insertions(+), 15 deletions(-) diff --git a/src/gui/itemviews/qtreeview.cpp b/src/gui/itemviews/qtreeview.cpp index 78184a9..2d9f9c6 100644 --- a/src/gui/itemviews/qtreeview.cpp +++ b/src/gui/itemviews/qtreeview.cpp @@ -2480,6 +2480,7 @@ void QTreeView::rowsInserted(const QModelIndex &parent, int start, int end) for (int i = 0; i < delta; ++i) { QTreeViewItem &item = insertedItems[i]; item.index = d->model->index(i + start, 0, parent); + item.parentItem = parentItem; item.level = childLevel; item.hasChildren = d->hasVisibleChildren(item.index); item.hasMoreSiblings = !((i == delta - 1) && (parentRowCount == end +1)); @@ -2518,7 +2519,7 @@ void QTreeView::rowsInserted(const QModelIndex &parent, int start, int end) } } - d->viewItems.insert(insertPos, delta, insertedItems.at(0)); + d->insertViewItems(insertPos, delta, insertedItems.at(0)); if (delta > 1) { qCopy(insertedItems.begin() + 1, insertedItems.end(), d->viewItems.begin() + insertPos + 1); @@ -2952,6 +2953,37 @@ void QTreeViewPrivate::expand(int item, bool emitSignal) } } +void QTreeViewPrivate::insertViewItems(int pos, int count, const QTreeViewItem &viewItem) +{ + viewItems.insert(pos, count, viewItem); + for (int i = pos + count; i < viewItems.count(); i++) + if (viewItems[i].parentItem >= pos) + viewItems[i].parentItem += count; +} + +void QTreeViewPrivate::removeViewItems(int pos, int count) +{ + viewItems.remove(pos, count); + for (int i = pos; i < viewItems.count(); i++) + if (viewItems[i].parentItem >= pos) + viewItems[i].parentItem -= count; +} + +#if 0 +bool QTreeViewPrivate::checkViewItems() const +{ + for (int i = 0; i < viewItems.count(); ++i) { + const QTreeViewItem &vi = viewItems.at(i); + if (vi.parentItem == -1) { + Q_ASSERT(!vi.index.parent().isValid() || vi.index.parent() == root); + } else { + Q_ASSERT(vi.index.parent() == viewItems.at(vi.parentItem).index); + } + } + return true; +} +#endif + void QTreeViewPrivate::collapse(int item, bool emitSignal) { Q_Q(QTreeView); @@ -2980,14 +3012,11 @@ void QTreeViewPrivate::collapse(int item, bool emitSignal) expandedIndexes.erase(it); viewItems[item].expanded = false; int index = item; - QModelIndex parent = modelIndex; - while (parent.isValid() && parent != root) { - Q_ASSERT(index > -1); + while (index > -1) { viewItems[index].total -= total; - parent = parent.parent(); - index = viewIndex(parent); + index = viewItems[index].parentItem; } - viewItems.remove(item + 1, total); // collapse + removeViewItems(item + 1, total); // collapse q->setState(oldState); if (emitSignal) { @@ -3152,7 +3181,7 @@ void QTreeViewPrivate::layout(int i) } viewItems.resize(count); } else if (viewItems[i].total != (uint)count) { - viewItems.insert(i + 1, count, QTreeViewItem()); // expand + insertViewItems(i + 1, count, QTreeViewItem()); // expand } else { expanding = false; } @@ -3174,6 +3203,7 @@ void QTreeViewPrivate::layout(int i) item->hasMoreSiblings = true; item = &viewItems[last]; item->index = current; + item->parentItem = i; item->level = level; item->height = 0; item->spanning = q->isFirstColumnSpanned(current.row(), parent); @@ -3195,16 +3225,14 @@ void QTreeViewPrivate::layout(int i) // remove hidden items if (hidden > 0) - viewItems.remove(last + 1, hidden); // collapse + removeViewItems(last + 1, hidden); // collapse if (!expanding) return; // nothing changed - while (parent != root) { - Q_ASSERT(i > -1); + while (i > -1) { viewItems[i].total += count - hidden; - parent = parent.parent(); - i = viewIndex(parent); + i = viewItems[i].parentItem; } } @@ -3757,7 +3785,7 @@ void QTreeViewPrivate::rowsRemoved(const QModelIndex &parent, item += count; } else if (modelIndex.row() <= end) { // removed - viewItems.remove(item, count); + removeViewItems(item, count); removedCount += count; lastChildItem -= count; } else { @@ -3765,6 +3793,7 @@ void QTreeViewPrivate::rowsRemoved(const QModelIndex &parent, // moved; update the model index viewItems[item].index = model->index( modelIndex.row() - delta, modelIndex.column(), parent); +// viewItems[item].parentItem = parentItem; } item += count; } diff --git a/src/gui/itemviews/qtreeview_p.h b/src/gui/itemviews/qtreeview_p.h index 589a224..7893e04 100644 --- a/src/gui/itemviews/qtreeview_p.h +++ b/src/gui/itemviews/qtreeview_p.h @@ -62,9 +62,10 @@ QT_BEGIN_NAMESPACE struct QTreeViewItem { - QTreeViewItem() : expanded(false), spanning(false), hasChildren(false), + QTreeViewItem() : parentItem(-1), expanded(false), spanning(false), hasChildren(false), hasMoreSiblings(false), total(0), level(0), height(0) {} QModelIndex index; // we remove items whenever the indexes are invalidated + int parentItem; // parent item index in viewItems uint expanded : 1; uint spanning : 1; uint hasChildren : 1; // if the item has visible children (even if collapsed) @@ -136,6 +137,12 @@ public: int viewIndex(const QModelIndex &index) const; QModelIndex modelIndex(int i, int column = 0) const; + void insertViewItems(int pos, int count, const QTreeViewItem &viewItem); + void removeViewItems(int pos, int count); +#if 0 + bool checkViewItems() const; +#endif + int firstVisibleItem(int *offset = 0) const; int columnAt(int x) const; bool hasVisibleChildren( const QModelIndex& parent) const; -- cgit v0.12