Re: [PATCH 09/13] refs: introduce an iterator interface

[Ramsay Jones <ramsay@ramsayjones.plus.com>]

On 30/05/16 08:55, Michael Haggerty wrote:
[snip]

>  /* Reference is a symbolic reference. */
> diff --git a/refs/files-backend.c b/refs/files-backend.c
> index 8ab4d5f..dbf1587 100644
> --- a/refs/files-backend.c
> +++ b/refs/files-backend.c
> @@ -1,6 +1,7 @@
>  #include "../cache.h"
>  #include "../refs.h"
>  #include "refs-internal.h"
> +#include "../iterator.h"
>  #include "../lockfile.h"
>  #include "../object.h"
>  #include "../dir.h"
> @@ -704,6 +705,154 @@ static void prime_ref_dir(struct ref_dir *dir)
>  	}
>  }
>  
> +/*
> + * A level in the reference hierarchy that is currently being iterated
> + * through.
> + */
> +struct cache_ref_iterator_level {
> +	/*
> +	 * The ref_dir being iterated over at this level. The ref_dir
> +         * is sorted before being stored here.
> +	 */
> +	struct ref_dir *dir;
> +
> +	/*
> +	 * The index of the current entry within dir (which might
> +	 * itself be a directory). If index == -1, then the iteration
> +	 * hasn't yet begun. If index == dir->nr, then the iteration
> +	 * through this level is over.
> +	 */
> +	int index;
> +};
> +
> +/*
> + * Represent an iteration through a ref_dir in the memory cache. The
> + * iteration recurses through subdirectories.
> + */
> +struct cache_ref_iterator {
> +	struct ref_iterator base;
> +
> +	/*
> +	 * The number of levels currently on the stack. This is always
> +	 * at least 1, because when it becomes zero the iteration is
> +	 * ended and this struct is freed.
> +	 */
> +	size_t levels_nr;
> +
> +	/* The number of levels that have been allocated on the stack */
> +	size_t levels_alloc;
> +
> +	/*
> +	 * A stack of levels. levels[0] is the uppermost level that is
> +	 * being iterated over in this iteration. (This is not
> +	 * necessary the top level in the references hierarchy. If we
> +	 * are iterating through a subtree, then levels[0] will hold
> +	 * the ref_dir for that subtree, and subsequent levels will go
> +	 * on from there.)
> +	 */
> +	struct cache_ref_iterator_level *levels;
> +};
> +
> +static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)
> +{
> +	struct cache_ref_iterator *iter =
> +		(struct cache_ref_iterator *)ref_iterator;
> +
> +	while (1) {
> +		struct cache_ref_iterator_level *level =
> +			&iter->levels[iter->levels_nr - 1];
> +		struct ref_dir *dir = level->dir;
> +		struct ref_entry *entry;
> +
> +		if (level->index == -1)
> +			sort_ref_dir(dir);

do you need to sort here ...
> +
> +		if (++level->index == level->dir->nr) {
> +			/* This level is exhausted; pop up a level */
> +			if (--iter->levels_nr == 0)
> +				return ref_iterator_abort(ref_iterator);
> +
> +			continue;
> +		}
> +
> +		entry = dir->entries[level->index];
> +
> +		if (entry->flag & REF_DIR) {
> +			/* push down a level */
> +			ALLOC_GROW(iter->levels, iter->levels_nr + 1,
> +				   iter->levels_alloc);
> +
> +			level = &iter->levels[iter->levels_nr++];
> +			level->dir = get_ref_dir(entry);
> +			sort_ref_dir(level->dir);

... given that you sort here?

> +			level->index = -1;
> +		} else {
> +			iter->base.refname = entry->name;
> +			iter->base.oid = &entry->u.value.oid;
> +			iter->base.flags = entry->flag;
> +			return ITER_OK;
> +		}
> +	}
> +}
> +

ATB,
Ramsay Jones