glib/gpattern.c

   1 /* GLIB - Library of useful routines for C programming
   2  * Copyright (C) 1995-1997, 1999  Peter Mattis, Red Hat, Inc.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19 #include "gpattern.h"
  20
  21 #include "gmacros.h"
  22 #include "gmessages.h"
  23 #include "gmem.h"
  24 #include "gutils.h" /* inline hassle */
  25 #include <string.h>
  26
  27 /* keep enum and structure of gpattern.c and patterntest.c in sync */
  28 typedef enum
  29 {
  30   G_MATCH_ALL,       /* "*A?A*" */
  31   G_MATCH_ALL_TAIL,  /* "*A?AA" */
  32   G_MATCH_HEAD,      /* "AAAA*" */
  33   G_MATCH_TAIL,      /* "*AAAA" */
  34   G_MATCH_EXACT,     /* "AAAAA" */
  35   G_MATCH_LAST
  36 } GMatchType;
  37 struct _GPatternSpec
  38 {
  39   GMatchType match_type;
  40   guint      pattern_length;
  41   gchar     *pattern;
  42 };
  43
  44
  45 /* --- functions --- */
  46 static inline void
  47 instring_reverse (guint  length,
  48                   gchar *str)
  49 {
  50   gchar *f, *l, *b;
  51
  52   f = str;
  53   l = str + length - 1;
  54   b = str + length / 2;
  55   while (f < b)
  56     {
  57       gchar tmp = *l;
  58
  59       *l-- = *f;
  60       *f++ = tmp;
  61     }
  62 }
  63
  64 static inline gchar*
  65 strdup_reverse (guint        length,
  66                 const gchar *str)
  67 {
  68   gchar *t, *dest = g_new (gchar, length + 1);
  69
  70   t = dest + length;
  71   *t-- = 0;
  72   while (t >= dest)
  73     *t-- = *str++;
  74   return dest;
  75 }
  76
  77 static inline gboolean
  78 g_pattern_ph_match (const gchar *match_pattern,
  79                     const gchar *match_string)
  80 {
  81   register const gchar *pattern, *string;
  82   register gchar ch;
  83
  84   pattern = match_pattern;
  85   string = match_string;
  86
  87   ch = *pattern;
  88   pattern++;
  89   while (ch)
  90     {
  91       switch (ch)
  92         {
  93         case '?':
  94           if (!*string)
  95             return FALSE;
  96           string++;
  97           break;
  98
  99         case '*':
 100           do
 101             {
 102               ch = *pattern;
 103               pattern++;
 104               if (ch == '?')
 105                 {
 106                   if (!*string)
 107                     return FALSE;
 108                   string++;
 109                 }
 110             }
 111           while (ch == '*' || ch == '?');
 112           if (!ch)
 113             return TRUE;
 114           do
 115             {
 116               while (ch != *string)
 117                 {
 118                   if (!*string)
 119                     return FALSE;
 120                   string++;
 121                 }
 122               string++;
 123               if (g_pattern_ph_match (pattern, string))
 124                 return TRUE;
 125             }
 126           while (*string);
 127           break;
 128
 129         default:
 130           if (ch == *string)
 131             string++;
 132           else
 133             return FALSE;
 134           break;
 135         }
 136
 137       ch = *pattern;
 138       pattern++;
 139     }
 140
 141   return *string == 0;
 142 }
 143
 144 gboolean
 145 g_pattern_match (GPatternSpec *pspec,
 146                  guint         string_length,
 147                  const gchar  *string,
 148                  const gchar  *string_reversed)
 149 {
 150   g_return_val_if_fail (pspec != NULL, FALSE);
 151   g_return_val_if_fail (string != NULL, FALSE);
 152
 153   switch (pspec->match_type)
 154     {
 155       gboolean result;
 156       gchar *tmp;
 157     case G_MATCH_ALL:
 158       return g_pattern_ph_match (pspec->pattern, string);
 159     case G_MATCH_ALL_TAIL:
 160       if (string_reversed)
 161         return g_pattern_ph_match (pspec->pattern, string_reversed);
 162       else
 163         {
 164           tmp = strdup_reverse (string_length, string);
 165           result = g_pattern_ph_match (pspec->pattern, tmp);
 166           g_free (tmp);
 167           return result;
 168         }
 169     case G_MATCH_HEAD:
 170       if (pspec->pattern_length > string_length)
 171         return FALSE;
 172       else if (pspec->pattern_length == string_length)
 173         return strcmp (pspec->pattern, string) == 0;
 174       else if (pspec->pattern_length)
 175         return strncmp (pspec->pattern, string, pspec->pattern_length) == 0;
 176       else
 177         return TRUE;
 178     case G_MATCH_TAIL:
 179       if (pspec->pattern_length > string_length)
 180         return FALSE;
 181       else if (pspec->pattern_length == string_length)
 182         {
 183           if (string_reversed)
 184             return strcmp (pspec->pattern, string_reversed) == 0;
 185           else
 186             {
 187               tmp = strdup_reverse (string_length, string);
 188               result = strcmp (pspec->pattern, tmp) == 0;
 189               g_free (tmp);
 190               return result;
 191             }
 192         }
 193       else if (pspec->pattern_length)
 194         {
 195           if (string_reversed)
 196             return strncmp (pspec->pattern, string_reversed, pspec->pattern_length) == 0;
 197           else
 198             {
 199               tmp = strdup_reverse (string_length, string);
 200               result = strncmp (pspec->pattern, tmp, pspec->pattern_length) == 0;
 201               g_free (tmp);
 202               return result;
 203             }
 204         }
 205       else
 206         return TRUE;
 207     case G_MATCH_EXACT:
 208       if (pspec->pattern_length != string_length)
 209         return FALSE;
 210       else
 211         return strcmp (pspec->pattern, string) == 0;
 212     default:
 213       g_return_val_if_fail (pspec->match_type < G_MATCH_LAST, FALSE);
 214       return FALSE;
 215     }
 216 }
 217
 218 GPatternSpec*
 219 g_pattern_spec_new (const gchar *pattern)
 220 {
 221   GPatternSpec *pspec;
 222   gboolean seen_joker = FALSE, seen_wildcard = FALSE, more_wildcards = FALSE;
 223   gint hw_pos = -1, tw_pos = -1, hj_pos = -1, tj_pos = -1;
 224   gboolean follows_wildcard = FALSE;
 225   const gchar *s;
 226   gchar *d;
 227   guint i;
 228
 229   g_return_val_if_fail (pattern != NULL, NULL);
 230
 231   /* canonicalize pattern and collect necessary stats */
 232   pspec = g_new (GPatternSpec, 1);
 233   pspec->pattern_length = strlen (pattern);
 234   pspec->pattern = g_new (gchar, pspec->pattern_length + 1);
 235   d = pspec->pattern;
 236   for (i = 0, s = pattern; *s != 0; s++)
 237     {
 238       switch (*s)
 239         {
 240         case '*':
 241           if (follows_wildcard) /* compress multiple wildcards */
 242             {
 243               pspec->pattern_length--;
 244               continue;
 245             }
 246           follows_wildcard = TRUE;
 247           if (hw_pos < 0)
 248             hw_pos = i;
 249           tw_pos = i;
 250           break;
 251         case '?':
 252           if (hj_pos < 0)
 253             hj_pos = i;
 254           tj_pos = i;
 255           /* fall through */
 256         default:
 257           follows_wildcard = FALSE;
 258           break;
 259         }
 260       *d++ = *s;
 261       i++;
 262     }
 263   *d++ = 0;
 264   seen_joker = hj_pos >= 0;
 265   seen_wildcard = hw_pos >= 0;
 266   more_wildcards = seen_wildcard && hw_pos != tw_pos;
 267
 268   /* special case sole head/tail wildcard or exact matches */
 269   if (!seen_joker && !more_wildcards)
 270     {
 271       if (pspec->pattern[0] == '*')
 272         {
 273           pspec->match_type = G_MATCH_TAIL;
 274           instring_reverse (pspec->pattern_length, pspec->pattern);
 275           pspec->pattern[--pspec->pattern_length] = 0;
 276           return pspec;
 277         }
 278       if (pspec->pattern[pspec->pattern_length - 1] == '*')
 279         {
 280           pspec->match_type = G_MATCH_HEAD;
 281           pspec->pattern[--pspec->pattern_length] = 0;
 282           return pspec;
 283         }
 284       if (!seen_wildcard)
 285         {
 286           pspec->match_type = G_MATCH_EXACT;
 287           return pspec;
 288         }
 289     }
 290
 291   /* now just need to distinguish between head or tail match start */
 292   tw_pos = pspec->pattern_length - 1 - tw_pos;  /* last pos to tail distance */
 293   tj_pos = pspec->pattern_length - 1 - tj_pos;  /* last pos to tail distance */
 294   if (seen_wildcard)
 295     pspec->match_type = tw_pos > hw_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 296   else /* seen_joker */
 297     pspec->match_type = tj_pos > hj_pos ? G_MATCH_ALL_TAIL : G_MATCH_ALL;
 298   if (pspec->match_type == G_MATCH_ALL_TAIL)
 299     instring_reverse (pspec->pattern_length, pspec->pattern);
 300   return pspec;
 301 }
 302
 303 void
 304 g_pattern_spec_free (GPatternSpec *pspec)
 305 {
 306   g_return_if_fail (pspec != NULL);
 307
 308   g_free (pspec->pattern);
 309   g_free (pspec);
 310 }
 311
 312 gboolean
 313 g_pattern_spec_equal (GPatternSpec *pspec1,
 314                       GPatternSpec *pspec2)
 315 {
 316   g_return_val_if_fail (pspec1 != NULL, FALSE);
 317   g_return_val_if_fail (pspec2 != NULL, FALSE);
 318
 319   return (pspec1->pattern_length == pspec2->pattern_length &&
 320           pspec1->match_type == pspec2->match_type &&
 321           strcmp (pspec1->pattern, pspec2->pattern) == 0);
 322 }
 323
 324 gboolean
 325 g_pattern_match_string (GPatternSpec *pspec,
 326                         const gchar  *string)
 327 {
 328   g_return_val_if_fail (pspec != NULL, FALSE);
 329   g_return_val_if_fail (string != NULL, FALSE);
 330
 331   return g_pattern_match (pspec, strlen (string), string, NULL);
 332 }
 333
 334 gboolean
 335 g_pattern_match_simple (const gchar *pattern,
 336                         const gchar *string)
 337 {
 338   GPatternSpec *pspec;
 339   gboolean ergo;
 340
 341   g_return_val_if_fail (pattern != NULL, FALSE);
 342   g_return_val_if_fail (string != NULL, FALSE);
 343
 344   pspec = g_pattern_spec_new (pattern);
 345   ergo = g_pattern_match (pspec, strlen (string), string, NULL);
 346   g_pattern_spec_free (pspec);
 347
 348   return ergo;
 349 }