FD.io VPP  v16.06
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  /* Next node along this link. */
26 
27  /* Other direction link index to reach back to current node. */
29 
30  /* Distance to next node. */
32 } graph_link_t;
33 
34 /* Direction on graph: either next or previous. */
35 typedef struct {
36  /* Vector of links. */
38 
39  /* Hash mapping node index to link which visits this node. */
41 } graph_dir_t;
42 
43 always_inline void
45 {
46  vec_free (d->links);
48 }
49 
52 {
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;
55 }
56 
58 graph_dir_add_link (graph_dir_t * d, u32 node_index, u32 distance)
59 {
60  graph_link_t * l;
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);
66  return l - d->links;
67 }
68 
69 always_inline void
71 {
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);
75 
76  ASSERT (l != 0);
77  hash_unset (d->link_index_by_node_index, node_index);
78  n_links -= 1;
79  if (li < n_links)
80  d->links[li] = d->links[n_links];
81  _vec_len (d->links) = n_links;
82 }
83 
84 typedef struct {
85  /* Nodes we are connected to plus distances. */
87 } graph_node_t;
88 
89 typedef struct {
90  /* Pool of nodes. */
92 
93  void * opaque;
94 
96 } graph_t;
97 
98 /* Set link distance, creating link if not found. */
99 u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance);
100 
102 {
103  graph_set_link (g, src, dst, distance);
104  graph_set_link (g, dst, src, distance);
105 }
106 
107 void graph_del_link (graph_t * g, u32 src, u32 dst);
108 uword graph_del_node (graph_t * g, u32 src);
109 
113 
114 #endif /* included_clib_graph_h */
#define hash_set(h, key, value)
Definition: hash.h:237
format_function_t format_graph_node
Definition: graph.h:112
uword( unformat_function_t)(unformat_input_t *input, va_list *args)
Definition: format.h:229
#define hash_unset(h, key)
Definition: hash.h:243
always_inline void graph_set_bidirectional_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.h:101
format_function_t format_graph
Definition: graph.h:111
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:519
always_inline void graph_dir_free(graph_dir_t *d)
Definition: graph.h:44
uword * link_index_by_node_index
Definition: graph.h:40
unformat_function_t unformat_graph
Definition: graph.h:110
#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:231
always_inline void graph_dir_del_link(graph_dir_t *d, u32 node_index)
Definition: graph.h:70
#define hash_free(h)
Definition: hash.h:269
void * opaque
Definition: graph.h:93
graph_node_t * nodes
Definition: graph.h:91
uword graph_del_node(graph_t *g, u32 src)
Definition: graph.c:77
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:298
void graph_del_link(graph_t *g, u32 src, u32 dst)
Definition: graph.c:65
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
format_function_t * format_node
Definition: graph.h:95
u8 *( format_function_t)(u8 *s, va_list *args)
Definition: format.h:48
u64 uword
Definition: types.h:112
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: graph.h:89
always_inline graph_link_t * graph_dir_get_link_to_node(graph_dir_t *d, u32 node_index)
Definition: graph.h:51
graph_dir_t prev
Definition: graph.h:86
graph_link_t * links
Definition: graph.h:37
always_inline uword graph_dir_add_link(graph_dir_t *d, u32 node_index, u32 distance)
Definition: graph.h:58
u32 graph_set_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.c:18