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 along
  20  * with this program; see the file COPYING; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  22  */
  23 #include <zebra.h>
  24 #include "graph.h"
  25 #include "memory.h"
  26
  27 DEFINE_MTYPE_STATIC(LIB, GRAPH,      "Graph")
  28 DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node")
  29 struct graph *
  30 graph_new ()
  31 {
  32   struct graph *graph = XCALLOC (MTYPE_GRAPH, sizeof(struct graph));
  33   graph->nodes = vector_init (VECTOR_MIN_SIZE);
  34
  35   return graph;
  36 }
  37
  38 struct graph_node *
  39 graph_new_node (struct graph *graph, void *data, void (*del) (void*))
  40 {
  41   struct graph_node *node =
  42      XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node));
  43
  44   node->from = vector_init (VECTOR_MIN_SIZE);
  45   node->to   = vector_init (VECTOR_MIN_SIZE);
  46   node->data = data;
  47   node->del  = del;
  48
  49   vector_set (graph->nodes, node);
  50
  51   return node;
  52 }
  53
  54 static void
  55 vector_remove (vector v, unsigned int ix)
  56 {
  57   if (ix >= v->active)
  58     return;
  59
  60   /* v->active is guaranteed >= 1 because ix can't be lower than 0
  61    * and v->active is > ix. */
  62   v->active--;
  63   /* if ix == v->active--, we set the item to itself, then to NULL...
  64    * still correct, no check neccessary. */
  65   v->index[ix] = v->index[v->active];
  66   v->index[v->active] = NULL;
  67 }
  68
  69 void
  70 graph_delete_node (struct graph *graph, struct graph_node *node)
  71 {
  72   if (!node) return;
  73
  74   // an adjacent node
  75   struct graph_node *adj;
  76
  77   // remove all edges from other nodes to us
  78   for (unsigned int i = vector_active (node->from); i--; /**/)
  79     {
  80       adj = vector_slot (node->from, i);
  81       graph_remove_edge (adj, node);
  82     }
  83
  84   // remove all edges from us to other nodes
  85   for (unsigned int i = vector_active (node->to); i--; /**/)
  86     {
  87       adj = vector_slot (node->to, i);
  88       graph_remove_edge (node, adj);
  89     }
  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 = vector_active (graph->nodes); i--; /**/)
 101     if (vector_slot (graph->nodes, i) == node)
 102       {
 103         vector_remove (graph->nodes, i);
 104         break;
 105       }
 106
 107   // free the node itself
 108   XFREE (MTYPE_GRAPH_NODE, node);
 109 }
 110
 111 struct graph_node *
 112 graph_add_edge (struct graph_node *from, struct graph_node *to)
 113 {
 114   vector_set (from->to, to);
 115   vector_set (to->from, from);
 116   return to;
 117 }
 118
 119 void
 120 graph_remove_edge (struct graph_node *from, struct graph_node *to)
 121 {
 122   // remove from from to->from
 123   for (unsigned int i = vector_active (to->from); i--; /**/)
 124     if (vector_slot (to->from, i) == from)
 125       {
 126         vector_remove (to->from, i);
 127         break;
 128       }
 129   // remove to from from->to
 130   for (unsigned int i = vector_active (from->to); i--; /**/)
 131     if (vector_slot (from->to, i) == to)
 132       {
 133         vector_remove (from->to, i);
 134         break;
 135       }
 136 }
 137
 138 void
 139 graph_delete_graph (struct graph *graph)
 140 {
 141   // delete each node in the graph
 142   for (unsigned int i = vector_active (graph->nodes); i--; /**/)
 143     graph_delete_node (graph, vector_slot (graph->nodes, i));
 144
 145   vector_free (graph->nodes);
 146   XFREE (MTYPE_GRAPH, graph);
 147 }