Avoid traversing the same nodes multiple times

This is a small performance improvement.

Change-Id: I3283f1ec40227b11952557fd2d0cfd32de6824cc
Reviewed-by: Oliver Wolff <oliver.wolff@qt.io>

2 files changed, 10 insertions, 4 deletions

diff --git a/src/jomlib/dependencygraph.cpp b/src/jomlib/dependencygraph.cpp
index d3db7f9..1807e72 100644
--- a/src/jomlib/dependencygraph.cpp
+++ b/src/jomlib/dependencygraph.cpp
@@ -69,7 +69,8 @@ void DependencyGraph::build(DescriptionBlock* target)
 {
     m_bDirtyLeaves = true;
     m_root = createNode(target, 0);
-    internalBuild(m_root);
+    QSet<Node *> seen;
+    internalBuild(m_root, seen);
     //dump();
     //qDebug() << "\n\n-------------------------------------------------\n";
 
@@ -160,8 +161,13 @@ bool DependencyGraph::isTargetUpToDate(DescriptionBlock* target)
     return isUpToDate;
 }
 
-void DependencyGraph::internalBuild(Node* node)
+void DependencyGraph::internalBuild(Node *node, QSet<Node *> &seen)
 {
+    const int c = seen.count();
+    seen << node;
+    if (c == seen.count())
+        return;
+
     foreach (const QString& dependentName, node->target->m_dependents) {
         Makefile* const makefile = node->target->makefile();
         DescriptionBlock* dependent = makefile->target(dependentName);
@@ -186,7 +192,7 @@ void DependencyGraph::internalBuild(Node* node)
         else
             child = createNode(dependent, node);
 
-        internalBuild(child);
+        internalBuild(child, seen);
     }
 
     if (node->children.isEmpty() && !m_leavesSet.contains(node)) {
diff --git a/src/jomlib/dependencygraph.h b/src/jomlib/dependencygraph.h
index 3384c4a..f94e32d 100644
--- a/src/jomlib/dependencygraph.h
+++ b/src/jomlib/dependencygraph.h
@@ -63,7 +63,7 @@ private:
     Node* createNode(DescriptionBlock* target, Node* parent);
     void deleteNode(Node* node);
     void removeLeaf(Node* node);
-    void internalBuild(Node* node);
+    void internalBuild(Node *node, QSet<Node *> &seen);
     void addEdge(Node* parent, Node* child);
     void internalDump(Node* node, QString& indent);
     void internalDotDump(Node* node, const QString& parent);