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