FD.io VPP  v17.01-9-ge7dcee4
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 {
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;
57 }
58 
60 graph_dir_add_link (graph_dir_t * d, u32 node_index, u32 distance)
61 {
62  graph_link_t *l;
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);
68  return l - d->links;
69 }
70 
71 always_inline void
73 {
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);
77 
78  ASSERT (l != 0);
79  hash_unset (d->link_index_by_node_index, node_index);
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
106 graph_set_bidirectional_link (graph_t * g, u32 src, u32 dst, u32 distance)
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);
113 uword graph_del_node (graph_t * g, u32 src);
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  */
#define hash_set(h, key, value)
Definition: hash.h:254
format_function_t format_graph_node
Definition: graph.h:117
uword( unformat_function_t)(unformat_input_t *input, va_list *args)
Definition: format.h:231
#define hash_unset(h, key)
Definition: hash.h:260
Fixed length block allocator.
format_function_t format_graph
Definition: graph.h:116
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:521
uword * link_index_by_node_index
Definition: graph.h:42
static void graph_set_bidirectional_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.h:106
unformat_function_t unformat_graph
Definition: graph.h:115
#define always_inline
Definition: clib.h:84
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
#define hash_get(h, key)
Definition: hash.h:248
#define hash_free(h)
Definition: hash.h:286
void * opaque
Definition: graph.h:97
graph_node_t * nodes
Definition: graph.h:95
uword graph_del_node(graph_t *g, u32 src)
Definition: graph.c:80
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
void graph_del_link(graph_t *g, u32 src, u32 dst)
Definition: graph.c:67
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
format_function_t * format_node
Definition: graph.h:99
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
u64 uword
Definition: types.h:112
static void graph_dir_del_link(graph_dir_t *d, u32 node_index)
Definition: graph.h:72
static uword graph_dir_add_link(graph_dir_t *d, u32 node_index, u32 distance)
Definition: graph.h:60
static graph_link_t * graph_dir_get_link_to_node(graph_dir_t *d, u32 node_index)
Definition: graph.h:53
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static void graph_dir_free(graph_dir_t *d)
Definition: graph.h:46
Definition: graph.h:92
graph_dir_t prev
Definition: graph.h:89
graph_link_t * links
Definition: graph.h:39
u32 graph_set_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.c:19