FD.io VPP  v17.07-30-g839fa73
Vector Packet Processing
graph.c
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 #include <vppinfra/graph.h>
16 
17 /* Set link distance, creating link if not found. */
18 u32
19 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance)
20 {
21  graph_node_t *src_node, *dst_node;
22  graph_link_t *l;
23  u32 old_distance;
24 
25  /* The following validate will not work if src or dst are on the
26  pool free list. */
27  if (src < vec_len (g->nodes))
28  ASSERT (!pool_is_free_index (g->nodes, src));
29  if (dst < vec_len (g->nodes))
30  ASSERT (!pool_is_free_index (g->nodes, dst));
31 
32  /* Make new (empty) nodes to make src and dst valid. */
33  pool_validate_index (g->nodes, clib_max (src, dst));
34 
35  src_node = pool_elt_at_index (g->nodes, src);
36  dst_node = pool_elt_at_index (g->nodes, dst);
37 
38  l = graph_dir_get_link_to_node (&src_node->next, dst);
39  if (l)
40  {
41  old_distance = l->distance;
42  l->distance = distance;
43 
44  l = graph_dir_get_link_to_node (&dst_node->prev, src);
45  l->distance = distance;
46  }
47  else
48  {
49  uword li_next, li_prev;
50 
51  old_distance = ~0;
52 
53  li_next = graph_dir_add_link (&src_node->next, dst, distance);
54  li_prev = graph_dir_add_link (&dst_node->prev, src, distance);
55 
56  l = vec_elt_at_index (src_node->next.links, li_next);
57  l->link_to_self_index = li_prev;
58 
59  l = vec_elt_at_index (dst_node->prev.links, li_prev);
60  l->link_to_self_index = li_next;
61  }
62 
63  return old_distance;
64 }
65 
66 void
67 graph_del_link (graph_t * g, u32 src, u32 dst)
68 {
69  graph_node_t *src_node, *dst_node;
70 
71  src_node = pool_elt_at_index (g->nodes, src);
72  dst_node = pool_elt_at_index (g->nodes, dst);
73 
74  graph_dir_del_link (&src_node->next, dst);
75  graph_dir_del_link (&dst_node->next, src);
76 }
77 
78 /* Delete source node and all links from other nodes from/to source. */
79 uword
81 {
82  graph_node_t *src_node, *n;
83  uword index;
84  graph_link_t *l;
85 
86  src_node = pool_elt_at_index (g->nodes, src);
87 
88  vec_foreach (l, src_node->next.links)
89  {
90  n = pool_elt_at_index (g->nodes, l->node_index);
91  graph_dir_del_link (&n->prev, src);
92  }
93 
94  vec_foreach (l, src_node->prev.links)
95  {
96  n = pool_elt_at_index (g->nodes, l->node_index);
97  graph_dir_del_link (&n->next, src);
98  }
99 
100  graph_dir_free (&src_node->next);
101  graph_dir_free (&src_node->prev);
102 
103  index = src_node - g->nodes;
104  pool_put (g->nodes, src_node);
105  memset (src_node, ~0, sizeof (src_node[0]));
106 
107  return index;
108 }
109 
110 uword
111 unformat_graph (unformat_input_t * input, va_list * args)
112 {
113  graph_t *g = va_arg (*args, graph_t *);
114  typedef struct
115  {
116  u32 src, dst, distance;
117  } T;
118  T *links = 0, *l;
119  uword result;
120 
121  while (1)
122  {
123  vec_add2 (links, l, 1);
124  if (!unformat (input, "%d%d%d", &l->src, &l->dst, &l->distance))
125  break;
126  }
127  _vec_len (links) -= 1;
128  result = vec_len (links) > 0;
129  vec_foreach (l, links)
130  {
131  graph_set_link (g, l->src, l->dst, l->distance);
132  graph_set_link (g, l->dst, l->src, l->distance);
133  }
134 
135  vec_free (links);
136  return result;
137 }
138 
139 u8 *
140 format_graph_node (u8 * s, va_list * args)
141 {
142  graph_t *g = va_arg (*args, graph_t *);
143  u32 node_index = va_arg (*args, u32);
144 
145  if (g->format_node)
146  s = format (s, "%U", g->format_node, g, node_index);
147  else
148  s = format (s, "%d", node_index);
149 
150  return s;
151 }
152 
153 u8 *
154 format_graph (u8 * s, va_list * args)
155 {
156  graph_t *g = va_arg (*args, graph_t *);
157  graph_node_t *n;
158  graph_link_t *l;
159  uword indent = format_get_indent (s);
160 
161  s = format (s, "graph %d nodes", pool_elts (g->nodes));
162  /* *INDENT-OFF* */
163  pool_foreach (n, g->nodes, ({
164  s = format (s, "\n%U", format_white_space, indent + 2);
165  s = format (s, "%U -> ", format_graph_node, g, n - g->nodes);
166  vec_foreach (l, n->next.links)
167  s = format (s, "%U (%d), ",
168  format_graph_node, g, l->node_index,
169  l->distance);
170  }));
171  /* *INDENT-ON* */
172 
173  return s;
174 }
175 
176 /*
177  * fd.io coding-style-patch-verification: ON
178  *
179  * Local Variables:
180  * eval: (c-set-style "gnu")
181  * End:
182  */
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:561
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:376
static uword format_get_indent(u8 *s)
Definition: format.h:72
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
#define pool_validate_index(v, i)
Definition: pool.h:97
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:397
struct _unformat_input_t unformat_input_t
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
void graph_del_link(graph_t *g, u32 src, u32 dst)
Definition: graph.c:67
graph_node_t * nodes
Definition: graph.h:95
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
graph_dir_t next
Definition: graph.h:89
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:238
uword unformat_graph(unformat_input_t *input, va_list *args)
Definition: graph.c:111
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
uword graph_del_node(graph_t *g, u32 src)
Definition: graph.c:80
format_function_t * format_node
Definition: graph.h:99
#define clib_max(x, y)
Definition: clib.h:325
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
u32 graph_set_link(graph_t *g, u32 src, u32 dst, u32 distance)
Definition: graph.c:19
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)
unsigned char u8
Definition: types.h:56
static void graph_dir_free(graph_dir_t *d)
Definition: graph.h:46
Definition: graph.h:92
u8 * format_graph_node(u8 *s, va_list *args)
Definition: graph.c:140
u8 * format_graph(u8 *s, va_list *args)
Definition: graph.c:154
#define vec_foreach(var, vec)
Vector iterator.
graph_dir_t prev
Definition: graph.h:89
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
graph_link_t * links
Definition: graph.h:39
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109