Use linked list instead of QList for node children.

10 files changed, 134 insertions, 67 deletions

diff --git a/src/declarative/items/qsgcanvas.cpp b/src/declarative/items/qsgcanvas.cpp
index 28a65d0b40..f12f936b4e 100644
--- a/src/declarative/items/qsgcanvas.cpp
+++ b/src/declarative/items/qsgcanvas.cpp
@@ -1655,7 +1655,6 @@ void QSGCanvasPrivate::updateDirtyNode(QSGItem *item)
         QList<QSGItem *> 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 2bba4da216..3b07503f35 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 0f4a3213b4..c955c44fe6 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 24e2be37f4..c4c09868d2 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 33325a14ab..610513722e 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; i<childCount(); ++i) {
-            QSGNode *childNode = childAtIndex(i);
+        for (QSGNode *childNode = firstChild(); childNode; childNode = childNode->nextSibling()) {
             if (childNode->subType() == GlyphNodeSubType) {
                 QSGGlyphNode *glyphNode = static_cast<QSGGlyphNode *>(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; i<childCount(); ++i) {
-                QSGNode *childNode = childAtIndex(i);
+            for (QSGNode *childNode = firstChild(); childNode; childNode = childNode->nextSibling()) {
                 if (childNode->subType() == GlyphNodeSubType) {
                     QSGGlyphNode *glyphNode = static_cast<QSGGlyphNode *>(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 8e8f811ae1..1e6b6919cb 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<int, 16> beginIndices(count);
-        QVarLengthArray<int, 16> endIndices(count);
+    if (reorder && node->firstChild() != node->lastChild() && (node->flags() & QSGNode::ChildrenDoNotOverlap)) {
+        QVarLengthArray<int, 16> beginIndices;
+        QVarLengthArray<int, 16> 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 66ce836565..fa720a3b72 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; i<count; ++i) {
-        visitNode(n->childAtIndex(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 b2444d593c..2705958e04 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<QSGNode *> 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 7a660745e2..3c3ff31fd5 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 7ceea36b3a..c6afb3154b 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);
 }