From 6f1a31f0aae6dbd5414b81fb6c0f4ff087146fc5 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Nguy=E1=BB=85n=20Th=C3=A1i=20Ng=E1=BB=8Dc=20Duy?= Date: Tue, 1 Jan 2013 09:44:10 +0700 Subject: [PATCH] wildmatch: advance faster in + patterns MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 Signed-off-by: Junio C Hamano --- 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 97f1daff8..4c37057dd 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 bb425220b..7192bdc1b 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; -- 2.26.2