From f53aed12cae42db9d142b8829b9d815b4384dced Mon Sep 17 00:00:00 2001 From: Friedemann Kleint Date: Thu, 28 Mar 2019 10:46:02 +0100 Subject: shiboken: Replace QLinkedList by a QVector in the Graph class Change-Id: I4d76a29699867e9d4ff6138cc40fae9b1f519121 Reviewed-by: Cristian Maureira-Fredes --- .../shiboken2/ApiExtractor/abstractmetabuilder.cpp | 3 +-- sources/shiboken2/ApiExtractor/graph.cpp | 20 +++++++++++--------- sources/shiboken2/ApiExtractor/graph.h | 9 ++++++--- .../shiboken2/ApiExtractor/tests/testtoposort.cpp | 11 +++++------ .../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 unmappedResult; QHash map; QHash 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 #include -#include #include #include #include @@ -48,7 +47,7 @@ struct Graph::GraphPrivate { } - void dfsVisit(int node, QLinkedList& result, QVector& colors) const + void dfsVisit(int node, Graph::Indexes &result, QVector &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 Graph::topologicalSort() const +Graph::Indexes Graph::topologicalSort() const { - int nodeCount = Graph::nodeCount(); - QLinkedList result; + const int nodeCount = Graph::nodeCount(); + Indexes result; + result.reserve(nodeCount); + QVector colors(nodeCount, GraphPrivate::WHITE); for (int i = 0; i < nodeCount; ++i) { @@ -88,9 +89,10 @@ QLinkedList Graph::topologicalSort() const m_d->dfsVisit(i, result, colors); } - // Not a DAG! - if (result.size() != nodeCount) - return QLinkedList(); + 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 +#include #include #include @@ -37,6 +37,8 @@ class Graph { public: + using Indexes = QVector; + /// 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 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 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::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::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 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 unmappedResult = graph.topologicalSort(); + const auto unmappedResult = graph.topologicalSort(); if (unmappedResult.isEmpty()) { QString funcName = referenceFunction()->name(); if (referenceFunction()->ownerClass()) -- cgit v1.2.3