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