ucw/wildmatch.c

   1 /*
   2  *      UCW Library -- Fast Pattern Matcher for Short Wildcard Patterns (only `?' and `*' supported)
   3  *
   4  *      Traditional NFA -> DFA method with on-the-fly DFA construction.
   5  *
   6  *      (c) 1999 Martin Mares <mj@ucw.cz>
   7  *
   8  *      This software may be freely distributed and used according to the terms
   9  *      of the GNU Lesser General Public License.
  10  */
  11
  12 #include "ucw/lib.h"
  13 #include "ucw/mempool.h"
  14 #include "ucw/wildmatch.h"
  15
  16 #include <stdio.h>
  17 #include <string.h>
  18
  19 #define MAX_STATES 32           /* Must be <= 32, state 0 is reserved, state 1 is initial */
  20 #define MAX_CACHED 256          /* Maximum number of cached DFA states */
  21 #define HASH_SIZE 512           /* Number of entries in DFA hash table (at least MAX_CACHED+MAX_STATES) */
  22 #define HASH_SKIP 137
  23
  24 struct nfa_state {
  25   char ch;                      /* 0 for non-matching state */
  26   byte final;                   /* Accepting state */
  27   u32 match_states;             /* States to go to when input character == ch */
  28   u32 default_states;           /* States to go to whatever the input is */
  29 };
  30
  31 struct dfa_state {
  32   uintptr_t edge[256];          /* Outgoing DFA edges. Bit 0 is set for incomplete edges which
  33                                  * contain just state set and clear for complete ones which point
  34                                  * to other states. NULL means `no match'.
  35                                  */
  36   u32 nfa_set;                  /* A set of NFA states this DFA state represents */
  37   int final;                    /* This is an accepting state */
  38   struct dfa_state *next;       /* Next in the chain of free states */
  39 };
  40
  41 struct wildpatt {
  42   struct nfa_state nfa[MAX_STATES];
  43   struct dfa_state *hash[HASH_SIZE];
  44   struct dfa_state *dfa_start;
  45   uns nfa_states;
  46   uns dfa_cache_counter;
  47   struct mempool *pool;
  48   struct dfa_state *free_states;
  49 };
  50
  51 static inline unsigned
  52 wp_hash(u32 set)
  53 {
  54   set ^= set >> 16;
  55   set ^= set >> 8;
  56   return set % HASH_SIZE;
  57 }
  58
  59 static struct dfa_state *
  60 wp_new_state(struct wildpatt *w, u32 set)
  61 {
  62   unsigned h = wp_hash(set);
  63   struct dfa_state *d;
  64   unsigned bit;
  65   u32 def_set;
  66
  67   while (d = w->hash[h])
  68     {
  69       if (d->nfa_set == set)
  70         return d;
  71       h = (h + HASH_SKIP) % HASH_SIZE;
  72     }
  73   if (d = w->free_states)
  74     w->free_states = d->next;
  75   else
  76     d = mp_alloc(w->pool, sizeof(*d));
  77   w->hash[h] = d;
  78   bzero(d, sizeof(*d));
  79   d->nfa_set = set;
  80   def_set = 0;
  81   for(bit=1; bit <= w->nfa_states; bit++)
  82     if (set & (1 << bit))
  83       {
  84         struct nfa_state *n = &w->nfa[bit];
  85         if (n->ch)
  86           d->edge[(unsigned char)n->ch] |= n->match_states | 1;
  87         d->final |= n->final;
  88         def_set |= n->default_states;
  89       }
  90   if (def_set)
  91     {
  92       unsigned i;
  93       def_set |= 1;
  94       for(i=0; i<256; i++)
  95         d->edge[i] |= def_set;
  96     }
  97   w->dfa_cache_counter++;
  98   return d;
  99 }
 100
 101 struct wildpatt *
 102 wp_compile(const char *p, struct mempool *pool)
 103 {
 104   struct wildpatt *w;
 105   uns i;
 106
 107   if (strlen(p) >= MAX_STATES)          /* Too long */
 108     return NULL;
 109   w = mp_alloc_zero(pool, sizeof(*w));
 110   w->pool = pool;
 111   for(i=1; *p; p++)
 112     {
 113       struct nfa_state *n = w->nfa + i;
 114       if (*p == '?')
 115         n->default_states |= 1 << (++i);/* Default edge to a new state */
 116       else if (*p == '*')
 117         n->default_states |= 1 << i;    /* Default edge to the same state */
 118       else
 119         {
 120           n->ch = *p;                   /* Edge to new state labelled with 'c' */
 121           n->match_states = 1 << (++i);
 122         }
 123     }
 124   w->nfa[i].final = 1;
 125   w->nfa_states = i;
 126   w->dfa_start = wp_new_state(w, 1 << 1);
 127   return w;
 128 }
 129
 130 static void
 131 wp_prune_cache(struct wildpatt *w)
 132 {
 133   /*
 134    *    I was unable to trigger cache overflow on my large set of
 135    *    test cases, so I decided to handle it in an extremely dumb
 136    *    way.   --mj
 137    */
 138   int i;
 139   for(i=0; i<HASH_SIZE; i++)
 140     if (w->hash[i] && w->hash[i]->nfa_set != (1 << 1))
 141       {
 142         struct dfa_state *d = w->hash[i];
 143         w->hash[i] = NULL;
 144         d->next = w->free_states;
 145         w->free_states = d;
 146       }
 147   w->dfa_cache_counter = 1;     /* Only the initial state remains */
 148 }
 149
 150 int
 151 wp_match(struct wildpatt *w, const char *s)
 152 {
 153   struct dfa_state *d;
 154
 155   if (w->dfa_cache_counter >= MAX_CACHED)
 156     wp_prune_cache(w);
 157   d = w->dfa_start;
 158   while (*s)
 159     {
 160       uintptr_t next = d->edge[(unsigned char)*s];
 161       if (next & 1)
 162         {
 163           /* Need to lookup/create the destination state */
 164           struct dfa_state *new = wp_new_state(w, next & ~1);
 165           d->edge[(unsigned char)*s] = (uintptr_t) new;
 166           d = new;
 167         }
 168       else if (!next)
 169         return 0;
 170       else
 171         d = (struct dfa_state *) next;
 172       s++;
 173     }
 174   return d->final;
 175 }
 176
 177 int
 178 wp_min_size(const char *p)
 179 {
 180   int s = 0;
 181
 182   while (*p)
 183     if (*p++ != '*')
 184       s++;
 185   return s;
 186 }
 187
 188 #ifdef TEST
 189
 190 void
 191 wp_dump(struct wildpatt *w)
 192 {
 193   int i;
 194
 195   puts("NFA:");
 196   for(i=1; i<=w->nfa_states; i++)
 197     {
 198       struct nfa_state *n = w->nfa + i;
 199       printf("%2d: %d %02x %08x %08x\n", i, n->final, n->ch, n->match_states, n->default_states);
 200     }
 201   puts("DFA:");
 202   for(i=0; i<HASH_SIZE; i++)
 203     if (w->hash[i])
 204       printf("%3d: %08x\n", i, w->hash[i]->nfa_set);
 205   printf("%d DFA states cached.\n", w->dfa_cache_counter);
 206 }
 207
 208 int main(int argc, char **argv)
 209 {
 210   struct wildpatt *w;
 211   char buf[1024];
 212
 213   if (argc != 2) return 1;
 214   w = wp_compile(argv[1], mp_new(65536));
 215   if (!w)
 216     {
 217       puts("Compile error");
 218       return 1;
 219     }
 220   wp_dump(w);
 221   while (fgets(buf, sizeof(buf)-1, stdin))
 222     {
 223       char *c = strchr(buf, '\n');
 224       if (!c) break;
 225       *c = 0;
 226 #if 0
 227       printf("%d\n", wp_match(w, buf));
 228 #else
 229       if (wp_match(w, buf))
 230         puts(buf);
 231 #endif
 232     }
 233   wp_dump(w);
 234   return 0;
 235 }
 236
 237 #endif