Depsgraph: Use own implementation of stack rather than the one from STL

This way we always have predictable behavior, especially from the
performance point of view. Additionally, if some bottleneck is found
in stack implementation it'll be easier for us to address.

1 files changed, 20 insertions, 16 deletions

diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
index 9b37aaa12ff..1420b5fc8a5 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
@@ -32,10 +32,10 @@
 // TOO(sergey): Use some wrappers over those?
 #include <cstdio>
 #include <cstdlib>
-#include <stack>
 
 extern "C" {
 #include "BLI_utildefines.h"
+#include "BLI_stack.h"
 }
 
 #include "util/deg_util_foreach.h"
@@ -48,12 +48,6 @@ extern "C" {
 
 namespace DEG {
 
-struct StackEntry {
-	OperationDepsNode *node;
-	StackEntry *from;
-	DepsRelation *via_relation;
-};
-
 void deg_graph_detect_cycles(Depsgraph *graph)
 {
 	enum {
@@ -65,7 +59,15 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 		NODE_IN_STACK = 2,
 	};
 
-	std::stack<StackEntry> traversal_stack;
+	struct StackEntry {
+		OperationDepsNode *node;
+		StackEntry *from;
+		DepsRelation *via_relation;
+	};
+
+	BLI_Stack *traversal_stack = BLI_stack_new(sizeof(StackEntry),
+	                                           "DEG detect cycles stack");
+
 	foreach (OperationDepsNode *node, graph->operations) {
 		bool has_inlinks = false;
 		foreach (DepsRelation *rel, node->inlinks) {
@@ -78,7 +80,7 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 			entry.node = node;
 			entry.from = NULL;
 			entry.via_relation = NULL;
-			traversal_stack.push(entry);
+			BLI_stack_push(traversal_stack, &entry);
 			node->tag = NODE_IN_STACK;
 		}
 		else {
@@ -87,9 +89,9 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 		node->done = 0;
 	}
 
-	while (!traversal_stack.empty()) {
-		StackEntry& entry = traversal_stack.top();
-		OperationDepsNode *node = entry.node;
+	while (!BLI_stack_is_empty(traversal_stack)) {
+		StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
+		OperationDepsNode *node = entry->node;
 		bool all_child_traversed = true;
 		for (int i = node->done; i < node->outlinks.size(); ++i) {
 			DepsRelation *rel = node->outlinks[i];
@@ -102,7 +104,7 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 					       node->full_identifier().c_str(),
 					       rel->name);
 
-					StackEntry *current = &entry;
+					StackEntry *current = entry;
 					while (current->node != to) {
 						BLI_assert(current != NULL);
 						printf("  '%s' depends on '%s' through '%s'\n",
@@ -117,9 +119,9 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 				else if (to->tag == NODE_NOT_VISITED) {
 					StackEntry new_entry;
 					new_entry.node = to;
-					new_entry.from = &entry;
+					new_entry.from = entry;
 					new_entry.via_relation = rel;
-					traversal_stack.push(new_entry);
+					BLI_stack_push(traversal_stack, &new_entry);
 					to->tag = NODE_IN_STACK;
 					all_child_traversed = false;
 					node->done = i;
@@ -129,9 +131,11 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 		}
 		if (all_child_traversed) {
 			node->tag = NODE_VISITED;
-			traversal_stack.pop();
+			BLI_stack_discard(traversal_stack);
 		}
 	}
+
+	BLI_stack_free(traversal_stack);
 }
 
 }  // namespace DEG