mono/eglib/gpattern.c

   1 /*
   2  * Simple pattern matching
   3  *
   4  * Author:
   5  *   Gonzalo Paniagua Javier (gonzalo@novell.com
   6  *
   7  * (C) 2006 Novell, Inc.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining
  10  * a copy of this software and associated documentation files (the
  11  * "Software"), to deal in the Software without restriction, including
  12  * without limitation the rights to use, copy, modify, merge, publish,
  13  * distribute, sublicense, and/or sell copies of the Software, and to
  14  * permit persons to whom the Software is furnished to do so, subject to
  15  * the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27  */
  28 #include <glib.h>
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <errno.h>
  32 #ifndef _MSC_VER
  33 #include <unistd.h>
  34 #endif
  35
  36 typedef enum {
  37         MATCH_LITERAL,
  38         MATCH_ANYCHAR,
  39         MATCH_ANYTHING,
  40         MATCH_ANYTHING_END,
  41         MATCH_INVALID = -1
  42 } MatchType;
  43
  44 typedef struct {
  45         MatchType type;
  46         gchar *str;
  47 } PData;
  48
  49 struct _GPatternSpec {
  50         GSList *pattern;
  51 };
  52
  53 static GSList *
  54 compile_pattern (const gchar *pattern)
  55 {
  56         GSList *list;
  57         size_t i, len;
  58         PData *data;
  59         gchar c;
  60         MatchType last = MATCH_INVALID;
  61         GString *str;
  62         gboolean free_str;
  63
  64         if (pattern == NULL)
  65                 return NULL;
  66
  67         data = NULL;
  68         list = NULL;
  69         free_str = TRUE;
  70         str = g_string_new ("");
  71         for (i = 0, len = strlen (pattern); i < len; i++) {
  72                 c = pattern [i];
  73                 if (c == '*' || c == '?') {
  74                         if (str->len > 0) {
  75                                 data = g_new0 (PData, 1);
  76                                 data->type = MATCH_LITERAL;
  77                                 data->str = g_string_free (str, FALSE);
  78                                 list = g_slist_append (list, data);
  79                                 str = g_string_new ("");
  80                         }
  81
  82                         if (last == MATCH_ANYTHING && c == '*')
  83                                 continue;
  84
  85                         data = g_new0 (PData, 1);
  86                         data->type = (c == '*') ? MATCH_ANYTHING : MATCH_ANYCHAR;
  87                         list = g_slist_append (list, data);
  88                         last = data->type;
  89                 } else {
  90                         g_string_append_c (str, c);
  91                         last = MATCH_LITERAL;
  92                 }
  93         }
  94
  95         if (last == MATCH_ANYTHING && str->len == 0) {
  96                 data->type = MATCH_ANYTHING_END;
  97                 free_str = TRUE;
  98         } else if (str->len > 0) {
  99                 data = g_new0 (PData, 1);
 100                 data->type = MATCH_LITERAL;
 101                 data->str = str->str;
 102                 free_str = FALSE;
 103                 list = g_slist_append (list, data);
 104         }
 105         g_string_free (str, free_str);
 106         return list;
 107 }
 108
 109 #ifdef DEBUG_PATTERN
 110 static void
 111 print_pattern (gpointer data, gpointer user_data)
 112 {
 113         PData *d = (PData *) data;
 114
 115         printf ("Type: %s", d->type == MATCH_LITERAL ? "literal" : d->type == MATCH_ANYCHAR ? "any char" : "anything");
 116         if (d->type == MATCH_LITERAL)
 117                 printf (" String: %s", d->str);
 118         printf ("\n");
 119 }
 120 #endif
 121
 122 GPatternSpec *
 123 g_pattern_spec_new (const gchar *pattern)
 124 {
 125         GPatternSpec *spec;
 126
 127         g_return_val_if_fail (pattern != NULL, NULL);
 128         spec = g_new0 (GPatternSpec, 1);
 129         if (pattern) {
 130                 spec->pattern = compile_pattern (pattern);
 131 #ifdef DEBUG_PATTERN
 132                 g_slist_foreach (spec->pattern, print_pattern, NULL);
 133                 printf ("\n");
 134 #endif
 135         }
 136         return spec;
 137 }
 138
 139 static void
 140 free_pdata (gpointer data, gpointer user_data)
 141 {
 142         PData *d = (PData *) data;
 143
 144         if (d->str)
 145                 g_free (d->str);
 146         g_free (d);
 147 }
 148
 149 void
 150 g_pattern_spec_free (GPatternSpec *pspec)
 151 {
 152         if (pspec) {
 153                 g_slist_foreach (pspec->pattern, free_pdata, NULL);
 154                 g_slist_free (pspec->pattern);
 155                 pspec->pattern = NULL;
 156         }
 157         g_free (pspec);
 158 }
 159
 160 static gboolean
 161 match_string (GSList *list, const gchar *str, size_t idx, size_t max)
 162 {
 163         size_t len;
 164
 165         while (list && idx < max) {
 166                 PData *data = (PData *) list->data;
 167
 168                 if (data->type == MATCH_ANYTHING_END)
 169                         return TRUE;
 170
 171                 if (data->type == MATCH_LITERAL) {
 172                         len = strlen (data->str);
 173                         if (strncmp (&str [idx], data->str, len) != 0)
 174                                 return FALSE;
 175                         idx += len;
 176                         list = list->next;
 177                         if (list) {
 178                                 /*
 179                                  * When recursing, we need this to avoid returning FALSE
 180                                  * because 'list' will not be NULL
 181                                  */
 182                                 data = (PData *) list->data;
 183                                 if (data->type == MATCH_ANYTHING_END)
 184                                         return TRUE;
 185                         }
 186                 } else if (data->type == MATCH_ANYCHAR) {
 187                         idx++;
 188                         list = list->next;
 189                 } else if (data->type == MATCH_ANYTHING) {
 190                         while (idx < max) {
 191                                 if (match_string (list->next, str, idx++, max))
 192                                         return TRUE;
 193                         }
 194                         return FALSE;
 195                 } else {
 196                         g_assert_not_reached ();
 197                 }
 198         }
 199
 200         return (list == NULL && idx >= max);
 201 }
 202 gboolean
 203 g_pattern_match_string (GPatternSpec *pspec, const gchar *string)
 204 {
 205         g_return_val_if_fail (pspec != NULL, FALSE);
 206         g_return_val_if_fail (string != NULL, FALSE);
 207
 208         if (pspec->pattern == NULL)
 209                 return FALSE;
 210         return match_string (pspec->pattern, string, 0, strlen (string));
 211 }
 212
 213