lib/graph.c

   1 /*
   2  * Graph data structure.
   3  *
   4  * --
   5  * Copyright (C) 2016 Cumulus Networks, Inc.
   6  *
   7  * This file is part of GNU Zebra.
   8  *
   9  * GNU Zebra is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the
  11  * Free Software Foundation; either version 2, or (at your option) any
  12  * later version.
  13  *
  14  * GNU Zebra is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with GNU Zebra; see the file COPYING.  If not, write to the Free
  21  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  22  * 02111-1307, USA.
  23  */
  24 #include <zebra.h>
  25 #include "graph.h"
  26 #include "memory.h"
  27
  28 DEFINE_MTYPE_STATIC(LIB, GRAPH,      "Graph")
  29 DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node")
  30 struct graph *
  31 graph_new ()
  32 {
  33   struct graph *graph = XCALLOC (MTYPE_GRAPH, sizeof(struct graph));
  34   graph->nodes = vector_init (VECTOR_MIN_SIZE);
  35
  36   return graph;
  37 }
  38
  39 struct graph_node *
  40 graph_new_node (struct graph *graph, void *data, void (*del) (void*))
  41 {
  42   struct graph_node *node =
  43      XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node));
  44
  45   node->from = vector_init (VECTOR_MIN_SIZE);
  46   node->to   = vector_init (VECTOR_MIN_SIZE);
  47   node->data = data;
  48   node->del  = del;
  49
  50   vector_set (graph->nodes, node);
  51
  52   return node;
  53 }
  54
  55 static void
  56 vector_remove (vector v, unsigned int ix)
  57 {
  58   vector_unset (v, ix);
  59   if (ix == vector_active (v)) return;
  60   for (; ix < vector_active (v) - 1; ix++)
  61     v->index[ix] = v->index[ix+1];
  62   v->active--;
  63 }
  64
  65 void
  66 graph_delete_node (struct graph *graph, struct graph_node *node)
  67 {
  68   if (!node) return;
  69
  70   // an adjacent node
  71   struct graph_node *adj;
  72
  73   // remove all edges from other nodes to us
  74   vector edges = vector_copy (node->from);
  75   for (unsigned int i = 0; i < vector_active (edges); i++)
  76     {
  77       adj = vector_slot (edges, i);
  78       graph_remove_edge (adj, node);
  79     }
  80   vector_free (edges);
  81
  82   // remove all edges from us to other nodes
  83   edges = vector_copy (node->to);
  84   for (unsigned int i = 0; i < vector_active (edges); i++)
  85     {
  86       adj = vector_slot (edges, i);
  87       graph_remove_edge (node, adj);
  88     }
  89   vector_free (edges);
  90
  91   // if there is a deletion callback, call it
  92   if (node->del && node->data)
  93     (*node->del) (node->data);
  94
  95   // free adjacency lists
  96   vector_free (node->to);
  97   vector_free (node->from);
  98
  99   // remove node from graph->nodes
 100   for (unsigned int i = 0; i < vector_active (graph->nodes); i++)
 101     if (vector_slot (graph->nodes, i) == node)
 102       vector_remove (graph->nodes, i);
 103
 104   // free the node itself
 105   XFREE (MTYPE_GRAPH_NODE, node);
 106 }
 107
 108 struct graph_node *
 109 graph_add_edge (struct graph_node *from, struct graph_node *to)
 110 {
 111   vector_set (from->to, to);
 112   vector_set (to->from, from);
 113   return to;
 114 }
 115
 116 void
 117 graph_remove_edge (struct graph_node *from, struct graph_node *to)
 118 {
 119   // remove from from to->from
 120   for (unsigned int i = 0; i < vector_active (to->from); i++)
 121     if (vector_slot (to->from, i) == from)
 122       vector_remove (to->from, i);
 123   // remove to from from->to
 124   for (unsigned int i = 0; i < vector_active (from->to); i++)
 125     if (vector_slot (from->to, i) == to)
 126       vector_remove (from->to, i);
 127 }
 128
 129 void
 130 graph_delete_graph (struct graph *graph)
 131 {
 132   // delete each node in the graph
 133   for (unsigned int i = 0; i < vector_active (graph->nodes); i++)
 134     graph_delete_node (graph, vector_slot (graph->nodes, i));
 135
 136   vector_free (graph->nodes);
 137   XFREE (MTYPE_GRAPH, graph);
 138 }