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