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