From 744a4397ffedcf001b984b567ad6ffc2200812e6 Mon Sep 17 00:00:00 2001 From: Tim Janik Date: Tue, 20 Sep 2005 11:20:23 +0000 Subject: [PATCH] applied significant recursion complexity optimization, based on a patch Tue Sep 20 13:16:04 2005 Tim Janik * glib/gpattern.c (g_pattern_ph_match): applied significant recursion complexity optimization, based on a patch from Matthias Clasen. * tests/patterntest.c: more tests, mostly from matthias. --- ChangeLog | 7 +++++++ ChangeLog.pre-2-10 | 7 +++++++ ChangeLog.pre-2-12 | 7 +++++++ glib/gpattern.c | 23 +++++++++++++++++------ tests/patterntest.c | 16 +++++++++++++++- 5 files changed, 53 insertions(+), 7 deletions(-) diff --git a/ChangeLog b/ChangeLog index 674d220..01136a8 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +Tue Sep 20 13:16:04 2005 Tim Janik + + * glib/gpattern.c (g_pattern_ph_match): applied significant recursion + complexity optimization, based on a patch from Matthias Clasen. + + * tests/patterntest.c: more tests, mostly from matthias. + 2005-09-20 Matthias Clasen * glib/gqueue.c (g_queue_insert_sorted): Correct the docs. diff --git a/ChangeLog.pre-2-10 b/ChangeLog.pre-2-10 index 674d220..01136a8 100644 --- a/ChangeLog.pre-2-10 +++ b/ChangeLog.pre-2-10 @@ -1,3 +1,10 @@ +Tue Sep 20 13:16:04 2005 Tim Janik + + * glib/gpattern.c (g_pattern_ph_match): applied significant recursion + complexity optimization, based on a patch from Matthias Clasen. + + * tests/patterntest.c: more tests, mostly from matthias. + 2005-09-20 Matthias Clasen * glib/gqueue.c (g_queue_insert_sorted): Correct the docs. diff --git a/ChangeLog.pre-2-12 b/ChangeLog.pre-2-12 index 674d220..01136a8 100644 --- a/ChangeLog.pre-2-12 +++ b/ChangeLog.pre-2-12 @@ -1,3 +1,10 @@ +Tue Sep 20 13:16:04 2005 Tim Janik + + * glib/gpattern.c (g_pattern_ph_match): applied significant recursion + complexity optimization, based on a patch from Matthias Clasen. + + * tests/patterntest.c: more tests, mostly from matthias. + 2005-09-20 Matthias Clasen * glib/gqueue.c (g_queue_insert_sorted): Correct the docs. diff --git a/glib/gpattern.c b/glib/gpattern.c index 49bac6b..938083e 100644 --- a/glib/gpattern.c +++ b/glib/gpattern.c @@ -52,10 +52,10 @@ struct _GPatternSpec /* --- functions --- */ - static inline gboolean g_pattern_ph_match (const gchar *match_pattern, - const gchar *match_string) + const gchar *match_string, + gboolean *wildcard_reached_p) { register const gchar *pattern, *string; register gchar ch; @@ -76,6 +76,7 @@ g_pattern_ph_match (const gchar *match_pattern, break; case '*': + *wildcard_reached_p = TRUE; do { ch = *pattern; @@ -92,6 +93,7 @@ g_pattern_ph_match (const gchar *match_pattern, return TRUE; do { + gboolean next_wildcard_reached = FALSE; while (ch != *string) { if (!*string) @@ -99,8 +101,16 @@ g_pattern_ph_match (const gchar *match_pattern, string = g_utf8_next_char (string); } string++; - if (g_pattern_ph_match (pattern, string)) + if (g_pattern_ph_match (pattern, string, &next_wildcard_reached)) return TRUE; + if (next_wildcard_reached) + /* the forthcoming pattern substring up to the next wildcard has + * been matched, but a mismatch occoured for the rest of the + * pattern, following the next wildcard. + * there's no need to advance the current match position any + * further if the rest pattern will not match. + */ + return FALSE; } while (*string); break; @@ -135,17 +145,18 @@ g_pattern_match (GPatternSpec *pspec, switch (pspec->match_type) { + gboolean dummy; case G_MATCH_ALL: - return g_pattern_ph_match (pspec->pattern, string); + return g_pattern_ph_match (pspec->pattern, string, &dummy); case G_MATCH_ALL_TAIL: if (string_reversed) - return g_pattern_ph_match (pspec->pattern, string_reversed); + return g_pattern_ph_match (pspec->pattern, string_reversed, &dummy); else { gboolean result; gchar *tmp; tmp = g_utf8_strreverse (string, string_length); - result = g_pattern_ph_match (pspec->pattern, tmp); + result = g_pattern_ph_match (pspec->pattern, tmp, &dummy); g_free (tmp); return result; } diff --git a/tests/patterntest.c b/tests/patterntest.c index a9aa519..aceeb5d 100644 --- a/tests/patterntest.c +++ b/tests/patterntest.c @@ -281,7 +281,21 @@ main (int argc, char** argv) TEST_MATCH("*fo1*bar", "yyyfoxfo1bar", TRUE); TEST_MATCH("12*fo1g*bar", "12yyyfoxfo1gbar", TRUE); TEST_MATCH("__________:*fo1g*bar", "__________:yyyfoxfo1gbar", TRUE); - + TEST_MATCH("*abc*cde", "abcde", FALSE); + TEST_MATCH("*abc*cde", "abccde", TRUE); + TEST_MATCH("*abc*cde", "abcxcde", TRUE); + TEST_MATCH("*abc*?cde", "abccde", FALSE); + TEST_MATCH("*abc*?cde", "abcxcde", TRUE); + TEST_MATCH("*abc*def", "abababcdededef", TRUE); + TEST_MATCH("*abc*def", "abcbcbcdededef", TRUE); + TEST_MATCH("*acbc*def", "acbcbcbcdededef", TRUE); + TEST_MATCH("*a?bc*def", "acbcbcbcdededef", TRUE); + TEST_MATCH("*abc*def", "bcbcbcdefdef", FALSE); + TEST_MATCH("*abc*def*ghi", "abcbcbcbcbcbcdefefdefdefghi", TRUE); + TEST_MATCH("*abc*def*ghi", "bcbcbcbcbcbcdefdefdefdefghi", FALSE); + TEST_MATCH("_1_2_3_4_5_6_7_8_9_0_1_2_3_4_5_*abc*def*ghi", "_1_2_3_4_5_6_7_8_9_0_1_2_3_4_5_abcbcbcbcbcbcdefefdefdefghi", TRUE); + TEST_MATCH("fooooooo*a*bc", "fooooooo_a_bd_a_bc", TRUE); + verbose ("\n%u tests passed, %u failed\n", passed, failed); return failed; -- 2.7.4