glob.c

   1 /*
   2  * Copyright 2005 Timo Hirvonen
   3  */
   4
   5 #include "glob.h"
   6 #include "uchar.h"
   7 #include "list.h"
   8 #include "xmalloc.h"
   9 #include "debug.h"
  10
  11 #include <string.h>
  12
  13 struct glob_item {
  14         struct list_head node;
  15         enum {
  16                 GLOB_STAR,
  17                 GLOB_QMARK,
  18                 GLOB_TEXT
  19         } type;
  20         char text[0];
  21 };
  22
  23 /* simplification:
  24  *
  25  *   ??*? => ???*
  26  *   *?*  => ?*
  27  *   *?   => ?*
  28  *   ...
  29  */
  30 static void simplify(struct list_head *head)
  31 {
  32         struct list_head *item;
  33
  34         item = head->next;
  35         while (item != head) {
  36                 struct list_head *i, *next;
  37                 int qcount = 0;
  38                 int scount = 0;
  39
  40                 i = item;
  41                 do {
  42                         struct glob_item *gi;
  43
  44                         gi = container_of(i, struct glob_item, node);
  45                         if (gi->type == GLOB_STAR) {
  46                                 scount++;
  47                         } else if (gi->type == GLOB_QMARK) {
  48                                 qcount++;
  49                         } else {
  50                                 i = i->next;
  51                                 break;
  52                         }
  53                         i = i->next;
  54                 } while (i != head);
  55
  56                 next = i;
  57
  58                 if (scount) {
  59                         /* move all qmarks to front and
  60                          * if there are >1 stars remove all but the last */
  61                         struct list_head *insert_after = item->prev;
  62
  63                         i = item;
  64                         while (qcount) {
  65                                 struct glob_item *gi;
  66
  67                                 gi = container_of(i, struct glob_item, node);
  68                                 i = i->next;
  69                                 if (gi->type == GLOB_QMARK) {
  70                                         list_del(&gi->node);
  71                                         list_add(&gi->node, insert_after);
  72                                         qcount--;
  73                                 }
  74                         }
  75
  76                         i = item;
  77                         while (scount > 1) {
  78                                 struct glob_item *gi;
  79
  80                                 gi = container_of(i, struct glob_item, node);
  81                                 i = i->next;
  82                                 if (gi->type == GLOB_STAR) {
  83                                         list_del(&gi->node);
  84                                         free(gi);
  85                                         scount--;
  86                                 }
  87                         }
  88                 }
  89
  90                 item = next;
  91         }
  92 }
  93
  94 void glob_compile(struct list_head *head, const char *pattern)
  95 {
  96         int i = 0;
  97
  98         list_init(head);
  99         while (pattern[i]) {
 100                 struct glob_item *item;
 101
 102                 if (pattern[i] == '*') {
 103                         item = xnew(struct glob_item, 1);
 104                         item->type = GLOB_STAR;
 105                         i++;
 106                 } else if (pattern[i] == '?') {
 107                         item = xnew(struct glob_item, 1);
 108                         item->type = GLOB_QMARK;
 109                         i++;
 110                 } else {
 111                         int start, len, j;
 112                         char *str;
 113
 114                         start = i;
 115                         len = 0;
 116                         while (pattern[i]) {
 117                                 if (pattern[i] == '\\') {
 118                                         i++;
 119                                         len++;
 120                                         if (pattern[i])
 121                                                 i++;
 122                                 } else if (pattern[i] == '*') {
 123                                         break;
 124                                 } else if (pattern[i] == '?') {
 125                                         break;
 126                                 } else {
 127                                         i++;
 128                                         len++;
 129                                 }
 130                         }
 131
 132                         item = xmalloc(sizeof(struct glob_item) + len + 1);
 133                         item->type = GLOB_TEXT;
 134
 135                         str = item->text;
 136                         i = start;
 137                         j = 0;
 138                         while (j < len) {
 139                                 if (pattern[i] == '\\') {
 140                                         i++;
 141                                         if (pattern[i]) {
 142                                                 str[j++] = pattern[i++];
 143                                         } else {
 144                                                 str[j++] = '\\';
 145                                         }
 146                                 } else {
 147                                         str[j++] = pattern[i++];
 148                                 }
 149                         }
 150                         str[j] = 0;
 151                 }
 152                 list_add_tail(&item->node, head);
 153         }
 154         simplify(head);
 155 }
 156
 157 void glob_free(struct list_head *head)
 158 {
 159         struct list_head *item = head->next;
 160
 161         while (item != head) {
 162                 struct glob_item *gi;
 163                 struct list_head *next = item->next;
 164
 165                 gi = container_of(item, struct glob_item, node);
 166                 free(gi);
 167                 item = next;
 168         }
 169 }
 170
 171 static int do_glob_match(struct list_head *head, struct list_head *first, const char *text)
 172 {
 173         struct list_head *item = first;
 174
 175         while (item != head) {
 176                 struct glob_item *gitem;
 177
 178                 gitem = container_of(item, struct glob_item, node);
 179                 if (gitem->type == GLOB_TEXT) {
 180                         int len = u_strlen(gitem->text);
 181
 182                         if (u_strncasecmp(gitem->text, text, len))
 183                                 return 0;
 184                         text += strlen(gitem->text);
 185                 } else if (gitem->type == GLOB_QMARK) {
 186                         uchar u;
 187                         int idx = 0;
 188
 189                         u_get_char(text, &idx, &u);
 190                         if (u == 0)
 191                                 return 0;
 192                         text += idx;
 193                 } else if (gitem->type == GLOB_STAR) {
 194                         /* after star there MUST be normal text (or nothing),
 195                          * question marks have been moved before this star and
 196                          * other stars have been sripped (see simplify)
 197                          */
 198                         struct list_head *next;
 199                         struct glob_item *next_gi;
 200                         const char *t;
 201                         int tlen;
 202
 203                         next = item->next;
 204                         if (next == head) {
 205                                 /* this star was the last item => matched */
 206                                 return 1;
 207                         }
 208                         next_gi = container_of(next, struct glob_item, node);
 209                         BUG_ON(next_gi->type != GLOB_TEXT);
 210                         t = next_gi->text;
 211                         tlen = strlen(t);
 212                         while (1) {
 213                                 const char *pos;
 214
 215                                 pos = u_strcasestr(text, t);
 216                                 if (pos == NULL)
 217                                         return 0;
 218                                 if (do_glob_match(head, next->next, pos + tlen))
 219                                         return 1;
 220                                 text = pos + 1;
 221                         }
 222                 }
 223                 item = item->next;
 224         }
 225         return text[0] == 0;
 226 }
 227
 228 int glob_match(struct list_head *head, const char *text)
 229 {
 230         return do_glob_match(head, head->next, text);
 231 }