[ccan] [PATCH 1/6] aga: Abstract Graph Algorithms
David Gibson
david at gibson.dropbear.id.au
Wed May 27 21:21:23 AEST 2015
This module implements some standard graph algoriths. Rather than
expecting a specific concrete representation of the graph, it uses
callbacks, so that the calling code can compute the graph edges on the fly.
The graph nodes can also be constructed as they're discovered, although
some information about them does then need to be retained for the life of
the algorithm.
Because the routines rely on a structure embedded within the callers
representation of the graph nodes/states, they're not re-entrant - only
one can be running at a time (per aga_node instance).
This patch just adds the module, with some generic helper routines, no
actual algorithms are implemented yet.
Signed-off-by: David Gibson <david at gibson.dropbear.id.au>
---
ccan/aga/LICENSE | 1 +
ccan/aga/_info | 33 ++++++++++
ccan/aga/aga.c | 91 ++++++++++++++++++++++++++++
ccan/aga/aga.h | 175 +++++++++++++++++++++++++++++++++++++++++++++++++++++
ccan/aga/private.h | 10 +++
5 files changed, 310 insertions(+)
create mode 120000 ccan/aga/LICENSE
create mode 100644 ccan/aga/_info
create mode 100644 ccan/aga/aga.c
create mode 100644 ccan/aga/aga.h
create mode 100644 ccan/aga/private.h
diff --git a/ccan/aga/LICENSE b/ccan/aga/LICENSE
new file mode 120000
index 0000000..dc314ec
--- /dev/null
+++ b/ccan/aga/LICENSE
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/aga/_info b/ccan/aga/_info
new file mode 100644
index 0000000..ff1bc33
--- /dev/null
+++ b/ccan/aga/_info
@@ -0,0 +1,33 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+
+/**
+ * aga - Abstract Graph Algorithms
+ *
+ * This modules contains several standard graph algorithms,
+ * implemented so that they don't rely on a specific represnetation of
+ * the graph structure. Instead, user supplied callbacks can compute
+ * the graph's edges as required. Graph nodes can even be constructed
+ * on the fly as they're discovered by edge traversal.
+ *
+ * License: LGPL (v2.1 or any later version)
+ * Author: David Gibson <david at gibson.dropbear.id.au>
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ return 0;
+ }
+
+ if (strcmp(argv[1], "testdepends") == 0) {
+ printf("ccan/container_of\n");
+ return 0;
+ }
+
+ return 1;
+}
diff --git a/ccan/aga/aga.c b/ccan/aga/aga.c
new file mode 100644
index 0000000..e21852b
--- /dev/null
+++ b/ccan/aga/aga.c
@@ -0,0 +1,91 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include "config.h"
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <ccan/aga/aga.h>
+
+#include "private.h"
+
+void aga_init_graph(struct aga_graph *g, aga_edge_info_fn edge_info,
+ aga_first_edge_fn first_edge, aga_next_edge_fn next_edge)
+{
+ g->sequence = 0;
+ g->error = 0;
+
+ g->edge_info = edge_info;
+ g->first_edge = first_edge;
+ g->next_edge = next_edge;
+}
+
+int aga_error(struct aga_graph *g)
+{
+ return g->error;
+}
+
+void aga_fail(struct aga_graph *g, int error)
+{
+ g->error = error;
+}
+
+int aga_start(struct aga_graph *g)
+{
+ if (g->sequence & 1) /* Odd means someone's already running */
+ return -1;
+ assert(g->error == 0);
+ /* FIXME: Want an atomic cmpxchg to make this thread safe */
+ ++g->sequence;
+ return 0;
+}
+
+bool aga_check_state(const struct aga_graph *g)
+{
+ if (!(g->sequence & 1))
+ return false; /* No algo in progress */
+ if (g->error)
+ return false; /* error state */
+ return true;
+}
+
+void aga_finish(struct aga_graph *g)
+{
+ assert(g->sequence & 1);
+ g->error = 0;
+ g->sequence++;
+}
+
+bool aga_update_node(const struct aga_graph *g, struct aga_node *node)
+{
+ if (node->sequence == g->sequence)
+ return false;
+
+ node->sequence = g->sequence;
+ return true;
+}
+
+const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n)
+{
+ return g->first_edge(g, n);
+}
+
+const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
+ const void *e)
+{
+ if (!e)
+ return NULL;
+ else
+ return g->next_edge(g, n, e);
+}
+
+int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
+ const void *e, struct aga_edge_info *ei)
+{
+ int rc;
+
+ ei->to = NULL;
+ rc = g->edge_info(g, n, e, ei);
+ assert(rc <= 0);
+ return rc;
+}
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
new file mode 100644
index 0000000..21ca13c
--- /dev/null
+++ b/ccan/aga/aga.h
@@ -0,0 +1,175 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_AGA_H
+#define CCAN_AGA_H
+/*
+ * Abstract Graph Algorithms
+ *
+ * This module implements several standard algorithms on "abstract"
+ * (directed) graphs. That is to say rather than requiring a specific
+ * concrete representation of the graph, user-supplied callbacks allow
+ * the graph to be constructed as it is explored.
+ *
+ *
+ * Node representation
+ * ===================
+ *
+ * Graph nodes are represented by 'struct aga_node'
+ *
+ * - These will often be embedded in a caller-specific structure
+ * (calling code can then locate its own structures using
+ * container_of)
+ *
+ * - Nodes are semi-persistent - they MAY be constructed on the fly by
+ * the edge_info callback (see below), but MUST then remain in place
+ * at least as long as the completion of the current graph
+ * algorithm.
+ *
+ * - Nodes must be initialized with aga_node_init(), either up front,
+ * or as they are constructed on the fly.
+ *
+ * - The contents of the structure should be treated as opaque by the
+ * caller.
+ *
+ *
+ * Edge representation
+ * ===================
+ *
+ * Graph edges are reported by three caller supplied functions,
+ * 'first_edge', 'next_edge' and 'edge_info'.
+ *
+ * - Edges are identified by a (void *)
+ * - The combination of a graph, a node and this (void *) MUST
+ * uniquely identify an edge
+ * - Different edges leading from different nodes MAY have the same
+ * (void *) identifier
+ * - NULL has a special meaning (indicating there are no more edges
+ * from a given node).
+ * - Otherwise, edge identifiers are treated as opaque by aga
+ *
+ * - Calling first_edge, followed by next_edge repeatedly must iterate
+ * through all the edges leading from node n.
+ *
+ * - Either first_edge or next_edge may return NULL indicating there
+ * are no further edges from this node
+ *
+ * - edge_info MAY return a negative value in case of error. This
+ * will generally abort any aga algorithm which encounters it.
+ *
+ * - Otherwise edge_info must return 0. Any other return value will
+ * cause an abort().
+ *
+ * - edge_info MAY set ei->to to NULL, indicating a "missing" edge,
+ * thus there MAY be more edge identifiers than actual edges from a
+ * given node. Otherwise, edge_info MUST fill in the ei->to field
+ * with a pointer to the destination node of the given edge
+ *
+ * - The ei->to field for a returned edge MAY point to an existing
+ * struct aga_node, or it MAY have just been allocated by the edge
+ * callback itself. If the latter, it MUST have been initialized
+ * with aga_node_init() before the edge callback returns.
+ *
+ * - If a node is contructed by the edge callback, any subsequent
+ * reference to that node by the edge callback for *any* node and
+ * index MUST use the same pointer.
+ *
+ * Concurrency
+ * ===========
+ *
+ * - Because the algorithms implemented here keep state in the
+ * aga_node structures, only one algorithm can run at a time.
+ * Global state for algorithms is stored in the aga_graph structure.
+ *
+ * - When you start an algorithm (aga_*_start()) the graph is marked
+ * as in-use.
+ *
+ * - Subsequent attempts to start an algorithm will fail;
+ * aga_*_start() will return -1.
+ *
+ * - To release the graph for another algorithm, use aga_finish().
+ *
+ * - Calling functions associated with one algorithm while another is
+ * running has undefined results.
+ *
+ * Errors
+ * ======
+ *
+ * - Errors may be reported by the edge_info callback, or may be
+ * detected internally by algorithms.
+ *
+ * - Algorithms will generally stop running when they encounter an
+ * error; the call which detects the error and subsequent calls will
+ * return a "safe", but otherwise meaningless value.
+ *
+ * - After an error is encountered aga_error() will return a non-zero
+ * value. Negative values are reserved for errors reported by the
+ * user supplied edge callback. Positive values are reserved for
+ * errors detected interally by aga.
+ *
+ * - Errors are cleared on aga_finish().
+ */
+
+#include "config.h"
+#include <string.h>
+
+struct aga_graph;
+
+struct aga_node {
+ int sequence;
+ union {
+ /* Per-algorithm state here */
+ } u;
+};
+
+struct aga_edge_info {
+ struct aga_node *to;
+};
+
+typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
+ const struct aga_node *n,
+ const void *e, struct aga_edge_info *ei);
+typedef const void *(*aga_first_edge_fn)(const struct aga_graph *g,
+ const struct aga_node *n);
+typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
+ const struct aga_node *n,
+ const void *e);
+
+struct aga_graph {
+ int sequence;
+ int error;
+
+ aga_edge_info_fn edge_info;
+ aga_first_edge_fn first_edge;
+ aga_next_edge_fn next_edge;
+
+ union {
+ } state;
+};
+
+void aga_init_graph(struct aga_graph *g, aga_edge_info_fn edge_info,
+ aga_first_edge_fn first_edge, aga_next_edge_fn next_edge);
+int aga_error(struct aga_graph *g);
+
+static inline void aga_node_init(struct aga_node *node)
+{
+ memset(node, 0, sizeof(*node));
+}
+
+void aga_finish(struct aga_graph *g);
+
+const void *aga_first_edge(const struct aga_graph *g, const struct aga_node *n);
+const void *aga_next_edge(const struct aga_graph *g, const struct aga_node *n,
+ const void *e);
+int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
+ const void *e, struct aga_edge_info *ei);
+
+#define aga_for_each_edge(_e, _g, _n) \
+ for ((_e) = aga_first_edge((_g), (_n)); (_e); \
+ (_e) = aga_next_edge((_g), (_n), (_e)))
+
+#define aga_for_each_edge_info(_e, _ei, _err, _g, _n) \
+ for ((_e) = aga_first_edge((_g), (_n)); \
+ (_e) && ((((_err) = aga_edge_info((_g), (_n), (_e), &(_ei)))) == 0); \
+ (_e) = aga_next_edge((_g), (_n), (_e))) \
+ if ((_ei).to)
+
+#endif /* CCAN_AGA_H */
diff --git a/ccan/aga/private.h b/ccan/aga/private.h
new file mode 100644
index 0000000..ff9f189
--- /dev/null
+++ b/ccan/aga/private.h
@@ -0,0 +1,10 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#ifndef CCAN_AGA_PRIVATE_H
+#define CCAN_AGA_PRIVATE_H
+
+int aga_start(struct aga_graph *g);
+bool aga_update_node(const struct aga_graph *g, struct aga_node *node);
+bool aga_check_state(const struct aga_graph *g);
+void aga_fail(struct aga_graph *g, int error);
+
+#endif /* CCAN_AGA_PRIVATE_H */
--
2.1.0
More information about the ccan
mailing list