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 util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
115 dag_traverse_bottom_up_node(edge->child, cb, state);
116 }
117
118 cb(node, state->data);
119 _mesa_set_add(state->seen, node);
120 }
121
122 /**
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.
125 */
126 void
dag_traverse_bottom_up(struct dag * dag,void (* cb)(struct dag_node * node,void * data),void * data)127 dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
128 void *data), void *data)
129 {
130 struct dag_traverse_bottom_up_state state = {
131 .seen = _mesa_pointer_set_create(NULL),
132 .data = data,
133 };
134
135 list_for_each_entry(struct dag_node, node, &dag->heads, link) {
136 dag_traverse_bottom_up_node(node, cb, &state);
137 }
138
139 ralloc_free(state.seen);
140 }
141
142 /**
143 * Creates an empty DAG datastructure.
144 */
145 struct dag *
dag_create(void * mem_ctx)146 dag_create(void *mem_ctx)
147 {
148 struct dag *dag = rzalloc(mem_ctx, struct dag);
149
150 list_inithead(&dag->heads);
151
152 return dag;
153 }
154
155