[Bf-blender-cvs] [dc171b2a3e1] functions: non recursive method to find required sockets

[Jacques Lucke]

Commit: dc171b2a3e185cebd03d021cdc3a43849c259730
Author: Jacques Lucke
Date:   Sun Mar 24 10:41:01 2019 +0100
Branches: functions
https://developer.blender.org/rBdc171b2a3e185cebd03d021cdc3a43849c259730

non recursive method to find required sockets

===================================================================

M	source/blender/blenlib/BLI_small_set.hpp
M	source/blender/blenlib/BLI_small_vector.hpp
M	source/blender/functions/backends/llvm/fgraph_ir_generation.cpp
M	source/blender/functions/core/data_flow_graph.cpp
M	source/blender/functions/core/data_flow_graph.hpp

===================================================================

diff --git a/source/blender/blenlib/BLI_small_set.hpp b/source/blender/blenlib/BLI_small_set.hpp
index 1f6e7f680db..d01d5a6f0c2 100644
--- a/source/blender/blenlib/BLI_small_set.hpp
+++ b/source/blender/blenlib/BLI_small_set.hpp
@@ -54,6 +54,11 @@ namespace BLI {
 			return m_entries[0];
 		}
 
+		T pop()
+		{
+			return m_entries.pop_last();
+		}
+
 
 		/* Iterators */
 
diff --git a/source/blender/blenlib/BLI_small_vector.hpp b/source/blender/blenlib/BLI_small_vector.hpp
index 9044908eaa3..182164b428b 100644
--- a/source/blender/blenlib/BLI_small_vector.hpp
+++ b/source/blender/blenlib/BLI_small_vector.hpp
@@ -133,6 +133,14 @@ namespace BLI {
 			m_size--;
 		}
 
+		T pop_last()
+		{
+			BLI_assert(!this->empty());
+			T value = m_elements[this->size() - 1];
+			this->remove_last();
+			return value;
+		}
+
 		void remove_and_reorder(uint index)
 		{
 			BLI_assert(this->is_index_in_range(index));
diff --git a/source/blender/functions/backends/llvm/fgraph_ir_generation.cpp b/source/blender/functions/backends/llvm/fgraph_ir_generation.cpp
index cc47bfa9393..86f6af83d03 100644
--- a/source/blender/functions/backends/llvm/fgraph_ir_generation.cpp
+++ b/source/blender/functions/backends/llvm/fgraph_ir_generation.cpp
@@ -29,7 +29,7 @@ namespace FN {
 					continue;
 				}
 			}
-			m_required_sockets = this->find_required_sockets();
+			m_required_sockets = fgraph.find_required_sockets();
 		}
 
 		void build_ir(
@@ -50,41 +50,6 @@ namespace FN {
 		}
 
 	private:
-		SocketSet find_required_sockets() const
-		{
-			SocketSet required_sockets;
-			for (Socket socket : m_fgraph.outputs()) {
-				this->find_required_sockets(socket, required_sockets);
-			}
-			return required_sockets;
-		}
-
-		void find_required_sockets(Socket socket, SocketSet &required_sockets) const
-		{
-			if (required_sockets.contains(socket)) {
-				return;
-			}
-
-			required_sockets.add(socket);
-
-			if (m_inputs.contains(socket)) {
-				/* do nothing */
-			}
-			else if (socket.is_input()) {
-				this->find_required_sockets(socket.origin(), required_sockets);
-				return;
-			}
-			else if (socket.is_output()) {
-				for (Socket input : socket.node()->inputs()) {
-					this->find_required_sockets(input, required_sockets);
-				}
-				return;
-			}
-			else {
-				BLI_assert(!"should never happen");
-			}
-		}
-
 		void generate_for_socket(
 			llvm::IRBuilder<> &builder,
 			Socket socket,
diff --git a/source/blender/functions/core/data_flow_graph.cpp b/source/blender/functions/core/data_flow_graph.cpp
index 408437d9d04..49fddd65e2d 100644
--- a/source/blender/functions/core/data_flow_graph.cpp
+++ b/source/blender/functions/core/data_flow_graph.cpp
@@ -55,4 +55,37 @@ namespace FN {
 
 		m_links.insert(Link::New(a, b));
 	}
+
+
+	SocketSet FunctionGraph::find_required_sockets() const
+	{
+		SocketSet found;
+
+		SocketSet to_be_checked;
+		for (Socket socket : m_outputs) {
+			to_be_checked.add(socket);
+		}
+
+		while (to_be_checked.size() > 0) {
+			Socket socket = to_be_checked.pop();
+
+			if (m_inputs.contains(socket)) {
+				continue;
+			}
+
+			found.add(socket);
+
+			if (socket.is_input()) {
+				to_be_checked.add(socket.origin());
+			}
+			else {
+				for (Socket input : socket.node()->inputs()) {
+					to_be_checked.add(input);
+				}
+			}
+		}
+
+		return found;
+	}
+
 };
\ No newline at end of file
diff --git a/source/blender/functions/core/data_flow_graph.hpp b/source/blender/functions/core/data_flow_graph.hpp
index 7f1644621f5..43fe156b296 100644
--- a/source/blender/functions/core/data_flow_graph.hpp
+++ b/source/blender/functions/core/data_flow_graph.hpp
@@ -301,12 +301,12 @@ namespace FN {
 			return m_graph;
 		}
 
-		const SmallSocketVector &inputs() const
+		const SmallSocketSetVector &inputs() const
 		{
 			return m_inputs;
 		}
 
-		const SmallSocketVector &outputs() const
+		const SmallSocketSetVector &outputs() const
 		{
 			return m_outputs;
 		}
@@ -326,10 +326,12 @@ namespace FN {
 			return Signature(inputs, outputs);
 		}
 
+		SocketSet find_required_sockets() const;
+
 	private:
 		SharedDataFlowGraph m_graph;
-		SmallSocketVector m_inputs;
-		SmallSocketVector m_outputs;
+		SmallSocketSetVector m_inputs;
+		SmallSocketSetVector m_outputs;
 	};