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

> 
> 
> 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?