]>
Commit | Line | Data |
---|---|---|
16d7c050 QY |
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> | |
1eb5e8dc | 25 | #include "graph.h" |
16d7c050 QY |
26 | #include "memory.h" |
27 | ||
ac4d0be5 | 28 | DEFINE_MTYPE_STATIC(LIB, GRAPH, "Graph") |
460a7689 | 29 | DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node") |
ac4d0be5 | 30 | struct graph *graph_new() |
1eb5e8dc | 31 | { |
ac4d0be5 | 32 | struct graph *graph = XCALLOC(MTYPE_GRAPH, sizeof(struct graph)); |
33 | graph->nodes = vector_init(VECTOR_MIN_SIZE); | |
1eb5e8dc | 34 | |
ac4d0be5 | 35 | return graph; |
1eb5e8dc | 36 | } |
16d7c050 | 37 | |
ac4d0be5 | 38 | struct graph_node *graph_new_node(struct graph *graph, void *data, |
39 | void (*del)(void *)) | |
16d7c050 | 40 | { |
ac4d0be5 | 41 | struct graph_node *node = |
42 | XCALLOC(MTYPE_GRAPH_NODE, sizeof(struct graph_node)); | |
16d7c050 | 43 | |
ac4d0be5 | 44 | node->from = vector_init(VECTOR_MIN_SIZE); |
45 | node->to = vector_init(VECTOR_MIN_SIZE); | |
46 | node->data = data; | |
47 | node->del = del; | |
16d7c050 | 48 | |
ac4d0be5 | 49 | vector_set(graph->nodes, node); |
16d7c050 | 50 | |
ac4d0be5 | 51 | return node; |
16d7c050 QY |
52 | } |
53 | ||
ac4d0be5 | 54 | static void vector_remove(vector v, unsigned int ix) |
ba06a3a0 | 55 | { |
ac4d0be5 | 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; | |
ba06a3a0 QY |
66 | } |
67 | ||
ac4d0be5 | 68 | void graph_delete_node(struct graph *graph, struct graph_node *node) |
16d7c050 | 69 | { |
ac4d0be5 | 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); | |
16d7c050 QY |
105 | } |
106 | ||
ac4d0be5 | 107 | struct graph_node *graph_add_edge(struct graph_node *from, |
108 | struct graph_node *to) | |
16d7c050 | 109 | { |
ac4d0be5 | 110 | vector_set(from->to, to); |
111 | vector_set(to->from, from); | |
112 | return to; | |
16d7c050 QY |
113 | } |
114 | ||
ac4d0be5 | 115 | void graph_remove_edge(struct graph_node *from, struct graph_node *to) |
ba06a3a0 | 116 | { |
ac4d0be5 | 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 | } | |
ba06a3a0 QY |
129 | } |
130 | ||
ac4d0be5 | 131 | void graph_delete_graph(struct graph *graph) |
16d7c050 | 132 | { |
ac4d0be5 | 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)); | |
16d7c050 | 136 | |
ac4d0be5 | 137 | vector_free(graph->nodes); |
138 | XFREE(MTYPE_GRAPH, graph); | |
16d7c050 | 139 | } |