diff options
author | Friedemann Kleint <Friedemann.Kleint@qt.io> | 2019-03-28 10:46:02 +0100 |
---|---|---|
committer | Friedemann Kleint <Friedemann.Kleint@qt.io> | 2019-04-01 15:36:21 +0000 |
commit | f53aed12cae42db9d142b8829b9d815b4384dced (patch) | |
tree | 90deead4ab04bc46d0ab25de7579463d275d6e69 /sources | |
parent | f02d84ea7953efbbd10f9823b461b3d473efc89e (diff) |
shiboken: Replace QLinkedList by a QVector in the Graph class
Change-Id: I4d76a29699867e9d4ff6138cc40fae9b1f519121
Reviewed-by: Cristian Maureira-Fredes <cristian.maureira-fredes@qt.io>
Diffstat (limited to 'sources')
-rw-r--r-- | sources/shiboken2/ApiExtractor/abstractmetabuilder.cpp | 3 | ||||
-rw-r--r-- | sources/shiboken2/ApiExtractor/graph.cpp | 20 | ||||
-rw-r--r-- | sources/shiboken2/ApiExtractor/graph.h | 9 | ||||
-rw-r--r-- | sources/shiboken2/ApiExtractor/tests/testtoposort.cpp | 11 | ||||
-rw-r--r-- | sources/shiboken2/generator/shiboken2/overloaddata.cpp | 2 |
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()) |