2 * Copyright (c) 2015 Cisco and/or its affiliates.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at:
7 * http://www.apache.org/licenses/LICENSE-2.0
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
15 #include <vppinfra/graph.h>
17 /* Set link distance, creating link if not found. */
18 u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance)
20 graph_node_t * src_node, * dst_node;
24 /* The following validate will not work if src or dst are on the
26 if (src < vec_len (g->nodes))
27 ASSERT (! pool_is_free_index (g->nodes, src));
28 if (dst < vec_len (g->nodes))
29 ASSERT (! pool_is_free_index (g->nodes, dst));
31 /* Make new (empty) nodes to make src and dst valid. */
32 pool_validate_index (g->nodes, clib_max (src, dst));
34 src_node = pool_elt_at_index (g->nodes, src);
35 dst_node = pool_elt_at_index (g->nodes, dst);
37 l = graph_dir_get_link_to_node (&src_node->next, dst);
40 old_distance = l->distance;
41 l->distance = distance;
43 l = graph_dir_get_link_to_node (&dst_node->prev, src);
44 l->distance = distance;
48 uword li_next, li_prev;
52 li_next = graph_dir_add_link (&src_node->next, dst, distance);
53 li_prev = graph_dir_add_link (&dst_node->prev, src, distance);
55 l = vec_elt_at_index (src_node->next.links, li_next);
56 l->link_to_self_index = li_prev;
58 l = vec_elt_at_index (dst_node->prev.links, li_prev);
59 l->link_to_self_index = li_next;
65 void graph_del_link (graph_t * g, u32 src, u32 dst)
67 graph_node_t * src_node, * dst_node;
69 src_node = pool_elt_at_index (g->nodes, src);
70 dst_node = pool_elt_at_index (g->nodes, dst);
72 graph_dir_del_link (&src_node->next, dst);
73 graph_dir_del_link (&dst_node->next, src);
76 /* Delete source node and all links from other nodes from/to source. */
77 uword graph_del_node (graph_t * g, u32 src)
79 graph_node_t * src_node, * n;
83 src_node = pool_elt_at_index (g->nodes, src);
85 vec_foreach (l, src_node->next.links)
87 n = pool_elt_at_index (g->nodes, l->node_index);
88 graph_dir_del_link (&n->prev, src);
91 vec_foreach (l, src_node->prev.links)
93 n = pool_elt_at_index (g->nodes, l->node_index);
94 graph_dir_del_link (&n->next, src);
97 graph_dir_free (&src_node->next);
98 graph_dir_free (&src_node->prev);
100 index = src_node - g->nodes;
101 pool_put (g->nodes, src_node);
102 memset (src_node, ~0, sizeof (src_node[0]));
107 uword unformat_graph (unformat_input_t * input, va_list * args)
109 graph_t * g = va_arg (*args, graph_t *);
111 u32 src, dst, distance;
118 vec_add2 (links, l, 1);
119 if (! unformat (input, "%d%d%d", &l->src, &l->dst, &l->distance))
122 _vec_len (links) -= 1;
123 result = vec_len (links) > 0;
124 vec_foreach (l, links)
126 graph_set_link (g, l->src, l->dst, l->distance);
127 graph_set_link (g, l->dst, l->src, l->distance);
134 u8 * format_graph_node (u8 * s, va_list * args)
136 graph_t * g = va_arg (*args, graph_t *);
137 u32 node_index = va_arg (*args, u32);
140 s = format (s, "%U", g->format_node, g, node_index);
142 s = format (s, "%d", node_index);
147 u8 * format_graph (u8 * s, va_list * args)
149 graph_t * g = va_arg (*args, graph_t *);
152 uword indent = format_get_indent (s);
154 s = format (s, "graph %d nodes", pool_elts (g->nodes));
155 pool_foreach (n, g->nodes, ({
156 s = format (s, "\n%U", format_white_space, indent + 2);
157 s = format (s, "%U -> ", format_graph_node, g, n - g->nodes);
158 vec_foreach (l, n->next.links)
159 s = format (s, "%U (%d), ",
160 format_graph_node, g, l->node_index,