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>
25 /* Next node along this link. */
28 /* Other direction link index to reach back to current node. */
29 u32 link_to_self_index;
31 /* Distance to next node. */
35 /* Direction on graph: either next or previous. */
38 /* Vector of links. */
41 /* Hash mapping node index to link which visits this node. */
42 uword *link_index_by_node_index;
46 graph_dir_free (graph_dir_t * d)
49 hash_free (d->link_index_by_node_index);
52 always_inline graph_link_t *
53 graph_dir_get_link_to_node (graph_dir_t * d, u32 node_index)
55 uword *p = hash_get (d->link_index_by_node_index, node_index);
56 return p ? vec_elt_at_index (d->links, p[0]) : 0;
60 graph_dir_add_link (graph_dir_t * d, u32 node_index, u32 distance)
63 ASSERT (!graph_dir_get_link_to_node (d, node_index));
64 vec_add2 (d->links, l, 1);
65 l->node_index = node_index;
66 l->distance = distance;
67 hash_set (d->link_index_by_node_index, node_index, l - d->links);
72 graph_dir_del_link (graph_dir_t * d, u32 node_index)
74 graph_link_t *l = graph_dir_get_link_to_node (d, node_index);
75 uword li = l - d->links;
76 uword n_links = vec_len (d->links);
79 hash_unset (d->link_index_by_node_index, node_index);
82 d->links[li] = d->links[n_links];
83 _vec_len (d->links) = n_links;
88 /* Nodes we are connected to plus distances. */
89 graph_dir_t next, prev;
99 format_function_t *format_node;
102 /* Set link distance, creating link if not found. */
103 u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance);
106 graph_set_bidirectional_link (graph_t * g, u32 src, u32 dst, u32 distance)
108 graph_set_link (g, src, dst, distance);
109 graph_set_link (g, dst, src, distance);
112 void graph_del_link (graph_t * g, u32 src, u32 dst);
113 uword graph_del_node (graph_t * g, u32 src);
115 unformat_function_t unformat_graph;
116 format_function_t format_graph;
117 format_function_t format_graph_node;
119 #endif /* included_clib_graph_h */
122 * fd.io coding-style-patch-verification: ON
125 * eval: (c-set-style "gnu")