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 "config.h"
  29 #include <glib.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <errno.h>
  33 #ifndef _MSC_VER
  34 #include <unistd.h>
  35 #endif
  36
  37 typedef enum {
  38         MATCH_LITERAL,
  39         MATCH_ANYCHAR,
  40         MATCH_ANYTHING,
  41         MATCH_ANYTHING_END,
  42         MATCH_INVALID = -1
  43 } MatchType;
  44
  45 typedef struct {
  46         MatchType type;
  47         gchar *str;
  48 } PData;
  49
  50 struct _GPatternSpec {
  51         GSList *pattern;
  52 };
  53
  54 static GSList *
  55 compile_pattern (const gchar *pattern)
  56 {
  57         GSList *list;
  58         size_t i, len;
  59         PData *data;
  60         gchar c;
  61         MatchType last = MATCH_INVALID;
  62         GString *str;
  63         gboolean free_str;
  64
  65         if (pattern == NULL)
  66                 return NULL;
  67
  68         data = NULL;
  69         list = NULL;
  70         free_str = TRUE;
  71         str = g_string_new ("");
  72         for (i = 0, len = strlen (pattern); i < len; i++) {
  73                 c = pattern [i];
  74                 if (c == '*' || c == '?') {
  75                         if (str->len > 0) {
  76                                 data = g_new0 (PData, 1);
  77                                 data->type = MATCH_LITERAL;
  78                                 data->str = g_string_free (str, FALSE);
  79                                 list = g_slist_append (list, data);
  80                                 str = g_string_new ("");
  81                         }
  82
  83                         if (last == MATCH_ANYTHING && c == '*')
  84                                 continue;
  85
  86                         data = g_new0 (PData, 1);
  87                         data->type = (c == '*') ? MATCH_ANYTHING : MATCH_ANYCHAR;
  88                         list = g_slist_append (list, data);
  89                         last = data->type;
  90                 } else {
  91                         g_string_append_c (str, c);
  92                         last = MATCH_LITERAL;
  93                 }
  94         }
  95
  96         if (last == MATCH_ANYTHING && str->len == 0) {
  97                 data->type = MATCH_ANYTHING_END;
  98                 free_str = TRUE;
  99         } else if (str->len > 0) {
 100                 data = g_new0 (PData, 1);
 101                 data->type = MATCH_LITERAL;
 102                 data->str = str->str;
 103                 free_str = FALSE;
 104                 list = g_slist_append (list, data);
 105         }
 106         g_string_free (str, free_str);
 107         return list;
 108 }
 109
 110 #ifdef DEBUG_PATTERN
 111 static void
 112 print_pattern (gpointer data, gpointer user_data)
 113 {
 114         PData *d = (PData *) data;
 115
 116         printf ("Type: %s", d->type == MATCH_LITERAL ? "literal" : d->type == MATCH_ANYCHAR ? "any char" : "anything");
 117         if (d->type == MATCH_LITERAL)
 118                 printf (" String: %s", d->str);
 119         printf ("\n");
 120 }
 121 #endif
 122
 123 GPatternSpec *
 124 g_pattern_spec_new (const gchar *pattern)
 125 {
 126         GPatternSpec *spec;
 127
 128         g_return_val_if_fail (pattern != NULL, NULL);
 129         spec = g_new0 (GPatternSpec, 1);
 130         if (pattern) {
 131                 spec->pattern = compile_pattern (pattern);
 132 #ifdef DEBUG_PATTERN
 133                 g_slist_foreach (spec->pattern, print_pattern, NULL);
 134                 printf ("\n");
 135 #endif
 136         }
 137         return spec;
 138 }
 139
 140 static void
 141 free_pdata (gpointer data, gpointer user_data)
 142 {
 143         PData *d = (PData *) data;
 144
 145         if (d->str)
 146                 g_free (d->str);
 147         g_free (d);
 148 }
 149
 150 void
 151 g_pattern_spec_free (GPatternSpec *pspec)
 152 {
 153         if (pspec) {
 154                 g_slist_foreach (pspec->pattern, free_pdata, NULL);
 155                 g_slist_free (pspec->pattern);
 156                 pspec->pattern = NULL;
 157         }
 158         g_free (pspec);
 159 }
 160
 161 static gboolean
 162 match_string (GSList *list, const gchar *str, size_t idx, size_t max)
 163 {
 164         size_t len;
 165
 166         while (list && idx < max) {
 167                 PData *data = (PData *) list->data;
 168
 169                 if (data->type == MATCH_ANYTHING_END)
 170                         return TRUE;
 171
 172                 if (data->type == MATCH_LITERAL) {
 173                         len = strlen (data->str);
 174                         if (strncmp (&str [idx], data->str, len) != 0)
 175                                 return FALSE;
 176                         idx += len;
 177                         list = list->next;
 178                         if (list) {
 179                                 /*
 180                                  * When recursing, we need this to avoid returning FALSE
 181                                  * because 'list' will not be NULL
 182                                  */
 183                                 data = (PData *) list->data;
 184                                 if (data->type == MATCH_ANYTHING_END)
 185                                         return TRUE;
 186                         }
 187                 } else if (data->type == MATCH_ANYCHAR) {
 188                         idx++;
 189                         list = list->next;
 190                 } else if (data->type == MATCH_ANYTHING) {
 191                         while (idx < max) {
 192                                 if (match_string (list->next, str, idx++, max))
 193                                         return TRUE;
 194                         }
 195                         return FALSE;
 196                 } else {
 197                         g_assert_not_reached ();
 198                 }
 199         }
 200
 201         return (list == NULL && idx >= max);
 202 }
 203 gboolean
 204 g_pattern_match_string (GPatternSpec *pspec, const gchar *string)
 205 {
 206         g_return_val_if_fail (pspec != NULL, FALSE);
 207         g_return_val_if_fail (string != NULL, FALSE);
 208
 209         if (pspec->pattern == NULL)
 210                 return FALSE;
 211         return match_string (pspec->pattern, string, 0, strlen (string));
 212 }
 213
 214