Mesa (main): util/dag: Add dag_add_edge_max_data

[GitLab Mirror]

Module: Mesa
Branch: main
Commit: b8fc7a08f9fac2822a58473b6806638709060e96
URL:    http://cgit.freedesktop.org/mesa/mesa/commit/?id=b8fc7a08f9fac2822a58473b6806638709060e96

Author: Connor Abbott <cwabbott0 at gmail.com>
Date:   Mon Nov  8 15:31:29 2021 +0100

util/dag: Add dag_add_edge_max_data

This will be useful for when the edge data represents a delay of some
sort, like it will with ir3.

Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/13722>

---

 src/util/dag.c              | 45 +++++++++++++++++++++++++++++++-------
 src/util/dag.h              |  1 +
 src/util/tests/dag_test.cpp | 53 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 91 insertions(+), 8 deletions(-)

diff --git a/src/util/dag.c b/src/util/dag.c
index 97fd7386a49..8625647f887 100644
--- a/src/util/dag.c
+++ b/src/util/dag.c
@@ -24,6 +24,21 @@
 #include "util/set.h"
 #include "util/dag.h"
 
+static void
+append_edge(struct dag_node *parent, struct dag_node *child, uintptr_t data)
+{
+   /* Remove the child as a DAG head. */
+   list_delinit(&child->link);
+
+   struct dag_edge edge = {
+      .child = child,
+      .data = data,
+   };
+
+   util_dynarray_append(&parent->edges, struct dag_edge, edge);
+   child->parent_count++;
+}
+
 /**
  * Adds a directed edge from the parent node to the child.
  *
@@ -37,16 +52,30 @@ dag_add_edge(struct dag_node *parent, struct dag_node *child, uintptr_t data)
       if (edge->child == child && edge->data == data)
          return;
    }
-   /* Remove the child as a DAG head. */
-   list_delinit(&child->link);
 
-   struct dag_edge edge = {
-      .child = child,
-      .data = data,
-   };
+   append_edge(parent, child, data);
+}
 
-   util_dynarray_append(&parent->edges, struct dag_edge, edge);
-   child->parent_count++;
+/**
+ * Adds a directed edge from the parent node to the child.
+ *
+ * Both nodes should have been initialized with dag_init_node(). If there is
+ * already an existing edge, the data is updated to the maximum of the
+ * previous data and the new data. This is useful if the data represents a
+ * delay.
+ */
+void
+dag_add_edge_max_data(struct dag_node *parent, struct dag_node *child,
+                      uintptr_t data)
+{
+   util_dynarray_foreach(&parent->edges, struct dag_edge, edge) {
+      if (edge->child == child) {
+         edge->data = MAX2(edge->data, data);
+         return;
+      }
+   }
+
+   append_edge(parent, child, data);
 }
 
 /* Removes a single edge from the graph, promoting the child to a DAG head.
diff --git a/src/util/dag.h b/src/util/dag.h
index fbc3ed93d48..3ede13d7548 100644
--- a/src/util/dag.h
+++ b/src/util/dag.h
@@ -53,6 +53,7 @@ struct dag {
 struct dag *dag_create(void *mem_ctx);
 void dag_init_node(struct dag *dag, struct dag_node *node);
 void dag_add_edge(struct dag_node *parent, struct dag_node *child, uintptr_t data);
+void dag_add_edge_max_data(struct dag_node *parent, struct dag_node *child, uintptr_t data);
 void dag_remove_edge(struct dag *dag, struct dag_edge *edge);
 void dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
                                                         void *data), void *data);
diff --git a/src/util/tests/dag_test.cpp b/src/util/tests/dag_test.cpp
index d8c2ae9483c..6cace736972 100644
--- a/src/util/tests/dag_test.cpp
+++ b/src/util/tests/dag_test.cpp
@@ -56,6 +56,16 @@ struct node: public dag_node {
                    static_cast<struct dag_node *>(&child), 0);
       return child;
    }
+
+   void add_edge(struct node &child, uintptr_t data) {
+      dag_add_edge(static_cast<struct dag_node *>(this),
+                   static_cast<struct dag_node *>(&child), data);
+   }
+
+   void add_edge_max_data(struct node &child, uintptr_t data) {
+      dag_add_edge_max_data(static_cast<struct dag_node *>(this),
+                            static_cast<struct dag_node *>(&child), data);
+   }
 };
 
 static void output_cb(struct dag_node *dag_node, void *data)
@@ -151,6 +161,49 @@ TEST_F(dag_test, simple)
    TEST_CHECK();
 }
 
+TEST_F(dag_test, duplicate_edge)
+{
+   INIT_NODES(3);
+
+   node[0].add_edge(node[1], 0);
+   node[0].add_edge(node[1], 1);
+   node[0].add_edge(node[2], 0);
+
+   EXPECT_EQ(util_dynarray_num_elements(&node[0].edges, struct dag_edge), 3);
+
+   SET_EXPECTED(1, 2, 0);
+
+   dag_traverse_bottom_up(dag, output_cb, &actual);
+
+   TEST_CHECK();
+}
+
+TEST_F(dag_test, duplicate_edge_max_data)
+{
+   INIT_NODES(3);
+
+   node[0].add_edge_max_data(node[1], 0);
+   node[0].add_edge_max_data(node[1], 1);
+   node[0].add_edge_max_data(node[2], 0);
+
+   EXPECT_EQ(util_dynarray_num_elements(&node[0].edges, struct dag_edge), 2);
+
+   util_dynarray_foreach (&node[0].edges, struct dag_edge, edge) {
+      if (edge->child == &node[1]) {
+         EXPECT_EQ(edge->data, 1);
+      } else {
+         EXPECT_EQ(edge->child, &node[2]);
+         EXPECT_EQ(edge->data, 0);
+      }
+   }
+
+   SET_EXPECTED(1, 2, 0);
+
+   dag_traverse_bottom_up(dag, output_cb, &actual);
+
+   TEST_CHECK();
+}
+
 TEST_F(dag_test, simple_many_children)
 {
    INIT_NODES(6);