home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V6 / usr / source / sno / sno3.c < prev    next >
Encoding:
C/C++ Source or Header  |  1975-05-13  |  3.6 KB  |  273 lines
  1. #include "sno.h"
  2.  
  3. /*
  4.  * sno3
  5.  */
  6.  
  7.  
  8. bextend(str, last)
  9. struct node *str, *last;
  10. {
  11.     register struct node *a, *s;
  12.     register int b;
  13.     int c, d;
  14.  
  15.     s = str;
  16.     if ((c = s->p1) == 0)
  17.         goto bad;
  18.     b = d = 0;
  19.     a = s->p2;
  20.     if(a == 0) {
  21.         a = c;
  22.         goto eb2;
  23.     }
  24. eb1:
  25.     if (a == last)
  26.         goto bad;
  27.     a = a->p1;
  28. eb2:
  29.     d++;
  30.     c = class(a->ch);
  31.     if (c == 1) { /* rp */
  32.         if (b == 0)
  33.             goto bad;
  34.         b--;
  35.         goto eb3;
  36.     }
  37.     if (c == 2) { /* lp */
  38.         b++;
  39.         goto eb1;
  40.     }
  41. eb3:
  42.     if (b == 0) {
  43.         s->p2= a;
  44.         return(d);
  45.     }
  46.     goto eb1;
  47. bad:
  48.     return(0);
  49. }
  50.  
  51. ubextend(str, last)
  52. struct node *str, *last;
  53. {
  54.     register struct node *a, *b, *s;
  55.  
  56.     s = str;
  57.     a = s->p1;
  58.     if(a == 0)
  59.         goto bad;
  60.     b = s->p2;
  61.     if(b == 0)
  62.         goto good;
  63.     if (b == last)
  64.         goto bad;
  65.     a = b->p1;
  66. good:
  67.     s->p2 = a;
  68.     return(1);
  69. bad:
  70.     return(0);
  71. }
  72.  
  73. search(arg, r)
  74. struct node *arg, *r;
  75. {
  76.     struct node *list, *back, *str,
  77.         *etc, *next, *last, *base, *e;
  78.     register struct node *a, *b, *var;
  79.     int c, d;
  80.  
  81.     a = arg->p2;
  82.     list = base = alloc();
  83.     last = next = 0;
  84.     goto badv1;
  85. badvanc:
  86.     a = a->p1;
  87.     if (a->typ == 0) {
  88.         list->p1 = 0;
  89.         if (rfail == 1) {
  90.             a = 0;
  91.             goto fail;
  92.         }
  93.         list = base;
  94.         if (r == 0)
  95.             next = last = 0; else {
  96.             next = r->p1;
  97.             last = r->p2;
  98.         }
  99.         goto adv1;
  100.     }
  101.     b = alloc();
  102.     list->p1 = b;
  103.     list = b;
  104. badv1:
  105.     list->p2 = back = alloc();
  106.     back->p1 = last;
  107.     b = a->p2;
  108.     c = a->typ;
  109.     list->typ = c;
  110.     if (c < 2) {
  111.         back->p2 = eval(b, 1);
  112.         goto badvanc;
  113.     }
  114.     last = list;
  115.     str = alloc();
  116.     etc = alloc();
  117.     back->p2 = var = alloc();
  118.     var->typ = b->typ;
  119.     var->p1 = str;
  120.     var->p2 = etc;
  121.     e = b->p1;
  122.     if (e == 0)
  123.         etc->p1 = 0; else
  124.         etc->p1 = eval(e, 0);
  125.     e = b->p2;
  126.     if (e == 0)
  127.         etc->p2 = 0; else {
  128.         e = eval(e, 1);
  129.         etc->p2 = strbin(e);
  130.         delete(e);
  131.     }
  132.     goto badvanc;
  133.  
  134. retard:
  135.     a = back->p1;
  136.     if (a == 0) {
  137.         rfail = 1;
  138.         goto fail;
  139.     }
  140.     list = a;
  141.     back = list->p2;
  142.     var = back->p2;
  143.     str = var->p1;
  144.     etc = var->p2;
  145.     if (etc->p2)
  146.         goto retard;
  147.     if (var->typ == 1) {
  148.         if (bextend(str, last) == 0)
  149.             goto retard;
  150.         goto adv0;
  151.     }
  152.     if (ubextend(str, last) == 0)
  153.         goto retard;
  154. adv0:
  155.     a = str->p2;
  156. adv01:
  157.     if (a == last)
  158.         next = 0; else
  159.         next = a->p1;
  160. advanc:
  161.     a = list->p1;
  162.     if (a == 0) {
  163.         a = alloc();
  164.         if (r == 0) {
  165.             a->p1 = a->p2 = 0;
  166.             goto fail;
  167.         }
  168.         b = r->p1;
  169.         a->p1 = b;
  170.         if (next == 0) {
  171.             a->p2 = r->p2;
  172.             goto fail;
  173.         }
  174.         while(1) {
  175.             e = b->p1;
  176.             if (e == next) {
  177.                 a->p2 = b;
  178.                 goto fail;
  179.             }
  180.             b = e;
  181.         }
  182.     }
  183.     list = a;
  184. adv1:
  185.     back = list->p2;
  186.     var = back->p2;
  187.     d = list->typ;
  188.     if(d < 2) {
  189.         if (var == 0)
  190.             goto advanc;
  191.         if (next == 0)
  192.             goto retard;
  193.         a = next;
  194.         b = var->p1;
  195.         e = var->p2;
  196.         while(1) {
  197.             if (a->ch != b->ch)
  198.                 goto retard;
  199.             if (b == e)
  200.                 goto adv01;
  201.             if (a == last)
  202.                 goto retard;
  203.             a = a->p1;
  204.             b = b->p1;
  205.         }
  206.     }
  207.     str = var->p1;
  208.     etc = var->p2;
  209.     str->p1 = next;
  210.     str->p2 = 0;
  211.     c = etc->p2;
  212.     if (var->typ == 1) {
  213.         d = bextend(str, last);
  214.         if (d == 0)
  215.             goto retard;
  216.         if (c == 0)
  217.             goto adv0;
  218.         while(1) {
  219.             c =- d;
  220.             if (c == 0)
  221.                 goto adv0;
  222.             if (c < 0)
  223.                 goto retard;
  224.             d = bextend(str, last);
  225.             if (d == 0)
  226.                 goto retard;
  227.         }
  228.     }
  229.     if (c == 0) {
  230.         if(d==3 & next!=0) {
  231.             str->p2 = last;
  232.             goto adv0;
  233.         }
  234.         goto advanc;
  235.     }
  236.     while(c--)
  237.         if (ubextend(str, last) == 0)
  238.             goto retard;
  239.     goto adv0;
  240.  
  241. fail:
  242.     list = base;
  243.     goto f1;
  244. fadv:
  245.     free(back);
  246.     b = list->p1;
  247.     free(list);
  248.     if (b == 0)
  249.         return(a);
  250.     list = b;
  251. f1:
  252.     back = list->p2;
  253.     var = back->p2;
  254.     if (list->typ < 2) {
  255.         delete(var);
  256.         goto fadv;
  257.     }
  258.     str = var->p1;
  259.     etc = var->p2;
  260.     if (a != 0 & etc->p1 != 0) {
  261.         if (str->p2 == 0) {
  262.             free(str);
  263.             str = 0;
  264.         }
  265.         assign(etc->p1, copy(str));
  266.     }
  267.     if (str)
  268.         free(str);
  269.     free(etc);
  270.     free(var);
  271.     goto fadv;
  272. }
  273.