lib/wildmatch.c

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