From fcbcd07b9d29a147b6a03f2c4c8d15648aacbcae Mon Sep 17 00:00:00 2001 From: Kim Motoyoshi Kalland Date: Tue, 31 May 2011 18:32:46 +0200 Subject: [PATCH] Use linked list instead of QList for node children. --- src/declarative/items/qsgcanvas.cpp | 15 +-- src/declarative/items/qsgitem.cpp | 4 +- src/declarative/items/qsgitem_p.h | 2 +- src/declarative/items/qsgshadereffectsource.cpp | 4 +- src/declarative/items/qsgtextnode.cpp | 10 +- .../scenegraph/coreapi/qsgdefaultrenderer.cpp | 23 ++-- src/declarative/scenegraph/coreapi/qsgnode.cpp | 117 +++++++++++++++----- src/declarative/scenegraph/coreapi/qsgnode.h | 13 ++- .../scenegraph/coreapi/qsgnodeupdater.cpp | 5 +- src/declarative/scenegraph/coreapi/qsgrenderer.cpp | 8 +- 10 files changed, 134 insertions(+), 67 deletions(-) diff --git a/src/declarative/items/qsgcanvas.cpp b/src/declarative/items/qsgcanvas.cpp index 28a65d0..f12f936 100644 --- a/src/declarative/items/qsgcanvas.cpp +++ b/src/declarative/items/qsgcanvas.cpp @@ -1655,7 +1655,6 @@ void QSGCanvasPrivate::updateDirtyNode(QSGItem *item) QList orderedChildren = itemPriv->paintOrderChildItems(); int ii = 0; - itemPriv->paintNodeIndex = 0; for (; ii < orderedChildren.count() && orderedChildren.at(ii)->z() < 0; ++ii) { QSGItemPrivate *childPrivate = QSGItemPrivate::get(orderedChildren.at(ii)); if (!childPrivate->explicitVisible && !childPrivate->effectRefCount) @@ -1664,8 +1663,8 @@ void QSGCanvasPrivate::updateDirtyNode(QSGItem *item) childPrivate->itemNode()->parent()->removeChildNode(childPrivate->itemNode()); itemPriv->childContainerNode()->appendChildNode(childPrivate->itemNode()); - itemPriv->paintNodeIndex++; } + itemPriv->beforePaintNode = itemPriv->groupNode ? itemPriv->groupNode->lastChild() : 0; if (itemPriv->paintNode) itemPriv->childContainerNode()->appendChildNode(itemPriv->paintNode); @@ -1721,10 +1720,10 @@ void QSGCanvasPrivate::updateDirtyNode(QSGItem *item) itemPriv->paintNode->parent() == itemPriv->childContainerNode()); if (itemPriv->paintNode && itemPriv->paintNode->parent() == 0) { - if (itemPriv->childContainerNode()->childCount() == itemPriv->paintNodeIndex) - itemPriv->childContainerNode()->appendChildNode(itemPriv->paintNode); - else - itemPriv->childContainerNode()->insertChildNodeBefore(itemPriv->paintNode, itemPriv->childContainerNode()->childAtIndex(itemPriv->paintNodeIndex)); + if (itemPriv->beforePaintNode) + itemPriv->childContainerNode()->insertChildNodeAfter(itemPriv->paintNode, itemPriv->beforePaintNode); + else + itemPriv->childContainerNode()->prependChildNode(itemPriv->paintNode); } } else if (itemPriv->paintNode) { delete itemPriv->paintNode; @@ -1760,8 +1759,8 @@ void QSGCanvasPrivate::updateDirtyNode(QSGItem *item) Q_ASSERT(parent == itemPriv->groupNode || parent->childCount() == 1); Q_ASSERT(child->parent() == parent); bool containsChild = false; - for (int i = 0; i < parent->childCount(); ++i) - containsChild |= (parent->childAtIndex(i) == child); + for (QSGNode *n = parent->firstChild(); n; n = n->nextSibling()) + containsChild |= (n == child); Q_ASSERT(containsChild); } ip = ic; diff --git a/src/declarative/items/qsgitem.cpp b/src/declarative/items/qsgitem.cpp index 2bba4da..3b07503 100644 --- a/src/declarative/items/qsgitem.cpp +++ b/src/declarative/items/qsgitem.cpp @@ -1179,7 +1179,7 @@ void QSGItemPrivate::initCanvas(InitializationState *state, QSGCanvas *c) rootNode = 0; groupNode = 0; paintNode = 0; - paintNodeIndex = 0; + beforePaintNode = 0; InitializationState _dummy; InitializationState *childState = state; @@ -1284,7 +1284,7 @@ QSGItemPrivate::QSGItemPrivate() dirtyAttributes(0), nextDirtyItem(0), prevDirtyItem(0), itemNodeInstance(0), opacityNode(0), clipNode(0), rootNode(0), groupNode(0), paintNode(0) - , paintNodeIndex(0), effectRefCount(0), hideRefCount(0) + , beforePaintNode(0), effectRefCount(0), hideRefCount(0) { } diff --git a/src/declarative/items/qsgitem_p.h b/src/declarative/items/qsgitem_p.h index 0f4a321..c955c44 100644 --- a/src/declarative/items/qsgitem_p.h +++ b/src/declarative/items/qsgitem_p.h @@ -387,7 +387,7 @@ public: QSGRootNode *rootNode; QSGNode *groupNode; QSGNode *paintNode; - int paintNodeIndex; + QSGNode *beforePaintNode; virtual QSGTransformNode *createTransformNode(); diff --git a/src/declarative/items/qsgshadereffectsource.cpp b/src/declarative/items/qsgshadereffectsource.cpp index 24e2be3..c4c0986 100644 --- a/src/declarative/items/qsgshadereffectsource.cpp +++ b/src/declarative/items/qsgshadereffectsource.cpp @@ -214,8 +214,8 @@ void QSGShaderEffectTexture::grab() return; } QSGNode *root = m_item; - while (root->childCount() && root->type() != QSGNode::RootNodeType) - root = root->childAtIndex(0); + while (root->firstChild() && root->type() != QSGNode::RootNodeType) + root = root->firstChild(); if (root->type() != QSGNode::RootNodeType) return; diff --git a/src/declarative/items/qsgtextnode.cpp b/src/declarative/items/qsgtextnode.cpp index 33325a1..6105137 100644 --- a/src/declarative/items/qsgtextnode.cpp +++ b/src/declarative/items/qsgtextnode.cpp @@ -81,8 +81,7 @@ void QSGTextNode::setColor(const QColor &color) if (m_usePixmapCache) { setUpdateFlag(UpdateNodes); } else { - for (int i=0; inextSibling()) { if (childNode->subType() == GlyphNodeSubType) { QSGGlyphNode *glyphNode = static_cast(childNode); if (glyphNode->color() == m_color) @@ -103,8 +102,7 @@ void QSGTextNode::setStyleColor(const QColor &styleColor) if (m_usePixmapCache) { setUpdateFlag(UpdateNodes); } else { - for (int i=0; inextSibling()) { if (childNode->subType() == GlyphNodeSubType) { QSGGlyphNode *glyphNode = static_cast(childNode); if (glyphNode->color() == m_styleColor) @@ -376,8 +374,8 @@ void QSGTextNode::addTextBlock(const QPointF &position, QTextDocument *textDocum void QSGTextNode::deleteContent() { - while (childCount() > 0) - delete childAtIndex(0); + while (firstChild() > 0) + delete firstChild(); } #if 0 diff --git a/src/declarative/scenegraph/coreapi/qsgdefaultrenderer.cpp b/src/declarative/scenegraph/coreapi/qsgdefaultrenderer.cpp index 8e8f811..1e6b691 100644 --- a/src/declarative/scenegraph/coreapi/qsgdefaultrenderer.cpp +++ b/src/declarative/scenegraph/coreapi/qsgdefaultrenderer.cpp @@ -371,8 +371,7 @@ void QMLRenderer::buildLists(QSGNode *node) } } - int count = node->childCount(); - if (!count) + if (!node->firstChild()) return; #ifdef FORCE_NO_REORDER @@ -381,14 +380,16 @@ void QMLRenderer::buildLists(QSGNode *node) static bool reorder = !qApp->arguments().contains(QLatin1String("--no-reorder")); #endif - if (reorder && count > 1 && (node->flags() & QSGNode::ChildrenDoNotOverlap)) { - QVarLengthArray beginIndices(count); - QVarLengthArray endIndices(count); + if (reorder && node->firstChild() != node->lastChild() && (node->flags() & QSGNode::ChildrenDoNotOverlap)) { + QVarLengthArray beginIndices; + QVarLengthArray endIndices; int baseCount = m_transparentNodes.size(); - for (int i = 0; i < count; ++i) { - beginIndices[i] = m_transparentNodes.size(); - buildLists(node->childAtIndex(i)); - endIndices[i] = m_transparentNodes.size(); + int count = 0; + for (QSGNode *c = node->firstChild(); c; c = c->nextSibling()) { + beginIndices.append(m_transparentNodes.size()); + buildLists(c); + endIndices.append(m_transparentNodes.size()); + ++count; } int childNodeCount = m_transparentNodes.size() - baseCount; @@ -414,8 +415,8 @@ void QMLRenderer::buildLists(QSGNode *node) qMemCopy(&m_transparentNodes.at(baseCount), &m_tempNodes.at(0), m_tempNodes.size() * sizeof(QSGGeometryNode *)); } } else { - for (int i = 0; i < count; ++i) - buildLists(node->childAtIndex(i)); + for (QSGNode *c = node->firstChild(); c; c = c->nextSibling()) + buildLists(c); } } diff --git a/src/declarative/scenegraph/coreapi/qsgnode.cpp b/src/declarative/scenegraph/coreapi/qsgnode.cpp index 66ce836..fa720a3 100644 --- a/src/declarative/scenegraph/coreapi/qsgnode.cpp +++ b/src/declarative/scenegraph/coreapi/qsgnode.cpp @@ -87,6 +87,10 @@ QSGNode::QSGNode() , m_subtreeGeometryCount(0) , m_nodeFlags(OwnedByParent) , m_flags(0) + , m_firstChild(0) + , m_lastChild(0) + , m_nextSibling(0) + , m_previousSibling(0) { init(); } @@ -97,6 +101,10 @@ QSGNode::QSGNode(NodeType type) , m_subtreeGeometryCount(type == GeometryNodeType ? 1 : 0) , m_nodeFlags(OwnedByParent) , m_flags(0) + , m_firstChild(0) + , m_lastChild(0) + , m_nextSibling(0) + , m_previousSibling(0) { init(); } @@ -173,14 +181,15 @@ void QSGNode::destroy() m_parent->removeChildNode(this); Q_ASSERT(m_parent == 0); } - for (int ii = m_children.count() - 1; ii >= 0; --ii) { - QSGNode *child = m_children.at(ii); + while (m_firstChild) { + QSGNode *child = m_firstChild; removeChildNode(child); Q_ASSERT(child->m_parent == 0); if (child->flags() & OwnedByParent) delete child; } - Q_ASSERT(m_children.isEmpty()); + + Q_ASSERT(m_firstChild == 0 && m_lastChild == 0); } @@ -193,7 +202,7 @@ void QSGNode::destroy() void QSGNode::prependChildNode(QSGNode *node) { - Q_ASSERT_X(!m_children.contains(node), "QSGNode::prependChildNode", "QSGNode is already a child!"); + //Q_ASSERT_X(!m_children.contains(node), "QSGNode::prependChildNode", "QSGNode is already a child!"); Q_ASSERT_X(!node->m_parent, "QSGNode::prependChildNode", "QSGNode already has a parent"); #ifndef QT_NO_DEBUG @@ -204,7 +213,12 @@ void QSGNode::prependChildNode(QSGNode *node) } #endif - m_children.prepend(node); + if (m_firstChild) + m_firstChild->m_previousSibling = node; + else + m_lastChild = node; + node->m_nextSibling = m_firstChild; + m_firstChild = node; node->m_parent = this; node->markDirty(DirtyNodeAdded); @@ -219,7 +233,7 @@ void QSGNode::prependChildNode(QSGNode *node) void QSGNode::appendChildNode(QSGNode *node) { - Q_ASSERT_X(!m_children.contains(node), "QSGNode::appendChildNode", "QSGNode is already a child!"); + //Q_ASSERT_X(!m_children.contains(node), "QSGNode::appendChildNode", "QSGNode is already a child!"); Q_ASSERT_X(!node->m_parent, "QSGNode::appendChildNode", "QSGNode already has a parent"); #ifndef QT_NO_DEBUG @@ -230,7 +244,12 @@ void QSGNode::appendChildNode(QSGNode *node) } #endif - m_children.append(node); + if (m_lastChild) + m_lastChild->m_nextSibling = node; + else + m_firstChild = node; + node->m_previousSibling = m_lastChild; + m_lastChild = node; node->m_parent = this; node->markDirty(DirtyNodeAdded); @@ -247,9 +266,9 @@ void QSGNode::appendChildNode(QSGNode *node) void QSGNode::insertChildNodeBefore(QSGNode *node, QSGNode *before) { - Q_ASSERT_X(!m_children.contains(node), "QSGNode::insertChildNodeBefore", "QSGNode is already a child!"); + //Q_ASSERT_X(!m_children.contains(node), "QSGNode::insertChildNodeBefore", "QSGNode is already a child!"); Q_ASSERT_X(!node->m_parent, "QSGNode::insertChildNodeBefore", "QSGNode already has a parent"); - Q_ASSERT_X(node->type() != RootNodeType, "QSGNode::insertChildNodeBefore", "RootNodes cannot be children of other nodes"); + Q_ASSERT_X(before && before->m_parent == this, "QSGNode::insertChildNodeBefore", "The parent of \'before\' is wrong"); #ifndef QT_NO_DEBUG if (node->type() == QSGNode::GeometryNodeType) { @@ -259,11 +278,14 @@ void QSGNode::insertChildNodeBefore(QSGNode *node, QSGNode *before) } #endif - int idx = before?m_children.indexOf(before):-1; - if (idx == -1) - m_children.append(node); + QSGNode *previous = before->m_previousSibling; + if (previous) + previous->m_nextSibling = node; else - m_children.insert(idx, node); + m_firstChild = node; + node->m_previousSibling = previous; + node->m_nextSibling = before; + before->m_previousSibling = node; node->m_parent = this; node->markDirty(DirtyNodeAdded); @@ -280,9 +302,9 @@ void QSGNode::insertChildNodeBefore(QSGNode *node, QSGNode *before) void QSGNode::insertChildNodeAfter(QSGNode *node, QSGNode *after) { - Q_ASSERT_X(!m_children.contains(node), "QSGNode::insertChildNodeAfter", "QSGNode is already a child!"); + //Q_ASSERT_X(!m_children.contains(node), "QSGNode::insertChildNodeAfter", "QSGNode is already a child!"); Q_ASSERT_X(!node->m_parent, "QSGNode::insertChildNodeAfter", "QSGNode already has a parent"); - Q_ASSERT_X(node->type() != RootNodeType, "QSGNode::insertChildNodeAfter", "RootNodes cannot be children of other nodes"); + Q_ASSERT_X(after && after->m_parent == this, "QSGNode::insertChildNodeBefore", "The parent of \'before\' is wrong"); #ifndef QT_NO_DEBUG if (node->type() == QSGNode::GeometryNodeType) { @@ -292,11 +314,14 @@ void QSGNode::insertChildNodeAfter(QSGNode *node, QSGNode *after) } #endif - int idx = after?m_children.indexOf(after):-1; - if (idx == -1) - m_children.append(node); + QSGNode *next = after->m_nextSibling; + if (next) + next->m_previousSibling = node; else - m_children.insert(idx + 1, node); + m_lastChild = node; + node->m_nextSibling = next; + node->m_previousSibling = after; + after->m_nextSibling = node; node->m_parent = this; node->markDirty(DirtyNodeAdded); @@ -310,10 +335,21 @@ void QSGNode::insertChildNodeAfter(QSGNode *node, QSGNode *after) void QSGNode::removeChildNode(QSGNode *node) { - Q_ASSERT(m_children.contains(node)); + //Q_ASSERT(m_children.contains(node)); Q_ASSERT(node->parent() == this); - m_children.removeOne(node); + QSGNode *previous = node->m_previousSibling; + QSGNode *next = node->m_nextSibling; + if (previous) + previous->m_nextSibling = next; + else + m_firstChild = next; + if (next) + next->m_previousSibling = previous; + else + m_lastChild = previous; + node->m_previousSibling = 0; + node->m_nextSibling = 0; node->markDirty(DirtyNodeRemoved); node->m_parent = 0; @@ -326,14 +362,43 @@ void QSGNode::removeChildNode(QSGNode *node) void QSGNode::removeAllChildNodes() { - while (!m_children.isEmpty()) { - QSGNode *node = m_children.takeLast(); + while (m_firstChild) { + QSGNode *node = m_firstChild; + m_firstChild = node->m_nextSibling; + node->m_nextSibling = 0; + if (m_firstChild) + m_firstChild->m_previousSibling = 0; + else + m_lastChild = 0; node->markDirty(DirtyNodeRemoved); node->m_parent = 0; } } +int QSGNode::childCount() const +{ + int count = 0; + QSGNode *n = m_firstChild; + while (n) { + ++count; + n = n->m_nextSibling; + } + return count; +} + + +QSGNode *QSGNode::childAtIndex(int i) const +{ + QSGNode *n = m_firstChild; + while (i && n) { + --i; + n = n->m_nextSibling; + } + return n; +} + + /*! Sets the flag \a f on this node if \a enabled is true; otherwise clears the flag. @@ -999,10 +1064,8 @@ void QSGNodeVisitor::visitNode(QSGNode *n) void QSGNodeVisitor::visitChildren(QSGNode *n) { - int count = n->childCount(); - for (int i=0; ichildAtIndex(i)); - } + for (QSGNode *c = n->firstChild(); c; c = c->nextSibling()) + visitNode(c); } diff --git a/src/declarative/scenegraph/coreapi/qsgnode.h b/src/declarative/scenegraph/coreapi/qsgnode.h index b2444d5..2705958 100644 --- a/src/declarative/scenegraph/coreapi/qsgnode.h +++ b/src/declarative/scenegraph/coreapi/qsgnode.h @@ -124,8 +124,12 @@ public: void insertChildNodeBefore(QSGNode *node, QSGNode *before); void insertChildNodeAfter(QSGNode *node, QSGNode *after); - int childCount() const { return m_children.size(); } - QSGNode *childAtIndex(int i) const { return m_children.at(i); } + int childCount() const; + QSGNode *childAtIndex(int i) const; + QSGNode *firstChild() const { return m_firstChild; } + QSGNode *lastChild() const { return m_lastChild; } + QSGNode *nextSibling() const { return m_nextSibling; } + QSGNode* previousSibling() const { return m_previousSibling; } inline NodeType type() const { return m_type; } @@ -161,7 +165,10 @@ private: QSGNode *m_parent; NodeType m_type; - QList m_children; + QSGNode *m_firstChild; + QSGNode *m_lastChild; + QSGNode *m_nextSibling; + QSGNode *m_previousSibling; int m_subtreeGeometryCount; Flags m_nodeFlags; diff --git a/src/declarative/scenegraph/coreapi/qsgnodeupdater.cpp b/src/declarative/scenegraph/coreapi/qsgnodeupdater.cpp index 7a66074..3c3ff31 100644 --- a/src/declarative/scenegraph/coreapi/qsgnodeupdater.cpp +++ b/src/declarative/scenegraph/coreapi/qsgnodeupdater.cpp @@ -222,9 +222,8 @@ void QSGNodeUpdater::leaveOpacityNode(QSGOpacityNode *o) void QSGNodeUpdater::visitChildren(QSGNode *n) { - int count = n->childCount(); - for (int i = 0; i < count; ++i) - visitNode(n->childAtIndex(i)); + for (QSGNode *c = n->firstChild(); c; c = c->nextSibling()) + visitNode(c); } void QSGNodeUpdater::visitNode(QSGNode *n) diff --git a/src/declarative/scenegraph/coreapi/qsgrenderer.cpp b/src/declarative/scenegraph/coreapi/qsgrenderer.cpp index 7ceea36..c6afb31 100644 --- a/src/declarative/scenegraph/coreapi/qsgrenderer.cpp +++ b/src/declarative/scenegraph/coreapi/qsgrenderer.cpp @@ -331,16 +331,16 @@ void QSGRenderer::preprocess() void QSGRenderer::addNodesToPreprocess(QSGNode *node) { - for (int i = 0; i < node->childCount(); ++i) - addNodesToPreprocess(node->childAtIndex(i)); + for (QSGNode *c = node->firstChild(); c; c = c->nextSibling()) + addNodesToPreprocess(c); if (node->flags() & QSGNode::UsePreprocess) m_nodes_to_preprocess.insert(node); } void QSGRenderer::removeNodesToPreprocess(QSGNode *node) { - for (int i = 0; i < node->childCount(); ++i) - removeNodesToPreprocess(node->childAtIndex(i)); + for (QSGNode *c = node->firstChild(); c; c = c->nextSibling()) + removeNodesToPreprocess(c); if (node->flags() & QSGNode::UsePreprocess) m_nodes_to_preprocess.remove(node); } -- 1.7.2.5