diff options
-rw-r--r-- | source/blender/depsgraph/intern/builder/deg_builder.cc | 21 | ||||
-rw-r--r-- | source/blender/depsgraph/intern/builder/deg_builder_cycle.cc | 36 |
2 files changed, 32 insertions, 25 deletions
diff --git a/source/blender/depsgraph/intern/builder/deg_builder.cc b/source/blender/depsgraph/intern/builder/deg_builder.cc index 7f62eb122db..143f9908db8 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder.cc @@ -30,9 +30,6 @@ #include "intern/builder/deg_builder.h" -// TODO(sergey): Use own wrapper over STD. -#include <stack> - #include "DNA_anim_types.h" #include "DNA_object_types.h" #include "DNA_ID.h" @@ -40,6 +37,10 @@ #include "BLI_utildefines.h" #include "BLI_ghash.h" +extern "C" { +#include "BLI_stack.h" +} + #include "intern/depsgraph.h" #include "intern/depsgraph_types.h" #include "intern/nodes/deg_node.h" @@ -71,7 +72,8 @@ static bool check_object_needs_evaluation(Object *object) void deg_graph_build_flush_layers(Depsgraph *graph) { - std::stack<OperationDepsNode *> stack; + BLI_Stack *stack = BLI_stack_new(sizeof(OperationDepsNode*), + "DEG flush layers stack"); foreach (OperationDepsNode *node, graph->operations) { IDDepsNode *id_node = node->owner->owner; node->done = 0; @@ -84,15 +86,15 @@ void deg_graph_build_flush_layers(Depsgraph *graph) } } if (node->num_links_pending == 0) { - stack.push(node); + BLI_stack_push(stack, &node); node->done = 1; } node->owner->layers = id_node->layers; id_node->id->tag |= LIB_TAG_DOIT; } - while (!stack.empty()) { - OperationDepsNode *node = stack.top(); - stack.pop(); + while (!BLI_stack_is_empty(stack)) { + OperationDepsNode *node; + BLI_stack_pop(stack, &node); /* Flush layers to parents. */ foreach (DepsRelation *rel, node->inlinks) { if (rel->from->type == DEPSNODE_TYPE_OPERATION) { @@ -109,12 +111,13 @@ void deg_graph_build_flush_layers(Depsgraph *graph) --from->num_links_pending; } if (from->num_links_pending == 0 && from->done == 0) { - stack.push(from); + BLI_stack_push(stack, &from); from->done = 1; } } } } + BLI_stack_free(stack); } void deg_graph_build_finalize(Depsgraph *graph) 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 |