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