zebra, lib: fix the ZEBRA_INTERFACE_VRF_UPDATE zapi message

[mirror_frr.git] / lib / graph.c

diff --git a/lib/graph.c b/lib/graph.c
index 945a58e68850bfd2086c4a2362469629cdff8b7f..4bc3eb82b8521b9b4bc4dd331ef824d1fa8fbe3d 100644 (file)
--- a/lib/graph.c
+++ b/lib/graph.c
@@ -23,6 +23,7 @@
 #include <zebra.h>
 #include "graph.h"
 #include "memory.h"
+#include "buffer.h"
 
 DEFINE_MTYPE_STATIC(LIB, GRAPH, "Graph")
 DEFINE_MTYPE_STATIC(LIB, GRAPH_NODE, "Graph Node")
@@ -34,6 +35,15 @@ struct graph *graph_new()
        return graph;
 }
 
+void graph_delete_graph(struct graph *graph)
+{
+       for (unsigned int i = vector_active(graph->nodes); i--; /**/)
+               graph_delete_node(graph, vector_slot(graph->nodes, i));
+
+       vector_free(graph->nodes);
+       XFREE(MTYPE_GRAPH, graph);
+}
+
 struct graph_node *graph_new_node(struct graph *graph, void *data,
                                  void (*del)(void *))
 {
@@ -50,7 +60,7 @@ struct graph_node *graph_new_node(struct graph *graph, void *data,
        return node;
 }
 
-static void vector_remove(vector v, unsigned int ix)
+static void graph_vector_remove(vector v, unsigned int ix)
 {
        if (ix >= v->active)
                return;
@@ -95,7 +105,7 @@ void graph_delete_node(struct graph *graph, struct graph_node *node)
        // remove node from graph->nodes
        for (unsigned int i = vector_active(graph->nodes); i--; /**/)
                if (vector_slot(graph->nodes, i) == node) {
-                       vector_remove(graph->nodes, i);
+                       graph_vector_remove(graph->nodes, i);
                        break;
                }
 
@@ -116,23 +126,105 @@ void graph_remove_edge(struct graph_node *from, struct graph_node *to)
        // remove from from to->from
        for (unsigned int i = vector_active(to->from); i--; /**/)
                if (vector_slot(to->from, i) == from) {
-                       vector_remove(to->from, i);
+                       graph_vector_remove(to->from, i);
                        break;
                }
        // remove to from from->to
        for (unsigned int i = vector_active(from->to); i--; /**/)
                if (vector_slot(from->to, i) == to) {
-                       vector_remove(from->to, i);
+                       graph_vector_remove(from->to, i);
                        break;
                }
 }
 
-void graph_delete_graph(struct graph *graph)
+struct graph_node *graph_find_node(struct graph *graph, void *data)
 {
-       // delete each node in the graph
-       for (unsigned int i = vector_active(graph->nodes); i--; /**/)
-               graph_delete_node(graph, vector_slot(graph->nodes, i));
+       struct graph_node *g;
 
-       vector_free(graph->nodes);
-       XFREE(MTYPE_GRAPH, graph);
+       for (unsigned int i = vector_active(graph->nodes); i--; /**/) {
+               g = vector_slot(graph->nodes, i);
+               if (g->data == data)
+                       return g;
+       }
+
+       return NULL;
+}
+
+bool graph_has_edge(struct graph_node *from, struct graph_node *to)
+{
+       for (unsigned int i = vector_active(from->to); i--; /**/)
+               if (vector_slot(from->to, i) == to)
+                       return true;
+
+       return false;
+}
+
+static void _graph_dfs(struct graph *graph, struct graph_node *start,
+                      vector visited,
+                      void (*dfs_cb)(struct graph_node *, void *), void *arg)
+{
+       /* check that we have not visited this node */
+       for (unsigned int i = 0; i < vector_active(visited); i++) {
+               if (start == vector_slot(visited, i))
+                       return;
+       }
+
+       /* put this node in visited stack */
+       vector_ensure(visited, vector_active(visited));
+       vector_set_index(visited, vector_active(visited), start);
+
+       /* callback */
+       dfs_cb(start, arg);
+
+       /* recurse into children */
+       for (unsigned int i = vector_active(start->to); i--; /**/) {
+               struct graph_node *c = vector_slot(start->to, i);
+
+               _graph_dfs(graph, c, visited, dfs_cb, arg);
+       }
 }
+
+void graph_dfs(struct graph *graph, struct graph_node *start,
+              void (*dfs_cb)(struct graph_node *, void *), void *arg)
+{
+       vector visited = vector_init(VECTOR_MIN_SIZE);
+
+       _graph_dfs(graph, start, visited, dfs_cb, arg);
+       vector_free(visited);
+}
+
+#ifndef BUILDING_CLIPPY
+
+void graph_dump_dot_default_print_cb(struct graph_node *gn, struct buffer *buf)
+{
+       char nbuf[64];
+
+       for (unsigned int i = 0; i < vector_active(gn->to); i++) {
+               struct graph_node *adj = vector_slot(gn->to, i);
+
+               snprintf(nbuf, sizeof(nbuf), "    n%p -> n%p;\n", gn, adj);
+               buffer_putstr(buf, nbuf);
+       }
+}
+
+char *graph_dump_dot(struct graph *graph, struct graph_node *start,
+                    void (*pcb)(struct graph_node *, struct buffer *))
+{
+       struct buffer *buf = buffer_new(0);
+       char *ret;
+
+       pcb = (pcb) ? pcb : graph_dump_dot_default_print_cb;
+       buffer_putstr(buf, "digraph {\n");
+
+       graph_dfs(graph, start, (void (*)(struct graph_node *, void *))pcb,
+                 buf);
+
+       buffer_putstr(buf, "}\n");
+
+       ret = buffer_getstr(buf);
+       buffer_free(buf);
+
+       return ret;
+}
+
+#endif /* BUILDING_CLIPPY */