From: Mikael Magnusson <mikachu@gmail.com>
To: zsh-workers@zsh.org
Subject: PATCH 2/2: [WIP] Efficient dedup for unsorted completions
Date: Sat, 26 Mar 2022 02:43:30 +0100 [thread overview]
Message-ID: <20220326014330.3050-1-mikachu@gmail.com> (raw)
In-Reply-To: <20220326014030.2802-1-mikachu@gmail.com>
This implements my idea for sorting a temporary array and then using
that for deduplication. This is fast enough that -2 isn't needed in
_path_files, and will also help for potential other cases other than
file completion.
PS
I realized a bit late that Cmatch is typedeffed to a pointer so the double
pointer shenanigans are a bit pointless, but I'll leave reworking that
until another evening...
---
Src/Zle/comp.h | 1 +
Src/Zle/compcore.c | 66 +++++++++++++++++++++++++++++++++++++-----------------
2 files changed, 46 insertions(+), 21 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..126cdd3ae9 100644
--- a/Src/Zle/compcore.c
+++ b/Src/Zle/compcore.c
@@ -3191,6 +3191,13 @@ matchcmp(Cmatch *a, Cmatch *b)
matchorder & CGF_NUMSORT) ? SORTIT_NUMERICALLY : 0));
}
+/**/
+static int
+matchcmp_pointer(Cmatch **a, Cmatch **b)
+{
+ return matchcmp(*a, *b);
+}
+
/* This tests whether two matches are equal (would produce the same
* strings on the command line). */
@@ -3284,30 +3291,47 @@ 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
- n--;
+ int dup, i;
+
+ /* To avoid O(n^2) here, sort a temporary list of pointers to the real array */
+ /* TODO: this can probably just be a copy of the array, i forgot Cmatch is typedef to pointer */
+ matchorder = flags;
+ Cmatch **sp, **asp;
+ sp = (Cmatch **) zhalloc((n + 1) * sizeof(Cmatch *));
+ asp = sp;
+ for (i = 0; i < n; i++)
+ *asp++ = rp + i;
+ *asp = NULL;
+ qsort((void *) sp, n, sizeof(Cmatch *),
+ (int (*) _((const void *, const void *)))matchcmp_pointer);
+ for (asp = sp + 1; *asp; asp++) {
+ Cmatch *ap = asp[-1], *bp = asp[0];
+ if (matcheq(*ap, *bp)) {
+ bp[0]->flags = CMF_DELETE;
+ } else if (!ap[0]->disp) {
+ /* Mark those, that would show the same string in the list. */
+ /* Mikael: I haven't tested this other than commenting out matcheq above */
+ Cmatch **bsp = sp;
+ 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;
}
- *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;
- }
}
+ 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;
+ }
+ *ap = NULL;
/* passed -1 but not -2, so remove consecutive duplicates (efficient) */
} else if (!(flags & CGF_UNIQCON)) {
int dup;
--
2.15.1
next prev parent reply other threads:[~2022-03-26 1:43 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-03-15 11:56 PATCH: Fix inverted condition for unique completions Mikael Magnusson
2022-03-17 17:08 ` Mikael Magnusson
2022-03-17 19:17 ` Bart Schaefer
2022-03-17 19:32 ` Mikael Magnusson
2022-03-26 1:40 ` PATCH 1/2: Fix comments for UNIQCON/ALL Mikael Magnusson
2022-03-26 1:43 ` Mikael Magnusson [this message]
2022-03-29 16:07 ` PATCHv2 2/2: Efficient dedup for unsorted completions Mikael Magnusson
2022-03-30 16:41 ` PATCH 2/2: [WIP] " Bart Schaefer
2022-03-30 18:33 ` Mikael Magnusson
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220326014330.3050-1-mikachu@gmail.com \
--to=mikachu@gmail.com \
--cc=zsh-workers@zsh.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/zsh/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).