Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0-or-later
       2             : /*
       3             :  * Graph data structure.
       4             :  *
       5             :  * --
       6             :  * Copyright (C) 2016 Cumulus Networks, Inc.
       7             :  */
       8             : #include <zebra.h>
       9             : #include "graph.h"
      10             : #include "memory.h"
      11             : #include "buffer.h"
      12             : 
      13          12 : DEFINE_MTYPE_STATIC(LIB, GRAPH, "Graph");
      14          12 : DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node");
      15        6438 : struct graph *graph_new(void)
      16             : {
      17        6438 :         struct graph *graph = XCALLOC(MTYPE_GRAPH, sizeof(struct graph));
      18        6438 :         graph->nodes = vector_init(VECTOR_MIN_SIZE);
      19             : 
      20        6438 :         return graph;
      21             : }
      22             : 
      23        6438 : void graph_delete_graph(struct graph *graph)
      24             : {
      25       77636 :         for (unsigned int i = vector_active(graph->nodes); i--; /**/)
      26       71198 :                 graph_delete_node(graph, vector_slot(graph->nodes, i));
      27             : 
      28        6438 :         vector_free(graph->nodes);
      29        6438 :         XFREE(MTYPE_GRAPH, graph);
      30        6438 : }
      31             : 
      32       71198 : struct graph_node *graph_new_node(struct graph *graph, void *data,
      33             :                                   void (*del)(void *))
      34             : {
      35       71198 :         struct graph_node *node =
      36       71198 :                 XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node));
      37             : 
      38       71198 :         node->from = vector_init(VECTOR_MIN_SIZE);
      39       71198 :         node->to = vector_init(VECTOR_MIN_SIZE);
      40       71198 :         node->data = data;
      41       71198 :         node->del = del;
      42             : 
      43       71198 :         vector_set(graph->nodes, node);
      44             : 
      45       71198 :         return node;
      46             : }
      47             : 
      48      238994 : static void graph_vector_remove(vector v, unsigned int ix)
      49             : {
      50      238994 :         if (ix >= v->active)
      51             :                 return;
      52             : 
      53             :         /* v->active is guaranteed >= 1 because ix can't be lower than 0
      54             :          * and v->active is > ix. */
      55      238994 :         v->active--;
      56             :         /* if ix == v->active--, we set the item to itself, then to NULL...
      57             :          * still correct, no check necessary. */
      58      238994 :         v->index[ix] = v->index[v->active];
      59      238994 :         v->index[v->active] = NULL;
      60             : }
      61             : 
      62       71198 : void graph_delete_node(struct graph *graph, struct graph_node *node)
      63             : {
      64       71198 :         if (!node)
      65             :                 return;
      66             : 
      67             :         // an adjacent node
      68       71198 :         struct graph_node *adj;
      69             : 
      70             :         // remove all edges from other nodes to us
      71      137214 :         for (unsigned int i = vector_active(node->from); i--; /**/) {
      72       66016 :                 adj = vector_slot(node->from, i);
      73       66016 :                 graph_remove_edge(adj, node);
      74             :         }
      75             : 
      76             :         // remove all edges from us to other nodes
      77       82786 :         for (unsigned int i = vector_active(node->to); i--; /**/) {
      78       11588 :                 adj = vector_slot(node->to, i);
      79       11588 :                 graph_remove_edge(node, adj);
      80             :         }
      81             : 
      82             :         // if there is a deletion callback, call it
      83       71198 :         if (node->del && node->data)
      84       64904 :                 (*node->del)(node->data);
      85             : 
      86             :         // free adjacency lists
      87       71198 :         vector_free(node->to);
      88       71198 :         vector_free(node->from);
      89             : 
      90             :         // remove node from graph->nodes
      91       71198 :         for (unsigned int i = vector_active(graph->nodes); i--; /**/)
      92       71198 :                 if (vector_slot(graph->nodes, i) == node) {
      93       71198 :                         graph_vector_remove(graph->nodes, i);
      94       71198 :                         break;
      95             :                 }
      96             : 
      97             :         // free the node itself
      98       71198 :         XFREE(MTYPE_GRAPH_NODE, node);
      99             : }
     100             : 
     101       83898 : struct graph_node *graph_add_edge(struct graph_node *from,
     102             :                                   struct graph_node *to)
     103             : {
     104       83898 :         vector_set(from->to, to);
     105       83898 :         vector_set(to->from, from);
     106       83898 :         return to;
     107             : }
     108             : 
     109       83898 : void graph_remove_edge(struct graph_node *from, struct graph_node *to)
     110             : {
     111             :         // remove from from to->from
     112       84260 :         for (unsigned int i = vector_active(to->from); i--; /**/)
     113       84260 :                 if (vector_slot(to->from, i) == from) {
     114       83898 :                         graph_vector_remove(to->from, i);
     115       83898 :                         break;
     116             :                 }
     117             :         // remove to from from->to
     118       84104 :         for (unsigned int i = vector_active(from->to); i--; /**/)
     119       84104 :                 if (vector_slot(from->to, i) == to) {
     120       83898 :                         graph_vector_remove(from->to, i);
     121       83898 :                         break;
     122             :                 }
     123       83898 : }
     124             : 
     125           0 : struct graph_node *graph_find_node(struct graph *graph, void *data)
     126             : {
     127           0 :         struct graph_node *g;
     128             : 
     129           0 :         for (unsigned int i = vector_active(graph->nodes); i--; /**/) {
     130           0 :                 g = vector_slot(graph->nodes, i);
     131           0 :                 if (g->data == data)
     132           0 :                         return g;
     133             :         }
     134             : 
     135             :         return NULL;
     136             : }
     137             : 
     138           0 : bool graph_has_edge(struct graph_node *from, struct graph_node *to)
     139             : {
     140           0 :         for (unsigned int i = vector_active(from->to); i--; /**/)
     141           0 :                 if (vector_slot(from->to, i) == to)
     142             :                         return true;
     143             : 
     144             :         return false;
     145             : }
     146             : 
     147           0 : static void _graph_dfs(struct graph *graph, struct graph_node *start,
     148             :                        vector visited,
     149             :                        void (*dfs_cb)(struct graph_node *, void *), void *arg)
     150             : {
     151             :         /* check that we have not visited this node */
     152           0 :         for (unsigned int i = 0; i < vector_active(visited); i++) {
     153           0 :                 if (start == vector_slot(visited, i))
     154             :                         return;
     155             :         }
     156             : 
     157             :         /* put this node in visited stack */
     158           0 :         vector_ensure(visited, vector_active(visited));
     159           0 :         vector_set_index(visited, vector_active(visited), start);
     160             : 
     161             :         /* callback */
     162           0 :         dfs_cb(start, arg);
     163             : 
     164             :         /* recurse into children */
     165           0 :         for (unsigned int i = vector_active(start->to); i--; /**/) {
     166           0 :                 struct graph_node *c = vector_slot(start->to, i);
     167             : 
     168           0 :                 _graph_dfs(graph, c, visited, dfs_cb, arg);
     169             :         }
     170             : }
     171             : 
     172           0 : void graph_dfs(struct graph *graph, struct graph_node *start,
     173             :                void (*dfs_cb)(struct graph_node *, void *), void *arg)
     174             : {
     175           0 :         vector visited = vector_init(VECTOR_MIN_SIZE);
     176             : 
     177           0 :         _graph_dfs(graph, start, visited, dfs_cb, arg);
     178           0 :         vector_free(visited);
     179           0 : }
     180             : 
     181             : #ifndef BUILDING_CLIPPY
     182             : 
     183           0 : void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf)
     184             : {
     185           0 :         char nbuf[64];
     186             : 
     187           0 :         for (unsigned int i = 0; i < vector_active(gn->to); i++) {
     188           0 :                 struct graph_node *adj = vector_slot(gn->to, i);
     189             : 
     190           0 :                 snprintf(nbuf, sizeof(nbuf), "    n%p -> n%p;\n", gn, adj);
     191           0 :                 buffer_putstr(buf, nbuf);
     192             :         }
     193           0 : }
     194             : 
     195           0 : char *graph_dump_dot(struct graph *graph, struct graph_node *start,
     196             :                      void (*pcb)(struct graph_node *, struct buffer *))
     197             : {
     198           0 :         struct buffer *buf = buffer_new(0);
     199           0 :         char *ret;
     200             : 
     201           0 :         pcb = (pcb) ? pcb : graph_dump_dot_default_print_cb;
     202           0 :         buffer_putstr(buf, "digraph {\n");
     203             : 
     204           0 :         graph_dfs(graph, start, (void (*)(struct graph_node *, void *))pcb,
     205             :                   buf);
     206             : 
     207           0 :         buffer_putstr(buf, "}\n");
     208             : 
     209           0 :         ret = buffer_getstr(buf);
     210           0 :         buffer_free(buf);
     211             : 
     212           0 :         return ret;
     213             : }
     214             : 
     215             : #endif /* BUILDING_CLIPPY */