src/vppinfra/graph.c

   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
  80 graph_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
 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   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  */