On Thu, Apr 20, 2017 at 10:00:04AM -0400, Jeff Hostetler wrote:

> Perhaps the thing to learn from this (and the other ones) is that
> we have lots of places where we are building a sorted list by
> iterating over a sorted list.  The insert routines are general
> purpose and cannot assume this, so they search first.  Perhaps it
> would be clearer to have independent _append and _insert functions
> and have the caller explicitly call the appropriate one.  The mainline
> iterations on the existing index could just call the _append form
> and never have to worry about searching or the negative-integer
> return trick.  Whereas, the random iterations (such as on the
> command's arg list), would always call the _insert form.

Yes. I'd be much happier if your patch was flipping between two
general-purpose insertion functions. And if that same trick was used on
the dst side.

Or even, given that this these functions are called from a single
location that has sorted input, the binary search was just replaced
completely with an append combined with a sort-check.

That's not the minimal change you were going for, but I think the end
result is simpler and more consistent.

E.g., something like this:

diff --git a/diffcore-rename.c b/diffcore-rename.c
index f7444c86b..a5c017198 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -43,26 +43,20 @@ static struct diff_rename_dst *locate_rename_dst(struct 
diff_filespec *two)
 }
 
 /*
- * Returns 0 on success, -1 if we found a duplicate.
+ * Returns 0 on success, -1 if we found a duplicate or a sorting problem.
  */
 static int add_rename_dst(struct diff_filespec *two)
 {
-       int first = find_rename_dst(two);
-
-       if (first >= 0)
+       if (rename_dst_nr > 0 &&
+           strcmp(two->path, rename_dst[rename_dst_nr - 1].two->path) <= 0)
                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].two = alloc_filespec(two->path);
+       fill_filespec(rename_dst[rename_dst_nr].two,
+                     two->oid.hash, two->oid_valid, two->mode);
+       rename_dst[rename_dst_nr].pair = NULL;
        rename_dst_nr++;
-       if (first < rename_dst_nr)
-               memmove(rename_dst + first + 1, rename_dst + first,
-                       (rename_dst_nr - first - 1) * sizeof(*rename_dst));
-       rename_dst[first].two = alloc_filespec(two->path);
-       fill_filespec(rename_dst[first].two, two->oid.hash, two->oid_valid,
-                     two->mode);
-       rename_dst[first].pair = NULL;
        return 0;
 }
 
@@ -73,36 +67,17 @@ static struct diff_rename_src {
 } *rename_src;
 static int rename_src_nr, rename_src_alloc;
 
-static struct diff_rename_src *register_rename_src(struct diff_filepair *p)
+static int register_rename_src(struct diff_filepair *p)
 {
-       int first, last;
-       struct diff_filespec *one = p->one;
-       unsigned short score = p->score;
-
-       first = 0;
-       last = rename_src_nr;
-       while (last > first) {
-               int next = (last + first) >> 1;
-               struct diff_rename_src *src = &(rename_src[next]);
-               int cmp = strcmp(one->path, src->p->one->path);
-               if (!cmp)
-                       return src;
-               if (cmp < 0) {
-                       last = next;
-                       continue;
-               }
-               first = next+1;
-       }
+       if (rename_src_nr > 0 &&
+           strcmp(p->one->path, rename_src[rename_src_nr - 1].p->one->path) <= 
0)
+               return -1;
 
-       /* insert to make it at "first" */
        ALLOC_GROW(rename_src, rename_src_nr + 1, rename_src_alloc);
+       rename_src[rename_src_nr].p = p;
+       rename_src[rename_src_nr].score = p->score;
        rename_src_nr++;
-       if (first < rename_src_nr)
-               memmove(rename_src + first + 1, rename_src + first,
-                       (rename_src_nr - first - 1) * sizeof(*rename_src));
-       rename_src[first].p = p;
-       rename_src[first].score = score;
-       return &(rename_src[first]);
+       return 0;
 }
 
 static int basename_same(struct diff_filespec *src, struct diff_filespec *dst)
@@ -468,7 +443,7 @@ void diffcore_rename(struct diff_options *options)
                                continue;
                        else if (add_rename_dst(p->two) < 0) {
                                warning("skipping rename detection, detected"
-                                       " duplicate destination '%s'",
+                                       " duplicate or out-of-order destination 
'%s'",
                                        p->two->path);
                                goto cleanup;
                        }
@@ -486,7 +461,12 @@ void diffcore_rename(struct diff_options *options)
                         */
                        if (p->broken_pair && !p->score)
                                p->one->rename_used++;
-                       register_rename_src(p);
+                       if (register_rename_src(p) < 0) {
+                               warning("skipping rename detection, detected"
+                                       " duplicate or out-of-order source 
'%s'",
+                                       p->one->path);
+                               goto cleanup;
+                       }
                }
                else if (detect_rename == DIFF_DETECT_COPY) {
                        /*
@@ -494,7 +474,12 @@ void diffcore_rename(struct diff_options *options)
                         * one, to indicate ourselves as a user.
                         */
                        p->one->rename_used++;
-                       register_rename_src(p);
+                       if (register_rename_src(p) < 0) {
+                               warning("skipping rename detection, detected"
+                                       " duplicate or out-of-order source 
'%s'",
+                                       p->one->path);
+                               goto cleanup;
+                       }
                }
        }
        if (rename_dst_nr == 0 || rename_src_nr == 0)

Reply via email to