On 4/5/20 10:55 AM, jer...@marvell.com wrote:
> From: Jerin Jacob <jer...@marvell.com>
>
> Adding internal graph API helpers support to check whether a graph has
> isolated nodes and any node have a loop to itself and BFS
> algorithm implementation etc.
>
> Signed-off-by: Jerin Jacob <jer...@marvell.com>
> Signed-off-by: Nithin Dabilpuram <ndabilpu...@marvell.com>
> ---
[...]> +/* 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;
> +}
In general, I'd expect such warnings/errors to be at usage - this is
simple test and its job should be just return true/false. But in this
particular case I guess it is always an error (no cycles in graph
allowed) so I'm fine if you leave it here.
> +
> +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;
> +}
[...]
> +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;
> +}
What is the purpose of this function? It looks like just marking as
visited. Then maybe change the name to graph_mark_bfs() or something
like that.
> +
> +/* 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;
You don't want to clear visited because it will not be used or cleared
on next call?
With regards
Andrzej Ostruszka
