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 */
33void
34dag_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 */
58void
59dag_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 */
77void
78dag_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 */
93void
94dag_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
100struct dag_traverse_bottom_up_state {
101   struct set *seen;
102   void *data;
103};
104
105static void
106dag_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 */
164void
165dag_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 */
183struct dag *
184dag_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