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 *graph_new()
  30 {
  31         struct graph *graph = XCALLOC(MTYPE_GRAPH, sizeof(struct graph));
  32         graph->nodes = vector_init(VECTOR_MIN_SIZE);
  33
  34         return graph;
  35 }
  36
  37 struct graph_node *graph_new_node(struct graph *graph, void *data,
  38                                   void (*del)(void *))
  39 {
  40         struct graph_node *node =
  41                 XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node));
  42
  43         node->from = vector_init(VECTOR_MIN_SIZE);
  44         node->to = vector_init(VECTOR_MIN_SIZE);
  45         node->data = data;
  46         node->del = del;
  47
  48         vector_set(graph->nodes, node);
  49
  50         return node;
  51 }
  52
  53 static void vector_remove(vector v, unsigned int ix)
  54 {
  55         if (ix >= v->active)
  56                 return;
  57
  58         /* v->active is guaranteed >= 1 because ix can't be lower than 0
  59          * and v->active is > ix. */
  60         v->active--;
  61         /* if ix == v->active--, we set the item to itself, then to NULL...
  62          * still correct, no check neccessary. */
  63         v->index[ix] = v->index[v->active];
  64         v->index[v->active] = NULL;
  65 }
  66
  67 void graph_delete_node(struct graph *graph, struct graph_node *node)
  68 {
  69         if (!node)
  70                 return;
  71
  72         // an adjacent node
  73         struct graph_node *adj;
  74
  75         // remove all edges from other nodes to us
  76         for (unsigned int i = vector_active(node->from); i--; /**/) {
  77                 adj = vector_slot(node->from, i);
  78                 graph_remove_edge(adj, node);
  79         }
  80
  81         // remove all edges from us to other nodes
  82         for (unsigned int i = vector_active(node->to); i--; /**/) {
  83                 adj = vector_slot(node->to, i);
  84                 graph_remove_edge(node, adj);
  85         }
  86
  87         // if there is a deletion callback, call it
  88         if (node->del && node->data)
  89                 (*node->del)(node->data);
  90
  91         // free adjacency lists
  92         vector_free(node->to);
  93         vector_free(node->from);
  94
  95         // remove node from graph->nodes
  96         for (unsigned int i = vector_active(graph->nodes); i--; /**/)
  97                 if (vector_slot(graph->nodes, i) == node) {
  98                         vector_remove(graph->nodes, i);
  99                         break;
 100                 }
 101
 102         // free the node itself
 103         XFREE(MTYPE_GRAPH_NODE, node);
 104 }
 105
 106 struct graph_node *graph_add_edge(struct graph_node *from,
 107                                   struct graph_node *to)
 108 {
 109         vector_set(from->to, to);
 110         vector_set(to->from, from);
 111         return to;
 112 }
 113
 114 void graph_remove_edge(struct graph_node *from, struct graph_node *to)
 115 {
 116         // remove from from to->from
 117         for (unsigned int i = vector_active(to->from); i--; /**/)
 118                 if (vector_slot(to->from, i) == from) {
 119                         vector_remove(to->from, i);
 120                         break;
 121                 }
 122         // remove to from from->to
 123         for (unsigned int i = vector_active(from->to); i--; /**/)
 124                 if (vector_slot(from->to, i) == to) {
 125                         vector_remove(from->to, i);
 126                         break;
 127                 }
 128 }
 129
 130 void graph_delete_graph(struct graph *graph)
 131 {
 132         // delete each node in the graph
 133         for (unsigned int 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 }