sys/src/cmd/spin/pangen4.h

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