]> mj.ucw.cz Git - libucw.git/blob - lib/wildmatch.c
Add directory to all includes.
[libucw.git] / 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 <stdio.h>
10 #include <string.h>
11
12 #include "lib/lib.h"
13 #include "lib/pools.h"
14 #include "lib/wildmatch.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 = pool_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 = pool_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], new_pool(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