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