2 * Copyright © 2019 Broadcom
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
28 * Adds a directed edge from the parent node to the child.
30 * Both nodes should have been initialized with dag_init_node(). The edge
31 * list may contain multiple edges to the same child with different data.
34 dag_add_edge(struct dag_node
*parent
, struct dag_node
*child
, void *data
)
36 util_dynarray_foreach(&parent
->edges
, struct dag_edge
, edge
) {
37 if (edge
->child
== child
&& edge
->data
== data
)
40 /* Remove the child as a DAG head. */
41 list_delinit(&child
->link
);
43 struct dag_edge edge
= {
48 util_dynarray_append(&parent
->edges
, struct dag_edge
, edge
);
49 child
->parent_count
++;
52 /* Removes a single edge from the graph, promoting the child to a DAG head.
54 * Note that calling this other than through dag_prune_head() means that you
55 * need to be careful when iterating the edges of remaining nodes for NULL
59 dag_remove_edge(struct dag
*dag
, struct dag_edge
*edge
)
64 struct dag_node
*child
= edge
->child
;
65 child
->parent_count
--;
66 if (child
->parent_count
== 0)
67 list_addtail(&child
->link
, &dag
->heads
);
74 * Removes a DAG head from the graph, and moves any new dag heads into the
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
) {
85 dag_remove_edge(dag
, 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
);
100 struct dag_traverse_bottom_up_state
{
106 dag_traverse_bottom_up_node(struct dag_node
*node
,
107 void (*cb
)(struct dag_node
*node
,
109 struct dag_traverse_bottom_up_state
*state
)
111 if (_mesa_set_search(state
->seen
, node
))
114 util_dynarray_foreach(&node
->edges
, struct dag_edge
, edge
) {
115 dag_traverse_bottom_up_node(edge
->child
, cb
, state
);
118 cb(node
, state
->data
);
119 _mesa_set_add(state
->seen
, node
);
123 * Walks the DAG from leaves to the root, ensuring that each node is only seen
124 * once its children have been, and each node is only traversed once.
127 dag_traverse_bottom_up(struct dag
*dag
, void (*cb
)(struct dag_node
*node
,
128 void *data
), void *data
)
130 struct dag_traverse_bottom_up_state state
= {
131 .seen
= _mesa_pointer_set_create(NULL
),
135 list_for_each_entry(struct dag_node
, node
, &dag
->heads
, link
) {
136 dag_traverse_bottom_up_node(node
, cb
, &state
);
139 ralloc_free(state
.seen
);
143 * Creates an empty DAG datastructure.
146 dag_create(void *mem_ctx
)
148 struct dag
*dag
= rzalloc(mem_ctx
, struct dag
);
150 list_inithead(&dag
->heads
);