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
node_has_loop_edge(struct node * node)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
graph_node_has_loop_edge(struct graph * graph)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
graph_src_nodes_count(struct graph * graph)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
graph_node_has_edge_to_src_node(struct graph * graph)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
graph_nodes_count(struct graph * graph)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
graph_mark_nodes_as_not_visited(struct graph * graph)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
graph_bfs(struct graph * graph,struct graph_node * start)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
graph_has_isolated_node(struct graph * graph)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 }
169