Changeset View
Changeset View
Standalone View
Standalone View
source/blender/blenkernel/intern/node_runtime.cc
| Show First 20 Lines • Show All 272 Lines • ▼ Show 20 Lines | static void toposort_from_start_node(const ToposortDirection direction, | ||||
| struct Item { | struct Item { | ||||
| bNode *node; | bNode *node; | ||||
| int socket_index = 0; | int socket_index = 0; | ||||
| int link_index = 0; | int link_index = 0; | ||||
| }; | }; | ||||
| Stack<Item, 64> nodes_to_check; | Stack<Item, 64> nodes_to_check; | ||||
| nodes_to_check.push({&start_node}); | nodes_to_check.push({&start_node}); | ||||
| node_states[start_node.runtime->index_in_tree].is_in_stack = true; | node_states[start_node.index()].is_in_stack = true; | ||||
| while (!nodes_to_check.is_empty()) { | while (!nodes_to_check.is_empty()) { | ||||
| Item &item = nodes_to_check.peek(); | Item &item = nodes_to_check.peek(); | ||||
| bNode &node = *item.node; | bNode &node = *item.node; | ||||
| const Span<bNodeSocket *> sockets = (direction == ToposortDirection::LeftToRight) ? | const Span<bNodeSocket *> sockets = (direction == ToposortDirection::LeftToRight) ? | ||||
| node.runtime->inputs : | node.runtime->inputs : | ||||
| node.runtime->outputs; | node.runtime->outputs; | ||||
| while (true) { | while (true) { | ||||
| if (item.socket_index == sockets.size()) { | if (item.socket_index == sockets.size()) { | ||||
| Show All 11 Lines | while (true) { | ||||
| bNodeLink &link = *linked_links[item.link_index]; | bNodeLink &link = *linked_links[item.link_index]; | ||||
| if (!link.is_available()) { | if (!link.is_available()) { | ||||
| /* Ignore unavailable links. */ | /* Ignore unavailable links. */ | ||||
| item.link_index++; | item.link_index++; | ||||
| continue; | continue; | ||||
| } | } | ||||
| bNodeSocket &linked_socket = *socket.runtime->directly_linked_sockets[item.link_index]; | bNodeSocket &linked_socket = *socket.runtime->directly_linked_sockets[item.link_index]; | ||||
| bNode &linked_node = *linked_socket.runtime->owner_node; | bNode &linked_node = *linked_socket.runtime->owner_node; | ||||
| ToposortNodeState &linked_node_state = node_states[linked_node.runtime->index_in_tree]; | ToposortNodeState &linked_node_state = node_states[linked_node.index()]; | ||||
| if (linked_node_state.is_done) { | if (linked_node_state.is_done) { | ||||
| /* The linked node has already been visited. */ | /* The linked node has already been visited. */ | ||||
| item.link_index++; | item.link_index++; | ||||
| continue; | continue; | ||||
| } | } | ||||
| if (linked_node_state.is_in_stack) { | if (linked_node_state.is_in_stack) { | ||||
| r_cycle_detected = true; | r_cycle_detected = true; | ||||
| } | } | ||||
| else { | else { | ||||
| nodes_to_check.push({&linked_node}); | nodes_to_check.push({&linked_node}); | ||||
| linked_node_state.is_in_stack = true; | linked_node_state.is_in_stack = true; | ||||
| } | } | ||||
| break; | break; | ||||
| } | } | ||||
| /* If no other element has been pushed, the current node can be pushed to the sorted list. */ | /* If no other element has been pushed, the current node can be pushed to the sorted list. */ | ||||
| if (&item == &nodes_to_check.peek()) { | if (&item == &nodes_to_check.peek()) { | ||||
| ToposortNodeState &node_state = node_states[node.runtime->index_in_tree]; | ToposortNodeState &node_state = node_states[node.index()]; | ||||
| node_state.is_done = true; | node_state.is_done = true; | ||||
| node_state.is_in_stack = false; | node_state.is_in_stack = false; | ||||
| r_sorted_nodes.append(&node); | r_sorted_nodes.append(&node); | ||||
| nodes_to_check.pop(); | nodes_to_check.pop(); | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| static void update_toposort(const bNodeTree &ntree, | static void update_toposort(const bNodeTree &ntree, | ||||
| const ToposortDirection direction, | const ToposortDirection direction, | ||||
| Vector<bNode *> &r_sorted_nodes, | Vector<bNode *> &r_sorted_nodes, | ||||
| bool &r_cycle_detected) | bool &r_cycle_detected) | ||||
| { | { | ||||
| bNodeTreeRuntime &tree_runtime = *ntree.runtime; | bNodeTreeRuntime &tree_runtime = *ntree.runtime; | ||||
| r_sorted_nodes.clear(); | r_sorted_nodes.clear(); | ||||
| r_sorted_nodes.reserve(tree_runtime.nodes_by_id.size()); | r_sorted_nodes.reserve(tree_runtime.nodes_by_id.size()); | ||||
| r_cycle_detected = false; | r_cycle_detected = false; | ||||
| Array<ToposortNodeState> node_states(tree_runtime.nodes_by_id.size()); | Array<ToposortNodeState> node_states(tree_runtime.nodes_by_id.size()); | ||||
| for (bNode *node : tree_runtime.nodes_by_id) { | for (bNode *node : tree_runtime.nodes_by_id) { | ||||
| if (node_states[node->runtime->index_in_tree].is_done) { | if (node_states[node->index()].is_done) { | ||||
| /* Ignore nodes that are done already. */ | /* Ignore nodes that are done already. */ | ||||
| continue; | continue; | ||||
| } | } | ||||
| if ((direction == ToposortDirection::LeftToRight) ? | if ((direction == ToposortDirection::LeftToRight) ? | ||||
| node->runtime->has_available_linked_outputs : | node->runtime->has_available_linked_outputs : | ||||
| node->runtime->has_available_linked_inputs) { | node->runtime->has_available_linked_inputs) { | ||||
| /* Ignore non-start nodes. */ | /* Ignore non-start nodes. */ | ||||
| continue; | continue; | ||||
| } | } | ||||
| toposort_from_start_node(direction, *node, node_states, r_sorted_nodes, r_cycle_detected); | toposort_from_start_node(direction, *node, node_states, r_sorted_nodes, r_cycle_detected); | ||||
| } | } | ||||
| if (r_sorted_nodes.size() < tree_runtime.nodes_by_id.size()) { | if (r_sorted_nodes.size() < tree_runtime.nodes_by_id.size()) { | ||||
| r_cycle_detected = true; | r_cycle_detected = true; | ||||
| for (bNode *node : tree_runtime.nodes_by_id) { | for (bNode *node : tree_runtime.nodes_by_id) { | ||||
| if (node_states[node->runtime->index_in_tree].is_done) { | if (node_states[node->index()].is_done) { | ||||
| /* Ignore nodes that are done already. */ | /* Ignore nodes that are done already. */ | ||||
| continue; | continue; | ||||
| } | } | ||||
| /* Start toposort at this node which is somewhere in the middle of a loop. */ | /* Start toposort at this node which is somewhere in the middle of a loop. */ | ||||
| toposort_from_start_node(direction, *node, node_states, r_sorted_nodes, r_cycle_detected); | toposort_from_start_node(direction, *node, node_states, r_sorted_nodes, r_cycle_detected); | ||||
| } | } | ||||
| } | } | ||||
| ▲ Show 20 Lines • Show All 95 Lines • Show Last 20 Lines | |||||