graph.c

Go to the documentation of this file.

/*
 * Copyright (c) 2015 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#include <vppinfra/graph.h>

/* Set link distance, creating link if not found. */
u32
graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance)
{
  graph_node_t *src_node, *dst_node;
  graph_link_t *l;
  u32 old_distance;

  /* The following validate will not work if src or dst are on the
     pool free list. */
  if (src < vec_len (g->nodes))
    ASSERT (!pool_is_free_index (g->nodes, src));
  if (dst < vec_len (g->nodes))
    ASSERT (!pool_is_free_index (g->nodes, dst));

  /* Make new (empty) nodes to make src and dst valid. */
  pool_validate_index (g->nodes, clib_max (src, dst));

  src_node = pool_elt_at_index (g->nodes, src);
  dst_node = pool_elt_at_index (g->nodes, dst);

  l = graph_dir_get_link_to_node (&src_node->next, dst);
  if (l)
    {
      old_distance = l->distance;
      l->distance = distance;

      l = graph_dir_get_link_to_node (&dst_node->prev, src);
      l->distance = distance;
    }
  else
    {
      uword li_next, li_prev;

      old_distance = ~0;

      li_next = graph_dir_add_link (&src_node->next, dst, distance);
      li_prev = graph_dir_add_link (&dst_node->prev, src, distance);

      l = vec_elt_at_index (src_node->next.links, li_next);
      l->link_to_self_index = li_prev;

      l = vec_elt_at_index (dst_node->prev.links, li_prev);
      l->link_to_self_index = li_next;
    }

  return old_distance;
}

void
graph_del_link (graph_t * g, u32 src, u32 dst)
{
  graph_node_t *src_node, *dst_node;

  src_node = pool_elt_at_index (g->nodes, src);
  dst_node = pool_elt_at_index (g->nodes, dst);

  graph_dir_del_link (&src_node->next, dst);
  graph_dir_del_link (&dst_node->next, src);
}

/* Delete source node and all links from other nodes from/to source. */
uword
graph_del_node (graph_t * g, u32 src)
{
  graph_node_t *src_node, *n;
  uword index;
  graph_link_t *l;

  src_node = pool_elt_at_index (g->nodes, src);

  vec_foreach (l, src_node->next.links)
  {
    n = pool_elt_at_index (g->nodes, l->node_index);
    graph_dir_del_link (&n->prev, src);
  }

  vec_foreach (l, src_node->prev.links)
  {
    n = pool_elt_at_index (g->nodes, l->node_index);
    graph_dir_del_link (&n->next, src);
  }

  graph_dir_free (&src_node->next);
  graph_dir_free (&src_node->prev);

  index = src_node - g->nodes;
  pool_put (g->nodes, src_node);
  clib_memset (src_node, ~0, sizeof (src_node[0]));

  return index;
}

uword
unformat_graph (unformat_input_t * input, va_list * args)
{
  graph_t *g = va_arg (*args, graph_t *);
  typedef struct
  {
    u32 src, dst, distance;
  } T;
  T *links = 0, *l;
  uword result;

  while (1)
    {
      vec_add2 (links, l, 1);
      if (!unformat (input, "%d%d%d", &l->src, &l->dst, &l->distance))
        break;
    }
  _vec_len (links) -= 1;
  result = vec_len (links) > 0;
  vec_foreach (l, links)
  {
    graph_set_link (g, l->src, l->dst, l->distance);
    graph_set_link (g, l->dst, l->src, l->distance);
  }

  vec_free (links);
  return result;
}

u8 *
format_graph_node (u8 * s, va_list * args)
{
  graph_t *g = va_arg (*args, graph_t *);
  u32 node_index = va_arg (*args, u32);

  if (g->format_node)
    s = format (s, "%U", g->format_node, g, node_index);
  else
    s = format (s, "%d", node_index);

  return s;
}

u8 *
format_graph (u8 * s, va_list * args)
{
  graph_t *g = va_arg (*args, graph_t *);
  graph_node_t *n;
  graph_link_t *l;
  u32 indent = format_get_indent (s);

  s = format (s, "graph %d nodes", pool_elts (g->nodes));
  /* *INDENT-OFF* */
  pool_foreach (n, g->nodes)  {
    s = format (s, "\n%U", format_white_space, indent + 2);
    s = format (s, "%U -> ", format_graph_node, g, n - g->nodes);
    vec_foreach (l, n->next.links)
      s = format (s, "%U (%d), ",
                  format_graph_node, g, l->node_index,
                  l->distance);
  }
  /* *INDENT-ON* */

  return s;
}

/*
 * fd.io coding-style-patch-verification: ON
 *
 * Local Variables:
 * eval: (c-set-style "gnu")
 * End:
 */