From 31bc9beeac9f7d2d5a272e77fa0e0ec5c22d7291 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 11:22:54 +0200 Subject: 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. --- .../depsgraph/intern/builder/deg_builder.cc | 21 +++++++------ .../depsgraph/intern/builder/deg_builder_cycle.cc | 36 ++++++++++++---------- 2 files changed, 32 insertions(+), 25 deletions(-) (limited to 'source/blender/depsgraph/intern') 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 - #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 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 #include -#include 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 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 -- cgit v1.2.3