vppinfra/vppinfra/graph.h

   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 #ifndef included_clib_graph_h
  16 #define included_clib_graph_h
  17
  18 #include <vppinfra/format.h>
  19 #include <vppinfra/hash.h>
  20 #include <vppinfra/pool.h>
  21
  22 /* Generic graphs. */
  23 typedef struct {
  24   /* Next node along this link. */
  25   u32 node_index;
  26
  27   /* Other direction link index to reach back to current node. */
  28   u32 link_to_self_index;
  29
  30   /* Distance to next node. */
  31   u32 distance;
  32 } graph_link_t;
  33
  34 /* Direction on graph: either next or previous. */
  35 typedef struct {
  36   /* Vector of links. */
  37   graph_link_t * links;
  38
  39   /* Hash mapping node index to link which visits this node. */
  40   uword * link_index_by_node_index;
  41 } graph_dir_t;
  42
  43 always_inline void
  44 graph_dir_free (graph_dir_t * d)
  45 {
  46   vec_free (d->links);
  47   hash_free (d->link_index_by_node_index);
  48 }
  49
  50 always_inline graph_link_t *
  51 graph_dir_get_link_to_node (graph_dir_t * d, u32 node_index)
  52 {
  53   uword * p = hash_get (d->link_index_by_node_index, node_index);
  54   return p ? vec_elt_at_index (d->links, p[0]) : 0;
  55 }
  56
  57 always_inline uword
  58 graph_dir_add_link (graph_dir_t * d, u32 node_index, u32 distance)
  59 {
  60   graph_link_t * l;
  61   ASSERT (! graph_dir_get_link_to_node (d, node_index));
  62   vec_add2 (d->links, l, 1);
  63   l->node_index = node_index;
  64   l->distance = distance;
  65   hash_set (d->link_index_by_node_index, node_index, l - d->links);
  66   return l - d->links;
  67 }
  68
  69 always_inline void
  70 graph_dir_del_link (graph_dir_t * d, u32 node_index)
  71 {
  72   graph_link_t * l = graph_dir_get_link_to_node (d, node_index);
  73   uword li = l - d->links;
  74   uword n_links = vec_len (d->links);
  75
  76   ASSERT (l != 0);
  77   hash_unset (d->link_index_by_node_index, node_index);
  78   n_links -= 1;
  79   if (li < n_links)
  80     d->links[li] = d->links[n_links];
  81   _vec_len (d->links) = n_links;
  82 }
  83
  84 typedef struct {
  85   /* Nodes we are connected to plus distances. */
  86   graph_dir_t next, prev;
  87 } graph_node_t;
  88
  89 typedef struct {
  90   /* Pool of nodes. */
  91   graph_node_t * nodes;
  92
  93   void * opaque;
  94
  95   format_function_t * format_node;
  96 } graph_t;
  97
  98 /* Set link distance, creating link if not found. */
  99 u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance);
 100
 101 always_inline void graph_set_bidirectional_link (graph_t * g, u32 src, u32 dst, u32 distance)
 102 {
 103   graph_set_link (g, src, dst, distance);
 104   graph_set_link (g, dst, src, distance);
 105 }
 106
 107 void graph_del_link (graph_t * g, u32 src, u32 dst);
 108 uword graph_del_node (graph_t * g, u32 src);
 109
 110 unformat_function_t unformat_graph;
 111 format_function_t format_graph;
 112 format_function_t format_graph_node;
 113
 114 #endif /* included_clib_graph_h */