FD.io VPP  v21.10.1-2-g0a485f517
Vector Packet Processing
graph.h
Go to the documentation of this file.
1 /*
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:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
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.
14  */
15 #ifndef included_clib_graph_h
16 #define included_clib_graph_h
17 
18 #include <vppinfra/format.h>
19 #include <vppinfra/hash.h>
20 #include <vppinfra/pool.h>
21 
22 /* Generic graphs. */
23 typedef struct
24 {
25  /* Next node along this link. */
27 
28  /* Other direction link index to reach back to current node. */
30 
31  /* Distance to next node. */
33 } graph_link_t;
34 
35 /* Direction on graph: either next or previous. */
36 typedef struct
37 {
38  /* Vector of links. */
40 
41  /* Hash mapping node index to link which visits this node. */
43 } graph_dir_t;
44 
45 always_inline void
47 {
48  vec_free (d->links);
50 }
51 
54 {
56  return p ? vec_elt_at_index (d->links, p[0]) : 0;
57 }
58 
61 {
62  graph_link_t *l;
64  vec_add2 (d->links, l, 1);
66  l->distance = distance;
68  return l - d->links;
69 }
70 
71 always_inline void
73 {
75  uword li = l - d->links;
76  uword n_links = vec_len (d->links);
77 
78  ASSERT (l != 0);
80  n_links -= 1;
81  if (li < n_links)
82  d->links[li] = d->links[n_links];
83  _vec_len (d->links) = n_links;
84 }
85 
86 typedef struct
87 {
88  /* Nodes we are connected to plus distances. */
90 } graph_node_t;
91 
92 typedef struct
93 {
94  /* Pool of nodes. */
96 
97  void *opaque;
98 
100 } graph_t;
101 
102 /* Set link distance, creating link if not found. */
103 u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance);
104 
105 always_inline void
107 {
108  graph_set_link (g, src, dst, distance);
109  graph_set_link (g, dst, src, distance);
110 }
111 
112 void graph_del_link (graph_t * g, u32 src, u32 dst);
114 
118 
119 #endif /* included_clib_graph_h */
120 
121 /*
122  * fd.io coding-style-patch-verification: ON
123  *
124  * Local Variables:
125  * eval: (c-set-style "gnu")
126  * End:
127  */
graph_t::format_node
format_function_t * format_node
Definition: graph.h:99
hash_set
#define hash_set(h, key, value)
Definition: hash.h:255
hash_free
#define hash_free(h)
Definition: hash.h:310
next
u16 * next
Definition: nat44_ei_out2in.c:718
node_index
node node_index
Definition: interface_output.c:440
graph_t::opaque
void * opaque
Definition: graph.h:97
hash_unset
#define hash_unset(h, key)
Definition: hash.h:261
graph_dir_get_link_to_node
static graph_link_t * graph_dir_get_link_to_node(graph_dir_t *d, u32 node_index)
Definition: graph.h:53
hash.h
graph_dir_free
static void graph_dir_free(graph_dir_t *d)
Definition: graph.h:46
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
vec_add2
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:644
vec_elt_at_index
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
Definition: vec_bootstrap.h:203
hash_get
#define hash_get(h, key)
Definition: hash.h:249
graph_dir_add_link
static uword graph_dir_add_link(graph_dir_t *d, u32 node_index, u32 distance)
Definition: graph.h:60
uword
u64 uword
Definition: types.h:112
pool.h
Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedl...
graph_set_bidirectional_link
static void graph_set_bidirectional_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.h:106
format.h
src
vl_api_address_t src
Definition: gre.api:54
unformat_graph
unformat_function_t unformat_graph
Definition: graph.h:115
graph_t::nodes
graph_node_t * nodes
Definition: graph.h:95
graph_dir_t::links
graph_link_t * links
Definition: graph.h:39
graph_del_link
void graph_del_link(graph_t *g, u32 src, u32 dst)
Definition: graph.c:67
graph_dir_del_link
static void graph_dir_del_link(graph_dir_t *d, u32 node_index)
Definition: graph.h:72
format_function_t
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
graph_dir_t
Definition: graph.h:36
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
format_graph
format_function_t format_graph
Definition: graph.h:116
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
u32
unsigned int u32
Definition: types.h:88
graph_node_t
Definition: graph.h:86
dst
vl_api_ip4_address_t dst
Definition: pnat.api:41
unformat_function_t
uword() unformat_function_t(unformat_input_t *input, va_list *args)
Definition: format.h:225
graph_set_link
u32 graph_set_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.c:19
graph_del_node
uword graph_del_node(graph_t *g, u32 src)
Definition: graph.c:80
graph_dir_t::link_index_by_node_index
uword * link_index_by_node_index
Definition: graph.h:42
graph_node_t::prev
graph_dir_t prev
Definition: graph.h:89
format_graph_node
format_function_t format_graph_node
Definition: graph.h:117
graph_t
Definition: graph.h:92