| 2 |
- |
1 |
/***** spin: pangen4.h *****/
|
|
|
2 |
|
|
|
3 |
/* Copyright (c) 1997-2003 by Lucent Technologies, Bell Laboratories. */
|
|
|
4 |
/* All Rights Reserved. This software is for educational purposes only. */
|
|
|
5 |
/* No guarantee whatsoever is expressed or implied by the distribution of */
|
|
|
6 |
/* this code. Permission is given to distribute this code provided that */
|
|
|
7 |
/* this introductory message is not removed and no monies are exchanged. */
|
|
|
8 |
/* Software written by Gerard J. Holzmann. For tool documentation see: */
|
|
|
9 |
/* http://spinroot.com/ */
|
|
|
10 |
/* Send all bug-reports and/or questions to: bugs@spinroot.com */
|
|
|
11 |
|
|
|
12 |
/* The DFA code below was written by Anuj Puri and Gerard J. Holzmann in */
|
|
|
13 |
/* May 1997, and was inspired by earlier work on data compression using */
|
|
|
14 |
/* sharing tree data structures and graph-encoded sets by J-Ch. Gregoire */
|
|
|
15 |
/* (INRS Telecom, Quebec, Canada) and D.Zampunieris (Univ.Namur, Belgium) */
|
|
|
16 |
|
|
|
17 |
/* The splay routine code included here is based on the public domain */
|
|
|
18 |
/* version written by D. Sleator <sleator@cs.cmu.edu> in 1992. */
|
|
|
19 |
|
|
|
20 |
static char *Dfa[] = {
|
|
|
21 |
"#ifdef MA",
|
|
|
22 |
"/*",
|
|
|
23 |
"#include <stdio.h>",
|
|
|
24 |
"#define uchar unsigned char",
|
|
|
25 |
"*/",
|
|
|
26 |
"#define ulong unsigned long",
|
|
|
27 |
"#define ushort unsigned short",
|
|
|
28 |
"",
|
|
|
29 |
"#define TWIDTH 256",
|
|
|
30 |
"#define HASH(y,n) (n)*(((long)y))",
|
|
|
31 |
"#define INRANGE(e,h) ((h>=e->From && h<=e->To)||(e->s==1 && e->S==h))",
|
|
|
32 |
"",
|
|
|
33 |
"extern char *emalloc(unsigned long); /* imported routine */",
|
|
|
34 |
"extern void dfa_init(ushort); /* 4 exported routines */",
|
|
|
35 |
"extern int dfa_member(ulong);",
|
|
|
36 |
"extern int dfa_store(uchar *);",
|
|
|
37 |
"extern void dfa_stats(void);",
|
|
|
38 |
"",
|
|
|
39 |
"typedef struct Edge {",
|
|
|
40 |
" uchar From, To; /* max range 0..255 */",
|
|
|
41 |
" uchar s, S; /* if s=1, S is singleton */",
|
|
|
42 |
" struct Vertex *Dst;",
|
|
|
43 |
" struct Edge *Nxt;",
|
|
|
44 |
"} Edge;",
|
|
|
45 |
"",
|
|
|
46 |
"typedef struct Vertex {",
|
|
|
47 |
" ulong key, num; /* key for splay tree, nr incoming edges */",
|
|
|
48 |
" uchar from[2], to[2]; /* in-node predefined edge info */",
|
|
|
49 |
" struct Vertex *dst[2];/* most nodes have 2 or more edges */",
|
|
|
50 |
" struct Edge *Succ; /* in case there are more edges */",
|
|
|
51 |
" struct Vertex *lnk, *left, *right; /* splay tree plumbing */",
|
|
|
52 |
"} Vertex;",
|
|
|
53 |
"",
|
|
|
54 |
"static Edge *free_edges;",
|
|
|
55 |
"static Vertex *free_vertices;",
|
|
|
56 |
"static Vertex **layers; /* one splay tree of nodes per layer */",
|
|
|
57 |
"static Vertex **path; /* run of word in the DFA */",
|
|
|
58 |
"static Vertex *R, *F, *NF; /* Root, Final, Not-Final */",
|
|
|
59 |
"static uchar *word, *lastword;/* string, and last string inserted */",
|
|
|
60 |
"static int dfa_depth, iv=0, nv=0, pfrst=0, Tally;",
|
|
|
61 |
"",
|
|
|
62 |
"static void insert_it(Vertex *, int); /* splay-tree code */",
|
|
|
63 |
"static void delete_it(Vertex *, int);",
|
|
|
64 |
"static Vertex *find_it(Vertex *, Vertex *, uchar, int);",
|
|
|
65 |
"",
|
|
|
66 |
"static void",
|
|
|
67 |
"recyc_edges(Edge *e)",
|
|
|
68 |
"{",
|
|
|
69 |
" if (!e) return;",
|
|
|
70 |
" recyc_edges(e->Nxt);",
|
|
|
71 |
" e->Nxt = free_edges;",
|
|
|
72 |
" free_edges = e;",
|
|
|
73 |
"}",
|
|
|
74 |
"",
|
|
|
75 |
"static Edge *",
|
|
|
76 |
"new_edge(Vertex *dst)",
|
|
|
77 |
"{ Edge *e;",
|
|
|
78 |
"",
|
|
|
79 |
" if (free_edges)",
|
|
|
80 |
" { e = free_edges;",
|
|
|
81 |
" free_edges = e->Nxt;",
|
|
|
82 |
" e->From = e->To = e->s = e->S = 0;",
|
|
|
83 |
" e->Nxt = (Edge *) 0;",
|
|
|
84 |
" } else",
|
|
|
85 |
" e = (Edge *) emalloc(sizeof(Edge));",
|
|
|
86 |
" e->Dst = dst;",
|
|
|
87 |
"",
|
|
|
88 |
" return e;",
|
|
|
89 |
"}",
|
|
|
90 |
"",
|
|
|
91 |
"static void",
|
|
|
92 |
"recyc_vertex(Vertex *v)",
|
|
|
93 |
"{",
|
|
|
94 |
" recyc_edges(v->Succ);",
|
|
|
95 |
" v->Succ = (Edge *) free_vertices;",
|
|
|
96 |
" free_vertices = v;",
|
|
|
97 |
" nr_states--;",
|
|
|
98 |
"}",
|
|
|
99 |
"",
|
|
|
100 |
"static Vertex *",
|
|
|
101 |
"new_vertex(void)",
|
|
|
102 |
"{ Vertex *v;",
|
|
|
103 |
"",
|
|
|
104 |
" if (free_vertices)",
|
|
|
105 |
" { v = free_vertices;",
|
|
|
106 |
" free_vertices = (Vertex *) v->Succ;",
|
|
|
107 |
" v->Succ = (Edge *) 0;",
|
|
|
108 |
" v->num = 0;",
|
|
|
109 |
" } else",
|
|
|
110 |
" v = (Vertex *) emalloc(sizeof(Vertex));",
|
|
|
111 |
"",
|
|
|
112 |
" nr_states++;",
|
|
|
113 |
" return v; ",
|
|
|
114 |
"}",
|
|
|
115 |
"",
|
|
|
116 |
"static Vertex *",
|
|
|
117 |
"allDelta(Vertex *v, int n)",
|
|
|
118 |
"{ Vertex *dst = new_vertex();",
|
|
|
119 |
"",
|
|
|
120 |
" v->from[0] = 0;",
|
|
|
121 |
" v->to[0] = 255;",
|
|
|
122 |
" v->dst[0] = dst;",
|
|
|
123 |
" dst->num = 256;",
|
|
|
124 |
" insert_it(v, n);",
|
|
|
125 |
" return dst;",
|
|
|
126 |
"}",
|
|
|
127 |
"",
|
|
|
128 |
"static void",
|
|
|
129 |
"insert_edge(Vertex *v, Edge *e)",
|
|
|
130 |
"{ /* put new edge first */",
|
|
|
131 |
" if (!v->dst[0])",
|
|
|
132 |
" { v->dst[0] = e->Dst;",
|
|
|
133 |
" v->from[0] = e->From;",
|
|
|
134 |
" v->to[0] = e->To;",
|
|
|
135 |
" recyc_edges(e);",
|
|
|
136 |
" return;",
|
|
|
137 |
" }",
|
|
|
138 |
" if (!v->dst[1])",
|
|
|
139 |
" { v->from[1] = v->from[0]; v->from[0] = e->From;",
|
|
|
140 |
" v->to[1] = v->to[0]; v->to[0] = e->To;",
|
|
|
141 |
" v->dst[1] = v->dst[0]; v->dst[0] = e->Dst;",
|
|
|
142 |
" recyc_edges(e);",
|
|
|
143 |
" return;",
|
|
|
144 |
" } /* shift */",
|
|
|
145 |
" { int f = v->from[1];",
|
|
|
146 |
" int t = v->to[1];",
|
|
|
147 |
" Vertex *d = v->dst[1];",
|
|
|
148 |
" v->from[1] = v->from[0]; v->from[0] = e->From;",
|
|
|
149 |
" v->to[1] = v->to[0]; v->to[0] = e->To;",
|
|
|
150 |
" v->dst[1] = v->dst[0]; v->dst[0] = e->Dst;",
|
|
|
151 |
" e->From = f;",
|
|
|
152 |
" e->To = t;",
|
|
|
153 |
" e->Dst = d;",
|
|
|
154 |
" }",
|
|
|
155 |
" e->Nxt = v->Succ;",
|
|
|
156 |
" v->Succ = e;",
|
|
|
157 |
"}",
|
|
|
158 |
"",
|
|
|
159 |
"static void",
|
|
|
160 |
"copyRecursive(Vertex *v, Edge *e)",
|
|
|
161 |
"{ Edge *f;",
|
|
|
162 |
" if (e->Nxt) copyRecursive(v, e->Nxt);",
|
|
|
163 |
" f = new_edge(e->Dst);",
|
|
|
164 |
" f->From = e->From;",
|
|
|
165 |
" f->To = e->To;",
|
|
|
166 |
" f->s = e->s;",
|
|
|
167 |
" f->S = e->S;",
|
|
|
168 |
" f->Nxt = v->Succ;",
|
|
|
169 |
" v->Succ = f;",
|
|
|
170 |
"}",
|
|
|
171 |
"",
|
|
|
172 |
"static void",
|
|
|
173 |
"copyEdges(Vertex *to, Vertex *from)",
|
|
|
174 |
"{ int i;",
|
|
|
175 |
" for (i = 0; i < 2; i++)",
|
|
|
176 |
" { to->from[i] = from->from[i];",
|
|
|
177 |
" to->to[i] = from->to[i];",
|
|
|
178 |
" to->dst[i] = from->dst[i];",
|
|
|
179 |
" }",
|
|
|
180 |
" if (from->Succ) copyRecursive(to, from->Succ);",
|
|
|
181 |
"}",
|
|
|
182 |
"",
|
|
|
183 |
"static Edge *",
|
|
|
184 |
"cacheDelta(Vertex *v, int h, int first)",
|
|
|
185 |
"{ static Edge *ov, tmp; int i;",
|
|
|
186 |
"",
|
|
|
187 |
" if (!first && INRANGE(ov,h))",
|
|
|
188 |
" return ov; /* intercepts about 10%% */",
|
|
|
189 |
" for (i = 0; i < 2; i++)",
|
|
|
190 |
" if (v->dst[i] && h >= v->from[i] && h <= v->to[i])",
|
|
|
191 |
" { tmp.From = v->from[i];",
|
|
|
192 |
" tmp.To = v->to[i];",
|
|
|
193 |
" tmp.Dst = v->dst[i];",
|
|
|
194 |
" tmp.s = tmp.S = 0;",
|
|
|
195 |
" ov = &tmp;",
|
|
|
196 |
" return ov;",
|
|
|
197 |
" }",
|
|
|
198 |
" for (ov = v->Succ; ov; ov = ov->Nxt)",
|
|
|
199 |
" if (INRANGE(ov,h)) return ov;",
|
|
|
200 |
"",
|
|
|
201 |
" Uerror(\"cannot get here, cacheDelta\");",
|
|
|
202 |
" return (Edge *) 0;",
|
|
|
203 |
"}",
|
|
|
204 |
"",
|
|
|
205 |
"static Vertex *",
|
|
|
206 |
"Delta(Vertex *v, int h) /* v->delta[h] */",
|
|
|
207 |
"{ Edge *e;",
|
|
|
208 |
"",
|
|
|
209 |
" if (v->dst[0] && h >= v->from[0] && h <= v->to[0])",
|
|
|
210 |
" return v->dst[0]; /* oldest edge */",
|
|
|
211 |
" if (v->dst[1] && h >= v->from[1] && h <= v->to[1])",
|
|
|
212 |
" return v->dst[1];",
|
|
|
213 |
" for (e = v->Succ; e; e = e->Nxt)",
|
|
|
214 |
" if (INRANGE(e,h))",
|
|
|
215 |
" return e->Dst;",
|
|
|
216 |
" Uerror(\"cannot happen Delta\");",
|
|
|
217 |
" return (Vertex *) 0;",
|
|
|
218 |
"}",
|
|
|
219 |
"",
|
|
|
220 |
"static void",
|
|
|
221 |
"numDelta(Vertex *v, int d)",
|
|
|
222 |
"{ Edge *e;",
|
|
|
223 |
" ulong cnt;",
|
|
|
224 |
" int i;",
|
|
|
225 |
"",
|
|
|
226 |
" for (i = 0; i < 2; i++)",
|
|
|
227 |
" if (v->dst[i])",
|
|
|
228 |
" { cnt = v->dst[i]->num + d*(1 + v->to[i] - v->from[i]);",
|
|
|
229 |
" if (d == 1 && cnt < v->dst[i]->num) goto bad;",
|
|
|
230 |
" v->dst[i]->num = cnt;",
|
|
|
231 |
" }",
|
|
|
232 |
" for (e = v->Succ; e; e = e->Nxt)",
|
|
|
233 |
" { cnt = e->Dst->num + d*(1 + e->To - e->From + e->s);",
|
|
|
234 |
" if (d == 1 && cnt < e->Dst->num)",
|
|
|
235 |
"bad: Uerror(\"too many incoming edges\");",
|
|
|
236 |
" e->Dst->num = cnt;",
|
|
|
237 |
" }",
|
|
|
238 |
"}",
|
|
|
239 |
"",
|
|
|
240 |
"static void",
|
|
|
241 |
"setDelta(Vertex *v, int h, Vertex *newdst) /* v->delta[h] = newdst; */",
|
|
|
242 |
"{ Edge *e, *f = (Edge *) 0, *g;",
|
|
|
243 |
" int i;",
|
|
|
244 |
"",
|
|
|
245 |
" /* remove the old entry, if there */",
|
|
|
246 |
" for (i = 0; i < 2; i++)",
|
|
|
247 |
" if (v->dst[i] && h >= v->from[i] && h <= v->to[i])",
|
|
|
248 |
" { if (h == v->from[i])",
|
|
|
249 |
" { if (h == v->to[i])",
|
|
|
250 |
" { v->dst[i] = (Vertex *) 0;",
|
|
|
251 |
" v->from[i] = v->to[i] = 0;",
|
|
|
252 |
" } else",
|
|
|
253 |
" v->from[i]++;",
|
|
|
254 |
" } else if (h == v->to[i])",
|
|
|
255 |
" { v->to[i]--;",
|
|
|
256 |
" } else",
|
|
|
257 |
" { g = new_edge(v->dst[i]);/* same dst */",
|
|
|
258 |
" g->From = v->from[i];",
|
|
|
259 |
" g->To = h-1; /* left half */",
|
|
|
260 |
" v->from[i] = h+1; /* right half */",
|
|
|
261 |
" insert_edge(v, g);",
|
|
|
262 |
" }",
|
|
|
263 |
" goto part2;",
|
|
|
264 |
" }",
|
|
|
265 |
" for (e = v->Succ; e; f = e, e = e->Nxt)",
|
|
|
266 |
" { if (e->s == 1 && e->S == h)",
|
|
|
267 |
" { e->s = e->S = 0;",
|
|
|
268 |
" goto rem_tst;",
|
|
|
269 |
" }",
|
|
|
270 |
" if (h >= e->From && h <= e->To)",
|
|
|
271 |
" { if (h == e->From)",
|
|
|
272 |
" { if (h == e->To)",
|
|
|
273 |
" { if (e->s)",
|
|
|
274 |
" { e->From = e->To = e->S;",
|
|
|
275 |
" e->s = 0;",
|
|
|
276 |
" break;",
|
|
|
277 |
" } else",
|
|
|
278 |
" goto rem_do;",
|
|
|
279 |
" } else",
|
|
|
280 |
" e->From++;",
|
|
|
281 |
" } else if (h == e->To)",
|
|
|
282 |
" { e->To--;",
|
|
|
283 |
" } else /* split */",
|
|
|
284 |
" { g = new_edge(e->Dst); /* same dst */",
|
|
|
285 |
" g->From = e->From;",
|
|
|
286 |
" g->To = h-1; /* g=left half */",
|
|
|
287 |
" e->From = h+1; /* e=right half */",
|
|
|
288 |
" g->Nxt = e->Nxt; /* insert g */",
|
|
|
289 |
" e->Nxt = g; /* behind e */",
|
|
|
290 |
" break; /* done */",
|
|
|
291 |
" }",
|
|
|
292 |
"",
|
|
|
293 |
"rem_tst: if (e->From > e->To)",
|
|
|
294 |
" { if (e->s == 0) {",
|
|
|
295 |
"rem_do: if (f)",
|
|
|
296 |
" f->Nxt = e->Nxt;",
|
|
|
297 |
" else",
|
|
|
298 |
" v->Succ = e->Nxt;",
|
|
|
299 |
" e->Nxt = (Edge *) 0;",
|
|
|
300 |
" recyc_edges(e);",
|
|
|
301 |
" } else",
|
|
|
302 |
" { e->From = e->To = e->S;",
|
|
|
303 |
" e->s = 0;",
|
|
|
304 |
" } }",
|
|
|
305 |
" break;",
|
|
|
306 |
" } }",
|
|
|
307 |
"part2:",
|
|
|
308 |
" /* check if newdst is already there */",
|
|
|
309 |
" for (i = 0; i < 2; i++)",
|
|
|
310 |
" if (v->dst[i] == newdst)",
|
|
|
311 |
" { if (h+1 == (int) v->from[i])",
|
|
|
312 |
" { v->from[i] = h;",
|
|
|
313 |
" return;",
|
|
|
314 |
" }",
|
|
|
315 |
" if (h == (int) v->to[i]+1)",
|
|
|
316 |
" { v->to[i] = h;",
|
|
|
317 |
" return;",
|
|
|
318 |
" } }",
|
|
|
319 |
" for (e = v->Succ; e; e = e->Nxt)",
|
|
|
320 |
" { if (e->Dst == newdst)",
|
|
|
321 |
" { if (h+1 == (int) e->From)",
|
|
|
322 |
" { e->From = h;",
|
|
|
323 |
" if (e->s == 1 && e->S+1 == e->From)",
|
|
|
324 |
" { e->From = e->S;",
|
|
|
325 |
" e->s = e->S = 0;",
|
|
|
326 |
" }",
|
|
|
327 |
" return;",
|
|
|
328 |
" }",
|
|
|
329 |
" if (h == (int) e->To+1)",
|
|
|
330 |
" { e->To = h;",
|
|
|
331 |
" if (e->s == 1 && e->S == e->To+1)",
|
|
|
332 |
" { e->To = e->S;",
|
|
|
333 |
" e->s = e->S = 0;",
|
|
|
334 |
" }",
|
|
|
335 |
" return;",
|
|
|
336 |
" }",
|
|
|
337 |
" if (e->s == 0)",
|
|
|
338 |
" { e->s = 1;",
|
|
|
339 |
" e->S = h;",
|
|
|
340 |
" return;",
|
|
|
341 |
" } } }",
|
|
|
342 |
" /* add as a new edge */",
|
|
|
343 |
" e = new_edge(newdst);",
|
|
|
344 |
" e->From = e->To = h;",
|
|
|
345 |
" insert_edge(v, e);",
|
|
|
346 |
"}",
|
|
|
347 |
"",
|
|
|
348 |
"static ulong",
|
|
|
349 |
"cheap_key(Vertex *v)",
|
|
|
350 |
"{ ulong vk2 = 0;",
|
|
|
351 |
"",
|
|
|
352 |
" if (v->dst[0])",
|
|
|
353 |
" { vk2 = (ulong) v->dst[0];",
|
|
|
354 |
" if ((ulong) v->dst[1] > vk2)",
|
|
|
355 |
" vk2 = (ulong) v->dst[1];",
|
|
|
356 |
" } else if (v->dst[1])",
|
|
|
357 |
" vk2 = (ulong) v->dst[1]; ",
|
|
|
358 |
" if (v->Succ)",
|
|
|
359 |
" { Edge *e;",
|
|
|
360 |
" for (e = v->Succ; e; e = e->Nxt)",
|
|
|
361 |
" if ((ulong) e->Dst > vk2)",
|
|
|
362 |
" vk2 = (ulong) e->Dst;",
|
|
|
363 |
" }",
|
|
|
364 |
" Tally = (vk2>>2)&(TWIDTH-1);",
|
|
|
365 |
" return v->key;",
|
|
|
366 |
"}",
|
|
|
367 |
"",
|
|
|
368 |
"static ulong",
|
|
|
369 |
"mk_key(Vertex *v) /* not sensitive to order */",
|
|
|
370 |
"{ ulong m = 0, vk2 = 0;",
|
|
|
371 |
" Edge *e;",
|
|
|
372 |
"",
|
|
|
373 |
" if (v->dst[0])",
|
|
|
374 |
" { m += HASH(v->dst[0], v->to[0] - v->from[0] + 1);",
|
|
|
375 |
" vk2 = (ulong) v->dst[0]; ",
|
|
|
376 |
" }",
|
|
|
377 |
" if (v->dst[1])",
|
|
|
378 |
" { m += HASH(v->dst[1], v->to[1] - v->from[1] + 1);",
|
|
|
379 |
" if ((ulong) v->dst[1] > vk2) vk2 = (ulong) v->dst[1]; ",
|
|
|
380 |
" }",
|
|
|
381 |
" for (e = v->Succ; e; e = e->Nxt)",
|
|
|
382 |
" { m += HASH(e->Dst, e->To - e->From + 1 + e->s);",
|
|
|
383 |
" if ((ulong) e->Dst > vk2) vk2 = (ulong) e->Dst; ",
|
|
|
384 |
" }",
|
|
|
385 |
" Tally = (vk2>>2)&(TWIDTH-1);",
|
|
|
386 |
" return m;",
|
|
|
387 |
"}",
|
|
|
388 |
"",
|
|
|
389 |
"static ulong",
|
|
|
390 |
"mk_special(int sigma, Vertex *n, Vertex *v)",
|
|
|
391 |
"{ ulong m = 0, vk2 = 0;",
|
|
|
392 |
" Edge *f;",
|
|
|
393 |
" int i;",
|
|
|
394 |
"",
|
|
|
395 |
" for (i = 0; i < 2; i++)",
|
|
|
396 |
" if (v->dst[i])",
|
|
|
397 |
" { if (sigma >= v->from[i] && sigma <= v->to[i])",
|
|
|
398 |
" { m += HASH(v->dst[i], v->to[i]-v->from[i]);",
|
|
|
399 |
" if ((ulong) v->dst[i] > vk2",
|
|
|
400 |
" && v->to[i] > v->from[i])",
|
|
|
401 |
" vk2 = (ulong) v->dst[i]; ",
|
|
|
402 |
" } else",
|
|
|
403 |
" { m += HASH(v->dst[i], v->to[i]-v->from[i]+1);",
|
|
|
404 |
" if ((ulong) v->dst[i] > vk2)",
|
|
|
405 |
" vk2 = (ulong) v->dst[i]; ",
|
|
|
406 |
" } }",
|
|
|
407 |
" for (f = v->Succ; f; f = f->Nxt)",
|
|
|
408 |
" { if (sigma >= f->From && sigma <= f->To)",
|
|
|
409 |
" { m += HASH(f->Dst, f->To - f->From + f->s);",
|
|
|
410 |
" if ((ulong) f->Dst > vk2",
|
|
|
411 |
" && f->To - f->From + f->s > 0)",
|
|
|
412 |
" vk2 = (ulong) f->Dst; ",
|
|
|
413 |
" } else if (f->s == 1 && sigma == f->S)",
|
|
|
414 |
" { m += HASH(f->Dst, f->To - f->From + 1);",
|
|
|
415 |
" if ((ulong) f->Dst > vk2) vk2 = (ulong) f->Dst; ",
|
|
|
416 |
" } else",
|
|
|
417 |
" { m += HASH(f->Dst, f->To - f->From + 1 + f->s);",
|
|
|
418 |
" if ((ulong) f->Dst > vk2) vk2 = (ulong) f->Dst; ",
|
|
|
419 |
" } }",
|
|
|
420 |
"",
|
|
|
421 |
" if ((ulong) n > vk2) vk2 = (ulong) n; ",
|
|
|
422 |
" Tally = (vk2>>2)&(TWIDTH-1);",
|
|
|
423 |
" m += HASH(n, 1);",
|
|
|
424 |
" return m;",
|
|
|
425 |
"}",
|
|
|
426 |
"",
|
|
|
427 |
"void ",
|
|
|
428 |
"dfa_init(ushort nr_layers)",
|
|
|
429 |
"{ int i; Vertex *r, *t;",
|
|
|
430 |
"",
|
|
|
431 |
" dfa_depth = nr_layers; /* one byte per layer */",
|
|
|
432 |
" path = (Vertex **) emalloc((dfa_depth+1)*sizeof(Vertex *));",
|
|
|
433 |
" layers = (Vertex **) emalloc(TWIDTH*(dfa_depth+1)*sizeof(Vertex *));",
|
|
|
434 |
" lastword = (uchar *) emalloc((dfa_depth+1)*sizeof(uchar));",
|
|
|
435 |
" lastword[dfa_depth] = lastword[0] = 255;",
|
|
|
436 |
" path[0] = R = new_vertex(); F = new_vertex();",
|
|
|
437 |
"",
|
|
|
438 |
" for (i = 1, r = R; i < dfa_depth; i++, r = t)",
|
|
|
439 |
" t = allDelta(r, i-1);",
|
|
|
440 |
" NF = allDelta(r, i-1);",
|
|
|
441 |
"}",
|
|
|
442 |
"",
|
|
|
443 |
"#if 0",
|
|
|
444 |
"static void complement_dfa(void) { Vertex *tmp = F; F = NF; NF = tmp; }",
|
|
|
445 |
"#endif",
|
|
|
446 |
"",
|
|
|
447 |
"double",
|
|
|
448 |
"tree_stats(Vertex *t)",
|
|
|
449 |
"{ Edge *e; double cnt=0.0;",
|
|
|
450 |
" if (!t) return 0;",
|
|
|
451 |
" if (!t->key) return 0;",
|
|
|
452 |
" t->key = 0; /* precaution */",
|
|
|
453 |
" if (t->dst[0]) cnt++;",
|
|
|
454 |
" if (t->dst[1]) cnt++;",
|
|
|
455 |
" for (e = t->Succ; e; e = e->Nxt)",
|
|
|
456 |
" cnt++;",
|
|
|
457 |
" cnt += tree_stats(t->lnk);",
|
|
|
458 |
" cnt += tree_stats(t->left);",
|
|
|
459 |
" cnt += tree_stats(t->right);",
|
|
|
460 |
" return cnt;",
|
|
|
461 |
"}",
|
|
|
462 |
"",
|
|
|
463 |
"void",
|
|
|
464 |
"dfa_stats(void)",
|
|
|
465 |
"{ int i, j; double cnt = 0.0;",
|
|
|
466 |
" for (j = 0; j < TWIDTH; j++)",
|
|
|
467 |
" for (i = 0; i < dfa_depth+1; i++)",
|
|
|
468 |
" cnt += tree_stats(layers[i*TWIDTH+j]);",
|
|
|
469 |
" printf(\"Minimized Automaton:\t%%6d nodes and %%6g edges\\n\",",
|
|
|
470 |
" nr_states, cnt);",
|
|
|
471 |
"}",
|
|
|
472 |
"",
|
|
|
473 |
"int",
|
|
|
474 |
"dfa_member(ulong n)",
|
|
|
475 |
"{ Vertex **p, **q;",
|
|
|
476 |
" uchar *w = &word[n];",
|
|
|
477 |
" int i;",
|
|
|
478 |
"",
|
|
|
479 |
" p = &path[n]; q = (p+1);",
|
|
|
480 |
" for (i = n; i < dfa_depth; i++)",
|
|
|
481 |
" *q++ = Delta(*p++, *w++);",
|
|
|
482 |
" return (*p == F);",
|
|
|
483 |
"}",
|
|
|
484 |
"",
|
|
|
485 |
"int",
|
|
|
486 |
"dfa_store(uchar *sv)",
|
|
|
487 |
"{ Vertex **p, **q, *s, *y, *old, *new = F;",
|
|
|
488 |
" uchar *w, *u = lastword;",
|
|
|
489 |
" int i, j, k;",
|
|
|
490 |
"",
|
|
|
491 |
" w = word = sv;",
|
|
|
492 |
" while (*w++ == *u++) /* find first byte that differs */",
|
|
|
493 |
" ;",
|
|
|
494 |
" pfrst = (int) (u - lastword) - 1;",
|
|
|
495 |
" memcpy(&lastword[pfrst], &sv[pfrst], dfa_depth-pfrst);",
|
|
|
496 |
" if (pfrst > iv) pfrst = iv;",
|
|
|
497 |
" if (pfrst > nv) pfrst = nv;",
|
|
|
498 |
"/* phase1: */",
|
|
|
499 |
" p = &path[pfrst]; q = (p+1); w = &word[pfrst];",
|
|
|
500 |
" for (i = pfrst; i < dfa_depth; i++)",
|
|
|
501 |
" *q++ = Delta(*p++, *w++); /* (*p)->delta[*w++]; */",
|
|
|
502 |
"",
|
|
|
503 |
" if (*p == F) return 1; /* it's already there */",
|
|
|
504 |
"/* phase2: */",
|
|
|
505 |
" iv = dfa_depth;",
|
|
|
506 |
" do { iv--;",
|
|
|
507 |
" old = new;",
|
|
|
508 |
" new = find_it(path[iv], old, word[iv], iv);",
|
|
|
509 |
" } while (new && iv > 0);",
|
|
|
510 |
"",
|
|
|
511 |
"/* phase3: */",
|
|
|
512 |
" nv = k = 0; s = path[0];",
|
|
|
513 |
" for (j = 1; j <= iv; ++j) ",
|
|
|
514 |
" if (path[j]->num > 1)",
|
|
|
515 |
" { y = new_vertex();",
|
|
|
516 |
" copyEdges(y, path[j]);",
|
|
|
517 |
" insert_it(y, j);",
|
|
|
518 |
" numDelta(y, 1);",
|
|
|
519 |
" delete_it(s, j-1);",
|
|
|
520 |
" setDelta(s, word[j-1], y);",
|
|
|
521 |
" insert_it(s, j-1);",
|
|
|
522 |
" y->num = 1; /* initial value 1 */",
|
|
|
523 |
" s = y;",
|
|
|
524 |
" path[j]->num--; /* only 1 moved from j to y */",
|
|
|
525 |
" k = 1;",
|
|
|
526 |
" } else",
|
|
|
527 |
" { s = path[j];",
|
|
|
528 |
" if (!k) nv = j;",
|
|
|
529 |
" }",
|
|
|
530 |
" y = Delta(s, word[iv]);",
|
|
|
531 |
" y->num--;",
|
|
|
532 |
" delete_it(s, iv); ",
|
|
|
533 |
" setDelta(s, word[iv], old);",
|
|
|
534 |
" insert_it(s, iv); ",
|
|
|
535 |
" old->num++;",
|
|
|
536 |
"",
|
|
|
537 |
" for (j = iv+1; j < dfa_depth; j++)",
|
|
|
538 |
" if (path[j]->num == 0)",
|
|
|
539 |
" { numDelta(path[j], -1);",
|
|
|
540 |
" delete_it(path[j], j);",
|
|
|
541 |
" recyc_vertex(path[j]);",
|
|
|
542 |
" } else",
|
|
|
543 |
" break;",
|
|
|
544 |
" return 0;",
|
|
|
545 |
"}",
|
|
|
546 |
"",
|
|
|
547 |
"static Vertex *",
|
|
|
548 |
"splay(ulong i, Vertex *t)",
|
|
|
549 |
"{ Vertex N, *l, *r, *y;",
|
|
|
550 |
"",
|
|
|
551 |
" if (!t) return t;",
|
|
|
552 |
" N.left = N.right = (Vertex *) 0;",
|
|
|
553 |
" l = r = &N;",
|
|
|
554 |
" for (;;)",
|
|
|
555 |
" { if (i < t->key)",
|
|
|
556 |
" { if (!t->left) break;",
|
|
|
557 |
" if (i < t->left->key)",
|
|
|
558 |
" { y = t->left;",
|
|
|
559 |
" t->left = y->right;",
|
|
|
560 |
" y->right = t;",
|
|
|
561 |
" t = y;",
|
|
|
562 |
" if (!t->left) break;",
|
|
|
563 |
" }",
|
|
|
564 |
" r->left = t;",
|
|
|
565 |
" r = t;",
|
|
|
566 |
" t = t->left;",
|
|
|
567 |
" } else if (i > t->key)",
|
|
|
568 |
" { if (!t->right) break;",
|
|
|
569 |
" if (i > t->right->key)",
|
|
|
570 |
" { y = t->right;",
|
|
|
571 |
" t->right = y->left;",
|
|
|
572 |
" y->left = t;",
|
|
|
573 |
" t = y;",
|
|
|
574 |
" if (!t->right) break;",
|
|
|
575 |
" }",
|
|
|
576 |
" l->right = t;",
|
|
|
577 |
" l = t;",
|
|
|
578 |
" t = t->right;",
|
|
|
579 |
" } else",
|
|
|
580 |
" break;",
|
|
|
581 |
" }",
|
|
|
582 |
" l->right = t->left;",
|
|
|
583 |
" r->left = t->right;",
|
|
|
584 |
" t->left = N.right;",
|
|
|
585 |
" t->right = N.left;",
|
|
|
586 |
" return t;",
|
|
|
587 |
"}",
|
|
|
588 |
"",
|
|
|
589 |
"static void",
|
|
|
590 |
"insert_it(Vertex *v, int L)",
|
|
|
591 |
"{ Vertex *new, *t;",
|
|
|
592 |
" ulong i; int nr;",
|
|
|
593 |
"",
|
|
|
594 |
" i = mk_key(v);",
|
|
|
595 |
" nr = ((L*TWIDTH)+Tally);",
|
|
|
596 |
" t = layers[nr];",
|
|
|
597 |
"",
|
|
|
598 |
" v->key = i; ",
|
|
|
599 |
" if (!t)",
|
|
|
600 |
" { layers[nr] = v;",
|
|
|
601 |
" return;",
|
|
|
602 |
" }",
|
|
|
603 |
" t = splay(i, t);",
|
|
|
604 |
" if (i < t->key)",
|
|
|
605 |
" { new = v;",
|
|
|
606 |
" new->left = t->left;",
|
|
|
607 |
" new->right = t;",
|
|
|
608 |
" t->left = (Vertex *) 0;",
|
|
|
609 |
" } else if (i > t->key)",
|
|
|
610 |
" { new = v;",
|
|
|
611 |
" new->right = t->right;",
|
|
|
612 |
" new->left = t;",
|
|
|
613 |
" t->right = (Vertex *) 0;",
|
|
|
614 |
" } else /* it's already there */",
|
|
|
615 |
" { v->lnk = t->lnk; /* put in linked list off v */",
|
|
|
616 |
" t->lnk = v;",
|
|
|
617 |
" new = t;",
|
|
|
618 |
" }",
|
|
|
619 |
" layers[nr] = new;",
|
|
|
620 |
"}",
|
|
|
621 |
"",
|
|
|
622 |
"static int",
|
|
|
623 |
"checkit(Vertex *h, Vertex *v, Vertex *n, uchar sigma)",
|
|
|
624 |
"{ Edge *g, *f;",
|
|
|
625 |
" int i, k, j = 1;",
|
|
|
626 |
"",
|
|
|
627 |
" for (k = 0; k < 2; k++)",
|
|
|
628 |
" if (h->dst[k])",
|
|
|
629 |
" { if (sigma >= h->from[k] && sigma <= h->to[k])",
|
|
|
630 |
" { if (h->dst[k] != n) goto no_match;",
|
|
|
631 |
" }",
|
|
|
632 |
" for (i = h->from[k]; i <= h->to[k]; i++)",
|
|
|
633 |
" { if (i == sigma) continue;",
|
|
|
634 |
" g = cacheDelta(v, i, j); j = 0;",
|
|
|
635 |
" if (h->dst[k] != g->Dst)",
|
|
|
636 |
" goto no_match;",
|
|
|
637 |
" if (g->s == 0 || g->S != i)",
|
|
|
638 |
" i = g->To;",
|
|
|
639 |
" } }",
|
|
|
640 |
" for (f = h->Succ; f; f = f->Nxt)",
|
|
|
641 |
" { if (INRANGE(f,sigma))",
|
|
|
642 |
" { if (f->Dst != n) goto no_match;",
|
|
|
643 |
" }",
|
|
|
644 |
" for (i = f->From; i <= f->To; i++)",
|
|
|
645 |
" { if (i == sigma) continue;",
|
|
|
646 |
" g = cacheDelta(v, i, j); j = 0;",
|
|
|
647 |
" if (f->Dst != g->Dst)",
|
|
|
648 |
" goto no_match;",
|
|
|
649 |
" if (g->s == 1 && i == g->S)",
|
|
|
650 |
" continue;",
|
|
|
651 |
" i = g->To;",
|
|
|
652 |
" }",
|
|
|
653 |
" if (f->s && f->S != sigma)",
|
|
|
654 |
" { g = cacheDelta(v, f->S, 1);",
|
|
|
655 |
" if (f->Dst != g->Dst)",
|
|
|
656 |
" goto no_match;",
|
|
|
657 |
" }",
|
|
|
658 |
" }",
|
|
|
659 |
" if (h->Succ || h->dst[0] || h->dst[1]) return 1;",
|
|
|
660 |
"no_match:",
|
|
|
661 |
" return 0;",
|
|
|
662 |
"}",
|
|
|
663 |
"",
|
|
|
664 |
"static Vertex *",
|
|
|
665 |
"find_it(Vertex *v, Vertex *n, uchar sigma, int L)",
|
|
|
666 |
"{ Vertex *z, *t;",
|
|
|
667 |
" ulong i; int nr;",
|
|
|
668 |
"",
|
|
|
669 |
" i = mk_special(sigma,n,v);",
|
|
|
670 |
" nr = ((L*TWIDTH)+Tally);",
|
|
|
671 |
" t = layers[nr];",
|
|
|
672 |
"",
|
|
|
673 |
" if (!t) return (Vertex *) 0;",
|
|
|
674 |
" layers[nr] = t = splay(i, t);",
|
|
|
675 |
" if (i == t->key)",
|
|
|
676 |
" for (z = t; z; z = z->lnk)",
|
|
|
677 |
" if (checkit(z, v, n, sigma))",
|
|
|
678 |
" return z;",
|
|
|
679 |
"",
|
|
|
680 |
" return (Vertex *) 0;",
|
|
|
681 |
"}",
|
|
|
682 |
"",
|
|
|
683 |
"static void",
|
|
|
684 |
"delete_it(Vertex *v, int L)",
|
|
|
685 |
"{ Vertex *x, *t;",
|
|
|
686 |
" ulong i; int nr;",
|
|
|
687 |
"",
|
|
|
688 |
" i = cheap_key(v);",
|
|
|
689 |
" nr = ((L*TWIDTH)+Tally);",
|
|
|
690 |
" t = layers[nr];",
|
|
|
691 |
" if (!t) return;",
|
|
|
692 |
"",
|
|
|
693 |
" t = splay(i, t);",
|
|
|
694 |
" if (i == t->key)",
|
|
|
695 |
" { Vertex *z, *y = (Vertex *) 0;",
|
|
|
696 |
" for (z = t; z && z != v; y = z, z = z->lnk)",
|
|
|
697 |
" ;",
|
|
|
698 |
" if (z != v) goto bad;",
|
|
|
699 |
" if (y)",
|
|
|
700 |
" { y->lnk = z->lnk;",
|
|
|
701 |
" z->lnk = (Vertex *) 0;",
|
|
|
702 |
" layers[nr] = t;",
|
|
|
703 |
" return;",
|
|
|
704 |
" } else if (z->lnk) /* z == t == v */",
|
|
|
705 |
" { y = z->lnk;",
|
|
|
706 |
" y->left = t->left;",
|
|
|
707 |
" y->right = t->right;",
|
|
|
708 |
" t->left = t->right = t->lnk = (Vertex *) 0;",
|
|
|
709 |
" layers[nr] = y;",
|
|
|
710 |
" return;",
|
|
|
711 |
" }",
|
|
|
712 |
" /* delete the node itself */",
|
|
|
713 |
" if (!t->left)",
|
|
|
714 |
" { x = t->right;",
|
|
|
715 |
" } else",
|
|
|
716 |
" { x = splay(i, t->left);",
|
|
|
717 |
" x->right = t->right;",
|
|
|
718 |
" }",
|
|
|
719 |
" t->left = t->right = t->lnk = (Vertex *) 0;",
|
|
|
720 |
" layers[nr] = x;",
|
|
|
721 |
" return;",
|
|
|
722 |
" }",
|
|
|
723 |
"bad: Uerror(\"cannot happen delete\");",
|
|
|
724 |
"}",
|
|
|
725 |
"#endif", /* MA */
|
|
|
726 |
0,
|
|
|
727 |
};
|