[ccan] [PATCH 3/7] aga: Depth first search

[Rusty Russell]

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.