PATCHv2 2/2: Efficient dedup for unsorted completions

[Mikael Magnusson <mikachu@xxxxxxxxx>]

Got rid of the pointless extra layer of pointers.

---
 Src/Zle/comp.h     |  1 +
 Src/Zle/compcore.c | 54 ++++++++++++++++++++++++++++++++++--------------------
 2 files changed, 35 insertions(+), 20 deletions(-)

diff --git a/Src/Zle/comp.h b/Src/Zle/comp.h
index a8480c2bac..2ca779fe53 100644
--- a/Src/Zle/comp.h
+++ b/Src/Zle/comp.h
@@ -140,6 +140,7 @@ struct cmatch {
 #define CMF_ALL      (1<<13)	/* a match representing all other matches */
 #define CMF_DUMMY    (1<<14)	/* unselectable dummy match */
 #define CMF_MORDER   (1<<15)    /* order by matches, not display strings */
+#define CMF_DELETE   (1<<16)    /* used for deduplication of unsorted matches, don't set */
 
 /* Stuff for completion matcher control. */
 
diff --git a/Src/Zle/compcore.c b/Src/Zle/compcore.c
index a9ace5587b..0b5b22a306 100644
--- a/Src/Zle/compcore.c
+++ b/Src/Zle/compcore.c
@@ -3284,30 +3284,44 @@ makearray(LinkList l, int type, int flags, int *np, int *nlp, int *llp)
 	    }
 	/* used -O nosort or -V, don't sort */
 	} else {
-	    /* didn't use -1 or -2, so remove all duplicates (inefficient) */
+	    /* didn't use -1 or -2, so remove all duplicates (efficient) */
 	    if (!(flags & CGF_UNIQALL) && !(flags & CGF_UNIQCON)) {
-                int dup;
-
-		for (ap = rp; *ap; ap++) {
-		    for (bp = cp = ap + 1; *bp; bp++) {
-			if (!matcheq(*ap, *bp))
-			    *cp++ = *bp;
-			else
+                int dup, i, del = 0;
+
+		/* To avoid O(n^2) here, sort a copy of the list, then remove marked elements */
+		matchorder = flags;
+		Cmatch *sp, *asp;
+		sp = (Cmatch *) zhalloc((n + 1) * sizeof(Cmatch));
+		memcpy(sp, rp, (n + 1) * sizeof(Cmatch));
+		qsort((void *) sp, n, sizeof(Cmatch),
+		      (int (*) _((const void *, const void *)))matchcmp);
+		for (asp = sp + 1; *asp; asp++) {
+		    Cmatch *ap = asp - 1, *bp = asp;
+		    if (matcheq(*ap, *bp)) {
+			bp[0]->flags = CMF_DELETE;
+			del = 1;
+		    } else if (!ap[0]->disp) {
+			/* Mark those, that would show the same string in the list. */
+			for (dup = 0; bp[0] && !(bp[0])->disp &&
+				 !strcmp((*ap)->str, (bp[0])->str); bp = ++sp) {
+			    (bp[0])->flags |= CMF_MULT;
+			    dup = 1;
+			}
+			if (dup)
+			    (*ap)->flags |= CMF_FMULT;
+		    }
+		}
+		if (del) {
+		    int n_orig = n;
+		    for (bp = rp, ap = rp; bp < rp + n_orig; ap++, bp++) {
+			while (bp[0]->flags & CMF_DELETE) {
+			    bp++;
 			    n--;
+			}
+			*ap = *bp;
 		    }
-		    *cp = NULL;
-                    if (!(*ap)->disp) {
-                        for (dup = 0, bp = ap + 1; *bp; bp++)
-                            if (!(*bp)->disp &&
-                                !((*bp)->flags & CMF_MULT) &&
-                                !strcmp((*ap)->str, (*bp)->str)) {
-                                (*bp)->flags |= CMF_MULT;
-                                dup = 1;
-                            }
-                        if (dup)
-                            (*ap)->flags |= CMF_FMULT;
-                    }
 		}
+		*ap = NULL;
 	    /* passed -1 but not -2, so remove consecutive duplicates (efficient) */
 	    } else if (!(flags & CGF_UNIQCON)) {
 		int dup;
-- 
2.15.1