From: "Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>
To: git@vger.kernel.org
Cc: "Junio C Hamano" <gitster@pobox.com>,
"Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>
Subject: [PATCH v3 09/10] wildmatch: advance faster in <asterisk> + <literal> patterns
Date: Tue, 1 Jan 2013 09:44:10 +0700 [thread overview]
Message-ID: <1357008251-10014-10-git-send-email-pclouds@gmail.com> (raw)
In-Reply-To: <1357008251-10014-1-git-send-email-pclouds@gmail.com>
Normally when we match "*X" on "abcX", we call dowild("X", "abcX"),
dowild("X", "bcX"), dowild("X", "cX") and dowild("X", "X"). Only the
last call may have a chance of matching. By skipping the text before
"X", we can eliminate the first three useless calls.
compat, '*/*/*' on linux-2.6.git file list 2000 times, before:
wildmatch 7s 985049us
fnmatch 2s 735541us or 34.26% faster
and after:
wildmatch 4s 492549us
fnmatch 0s 888263us or 19.77% slower
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
t/t3070-wildmatch.sh | 8 ++++++++
wildmatch.c | 23 +++++++++++++++++++++++
2 files changed, 31 insertions(+)
diff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh
index 97f1daf..4c37057 100755
--- a/t/t3070-wildmatch.sh
+++ b/t/t3070-wildmatch.sh
@@ -207,6 +207,11 @@ match 0 x foo '*/*/*'
match 0 x foo/bar '*/*/*'
match 1 x foo/bba/arr '*/*/*'
match 0 x foo/bb/aa/rr '*/*/*'
+match 1 x foo/bb/aa/rr '**/**/**'
+match 1 x abcXdefXghi '*X*i'
+match 0 x ab/cXd/efXg/hi '*X*i'
+match 1 x ab/cXd/efXg/hi '*/*X*/*/*i'
+match 1 x ab/cXd/efXg/hi '**/*X*/**/*i'
pathmatch 1 foo foo
pathmatch 0 foo fo
@@ -226,5 +231,8 @@ pathmatch 0 foo '*/*/*'
pathmatch 0 foo/bar '*/*/*'
pathmatch 1 foo/bba/arr '*/*/*'
pathmatch 1 foo/bb/aa/rr '*/*/*'
+pathmatch 1 abcXdefXghi '*X*i'
+pathmatch 1 ab/cXd/efXg/hi '*/*X*/*/*i'
+pathmatch 1 ab/cXd/efXg/hi '*Xg*i'
test_done
diff --git a/wildmatch.c b/wildmatch.c
index bb42522..7192bdc 100644
--- a/wildmatch.c
+++ b/wildmatch.c
@@ -133,6 +133,29 @@ static int dowild(const uchar *p, const uchar *text, unsigned int flags)
while (1) {
if (t_ch == '\0')
break;
+ /*
+ * Try to advance faster when an asterisk is
+ * followed by a literal. We know in this case
+ * that the the string before the literal
+ * must belong to "*".
+ * If match_slash is false, do not look past
+ * the first slash as it cannot belong to '*'.
+ */
+ if (!is_glob_special(*p)) {
+ p_ch = *p;
+ if ((flags & WM_CASEFOLD) && ISUPPER(p_ch))
+ p_ch = tolower(p_ch);
+ while ((t_ch = *text) != '\0' &&
+ (match_slash || t_ch != '/')) {
+ if ((flags & WM_CASEFOLD) && ISUPPER(t_ch))
+ t_ch = tolower(t_ch);
+ if (t_ch == p_ch)
+ break;
+ text++;
+ }
+ if (t_ch != p_ch)
+ return WM_NOMATCH;
+ }
if ((matched = dowild(p, text, flags)) != WM_NOMATCH) {
if (!match_slash || matched != WM_ABORT_TO_STARSTAR)
return matched;
--
1.8.0.rc2.23.g1fb49df
next prev parent reply other threads:[~2013-01-01 2:45 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-01-01 2:44 [PATCH v3 00/10] fnmatch replacement Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 01/10] wildmatch: fix "**" special case Nguyễn Thái Ngọc Duy
2013-01-22 21:36 ` Junio C Hamano
2013-01-22 22:51 ` Junio C Hamano
2013-01-23 1:04 ` Duy Nguyen
2013-01-24 4:49 ` Junio C Hamano
2013-01-24 5:51 ` Duy Nguyen
2013-01-24 18:22 ` Junio C Hamano
2013-01-25 1:46 ` Duy Nguyen
2013-01-25 4:55 ` Junio C Hamano
2013-01-01 2:44 ` [PATCH v3 02/10] compat/fnmatch: respect NO_FNMATCH* even on glibc Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 03/10] wildmatch: replace variable 'special' with better named ones Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 04/10] wildmatch: rename constants and update prototype Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 05/10] wildmatch: make dowild() take arbitrary flags Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 06/10] wildmatch: support "no FNM_PATHNAME" mode Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 07/10] test-wildmatch: add "perf" command to compare wildmatch and fnmatch Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` [PATCH v3 08/10] wildmatch: make a special case for "*/" with FNM_PATHNAME Nguyễn Thái Ngọc Duy
2013-01-01 2:44 ` Nguyễn Thái Ngọc Duy [this message]
2013-01-01 2:44 ` [PATCH v3 10/10] Makefile: add USE_WILDMATCH to use wildmatch as fnmatch Nguyễn Thái Ngọc Duy
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=1357008251-10014-10-git-send-email-pclouds@gmail.com \
--to=pclouds@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
/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.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.