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);
  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;
  uword indent = format_get_indent (s);

  s = format (s, "graph %d nodes", pool_elts (g->nodes));
  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);
  }));

  return s;
}