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