1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(C) 2020 Marvell International Ltd.
10 #include "graph_private.h"
12 /* Check whether a node has next_node to itself */
14 node_has_loop_edge(struct node *node)
20 for (i = 0; i < node->nb_edges; i++) {
21 if (strncmp(node->name, node->next_nodes[i],
22 RTE_NODE_NAMESIZE) == 0) {
25 SET_ERR_JMP(EINVAL, fail, "Node %s has loop to self",
34 graph_node_has_loop_edge(struct graph *graph)
36 struct graph_node *graph_node;
38 STAILQ_FOREACH(graph_node, &graph->node_list, next)
39 if (node_has_loop_edge(graph_node->node))
46 graph_src_nodes_count(struct graph *graph)
48 struct graph_node *graph_node;
51 STAILQ_FOREACH(graph_node, &graph->node_list, next)
52 if (graph_node->node->flags & RTE_NODE_SOURCE_F)
56 SET_ERR_JMP(EINVAL, fail, "Graph needs at least a source node");
61 /* Check whether a node has next_node to a source node */
63 graph_node_has_edge_to_src_node(struct graph *graph)
65 struct graph_node *graph_node;
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)
75 "Node %s points to the source node %s",
76 graph_node->node->name, node->name);
86 graph_nodes_count(struct graph *graph)
88 struct graph_node *graph_node;
91 STAILQ_FOREACH(graph_node, &graph->node_list, next)
98 graph_mark_nodes_as_not_visited(struct graph *graph)
100 struct graph_node *graph_node;
102 STAILQ_FOREACH(graph_node, &graph->node_list, next)
103 graph_node->visited = false;
107 graph_bfs(struct graph *graph, struct graph_node *start)
109 struct graph_node **queue, *v, *tmp;
110 uint16_t head = 0, tail = 0;
114 sz = sizeof(struct graph_node *) * graph_nodes_count(graph);
117 SET_ERR_JMP(ENOMEM, fail, "Failed to alloc BFS queue of %zu",
121 queue[tail++] = start;
122 start->visited = true;
123 while (head != tail) {
125 for (i = 0; i < v->node->nb_edges; i++) {
126 tmp = v->adjacency_list[i];
127 if (tmp->visited == false) {
141 /* Check whether a node has connected path or parent node */
143 graph_has_isolated_node(struct graph *graph)
145 struct graph_node *graph_node;
147 graph_mark_nodes_as_not_visited(graph);
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))
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);