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