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 #ifndef included_clib_graph_h
16 #define included_clib_graph_h
18 #include <vppinfra/format.h>
19 #include <vppinfra/hash.h>
20 #include <vppinfra/pool.h>
24 /* Next node along this link. */
27 /* Other direction link index to reach back to current node. */
28 u32 link_to_self_index;
30 /* Distance to next node. */
34 /* Direction on graph: either next or previous. */
36 /* Vector of links. */
39 /* Hash mapping node index to link which visits this node. */
40 uword * link_index_by_node_index;
44 graph_dir_free (graph_dir_t * d)
47 hash_free (d->link_index_by_node_index);
50 always_inline graph_link_t *
51 graph_dir_get_link_to_node (graph_dir_t * d, u32 node_index)
53 uword * p = hash_get (d->link_index_by_node_index, node_index);
54 return p ? vec_elt_at_index (d->links, p[0]) : 0;
58 graph_dir_add_link (graph_dir_t * d, u32 node_index, u32 distance)
61 ASSERT (! graph_dir_get_link_to_node (d, node_index));
62 vec_add2 (d->links, l, 1);
63 l->node_index = node_index;
64 l->distance = distance;
65 hash_set (d->link_index_by_node_index, node_index, l - d->links);
70 graph_dir_del_link (graph_dir_t * d, u32 node_index)
72 graph_link_t * l = graph_dir_get_link_to_node (d, node_index);
73 uword li = l - d->links;
74 uword n_links = vec_len (d->links);
77 hash_unset (d->link_index_by_node_index, node_index);
80 d->links[li] = d->links[n_links];
81 _vec_len (d->links) = n_links;
85 /* Nodes we are connected to plus distances. */
86 graph_dir_t next, prev;
95 format_function_t * format_node;
98 /* Set link distance, creating link if not found. */
99 u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance);
101 always_inline void graph_set_bidirectional_link (graph_t * g, u32 src, u32 dst, u32 distance)
103 graph_set_link (g, src, dst, distance);
104 graph_set_link (g, dst, src, distance);
107 void graph_del_link (graph_t * g, u32 src, u32 dst);
108 uword graph_del_node (graph_t * g, u32 src);
110 unformat_function_t unformat_graph;
111 format_function_t format_graph;
112 format_function_t format_graph_node;
114 #endif /* included_clib_graph_h */