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