summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorGabriel de Dietrich <gabriel.dietrich-de@nokia.com>2010-03-10 15:53:06 (GMT)
committerGabriel de Dietrich <gabriel.dietrich-de@nokia.com>2010-03-10 16:54:47 (GMT)
commit7baaea978200c82fdf65e3934cfa373edeca6524 (patch)
treefb6d5b9c8a550f27e8ef03bb2b5768f89d560d1d /src
parent1436c4f2e41100b45eed58edc5fc290fa94c976b (diff)
downloadQt-7baaea978200c82fdf65e3934cfa373edeca6524.zip
Qt-7baaea978200c82fdf65e3934cfa373edeca6524.tar.gz
Qt-7baaea978200c82fdf65e3934cfa373edeca6524.tar.bz2
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
Diffstat (limited to 'src')
-rw-r--r--src/gui/itemviews/qtreeview.cpp57
-rw-r--r--src/gui/itemviews/qtreeview_p.h9
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;