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   if (ix >= v->active)
  59     return;
  60
  61   /* v->active is guaranteed >= 1 because ix can't be lower than 0
  62    * and v->active is > ix. */
  63   v->active--;
  64   /* if ix == v->active--, we set the item to itself, then to NULL...
  65    * still correct, no check neccessary. */
  66   v->index[ix] = v->index[v->active];
  67   v->index[v->active] = NULL;
  68 }
  69
  70 void
  71 graph_delete_node (struct graph *graph, struct graph_node *node)
  72 {
  73   if (!node) return;
  74
  75   // an adjacent node
  76   struct graph_node *adj;
  77
  78   // remove all edges from other nodes to us
  79   for (unsigned int i = vector_active (node->from); i--; /**/)
  80     {
  81       adj = vector_slot (node->from, i);
  82       graph_remove_edge (adj, node);
  83     }
  84
  85   // remove all edges from us to other nodes
  86   for (unsigned int i = vector_active (node->to); i--; /**/)
  87     {
  88       adj = vector_slot (node->to, i);
  89       graph_remove_edge (node, adj);
  90     }
  91
  92   // if there is a deletion callback, call it
  93   if (node->del && node->data)
  94     (*node->del) (node->data);
  95
  96   // free adjacency lists
  97   vector_free (node->to);
  98   vector_free (node->from);
  99
 100   // remove node from graph->nodes
 101   for (unsigned int i = vector_active (graph->nodes); i--; /**/)
 102     if (vector_slot (graph->nodes, i) == node)
 103       {
 104         vector_remove (graph->nodes, i);
 105         break;
 106       }
 107
 108   // free the node itself
 109   XFREE (MTYPE_GRAPH_NODE, node);
 110 }
 111
 112 struct graph_node *
 113 graph_add_edge (struct graph_node *from, struct graph_node *to)
 114 {
 115   vector_set (from->to, to);
 116   vector_set (to->from, from);
 117   return to;
 118 }
 119
 120 void
 121 graph_remove_edge (struct graph_node *from, struct graph_node *to)
 122 {
 123   // remove from from to->from
 124   for (unsigned int i = vector_active (to->from); i--; /**/)
 125     if (vector_slot (to->from, i) == from)
 126       {
 127         vector_remove (to->from, i);
 128         break;
 129       }
 130   // remove to from from->to
 131   for (unsigned int i = vector_active (from->to); i--; /**/)
 132     if (vector_slot (from->to, i) == to)
 133       {
 134         vector_remove (from->to, i);
 135         break;
 136       }
 137 }
 138
 139 void
 140 graph_delete_graph (struct graph *graph)
 141 {
 142   // delete each node in the graph
 143   for (unsigned int i = vector_active (graph->nodes); i--; /**/)
 144     graph_delete_node (graph, vector_slot (graph->nodes, i));
 145
 146   vector_free (graph->nodes);
 147   XFREE (MTYPE_GRAPH, graph);
 148 }