Lines Matching refs:node
28 * Adds a directed edge from the parent node to the child.
78 dag_prune_head(struct dag *dag, struct dag_node *node)
80 assert(!node->parent_count);
82 list_delinit(&node->link);
84 util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
90 * Initializes DAG node (probably embedded in some other datastructure in the
94 dag_init_node(struct dag *dag, struct dag_node *node)
96 util_dynarray_init(&node->edges, dag);
97 list_addtail(&node->link, &dag->heads);
106 dag_traverse_bottom_up_node(struct dag_node *node,
107 void (*cb)(struct dag_node *node,
111 if (_mesa_set_search(state->seen, node))
118 assert(node);
120 while (node->edges.size != 0) {
121 util_dynarray_append(&stack, struct dag_node *, node);
127 util_dynarray_foreach_reverse(&node->edges, struct dag_edge, edge) {
133 /* Get last element pushed: either left-most child or current node.
134 * If it's the current node, that means that we've processed all its
138 if (top == node)
140 node = top;
143 /* Process the node */
144 cb(node, state->data);
145 _mesa_set_add(state->seen, node);
147 /* Find the next unprocessed node in the stack */
149 node = NULL;
153 node = util_dynarray_pop(&stack, struct dag_node *);
154 } while (_mesa_set_search(state->seen, node));
155 } while (node);
161 * Walks the DAG from leaves to the root, ensuring that each node is only seen
162 * once its children have been, and each node is only traversed once.
165 dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
173 list_for_each_entry(struct dag_node, node, &dag->heads, link) {
174 dag_traverse_bottom_up_node(node, cb, &state);