2 * Fast Pattern Matcher for Short Wildcard Patterns (only `?' and `*' supported)
4 * Traditional NFA -> DFA method with on-the-fly DFA construction.
6 * (c) 1999 Martin Mares <mj@ucw.cz>
10 #include "lib/pools.h"
11 #include "lib/wildmatch.h"
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) */
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 */
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'.
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 */
39 struct nfa_state nfa[MAX_STATES];
40 struct dfa_state *hash[HASH_SIZE];
41 struct dfa_state *dfa_start;
43 uns dfa_cache_counter;
45 struct dfa_state *free_states;
48 static inline unsigned
53 return set % HASH_SIZE;
56 static struct dfa_state *
57 wp_new_state(struct wildpatt *w, u32 set)
59 unsigned h = wp_hash(set);
64 while (d = w->hash[h])
66 if (d->nfa_set == set)
68 h = (h + HASH_SKIP) % HASH_SIZE;
70 if (d = w->free_states)
71 w->free_states = d->next;
73 d = mp_alloc(w->pool, sizeof(*d));
78 for(bit=1; bit <= w->nfa_states; bit++)
81 struct nfa_state *n = &w->nfa[bit];
83 d->edge[n->ch] |= n->match_states | 1;
85 def_set |= n->default_states;
92 d->edge[i] |= def_set;
94 w->dfa_cache_counter++;
99 wp_compile(byte *p, struct mempool *pool)
104 if (strlen(p) >= MAX_STATES) /* Too long */
106 w = mp_alloc_zero(pool, sizeof(*w));
110 struct nfa_state *n = w->nfa + i;
112 n->default_states |= 1 << (++i);/* Default edge to a new state */
114 n->default_states |= 1 << i; /* Default edge to the same state */
117 n->ch = *p; /* Edge to new state labelled with 'c' */
118 n->match_states = 1 << (++i);
123 w->dfa_start = wp_new_state(w, 1 << 1);
128 wp_prune_cache(struct wildpatt *w)
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
136 for(i=0; i<HASH_SIZE; i++)
137 if (w->hash[i] && w->hash[i]->nfa_set != (1 << 1))
139 struct dfa_state *d = w->hash[i];
141 d->next = w->free_states;
144 w->dfa_cache_counter = 1; /* Only the initial state remains */
148 wp_match(struct wildpatt *w, byte *s)
152 if (w->dfa_cache_counter >= MAX_CACHED)
157 addr_int_t next = d->edge[*s];
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;
168 d = (struct dfa_state *) next;
188 wp_dump(struct wildpatt *w)
193 for(i=1; i<=w->nfa_states; i++)
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);
199 for(i=0; i<HASH_SIZE; i++)
201 printf("%3d: %08x\n", i, w->hash[i]->nfa_set);
202 printf("%d DFA states cached.\n", w->dfa_cache_counter);
205 int main(int argc, char **argv)
210 if (argc != 2) return 1;
211 w = wp_compile(argv[1], mp_new(65536));
214 puts("Compile error");
218 while (fgets(buf, sizeof(buf)-1, stdin))
220 char *c = strchr(buf, '\n');
224 printf("%d\n", wp_match(w, buf));
226 if (wp_match(w, buf))