shiboken: Replace QLinkedList by a QVector in the Graph class

Change-Id: I4d76a29699867e9d4ff6138cc40fae9b1f519121
Reviewed-by: Cristian Maureira-Fredes <cristian.maureira-fredes@qt.io>

5 files changed, 24 insertions, 21 deletions

diff --git a/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp b/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
index 0b11b1666..5074770d3 100644
--- a/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
+++ b/sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp
@@ -3088,7 +3088,6 @@ void AbstractMetaBuilderPrivate::dumpLog() const
 AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const AbstractMetaClass *cppClass,
                                                                            const Dependencies &additionalDependencies) const
 {
-    QLinkedList<int> unmappedResult;
     QHash<QString, int> map;
     QHash<int, AbstractMetaClass*> reverseMap;
 
@@ -3175,7 +3174,7 @@ AbstractMetaClassList AbstractMetaBuilderPrivate::classesTopologicalSorted(const
     }
 
     AbstractMetaClassList result;
-    unmappedResult = graph.topologicalSort();
+    const auto unmappedResult = graph.topologicalSort();
     if (unmappedResult.isEmpty() && graph.nodeCount()) {
         QTemporaryFile tempFile;
         tempFile.setAutoRemove(false);
diff --git a/sources/shiboken2/ApiExtractor/graph.cpp b/sources/shiboken2/ApiExtractor/graph.cpp
index 65f33e373..c2ac81e6c 100644
--- a/sources/shiboken2/ApiExtractor/graph.cpp
+++ b/sources/shiboken2/ApiExtractor/graph.cpp
@@ -29,7 +29,6 @@
 #include "graph.h"
 #include <QVector>
 #include <QDebug>
-#include <QLinkedList>
 #include <QSet>
 #include <iterator>
 #include <algorithm>
@@ -48,7 +47,7 @@ struct Graph::GraphPrivate
     {
     }
 
-    void dfsVisit(int node, QLinkedList<int>& result, QVector<Color>& colors) const
+    void dfsVisit(int node, Graph::Indexes &result, QVector<Color> &colors) const
     {
         colors[node] = GRAY;
         EdgeIterator it = edges[node].begin();
@@ -59,7 +58,7 @@ struct Graph::GraphPrivate
                 return;
         }
         colors[node] = BLACK;
-        result.push_front(node);
+        result.append(node);
     }
 };
 
@@ -77,10 +76,12 @@ int Graph::nodeCount() const
     return m_d->edges.size();
 }
 
-QLinkedList<int> Graph::topologicalSort() const
+Graph::Indexes Graph::topologicalSort() const
 {
-    int nodeCount = Graph::nodeCount();
-    QLinkedList<int> result;
+    const int nodeCount = Graph::nodeCount();
+    Indexes result;
+    result.reserve(nodeCount);
+
     QVector<GraphPrivate::Color> colors(nodeCount, GraphPrivate::WHITE);
 
     for (int i = 0; i < nodeCount; ++i) {
@@ -88,9 +89,10 @@ QLinkedList<int> Graph::topologicalSort() const
             m_d->dfsVisit(i, result, colors);
     }
 
-    // Not a DAG!
-    if (result.size() != nodeCount)
-        return QLinkedList<int>();
+    if (result.size() == nodeCount)
+        std::reverse(result.begin(), result.end());
+    else
+        result.clear(); // Not a DAG!
     return result;
 }
 
diff --git a/sources/shiboken2/ApiExtractor/graph.h b/sources/shiboken2/ApiExtractor/graph.h
index 879ac97e4..043a182b5 100644
--- a/sources/shiboken2/ApiExtractor/graph.h
+++ b/sources/shiboken2/ApiExtractor/graph.h
@@ -29,7 +29,7 @@
 #ifndef GRAPH_H
 #define GRAPH_H
 
-#include <QLinkedList>
+#include <QVector>
 #include <QHash>
 #include <QString>
 
@@ -37,6 +37,8 @@
 class Graph
 {
 public:
+    using Indexes = QVector<int>;
+
     /// Create a new graph with \p numNodes nodes.
     Graph(int numNodes);
     ~Graph();
@@ -60,9 +62,10 @@ public:
 
     /**
     *   Topologically sort this graph.
-    *   \return A collection with all nodes topologically sorted or an empty collection if a ciclic dependency was found.
+    *   \return A collection with all nodes topologically sorted or an empty collection if a cyclic
+    *   dependency was found.
     */
-    QLinkedList<int> topologicalSort() const;
+    Indexes topologicalSort() const;
 private:
 
     struct GraphPrivate;
diff --git a/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp b/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp
index 9d7729513..c59fa8c3d 100644
--- a/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp
+++ b/sources/shiboken2/ApiExtractor/tests/testtoposort.cpp
@@ -33,23 +33,22 @@
 
 void TestTopoSort::testTopoSort()
 {
-    QLinkedList<int> result;
     {
         Graph g(3);
         g.addEdge(1, 2);
         g.addEdge(0, 1);
-        result = g.topologicalSort();
+        const auto result = g.topologicalSort();
         QCOMPARE(result.size(), 3);
-        QLinkedList<int>::iterator it = result.begin();
+        auto it = result.begin();
         QCOMPARE(*it, 0);
         QCOMPARE(*(++it), 1);
         QCOMPARE(*(++it), 2);
     }
     {
         Graph g(2);
-        result = g.topologicalSort();
+        const auto result = g.topologicalSort();
         QCOMPARE(result.size(), 2);
-        QLinkedList<int>::iterator it = result.begin();
+        auto it = result.begin();
         QCOMPARE(*it, 1);
         QCOMPARE(*(++it), 0);
     }
@@ -61,7 +60,7 @@ void TestTopoSort::testCiclicGraph()
     g.addEdge(0, 1);
     g.addEdge(1, 2);
     g.addEdge(2, 0);
-    QLinkedList<int> result = g.topologicalSort();
+    const auto result = g.topologicalSort();
     QVERIFY(result.isEmpty());
 }
 
diff --git a/sources/shiboken2/generator/shiboken2/overloaddata.cpp b/sources/shiboken2/generator/shiboken2/overloaddata.cpp
index 6a85bf7ef..9f0ac51e5 100644
--- a/sources/shiboken2/generator/shiboken2/overloaddata.cpp
+++ b/sources/shiboken2/generator/shiboken2/overloaddata.cpp
@@ -426,7 +426,7 @@ void OverloadData::sortNextOverloads()
     }
 
     // sort the overloads topologically based on the dependency graph.
-    const QLinkedList<int> unmappedResult = graph.topologicalSort();
+    const auto unmappedResult = graph.topologicalSort();
     if (unmappedResult.isEmpty()) {
         QString funcName = referenceFunction()->name();
         if (referenceFunction()->ownerClass())