diff options
Diffstat (limited to 'src/vppinfra/graph.c')
| -rw-r--r-- | src/vppinfra/graph.c | 182 |
1 files changed, 182 insertions, 0 deletions
diff --git a/src/vppinfra/graph.c b/src/vppinfra/graph.c new file mode 100644 index 00000000000..98a29046f17 --- /dev/null +++ b/src/vppinfra/graph.c @@ -0,0 +1,182 @@ +/* + * 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)); + /* *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: + */ |