1 /*
2 * Copyright © 2019 Broadcom
3 *
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:
10 *
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
13 * Software.
14 *
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
21 * IN THE SOFTWARE.
22 */
23
24 #include "util/set.h"
25 #include "util/dag.h"
26
27 static void
append_edge(struct dag_node * parent,struct dag_node * child,uintptr_t data)28 append_edge(struct dag_node *parent, struct dag_node *child, uintptr_t data)
29 {
30 /* Remove the child as a DAG head. */
31 list_delinit(&child->link);
32
33 struct dag_edge edge = {
34 .child = child,
35 .data = data,
36 };
37
38 util_dynarray_append(&parent->edges, struct dag_edge, edge);
39 child->parent_count++;
40 }
41
42 /**
43 * Adds a directed edge from the parent node to the child.
44 *
45 * Both nodes should have been initialized with dag_init_node(). The edge
46 * list may contain multiple edges to the same child with different data.
47 */
48 void
dag_add_edge(struct dag_node * parent,struct dag_node * child,uintptr_t data)49 dag_add_edge(struct dag_node *parent, struct dag_node *child, uintptr_t data)
50 {
51 util_dynarray_foreach(&parent->edges, struct dag_edge, edge) {
52 if (edge->child == child && edge->data == data)
53 return;
54 }
55
56 append_edge(parent, child, data);
57 }
58
59 /**
60 * Adds a directed edge from the parent node to the child.
61 *
62 * Both nodes should have been initialized with dag_init_node(). If there is
63 * already an existing edge, the data is updated to the maximum of the
64 * previous data and the new data. This is useful if the data represents a
65 * delay.
66 */
67 void
dag_add_edge_max_data(struct dag_node * parent,struct dag_node * child,uintptr_t data)68 dag_add_edge_max_data(struct dag_node *parent, struct dag_node *child,
69 uintptr_t data)
70 {
71 util_dynarray_foreach(&parent->edges, struct dag_edge, edge) {
72 if (edge->child == child) {
73 edge->data = MAX2(edge->data, data);
74 return;
75 }
76 }
77
78 append_edge(parent, child, data);
79 }
80
81 /* Removes a single edge from the graph, promoting the child to a DAG head.
82 *
83 * Note that calling this other than through dag_prune_head() means that you
84 * need to be careful when iterating the edges of remaining nodes for NULL
85 * children.
86 */
87 void
dag_remove_edge(struct dag * dag,struct dag_edge * edge)88 dag_remove_edge(struct dag *dag, struct dag_edge *edge)
89 {
90 if (!edge->child)
91 return;
92
93 struct dag_node *child = edge->child;
94 child->parent_count--;
95 if (child->parent_count == 0)
96 list_addtail(&child->link, &dag->heads);
97
98 edge->child = NULL;
99 edge->data = 0;
100 }
101
102 /**
103 * Removes a DAG head from the graph, and moves any new dag heads into the
104 * heads list.
105 */
106 void
dag_prune_head(struct dag * dag,struct dag_node * node)107 dag_prune_head(struct dag *dag, struct dag_node *node)
108 {
109 assert(!node->parent_count);
110
111 list_delinit(&node->link);
112
113 util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
114 dag_remove_edge(dag, edge);
115 }
116 }
117
118 /**
119 * Initializes DAG node (probably embedded in some other datastructure in the
120 * user).
121 */
122 void
dag_init_node(struct dag * dag,struct dag_node * node)123 dag_init_node(struct dag *dag, struct dag_node *node)
124 {
125 util_dynarray_init(&node->edges, dag);
126 list_addtail(&node->link, &dag->heads);
127 }
128
129 struct dag_traverse_bottom_up_state {
130 struct set *seen;
131 void *data;
132 };
133
134 static void
dag_traverse_bottom_up_node(struct dag_node * node,void (* cb)(struct dag_node * node,void * data),struct dag_traverse_bottom_up_state * state)135 dag_traverse_bottom_up_node(struct dag_node *node,
136 void (*cb)(struct dag_node *node,
137 void *data),
138 struct dag_traverse_bottom_up_state *state)
139 {
140 if (_mesa_set_search(state->seen, node))
141 return;
142
143 struct util_dynarray stack;
144 util_dynarray_init(&stack, NULL);
145
146 do {
147 assert(node);
148
149 while (node->edges.size != 0) {
150 util_dynarray_append(&stack, struct dag_node *, node);
151
152 /* Push unprocessed children onto stack in reverse order. Note that
153 * it's possible for any of the children nodes to already be on the
154 * stack.
155 */
156 util_dynarray_foreach_reverse(&node->edges, struct dag_edge, edge) {
157 if (!_mesa_set_search(state->seen, edge->child)) {
158 util_dynarray_append(&stack, struct dag_node *, edge->child);
159 }
160 }
161
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
164 * children already.
165 */
166 struct dag_node *top = util_dynarray_pop(&stack, struct dag_node *);
167 if (top == node)
168 break;
169 node = top;
170 }
171
172 /* Process the node */
173 cb(node, state->data);
174 _mesa_set_add(state->seen, node);
175
176 /* Find the next unprocessed node in the stack */
177 do {
178 node = NULL;
179 if (stack.size == 0)
180 break;
181
182 node = util_dynarray_pop(&stack, struct dag_node *);
183 } while (_mesa_set_search(state->seen, node));
184 } while (node);
185
186 util_dynarray_fini(&stack);
187 }
188
189 /**
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.
192 */
193 void
dag_traverse_bottom_up(struct dag * dag,void (* cb)(struct dag_node * node,void * data),void * data)194 dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
195 void *data), void *data)
196 {
197 struct dag_traverse_bottom_up_state state = {
198 .seen = _mesa_pointer_set_create(NULL),
199 .data = data,
200 };
201
202 list_for_each_entry(struct dag_node, node, &dag->heads, link) {
203 dag_traverse_bottom_up_node(node, cb, &state);
204 }
205
206 ralloc_free(state.seen);
207 }
208
209 /**
210 * Creates an empty DAG datastructure.
211 */
212 struct dag *
dag_create(void * mem_ctx)213 dag_create(void *mem_ctx)
214 {
215 struct dag *dag = rzalloc(mem_ctx, struct dag);
216
217 list_inithead(&dag->heads);
218
219 return dag;
220 }
221
222