0b55f123 |
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 | }; |