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 /**
28 * Adds a directed edge from the parent node to the child.
29 *
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.
32 */
33 void
dag_add_edge(struct dag_node * parent,struct dag_node * child,void * data)34 dag_add_edge(struct dag_node *parent, struct dag_node *child, void *data)
35 {
36 util_dynarray_foreach(&parent->edges, struct dag_edge, edge) {
37 if (edge->child == child && edge->data == data)
38 return;
39 }
40 /* Remove the child as a DAG head. */
41 list_delinit(&child->link);
42
43 struct dag_edge edge = {
44 .child = child,
45 .data = data,
46 };
47
48 util_dynarray_append(&parent->edges, struct dag_edge, edge);
49 child->parent_count++;
50 }
51
52 /* Removes a single edge from the graph, promoting the child to a DAG head.
53 *
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
56 * children.
57 */
58 void
dag_remove_edge(struct dag * dag,struct dag_edge * edge)59 dag_remove_edge(struct dag *dag, struct dag_edge *edge)
60 {
61 if (!edge->child)
62 return;
63
64 struct dag_node *child = edge->child;
65 child->parent_count--;
66 if (child->parent_count == 0)
67 list_addtail(&child->link, &dag->heads);
68
69 edge->child = NULL;
70 edge->data = NULL;
71 }
72
73 /**
74 * Removes a DAG head from the graph, and moves any new dag heads into the
75 * heads list.
76 */
77 void
dag_prune_head(struct dag * dag,struct dag_node * node)78 dag_prune_head(struct dag *dag, struct dag_node *node)
79 {
80 assert(!node->parent_count);
81
82 list_delinit(&node->link);
83
84 util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
85 dag_remove_edge(dag, edge);
86 }
87 }
88
89 /**
90 * Initializes DAG node (probably embedded in some other datastructure in the
91 * user).
92 */
93 void
dag_init_node(struct dag * dag,struct dag_node * node)94 dag_init_node(struct dag *dag, struct dag_node *node)
95 {
96 util_dynarray_init(&node->edges, dag);
97 list_addtail(&node->link, &dag->heads);
98 }
99
100 struct dag_traverse_bottom_up_state {
101 struct set *seen;
102 void *data;
103 };
104
105 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)106 dag_traverse_bottom_up_node(struct dag_node *node,
107 void (*cb)(struct dag_node *node,
108 void *data),
109 struct dag_traverse_bottom_up_state *state)
110 {
111 if (_mesa_set_search(state->seen, node))
112 return;
113
114 struct util_dynarray stack;
115 util_dynarray_init(&stack, NULL);
116
117 do {
118 assert(node);
119
120 while (node->edges.size != 0) {
121 util_dynarray_append(&stack, struct dag_node *, node);
122
123 /* Push unprocessed children onto stack in reverse order. Note that
124 * it's possible for any of the children nodes to already be on the
125 * stack.
126 */
127 util_dynarray_foreach_reverse(&node->edges, struct dag_edge, edge) {
128 if (!_mesa_set_search(state->seen, edge->child)) {
129 util_dynarray_append(&stack, struct dag_node *, edge->child);
130 }
131 }
132
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
135 * children already.
136 */
137 struct dag_node *top = util_dynarray_pop(&stack, struct dag_node *);
138 if (top == node)
139 break;
140 node = top;
141 }
142
143 /* Process the node */
144 cb(node, state->data);
145 _mesa_set_add(state->seen, node);
146
147 /* Find the next unprocessed node in the stack */
148 do {
149 node = NULL;
150 if (stack.size == 0)
151 break;
152
153 node = util_dynarray_pop(&stack, struct dag_node *);
154 } while (_mesa_set_search(state->seen, node));
155 } while (node);
156
157 util_dynarray_fini(&stack);
158 }
159
160 /**
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.
163 */
164 void
dag_traverse_bottom_up(struct dag * dag,void (* cb)(struct dag_node * node,void * data),void * data)165 dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
166 void *data), void *data)
167 {
168 struct dag_traverse_bottom_up_state state = {
169 .seen = _mesa_pointer_set_create(NULL),
170 .data = data,
171 };
172
173 list_for_each_entry(struct dag_node, node, &dag->heads, link) {
174 dag_traverse_bottom_up_node(node, cb, &state);
175 }
176
177 ralloc_free(state.seen);
178 }
179
180 /**
181 * Creates an empty DAG datastructure.
182 */
183 struct dag *
dag_create(void * mem_ctx)184 dag_create(void *mem_ctx)
185 {
186 struct dag *dag = rzalloc(mem_ctx, struct dag);
187
188 list_inithead(&dag->heads);
189
190 return dag;
191 }
192
193