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