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