diff options
Diffstat (limited to 'extras')
| -rw-r--r-- | extras/deprecated/vppinfra/graph.c | 182 | ||||
| -rw-r--r-- | extras/deprecated/vppinfra/graph.h | 127 |
2 files changed, 309 insertions, 0 deletions
diff --git a/extras/deprecated/vppinfra/graph.c b/extras/deprecated/vppinfra/graph.c new file mode 100644 index 00000000000..4c92f8ef45f --- /dev/null +++ b/extras/deprecated/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); + 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: + */ diff --git a/extras/deprecated/vppinfra/graph.h b/extras/deprecated/vppinfra/graph.h new file mode 100644 index 00000000000..1c26118f76c --- /dev/null +++ b/extras/deprecated/vppinfra/graph.h @@ -0,0 +1,127 @@ +/* + * 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. + */ +#ifndef included_clib_graph_h +#define included_clib_graph_h + +#include <vppinfra/format.h> +#include <vppinfra/hash.h> +#include <vppinfra/pool.h> + +/* Generic graphs. */ +typedef struct +{ + /* Next node along this link. */ + u32 node_index; + + /* Other direction link index to reach back to current node. */ + u32 link_to_self_index; + + /* Distance to next node. */ + u32 distance; +} graph_link_t; + +/* Direction on graph: either next or previous. */ +typedef struct +{ + /* Vector of links. */ + graph_link_t *links; + + /* Hash mapping node index to link which visits this node. */ + uword *link_index_by_node_index; +} graph_dir_t; + +always_inline void +graph_dir_free (graph_dir_t * d) +{ + vec_free (d->links); + hash_free (d->link_index_by_node_index); +} + +always_inline graph_link_t * +graph_dir_get_link_to_node (graph_dir_t * d, u32 node_index) +{ + uword *p = hash_get (d->link_index_by_node_index, node_index); + return p ? vec_elt_at_index (d->links, p[0]) : 0; +} + +always_inline uword +graph_dir_add_link (graph_dir_t * d, u32 node_index, u32 distance) +{ + graph_link_t *l; + ASSERT (!graph_dir_get_link_to_node (d, node_index)); + vec_add2 (d->links, l, 1); + l->node_index = node_index; + l->distance = distance; + hash_set (d->link_index_by_node_index, node_index, l - d->links); + return l - d->links; +} + +always_inline void +graph_dir_del_link (graph_dir_t * d, u32 node_index) +{ + graph_link_t *l = graph_dir_get_link_to_node (d, node_index); + uword li = l - d->links; + uword n_links = vec_len (d->links); + + ASSERT (l != 0); + hash_unset (d->link_index_by_node_index, node_index); + n_links -= 1; + if (li < n_links) + d->links[li] = d->links[n_links]; + _vec_len (d->links) = n_links; +} + +typedef struct +{ + /* Nodes we are connected to plus distances. */ + graph_dir_t next, prev; +} graph_node_t; + +typedef struct +{ + /* Pool of nodes. */ + graph_node_t *nodes; + + void *opaque; + + format_function_t *format_node; +} graph_t; + +/* Set link distance, creating link if not found. */ +u32 graph_set_link (graph_t * g, u32 src, u32 dst, u32 distance); + +always_inline void +graph_set_bidirectional_link (graph_t * g, u32 src, u32 dst, u32 distance) +{ + graph_set_link (g, src, dst, distance); + graph_set_link (g, dst, src, distance); +} + +void graph_del_link (graph_t * g, u32 src, u32 dst); +uword graph_del_node (graph_t * g, u32 src); + +unformat_function_t unformat_graph; +format_function_t format_graph; +format_function_t format_graph_node; + +#endif /* included_clib_graph_h */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |