Lines Matching refs:node
43 * Adds a directed edge from the parent node to the child.
60 * Adds a directed edge from the parent node to the child.
107 dag_prune_head(struct dag *dag, struct dag_node *node)
109 assert(!node->parent_count);
111 list_delinit(&node->link);
113 util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
119 * Initializes DAG node (probably embedded in some other datastructure in the
123 dag_init_node(struct dag *dag, struct dag_node *node)
125 util_dynarray_init(&node->edges, dag);
126 list_addtail(&node->link, &dag->heads);
135 dag_traverse_bottom_up_node(struct dag_node *node,
136 void (*cb)(struct dag_node *node,
140 if (_mesa_set_search(state->seen, node))
147 assert(node);
149 while (node->edges.size != 0) {
150 util_dynarray_append(&stack, struct dag_node *, node);
156 util_dynarray_foreach_reverse(&node->edges, struct dag_edge, edge) {
162 /* Get last element pushed: either left-most child or current node.
163 * If it's the current node, that means that we've processed all its
167 if (top == node)
169 node = top;
172 /* Process the node */
173 cb(node, state->data);
174 _mesa_set_add(state->seen, node);
176 /* Find the next unprocessed node in the stack */
178 node = NULL;
182 node = util_dynarray_pop(&stack, struct dag_node *);
183 } while (_mesa_set_search(state->seen, node));
184 } while (node);
190 * Walks the DAG from leaves to the root, ensuring that each node is only seen
191 * once its children have been, and each node is only traversed once.
194 dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
202 list_for_each_entry(struct dag_node, node, &dag->heads, link) {
203 dag_traverse_bottom_up_node(node, cb, &state);