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. */
18u32
19graph_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
66void
67graph_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. */
79uword
80graph_del_node (graph_t * g, u32 src)
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  clib_memset (src_node, ~0, sizeof (src_node[0]));
106
107  return index;
108}
109
110uword
111unformat_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
139u8 *
140format_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
153u8 *
154format_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  u32 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 */
183