1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(C) 2020 Marvell International Ltd.
8 #include <rte_common.h>
11 #include "graph_private.h"
13 /* Check whether a node has next_node to itself */
15 node_has_loop_edge(struct node *node)
21 for (i = 0; i < node->nb_edges; i++) {
22 if (strncmp(node->name, node->next_nodes[i],
23 RTE_NODE_NAMESIZE) == 0) {
26 SET_ERR_JMP(EINVAL, fail, "Node %s has loop to self",
35 graph_node_has_loop_edge(struct graph *graph)
37 struct graph_node *graph_node;
39 STAILQ_FOREACH(graph_node, &graph->node_list, next)
40 if (node_has_loop_edge(graph_node->node))
47 graph_src_nodes_count(struct graph *graph)
49 struct graph_node *graph_node;
52 STAILQ_FOREACH(graph_node, &graph->node_list, next)
53 if (graph_node->node->flags & RTE_NODE_SOURCE_F)
57 SET_ERR_JMP(EINVAL, fail, "Graph needs at least a source node");
62 /* Check whether a node has next_node to a source node */
64 graph_node_has_edge_to_src_node(struct graph *graph)
66 struct graph_node *graph_node;
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)
76 "Node %s points to the source node %s",
77 graph_node->node->name, node->name);
87 graph_nodes_count(struct graph *graph)
89 struct graph_node *graph_node;
92 STAILQ_FOREACH(graph_node, &graph->node_list, next)
99 graph_mark_nodes_as_not_visited(struct graph *graph)
101 struct graph_node *graph_node;
103 STAILQ_FOREACH(graph_node, &graph->node_list, next)
104 graph_node->visited = false;
108 graph_bfs(struct graph *graph, struct graph_node *start)
110 struct graph_node **queue, *v, *tmp;
111 uint16_t head = 0, tail = 0;
115 sz = sizeof(struct graph_node *) * graph_nodes_count(graph);
118 SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu",
122 queue[tail++] = start;
123 start->visited = true;
124 while (head != tail) {
126 for (i = 0; i < v->node->nb_edges; i++) {
127 tmp = v->adjacency_list[i];
128 if (tmp->visited == false) {
142 /* Check whether a node has connected path or parent node */
144 graph_has_isolated_node(struct graph *graph)
146 struct graph_node *graph_node;
148 graph_mark_nodes_as_not_visited(graph);
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))
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);