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