[ccan] [PATCH 3/7] aga: Depth first search
Rusty Russell
rusty at rustcorp.com.au
Fri Jul 10 10:56:34 AEST 2015
David Gibson <david at gibson.dropbear.id.au> writes:
> diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
> index 2088c0f..e41ed97 100644
> --- a/ccan/aga/aga.h
> +++ b/ccan/aga/aga.h
> @@ -111,12 +111,17 @@
> #include "config.h"
> #include <string.h>
>
> +#include <ccan/lstack/lstack.h>
> +
> struct aga_graph;
>
> struct aga_node {
> int sequence;
> union {
> - /* Per-algorithm state here */
> + struct {
> + struct lstack_link parent;
> + const void *edge;
> + } dfs;
> } u;
> };
>
> @@ -175,4 +180,14 @@ int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
> (_e) = aga_next_edge((_g), (_n), (_e))) \
> if ((_ei).to)
>
> +/*
> + * Depth first search
> + */
> +
> +int aga_dfs_start(struct aga_graph *g);
> +struct aga_node *aga_dfs_next(struct aga_graph *g, struct aga_node *n);
> +
> +#define aga_dfs_foreach(_n, _g, _start) \
> + for ((_n) = (_start); ((_n) = aga_dfs_next((_g), (_n))) != NULL; )
> +
This API is unexpected (at least to me, a casual observer).
I expected foreach() to call aga_dfs_start() for you, and aga_finish()
too.
I know that would make it hard to feed the reentrancy detection back to
the caller. But I wonder if you want a global callback on re-entrancy
detection, which defaults to aborting. Callers who care will replace
it.
Then you could make aga_dfs_start() return aga_dfs_next(), right? And
return NULL if that re-entrancy checkfn returns.
aga_dfs_next() should probably call aga_finish before returning NULL.
Or maybe not, since you'll need to call it if you break out of the loop?
The result would be:
/* If you break out of the loop, be sure to call aga_finish()! */
#define aga_dfs_foreach(_n, _g, _start) \
for ((_n) = aga_dfs_start(_g); (_n); (_n) = aga_dfs_next((_g), (_n)))
Cheers,
Rusty.
More information about the ccan
mailing list