Re: [PATCH 7/7] Accelerate rename_dst setup

> diff --git a/diffcore-rename.c b/diffcore-rename.c
> index 816d2fbac44..fb3c2817c6b 100644
> --- a/diffcore-rename.c
> +++ b/diffcore-rename.c
> @@ -5,67 +5,64 @@
>  #include "cache.h"
>  #include "diff.h"
>  #include "diffcore.h"
> -#include "object-store.h"
>  #include "hashmap.h"
> +#include "object-store.h"

>  #include "progress.h"
>  #include "promisor-remote.h"
> +#include "strmap.h"
>
>  /* Table of rename/copy destinations */
>
>  static struct diff_rename_dst {
> -	struct diff_filespec *two;
> -	struct diff_filepair *pair;
> +	struct diff_filepair *p;
> +	struct diff_filespec *filespec_to_free;
> +	int is_rename; /* false -> just a create; true -> rename or copy */
>  } *rename_dst;
>  static int rename_dst_nr, rename_dst_alloc;
> +/* Mapping from break source pathname to break destination index */
> +static struct strintmap *break_idx = NULL;
>
> -static int find_rename_dst(struct diff_filespec *two)
> -{
> -	int first, last;
> -
> -	first = 0;
> -	last = rename_dst_nr;
> -	while (last > first) {
> -		int next = first + ((last - first) >> 1);
> -		struct diff_rename_dst *dst = &(rename_dst[next]);
> -		int cmp = strcmp(two->path, dst->two->path);
> -		if (!cmp)
> -			return next;
> -		if (cmp < 0) {
> -			last = next;
> -			continue;
> -		}
> -		first = next+1;
> -	}
> -	return -first - 1;
> -}
> -
> -static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two)
> +static struct diff_rename_dst *locate_rename_dst(struct diff_filepair *p)
>  {
> -	int ofs = find_rename_dst(two);
> -	return ofs < 0 ? NULL : &rename_dst[ofs];
> +	/* Lookup by p->ONE->path */
> +	int idx = break_idx ? strintmap_get(break_idx, p->one->path) : -1;

> +	return (idx == -1) ? NULL : &rename_dst[idx];
>  }
>
>  /*
>   * Returns 0 on success, -1 if we found a duplicate.
>   */
> -static int add_rename_dst(struct diff_filespec *two)
> +static int add_rename_dst(struct diff_filepair *p)
>  {
> -	int first = find_rename_dst(two);
> -
> -	if (first >= 0)
> +	/*
> +	 * See t4058; trees might have duplicate entries.  I think
> +	 * trees with duplicate entries should be ignored and we
> +	 * should just leave rename detection on; while the results
> +	 * may be slightly harder to understand, that's merely a
> +	 * result of the underlying tree making no sense.  But I
> +	 * believe everything still works fine, the results do still
> +	 * make sense, and the extra overhead of doing this checking
> +	 * for a few historical weird trees from long ago seems like
> +	 * the dog wagging the tail to me.
> +	 *
> +	 * However: I don't feel like fighting that battle right now.
> +	 * For now, to keep the regression test passing, we have to
> +	 * detect it.  Since the diff machinery passes these to us in
> +	 * adjacent pairs, we just need to check to see if our name
> +	 * matches the previous one.
> +	 *
> +	 * TODO: Dispense with this test, rip out the test in t4058, and
> +	 * lobby folks for the change.
> +	 */
> +	if (rename_dst_nr > 0 &&
> +	    !strcmp(rename_dst[rename_dst_nr-1].p->two->path, p->two->path))
>  		return -1;
> -	first = -first - 1;
>
> -	/* insert to make it at "first" */
>  	ALLOC_GROW(rename_dst, rename_dst_nr + 1, rename_dst_alloc);
> +	rename_dst[rename_dst_nr].p = p;
> +	rename_dst[rename_dst_nr].filespec_to_free = NULL;
> +	rename_dst[rename_dst_nr].is_rename = 0;
>  	rename_dst_nr++;
> -	if (first < rename_dst_nr)
> -		MOVE_ARRAY(rename_dst + first + 1, rename_dst + first,
> -			   rename_dst_nr - first - 1);
> -	rename_dst[first].two = alloc_filespec(two->path);
> -	fill_filespec(rename_dst[first].two, &two->oid, two->oid_valid,
> -		      two->mode);
> -	rename_dst[first].pair = NULL;
>  	return 0;

> @@ -78,6 +75,14 @@ static int rename_src_nr, rename_src_alloc;
>
>  static void register_rename_src(struct diff_filepair *p)
>  {
> +	if (p->broken_pair) {
> +		if (!break_idx) {
> +			break_idx = xmalloc(sizeof(*break_idx));
> +			strintmap_init(break_idx, -1);
> +		}
> +		strintmap_set(break_idx, p->one->path, rename_dst_nr);
> +	}
> +

> @@ -664,8 +653,9 @@ void diffcore_rename(struct diff_options *options)
>  			 */
>  			if (DIFF_PAIR_BROKEN(p)) {
>  				/* broken delete */
> -				struct diff_rename_dst *dst = locate_rename_dst(p->one);
> -				if (dst && dst->pair)
> +				struct diff_rename_dst *dst = locate_rename_dst(p);
> +				assert(dst);