lib/graph/graph_ops.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(C) 2020 Marvell International Ltd.
   3  */
   4
   5 #include <stdbool.h>
   6 #include <string.h>
   7
   8 #include <rte_errno.h>
   9
  10 #include "graph_private.h"
  11
  12 /* Check whether a node has next_node to itself */
  13 static inline int
  14 node_has_loop_edge(struct node *node)
  15 {
  16         rte_edge_t i;
  17         char *name;
  18         int rc = 0;
  19
  20         for (i = 0; i < node->nb_edges; i++) {
  21                 if (strncmp(node->name, node->next_nodes[i],
  22                             RTE_NODE_NAMESIZE) == 0) {
  23                         name = node->name;
  24                         rc = 1;
  25                         SET_ERR_JMP(EINVAL, fail, "Node %s has loop to self",
  26                                     name);
  27                 }
  28         }
  29 fail:
  30         return rc;
  31 }
  32
  33 int
  34 graph_node_has_loop_edge(struct graph *graph)
  35 {
  36         struct graph_node *graph_node;
  37
  38         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  39                 if (node_has_loop_edge(graph_node->node))
  40                         return 1;
  41
  42         return 0;
  43 }
  44
  45 rte_node_t
  46 graph_src_nodes_count(struct graph *graph)
  47 {
  48         struct graph_node *graph_node;
  49         rte_node_t rc = 0;
  50
  51         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  52                 if (graph_node->node->flags & RTE_NODE_SOURCE_F)
  53                         rc++;
  54
  55         if (rc == 0)
  56                 SET_ERR_JMP(EINVAL, fail, "Graph needs at least a source node");
  57 fail:
  58         return rc;
  59 }
  60
  61 /* Check whether a node has next_node to a source node */
  62 int
  63 graph_node_has_edge_to_src_node(struct graph *graph)
  64 {
  65         struct graph_node *graph_node;
  66         struct node *node;
  67         rte_edge_t i;
  68
  69         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
  70                 for (i = 0; i < graph_node->node->nb_edges; i++) {
  71                         node = graph_node->adjacency_list[i]->node;
  72                         if (node->flags & RTE_NODE_SOURCE_F)
  73                                 SET_ERR_JMP(
  74                                         EEXIST, fail,
  75                                         "Node %s points to the source node %s",
  76                                         graph_node->node->name, node->name);
  77                 }
  78         }
  79
  80         return 0;
  81 fail:
  82         return 1;
  83 }
  84
  85 rte_node_t
  86 graph_nodes_count(struct graph *graph)
  87 {
  88         struct graph_node *graph_node;
  89         rte_node_t count = 0;
  90
  91         STAILQ_FOREACH(graph_node, &graph->node_list, next)
  92                 count++;
  93
  94         return count;
  95 }
  96
  97 void
  98 graph_mark_nodes_as_not_visited(struct graph *graph)
  99 {
 100         struct graph_node *graph_node;
 101
 102         STAILQ_FOREACH(graph_node, &graph->node_list, next)
 103                 graph_node->visited = false;
 104 }
 105
 106 int
 107 graph_bfs(struct graph *graph, struct graph_node *start)
 108 {
 109         struct graph_node **queue, *v, *tmp;
 110         uint16_t head = 0, tail = 0;
 111         rte_edge_t i;
 112         size_t sz;
 113
 114         sz = sizeof(struct graph_node *) * graph_nodes_count(graph);
 115         queue = malloc(sz);
 116         if (queue == NULL)
 117                 SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu",
 118                             sz);
 119
 120         /* BFS algorithm */
 121         queue[tail++] = start;
 122         start->visited = true;
 123         while (head != tail) {
 124                 v = queue[head++];
 125                 for (i = 0; i < v->node->nb_edges; i++) {
 126                         tmp = v->adjacency_list[i];
 127                         if (tmp->visited == false) {
 128                                 queue[tail++] = tmp;
 129                                 tmp->visited = true;
 130                         }
 131                 }
 132         }
 133
 134         free(queue);
 135         return 0;
 136
 137 fail:
 138         return -rte_errno;
 139 }
 140
 141 /* Check whether a node has connected path or parent node */
 142 int
 143 graph_has_isolated_node(struct graph *graph)
 144 {
 145         struct graph_node *graph_node;
 146
 147         graph_mark_nodes_as_not_visited(graph);
 148
 149         STAILQ_FOREACH(graph_node, &graph->node_list, next) {
 150                 if (graph_node->node->flags & RTE_NODE_SOURCE_F) {
 151                         if (graph_node->node->nb_edges == 0)
 152                                 SET_ERR_JMP(EINVAL, fail,
 153                                             "%s node needs minimum one edge",
 154                                             graph_node->node->name);
 155                         if (graph_bfs(graph, graph_node))
 156                                 goto fail;
 157                 }
 158         }
 159
 160         STAILQ_FOREACH(graph_node, &graph->node_list, next)
 161                 if (graph_node->visited == false)
 162                         SET_ERR_JMP(EINVAL, fail, "Found isolated node %s",
 163                                     graph_node->node->name);
 164
 165         return 0;
 166 fail:
 167         return 1;
 168 }