From 3b7409ea08a7d1643bc7de31ece63e20b89f319b Mon Sep 17 00:00:00 2001 From: David Gibson Date: Tue, 21 Jul 2015 21:38:22 +1000 Subject: [PATCH 1/1] aga: Abstract Graph Algorithms New module. This patch just adds the module, with some generic helper routines, no actual algorithms are implemented yet. Signed-off-by: David Gibson --- ccan/aga/LICENSE | 1 + ccan/aga/_info | 43 ++++++ ccan/aga/aga.c | 93 +++++++++++ ccan/aga/aga.h | 205 +++++++++++++++++++++++++ ccan/aga/private.h | 10 ++ ccan/aga/test/compile_fail-mismatch1.c | 6 + ccan/aga/test/compile_fail-mismatch2.c | 6 + ccan/aga/test/compile_fail-mismatch3.c | 6 + ccan/aga/test/compile_fail-mismatch4.c | 6 + ccan/aga/test/compile_ok.c | 39 +++++ 10 files changed, 415 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 create mode 100644 ccan/aga/test/compile_fail-mismatch1.c create mode 100644 ccan/aga/test/compile_fail-mismatch2.c create mode 100644 ccan/aga/test/compile_fail-mismatch3.c create mode 100644 ccan/aga/test/compile_fail-mismatch4.c create mode 100644 ccan/aga/test/compile_ok.c diff --git a/ccan/aga/LICENSE b/ccan/aga/LICENSE new file mode 120000 index 00000000..dc314eca --- /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 00000000..22b9a66f --- /dev/null +++ b/ccan/aga/_info @@ -0,0 +1,43 @@ +#include "config.h" +#include +#include + +/** + * aga - Abstract Graph Algorithms + * + * This modules contains several standard graph algorithms, + * implemented so that they don't rely on a specific representation 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. + * + * The algorithms do require a certain amount of persistent data + * per-node. The module doesn't allocate, so the callbacks are + * required to include an aga_node field inside new nodes when they're + * discovered. Because this relies on a structure embedded within the + * caller's representation of the graph nodes/states, it's not + * re-entrant - only one aga algorithm can be running at a time (per + * aga_node instance). + * + * License: LGPL (v2.1 or any later version) + * Author: David Gibson + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/build_assert\n"); + printf("ccan/check_type\n"); + 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 00000000..f27f9f30 --- /dev/null +++ b/ccan/aga/aga.c @@ -0,0 +1,93 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#include "config.h" + +#include +#include +#include + +#include + +#include "private.h" + +void aga_init_graph_(struct aga_graph *g, + aga_first_edge_fn first_edge, + aga_next_edge_fn next_edge, + aga_edge_info_fn edge_info) +{ + g->sequence = 0; + g->error = 0; + + g->first_edge = first_edge; + g->next_edge = next_edge; + g->edge_info = edge_info; +} + +int aga_error(const 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 00000000..d5cc434b --- /dev/null +++ b/ccan/aga/aga.h @@ -0,0 +1,205 @@ +/* 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 + +#include +#include + +struct aga_graph; +struct aga_node; + +/* + * Callbacks + */ +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_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); + +/* + * Internal data structures + */ + +struct aga_node { + int sequence; + union { + /* Per-algorithm state here */ + } u; +}; + +struct aga_graph { + int sequence; + int error; + + aga_first_edge_fn first_edge; + aga_next_edge_fn next_edge; + aga_edge_info_fn edge_info; +}; + +/* + * Core functions + */ + +void aga_init_graph_(struct aga_graph *g, + aga_first_edge_fn first_edge, + aga_next_edge_fn next_edge, + aga_edge_info_fn edge_info); +#define aga_init_graph(g_, fefn_, nefn_, eifn_) \ + do { \ + struct aga_node *n_; \ + struct aga_edge_info *ei_; \ + BUILD_ASSERT(check_types_match((fefn_)((g_), n_), \ + (nefn_)((g_), n_, \ + (fefn_)((g_), n_))) \ + == 0); \ + BUILD_ASSERT(check_type((eifn_)((g_), n_, \ + (fefn_)((g_), n_), ei_), \ + int) == 0); \ + aga_init_graph_((g_), (aga_first_edge_fn)(fefn_), \ + (aga_next_edge_fn)(nefn_), \ + (aga_edge_info_fn)(eifn_)); \ + } while (0) + +int aga_error(const 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 00000000..ff9f1894 --- /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 */ diff --git a/ccan/aga/test/compile_fail-mismatch1.c b/ccan/aga/test/compile_fail-mismatch1.c new file mode 100644 index 00000000..fba829d3 --- /dev/null +++ b/ccan/aga/test/compile_fail-mismatch1.c @@ -0,0 +1,6 @@ +#ifdef FAIL +typedef struct mismatch mismatch_t; +#define EDGE1 mismatch_t +#endif + +#include "compile_ok.c" diff --git a/ccan/aga/test/compile_fail-mismatch2.c b/ccan/aga/test/compile_fail-mismatch2.c new file mode 100644 index 00000000..7b939217 --- /dev/null +++ b/ccan/aga/test/compile_fail-mismatch2.c @@ -0,0 +1,6 @@ +#ifdef FAIL +typedef struct mismatch mismatch_t; +#define EDGE2 mismatch_t +#endif + +#include "compile_ok.c" diff --git a/ccan/aga/test/compile_fail-mismatch3.c b/ccan/aga/test/compile_fail-mismatch3.c new file mode 100644 index 00000000..132309b7 --- /dev/null +++ b/ccan/aga/test/compile_fail-mismatch3.c @@ -0,0 +1,6 @@ +#ifdef FAIL +typedef struct mismatch mismatch_t; +#define EDGE3 mismatch_t +#endif + +#include "compile_ok.c" diff --git a/ccan/aga/test/compile_fail-mismatch4.c b/ccan/aga/test/compile_fail-mismatch4.c new file mode 100644 index 00000000..993014b5 --- /dev/null +++ b/ccan/aga/test/compile_fail-mismatch4.c @@ -0,0 +1,6 @@ +#ifdef FAIL +typedef struct mismatch mismatch_t; +#define EDGE4 mismatch_t +#endif + +#include "compile_ok.c" diff --git a/ccan/aga/test/compile_ok.c b/ccan/aga/test/compile_ok.c new file mode 100644 index 00000000..f830a769 --- /dev/null +++ b/ccan/aga/test/compile_ok.c @@ -0,0 +1,39 @@ +#include "config.h" + +#include +#include + +typedef struct edge edge_t; + +#ifndef EDGE1 +#define EDGE1 edge_t +#endif + +#ifndef EDGE2 +#define EDGE2 edge_t +#endif + +#ifndef EDGE3 +#define EDGE3 edge_t +#endif + +#ifndef EDGE4 +#define EDGE4 edge_t +#endif + +int main(void) +{ + struct aga_graph g; + EDGE1 *(*first_edge)(const struct aga_graph *g, + const struct aga_node *n) = NULL; + EDGE2 *(*next_edge)(const struct aga_graph *g, + const struct aga_node *n, + EDGE3 *e) = NULL; + int (*edge_info)(const struct aga_graph *g, const struct aga_node *n, + EDGE4 *e, struct aga_edge_info *ei) = NULL; + + aga_init_graph(&g, first_edge, next_edge, edge_info); + + return 0; +} + -- 2.39.2