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_zero(pool, sizeof(*w));
 107   w->pool = pool;
 108   for(i=1; *p; p++)
 109     {
 110       struct nfa_state *n = w->nfa + i;
 111       if (*p == '?')
 112         n->default_states |= 1 << (++i);/* Default edge to a new state */
 113       else if (*p == '*')
 114         n->default_states |= 1 << i;    /* Default edge to the same state */
 115       else
 116         {
 117           n->ch = *p;                   /* Edge to new state labelled with 'c' */
 118           n->match_states = 1 << (++i);
 119         }
 120     }
 121   w->nfa[i].final = 1;
 122   w->nfa_states = i;
 123   w->dfa_start = wp_new_state(w, 1 << 1);
 124   return w;
 125 }
 126
 127 static void
 128 wp_prune_cache(struct wildpatt *w)
 129 {
 130   /*
 131    *    I was unable to trigger cache overflow on my large set of
 132    *    test cases, so I decided to handle it in an extremely dumb
 133    *    way.   --mj
 134    */
 135   int i;
 136   for(i=0; i<HASH_SIZE; i++)
 137     if (w->hash[i] && w->hash[i]->nfa_set != (1 << 1))
 138       {
 139         struct dfa_state *d = w->hash[i];
 140         w->hash[i] = NULL;
 141         d->next = w->free_states;
 142         w->free_states = d;
 143       }
 144   w->dfa_cache_counter = 1;     /* Only the initial state remains */
 145 }
 146
 147 int
 148 wp_match(struct wildpatt *w, byte *s)
 149 {
 150   struct dfa_state *d;
 151
 152   if (w->dfa_cache_counter >= MAX_CACHED)
 153     wp_prune_cache(w);
 154   d = w->dfa_start;
 155   while (*s)
 156     {
 157       addr_int_t next = d->edge[*s];
 158       if (next & 1)
 159         {
 160           /* Need to lookup/create the destination state */
 161           struct dfa_state *new = wp_new_state(w, next & ~1);
 162           d->edge[*s] = (addr_int_t) new;
 163           d = new;
 164         }
 165       else if (!next)
 166         return 0;
 167       else
 168         d = (struct dfa_state *) next;
 169       s++;
 170     }
 171   return d->final;
 172 }
 173
 174 int
 175 wp_min_size(byte *p)
 176 {
 177   int s = 0;
 178
 179   while (*p)
 180     if (*p++ != '*')
 181       s++;
 182   return s;
 183 }
 184
 185 #ifdef TEST
 186
 187 void
 188 wp_dump(struct wildpatt *w)
 189 {
 190   int i;
 191
 192   puts("NFA:");
 193   for(i=1; i<=w->nfa_states; i++)
 194     {
 195       struct nfa_state *n = w->nfa + i;
 196       printf("%2d: %d %02x %08x %08x\n", i, n->final, n->ch, n->match_states, n->default_states);
 197     }
 198   puts("DFA:");
 199   for(i=0; i<HASH_SIZE; i++)
 200     if (w->hash[i])
 201       printf("%3d: %08x\n", i, w->hash[i]->nfa_set);
 202   printf("%d DFA states cached.\n", w->dfa_cache_counter);
 203 }
 204
 205 int main(int argc, char **argv)
 206 {
 207   struct wildpatt *w;
 208   char buf[1024];
 209
 210   if (argc != 2) return 1;
 211   w = wp_compile(argv[1], mp_new(65536));
 212   if (!w)
 213     {
 214       puts("Compile error");
 215       return 1;
 216     }
 217   wp_dump(w);
 218   while (fgets(buf, sizeof(buf)-1, stdin))
 219     {
 220       char *c = strchr(buf, '\n');
 221       if (!c) break;
 222       *c = 0;
 223 #if 0
 224       printf("%d\n", wp_match(w, buf));
 225 #else
 226       if (wp_match(w, buf))
 227         puts(buf);
 228 #endif
 229     }
 230   wp_dump(w);
 231   return 0;
 232 }
 233
 234 #endif