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   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 */
126void
127dag_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 */
145struct dag *
146dag_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