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