1 /* SPDX-License-Identifier: BSD-3-Clause 2 * Copyright(C) 2020 Marvell International Ltd. 3 */ 4 5 #include <stdbool.h> 6 #include <stdlib.h> 7 #include <string.h> 8 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 } 170