Branch data     Line data    Source code

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