Depsgraph: Remove one of temporary tags in the node
authorSergey Sharybin <sergey.vfx@gmail.com>
Thu, 21 Dec 2017 10:47:34 +0000 (11:47 +0100)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 21 Dec 2017 10:47:34 +0000 (11:47 +0100)
No real reason to have that, better to free up space for something much more
awesome!

source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
source/blender/depsgraph/intern/nodes/deg_node.h

index 3eed0697b5e56e828de713a09e7dd37ef1d398b2..783fd84fa3c49146c3aead7b38c6b14c2aa6a473 100644 (file)
 
 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);
                }
        }
index b303b5ba010aa39334af8aea0793ec6609ca1a9c..79464ae5fa76b0ec66350756cc5fa7c8b0a1005c 100644 (file)
@@ -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();