]>
git.proxmox.com Git - mirror_frr.git/blob - lib/graph.c
2 * Graph data structure.
5 * Copyright (C) 2016 Cumulus Networks, Inc.
7 * This file is part of GNU Zebra.
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
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.
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
28 DEFINE_MTYPE_STATIC(LIB
, GRAPH
, "Graph")
29 DEFINE_MTYPE_STATIC(LIB
, GRAPH_NODE
, "Graph Node")
30 struct graph
*graph_new()
32 struct graph
*graph
= XCALLOC(MTYPE_GRAPH
, sizeof(struct graph
));
33 graph
->nodes
= vector_init(VECTOR_MIN_SIZE
);
38 struct graph_node
*graph_new_node(struct graph
*graph
, void *data
,
41 struct graph_node
*node
=
42 XCALLOC(MTYPE_GRAPH_NODE
, sizeof(struct graph_node
));
44 node
->from
= vector_init(VECTOR_MIN_SIZE
);
45 node
->to
= vector_init(VECTOR_MIN_SIZE
);
49 vector_set(graph
->nodes
, node
);
54 static void vector_remove(vector v
, unsigned int ix
)
59 /* v->active is guaranteed >= 1 because ix can't be lower than 0
60 * and v->active is > ix. */
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
;
68 void graph_delete_node(struct graph
*graph
, struct graph_node
*node
)
74 struct graph_node
*adj
;
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
);
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
);
88 // if there is a deletion callback, call it
89 if (node
->del
&& node
->data
)
90 (*node
->del
)(node
->data
);
92 // free adjacency lists
93 vector_free(node
->to
);
94 vector_free(node
->from
);
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
);
103 // free the node itself
104 XFREE(MTYPE_GRAPH_NODE
, node
);
107 struct graph_node
*graph_add_edge(struct graph_node
*from
,
108 struct graph_node
*to
)
110 vector_set(from
->to
, to
);
111 vector_set(to
->from
, from
);
115 void graph_remove_edge(struct graph_node
*from
, struct graph_node
*to
)
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
);
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
);
131 void graph_delete_graph(struct graph
*graph
)
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
));
137 vector_free(graph
->nodes
);
138 XFREE(MTYPE_GRAPH
, graph
);