vppinfra/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 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance)
  19 {
  20   graph_node_t * src_node, * dst_node;
  21   graph_link_t * l;
  22   u32 old_distance;
  23
  24   /* The following validate will not work if src or dst are on the
  25      pool free list. */
  26   if (src < vec_len (g->nodes))
  27     ASSERT (! pool_is_free_index (g->nodes, src));
  28   if (dst < vec_len (g->nodes))
  29     ASSERT (! pool_is_free_index (g->nodes, dst));
  30
  31   /* Make new (empty) nodes to make src and dst valid. */
  32   pool_validate_index (g->nodes, clib_max (src, dst));
  33
  34   src_node = pool_elt_at_index (g->nodes, src);
  35   dst_node = pool_elt_at_index (g->nodes, dst);
  36
  37   l = graph_dir_get_link_to_node (&src_node->next, dst);
  38   if (l)
  39     {
  40       old_distance = l->distance;
  41       l->distance = distance;
  42
  43       l = graph_dir_get_link_to_node (&dst_node->prev, src);
  44       l->distance = distance;
  45     }
  46   else
  47     {
  48       uword li_next, li_prev;
  49
  50       old_distance = ~0;
  51
  52       li_next = graph_dir_add_link (&src_node->next, dst, distance);
  53       li_prev = graph_dir_add_link (&dst_node->prev, src, distance);
  54
  55       l = vec_elt_at_index (src_node->next.links, li_next);
  56       l->link_to_self_index = li_prev;
  57
  58       l = vec_elt_at_index (dst_node->prev.links, li_prev);
  59       l->link_to_self_index = li_next;
  60     }
  61
  62   return old_distance;
  63 }
  64
  65 void graph_del_link (graph_t * g, u32 src, u32 dst)
  66 {
  67   graph_node_t * src_node, * dst_node;
  68
  69   src_node = pool_elt_at_index (g->nodes, src);
  70   dst_node = pool_elt_at_index (g->nodes, dst);
  71
  72   graph_dir_del_link (&src_node->next, dst);
  73   graph_dir_del_link (&dst_node->next, src);
  74 }
  75
  76 /* Delete source node and all links from other nodes from/to source. */
  77 uword graph_del_node (graph_t * g, u32 src)
  78 {
  79   graph_node_t * src_node, * n;
  80   uword index;
  81   graph_link_t * l;
  82
  83   src_node = pool_elt_at_index (g->nodes, src);
  84
  85   vec_foreach (l, src_node->next.links)
  86     {
  87       n = pool_elt_at_index (g->nodes, l->node_index);
  88       graph_dir_del_link (&n->prev, src);
  89     }
  90
  91   vec_foreach (l, src_node->prev.links)
  92     {
  93       n = pool_elt_at_index (g->nodes, l->node_index);
  94       graph_dir_del_link (&n->next, src);
  95     }
  96
  97   graph_dir_free (&src_node->next);
  98   graph_dir_free (&src_node->prev);
  99
 100   index = src_node - g->nodes;
 101   pool_put (g->nodes, src_node);
 102   memset (src_node, ~0, sizeof (src_node[0]));
 103
 104   return index;
 105 }
 106
 107 uword unformat_graph (unformat_input_t * input, va_list * args)
 108 {
 109   graph_t * g = va_arg (*args, graph_t *);
 110   typedef struct {
 111     u32 src, dst, distance;
 112   } T;
 113   T * links = 0, * l;
 114   uword result;
 115
 116   while (1)
 117     {
 118       vec_add2 (links, l, 1);
 119       if (! unformat (input, "%d%d%d", &l->src, &l->dst, &l->distance))
 120         break;
 121     }
 122   _vec_len (links) -= 1;
 123   result = vec_len (links) > 0;
 124   vec_foreach (l, links)
 125     {
 126       graph_set_link (g, l->src, l->dst, l->distance);
 127       graph_set_link (g, l->dst, l->src, l->distance);
 128     }
 129
 130   vec_free (links);
 131   return result;
 132 }
 133
 134 u8 * format_graph_node (u8 * s, va_list * args)
 135 {
 136   graph_t * g = va_arg (*args, graph_t *);
 137   u32 node_index = va_arg (*args, u32);
 138
 139   if (g->format_node)
 140     s = format (s, "%U", g->format_node, g, node_index);
 141   else
 142     s = format (s, "%d", node_index);
 143
 144   return s;
 145 }
 146
 147 u8 * format_graph (u8 * s, va_list * args)
 148 {
 149   graph_t * g = va_arg (*args, graph_t *);
 150   graph_node_t * n;
 151   graph_link_t * l;
 152   uword indent = format_get_indent (s);
 153
 154   s = format (s, "graph %d nodes", pool_elts (g->nodes));
 155   pool_foreach (n, g->nodes, ({
 156     s = format (s, "\n%U", format_white_space, indent + 2);
 157     s = format (s, "%U -> ", format_graph_node, g, n - g->nodes);
 158     vec_foreach (l, n->next.links)
 159       s = format (s, "%U (%d), ",
 160                   format_graph_node, g, l->node_index,
 161                   l->distance);
 162   }));
 163
 164   return s;
 165 }