Use linked list instead of QList for node children.

5 files changed, 118 insertions, 48 deletions

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);
 }