src/util/dag.c

   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
  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
  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
  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
  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
 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
 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 *
 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