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