From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FROM,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, T_SCC_BODY_TEXT_LINE,UNPARSEABLE_RELAY autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 22604 invoked from network); 29 Mar 2022 16:08:42 -0000 Received: from zero.zsh.org (2a02:898:31:0:48:4558:7a:7368) by inbox.vuxu.org with ESMTPUTF8; 29 Mar 2022 16:08:42 -0000 ARC-Seal: i=1; cv=none; a=rsa-sha256; d=zsh.org; s=rsa-20210803; t=1648570122; b=N/K5lntaErkjKPik6Lspx1hekALheIXkdEmxi/Z98zzv3QhYazD1hXzEr8xGX3iPXGCtnguEvT bObI24+insuA3Gnr8E8YRtV1aC70WrN8S7KQyes1POLtbVGw9bSu5YXFkIZk0A/2Res6gSGlff ti0jBwJSc/E3lIQsLrlZqTfm9wMHHZ41GUqfGVqaBL6N2GX/Q1HsHD9gutTSHb2o8mpLQObksk TXhYQxTCFHZk/2dWwZy5Rp0Vh9YH7UWz0nJ0cFzl4LYxD7NaZ4ZMpBjhNZ0mrTKZ1GCKWpf3Ub 4pOTif6uqFPC/oasBPAjBx76si+5RmpvTkIO5t115hBPew==; ARC-Authentication-Results: i=1; zsh.org; iprev=pass (mail-lf1-f51.google.com) smtp.remote-ip=209.85.167.51; dkim=pass header.d=gmail.com header.s=20210112 header.a=rsa-sha256; dmarc=pass header.from=gmail.com; arc=none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed; d=zsh.org; s=rsa-20210803; t=1648570122; bh=vaLxVoNB6cUx1tHyrYZ808TOysiplTgpNs5cc2z0O/4=; h=List-Archive:List-Owner:List-Post:List-Unsubscribe:List-Subscribe:List-Help: List-Id:Sender:References:In-Reply-To:Message-ID:Date:Subject:To:From: DKIM-Signature:DKIM-Signature; b=Xl0SEcxdnpW++uP5SELB6G5N/abvgjPvQ27hFVbRxCMutD9Wk3HEXX34MxTcnhVN46QIS6dFxR YU6WmaFUFCB3DBpX9gnzRPWUEINkfoDmvmqf7e2gviwnNY/mt2XwdsBAu7WVF04TCwbnbCDZVW 4wDzx5z1/x/8Dv92UfqFrefcXwszIhHuMpHKYjmfoikM/jsCCHMd50kvzn+D2/e/V/b5JqOKvv hGGJ40lWat16FCwdvG8AdbK+uA0r7ez8tekBrUgz0eVS03sab74Bqc7KDXpd2K205S1WyxW7nc n+jrDCQYR6mF7JQ5JH9ywHGtZ6ybKU/8sDNnL0HEIDAkFw==; DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=zsh.org; s=rsa-20210803; h=List-Archive:List-Owner:List-Post:List-Unsubscribe: List-Subscribe:List-Help:List-Id:Sender:References:In-Reply-To:Message-Id: Date:Subject:To:From:Reply-To:Cc:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID; bh=sUPsNhI8awjkLvV1H2/eg7bvh6712pyCeaqpujhgzVQ=; b=ibHHAbQwoyD2MxgEq71l7bI3zC /YV2dAj86kjMstUo05I6hbGyFTDEu9B6PX0AUtGV0YfTYXGvjiSEJSao+TdlQ0wkdxOI34sPy1FCO EKJK4W8rvv2KDmBeoJdxTaRtFM3u0GdMJhk0dMWWd2Mkqstx5DsJpWZ5aUby8XZMd98YTvUhCkTkO 60i7IgjtJiaNDOlskpOnLzMHT2avRRO4aBHscF2WyKK0/B2jgjMPsG1ic5YIxmTHzXLaOv8AeLRGB e9KE9l3elnTxi4Z9WyvJ1K4Cqt2EyGGz+8UXHhNz5SKBkU5dwbxp1sEN6o/T9PSdBAoPYuQ2BPmPT Ly6nAT5A==; Received: from authenticated user by zero.zsh.org with local id 1nZEOf-000EZh-R0; Tue, 29 Mar 2022 16:08:41 +0000 Authentication-Results: zsh.org; iprev=pass (mail-lf1-f51.google.com) smtp.remote-ip=209.85.167.51; dkim=pass header.d=gmail.com header.s=20210112 header.a=rsa-sha256; dmarc=pass header.from=gmail.com; arc=none Received: from mail-lf1-f51.google.com ([209.85.167.51]:35373) by zero.zsh.org with esmtps (TLS1.3:TLS_AES_128_GCM_SHA256:128) id 1nZEO6-000EFu-52; Tue, 29 Mar 2022 16:08:06 +0000 Received: by mail-lf1-f51.google.com with SMTP id h7so31140426lfl.2 for ; Tue, 29 Mar 2022 09:08:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:subject:date:message-id:in-reply-to:references; bh=sUPsNhI8awjkLvV1H2/eg7bvh6712pyCeaqpujhgzVQ=; b=YPGRRqGYL5/AJrN1lqXl4t/lhaFJhch0fYEKNfCuq2sEIP4qTwGzZlPekLpsxz1qBU IP6xZpZZHHSvLdqfzYJ/AH8UZ944tKu8goTgz/n2aBU9HcAWM/XizH3NHrcrRr5BpC8u a7qWLGKk3+RfsPq1AZxk71sn2HjHialnICl7AiNd/bzh7SiSqNFDa+6/HKl7pPM0gun3 Wd5hYUhiiu01jfx+BYRtMFArsyXrwijRyvlnnMnMuRf7antp6mUHXtf3R6cOlbzefEY+ 7AB2MVOPKjDQcw0lpC5efy7aGLgN4E1sXzkv1XB/lCkVfJs5ZM/zmNJVLvVoGgB5Uzrt BaHA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:in-reply-to :references; bh=sUPsNhI8awjkLvV1H2/eg7bvh6712pyCeaqpujhgzVQ=; b=Ihis1tLEcs5s0qNsTPjethM4Cwn2V+To93R7AIJ3AVnIFRrvx4xyNlr8d4WZAkyjwC c9kuFo3L3LzFA0+Ieqz4GI269UC0SVmhwR/vAVq85i8C/k5UmtfWuZi20GBfZLU1tNiC 3g4GYpCM9wZs4l7tcGOrsafPSpqn07quBZttK9twxqagQYfZFl6REwnYhHOxCEzLNG+c vqgjYl6u9m3e7V9K6CWcgqqJO4ueBvLyZntD97ox3y+FG7JCYPodlvJ1lzcIqNeNkRzA o1tyL9ErGTHA0vfvYPQ2KPMrXTfpTaTdP6QJuv0MY8HdsaRC/XrZeL231a15isqcOWfH VWtA== X-Gm-Message-State: AOAM533bgf5O6Cq9si5gJmsCIrImbBncqoBviEiGo16iA1R85cgZ1yMe JsfFv9AtaijDDvDHa9LXChQHDGm+kDY= X-Google-Smtp-Source: ABdhPJwntAMZHBMKuZSiK1dhs5gesNvmdM8l9sJEJ1juNrGRTki1/TWeHOWhfoJ3WP8RS+q+lNohoA== X-Received: by 2002:a05:6512:1154:b0:44a:91c4:6b95 with SMTP id m20-20020a056512115400b0044a91c46b95mr3467723lfg.646.1648570084729; Tue, 29 Mar 2022 09:08:04 -0700 (PDT) Received: from localhost.localdomain (h-212-85-88-110.A230.priv.bahnhof.se. [212.85.88.110]) by smtp.gmail.com with ESMTPSA id p9-20020a05651238c900b0044850d9c838sm2038081lft.4.2022.03.29.09.08.03 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 29 Mar 2022 09:08:04 -0700 (PDT) From: Mikael Magnusson To: zsh-workers@zsh.org Subject: PATCHv2 2/2: Efficient dedup for unsorted completions Date: Tue, 29 Mar 2022 18:07:59 +0200 Message-Id: <20220329160759.25297-1-mikachu@gmail.com> X-Mailer: git-send-email 2.15.1 In-Reply-To: <20220326014330.3050-1-mikachu@gmail.com> References: <20220326014330.3050-1-mikachu@gmail.com> X-Seq: 49915 Archived-At: X-Loop: zsh-workers@zsh.org Errors-To: zsh-workers-owner@zsh.org Precedence: list Precedence: bulk Sender: zsh-workers-request@zsh.org X-no-archive: yes List-Id: List-Help: List-Subscribe: List-Unsubscribe: List-Post: List-Owner: List-Archive: 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