diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2017-12-21 13:47:34 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2017-12-21 13:47:34 +0300 |
commit | 681a1028004342c739f056c51443516b9b49b38a (patch) | |
tree | 6500e256081882d3af1ce455c704ea1983cc9e66 /source/blender/depsgraph | |
parent | 5df49500731a4d36230477e82b45278902437ded (diff) |
Depsgraph: Remove one of temporary tags in the node
No real reason to have that, better to free up space for something much more
awesome!
Diffstat (limited to 'source/blender/depsgraph')
-rw-r--r-- | source/blender/depsgraph/intern/builder/deg_builder_cycle.cc | 58 | ||||
-rw-r--r-- | source/blender/depsgraph/intern/nodes/deg_node.h | 17 |
2 files changed, 46 insertions, 29 deletions
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc index 3eed0697b5e..783fd84fa3c 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc @@ -46,17 +46,38 @@ namespace DEG { -void deg_graph_detect_cycles(Depsgraph *graph) +typedef enum eCyclicCheckVisitedState { + /* Not is not visited at all during traversal. */ + NODE_NOT_VISITED = 0, + /* Node has been visited during traversal and not in current stack. */ + NODE_VISITED = 1, + /* Node has been visited during traversal and is in current stack. */ + NODE_IN_STACK = 2, +} eCyclicCheckVisitedState; + +BLI_INLINE void set_node_visited_state(DepsNode *node, + eCyclicCheckVisitedState state) { - enum { - /* Not is not visited at all during traversal. */ - NODE_NOT_VISITED = 0, - /* Node has been visited during traversal and not in current stack. */ - NODE_VISITED = 1, - /* Node has been visited during traversal and is in current stack. */ - NODE_IN_STACK = 2, - }; + node->done = (node->done & ~0x3) | (int)state; +} + +BLI_INLINE eCyclicCheckVisitedState get_node_visited_state(DepsNode *node) +{ + return (eCyclicCheckVisitedState)(node->done & 0x3); +} +BLI_INLINE void set_node_num_visited_children(DepsNode *node, int num_children) +{ + node->done = (node->done & 0x3) | (num_children << 2); +} + +BLI_INLINE int get_node_num_visited_children(DepsNode *node) +{ + return node->done >> 2; +} + +void deg_graph_detect_cycles(Depsgraph *graph) +{ struct StackEntry { OperationDepsNode *node; StackEntry *from; @@ -73,16 +94,17 @@ void deg_graph_detect_cycles(Depsgraph *graph) has_inlinks = true; } } + node->done = 0; if (has_inlinks == false) { StackEntry entry; entry.node = node; entry.from = NULL; entry.via_relation = NULL; BLI_stack_push(traversal_stack, &entry); - node->tag = NODE_IN_STACK; + set_node_visited_state(node, NODE_IN_STACK); } else { - node->tag = NODE_NOT_VISITED; + set_node_visited_state(node, NODE_NOT_VISITED); } node->done = 0; } @@ -91,11 +113,13 @@ void deg_graph_detect_cycles(Depsgraph *graph) 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) { + const int num_visited = get_node_num_visited_children(node); + for (int i = num_visited; i < node->outlinks.size(); ++i) { DepsRelation *rel = node->outlinks[i]; if (rel->to->type == DEG_NODE_TYPE_OPERATION) { OperationDepsNode *to = (OperationDepsNode *)rel->to; - if (to->tag == NODE_IN_STACK) { + eCyclicCheckVisitedState state = get_node_visited_state(node); + if (state == NODE_IN_STACK) { printf("Dependency cycle detected:\n"); printf(" '%s' depends on '%s' through '%s'\n", to->full_identifier().c_str(), @@ -114,21 +138,21 @@ void deg_graph_detect_cycles(Depsgraph *graph) /* TODO(sergey): So called russian roulette cycle solver. */ rel->flag |= DEPSREL_FLAG_CYCLIC; } - else if (to->tag == NODE_NOT_VISITED) { + else if (state == NODE_NOT_VISITED) { StackEntry new_entry; new_entry.node = to; new_entry.from = entry; new_entry.via_relation = rel; BLI_stack_push(traversal_stack, &new_entry); - to->tag = NODE_IN_STACK; + set_node_visited_state(node, NODE_IN_STACK); all_child_traversed = false; - node->done = i; + set_node_num_visited_children(node, i); break; } } } if (all_child_traversed) { - node->tag = NODE_VISITED; + set_node_visited_state(node, NODE_VISITED); BLI_stack_discard(traversal_stack); } } diff --git a/source/blender/depsgraph/intern/nodes/deg_node.h b/source/blender/depsgraph/intern/nodes/deg_node.h index b303b5ba010..79464ae5fa7 100644 --- a/source/blender/depsgraph/intern/nodes/deg_node.h +++ b/source/blender/depsgraph/intern/nodes/deg_node.h @@ -63,18 +63,11 @@ struct DepsNode { */ typedef vector<DepsRelation *> Relations; - /* Identifier - mainly for debugging purposes. */ - const char *name; - /* Structural type of node. */ - eDepsNode_Type type; - /* Nodes which this one depends on. */ - Relations inlinks; - /* Nodes which depend on this one. */ - Relations outlinks; - - /* Generic tags for traversal algorithms. */ - int done; - int tag; + const char *name; /* Identifier - mainly for debugging purposes. */ + eDepsNode_Type type; /* Structural type of node. */ + Relations inlinks; /* Nodes which this one depends on. */ + Relations outlinks; /* Nodes which depend on this one. */ + int done; /* Generic tags for traversal algorithms. */ /* Methods. */ DepsNode(); |