diff -r 000000000000 -r e4d67989cc36 glib/libglib/src/gpattern.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/glib/libglib/src/gpattern.c Tue Feb 02 02:01:42 2010 +0200 @@ -0,0 +1,347 @@ +/* GLIB - Library of useful routines for C programming + * Copyright (C) 1995-1997, 1999 Peter Mattis, Red Hat, Inc. + * Portions copyright (c) 2006 Nokia Corporation. All rights reserved. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 02111-1307, USA. + */ + +#include "config.h" + +#include + +#include "gpattern.h" + +#include "gmacros.h" +#include "gmessages.h" +#include "gmem.h" +#include "gunicode.h" +#include "gutils.h" +#include "galias.h" + +#ifdef __SYMBIAN32__ +#include +#endif /* __SYMBIAN32__ */ + +/* keep enum and structure of gpattern.c and patterntest.c in sync */ +typedef enum +{ + G_MATCH_ALL, /* "*A?A*" */ + G_MATCH_ALL_TAIL, /* "*A?AA" */ + G_MATCH_HEAD, /* "AAAA*" */ + G_MATCH_TAIL, /* "*AAAA" */ + G_MATCH_EXACT, /* "AAAAA" */ + G_MATCH_LAST +} GMatchType; + +struct _GPatternSpec +{ + GMatchType match_type; + guint pattern_length; + guint min_length; + guint max_length; + gchar *pattern; +}; + + +/* --- functions --- */ +static inline gboolean +g_pattern_ph_match (const gchar *match_pattern, + const gchar *match_string, + gboolean *wildcard_reached_p) +{ + register const gchar *pattern, *string; + register gchar ch; + + pattern = match_pattern; + string = match_string; + + ch = *pattern; + pattern++; + while (ch) + { + switch (ch) + { + case '?': + if (!*string) + return FALSE; + string = g_utf8_next_char (string); + break; + + case '*': + *wildcard_reached_p = TRUE; + do + { + ch = *pattern; + pattern++; + if (ch == '?') + { + if (!*string) + return FALSE; + string = g_utf8_next_char (string); + } + } + while (ch == '*' || ch == '?'); + if (!ch) + return TRUE; + do + { + gboolean next_wildcard_reached = FALSE; + while (ch != *string) + { + if (!*string) + return FALSE; + string = g_utf8_next_char (string); + } + 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; + + default: + if (ch == *string) + string++; + else + return FALSE; + break; + } + + ch = *pattern; + pattern++; + } + + return *string == 0; +} + +EXPORT_C gboolean +g_pattern_match (GPatternSpec *pspec, + guint string_length, + const gchar *string, + const gchar *string_reversed) +{ + g_return_val_if_fail (pspec != NULL, FALSE); + g_return_val_if_fail (string != NULL, FALSE); + + if (string_length < pspec->min_length || + string_length > pspec->max_length) + return FALSE; + + switch (pspec->match_type) + { + gboolean dummy; + case G_MATCH_ALL: + 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, &dummy); + else + { + gboolean result; + gchar *tmp; + tmp = g_utf8_strreverse (string, string_length); + result = g_pattern_ph_match (pspec->pattern, tmp, &dummy); + g_free (tmp); + return result; + } + case G_MATCH_HEAD: + if (pspec->pattern_length == string_length) + return strcmp (pspec->pattern, string) == 0; + else if (pspec->pattern_length) + return strncmp (pspec->pattern, string, pspec->pattern_length) == 0; + else + return TRUE; + case G_MATCH_TAIL: + if (pspec->pattern_length) + return strcmp (pspec->pattern, string + (string_length - pspec->pattern_length)) == 0; + else + return TRUE; + case G_MATCH_EXACT: + if (pspec->pattern_length != string_length) + return FALSE; + else + return strcmp (pspec->pattern, string) == 0; + default: + g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE); + return FALSE; + } +} + +EXPORT_C GPatternSpec* +g_pattern_spec_new (const gchar *pattern) +{ + GPatternSpec *pspec; + gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE; + gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1; + gboolean follows_wildcard = FALSE; + guint pending_jokers = 0; + const gchar *s; + gchar *d; + guint i; + + g_return_val_if_fail (pattern != NULL, NULL); + + /* canonicalize pattern and collect necessary stats */ + pspec = g_new (GPatternSpec, 1); + pspec->pattern_length = strlen (pattern); + pspec->min_length = 0; + pspec->pattern = g_new (gchar, pspec->pattern_length + 1); + d = pspec->pattern; + for (i = 0, s = pattern; *s != 0; s++) + { + switch (*s) + { + case '*': + if (follows_wildcard) /* compress multiple wildcards */ + { + pspec->pattern_length--; + continue; + } + follows_wildcard = TRUE; + if (hw_pos < 0) + hw_pos = i; + tw_pos = i; + break; + case '?': + pending_jokers++; + pspec->min_length++; + pspec->max_length += 4; /* maximum UTF-8 character length */ + continue; + default: + for (; pending_jokers; pending_jokers--, i++) { + *d++ = '?'; + if (hj_pos < 0) + hj_pos = i; + tj_pos = i; + } + follows_wildcard = FALSE; + pspec->min_length++; + pspec->max_length++; + break; + } + *d++ = *s; + i++; + } + for (; pending_jokers; pending_jokers--) { + *d++ = '?'; + if (hj_pos < 0) + hj_pos = i; + tj_pos = i; + } + *d++ = 0; + seen_joker = hj_pos >= 0; + seen_wildcard = hw_pos >= 0; + more_wildcards = seen_wildcard && hw_pos != tw_pos; + if (seen_wildcard) + pspec->max_length = G_MAXUINT; + + /* special case sole head/tail wildcard or exact matches */ + if (!seen_joker && !more_wildcards) + { + if (pspec->pattern[0] == '*') + { + pspec->match_type = G_MATCH_TAIL; + memmove (pspec->pattern, pspec->pattern + 1, --pspec->pattern_length); + pspec->pattern[pspec->pattern_length] = 0; + return pspec; + } + if (pspec->pattern_length > 0 && + pspec->pattern[pspec->pattern_length - 1] == '*') + { + pspec->match_type = G_MATCH_HEAD; + pspec->pattern[--pspec->pattern_length] = 0; + return pspec; + } + if (!seen_wildcard) + { + pspec->match_type = G_MATCH_EXACT; + return pspec; + } + } + + /* now just need to distinguish between head or tail match start */ + tw_pos = pspec->pattern_length - 1 - tw_pos; /* last pos to tail distance */ + tj_pos = pspec->pattern_length - 1 - tj_pos; /* last pos to tail distance */ + if (seen_wildcard) + pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL; + else /* seen_joker */ + pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL; + if (pspec->match_type == G_MATCH_ALL_TAIL) { + gchar *tmp = pspec->pattern; + pspec->pattern = g_utf8_strreverse (pspec->pattern, pspec->pattern_length); + g_free (tmp); + } + return pspec; +} + +EXPORT_C void +g_pattern_spec_free (GPatternSpec *pspec) +{ + g_return_if_fail (pspec != NULL); + + g_free (pspec->pattern); + g_free (pspec); +} + +EXPORT_C gboolean +g_pattern_spec_equal (GPatternSpec *pspec1, + GPatternSpec *pspec2) +{ + g_return_val_if_fail (pspec1 != NULL, FALSE); + g_return_val_if_fail (pspec2 != NULL, FALSE); + + return (pspec1->pattern_length == pspec2->pattern_length && + pspec1->match_type == pspec2->match_type && + strcmp (pspec1->pattern, pspec2->pattern) == 0); +} + +EXPORT_C gboolean +g_pattern_match_string (GPatternSpec *pspec, + const gchar *string) +{ + g_return_val_if_fail (pspec != NULL, FALSE); + g_return_val_if_fail (string != NULL, FALSE); + + return g_pattern_match (pspec, strlen (string), string, NULL); +} + +EXPORT_C gboolean +g_pattern_match_simple (const gchar *pattern, + const gchar *string) +{ + GPatternSpec *pspec; + gboolean ergo; + + g_return_val_if_fail (pattern != NULL, FALSE); + g_return_val_if_fail (string != NULL, FALSE); + + pspec = g_pattern_spec_new (pattern); + ergo = g_pattern_match (pspec, strlen (string), string, NULL); + g_pattern_spec_free (pspec); + + return ergo; +} + +#define __G_PATTERN_C__ +#include "galiasdef.c"