home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / refer / glue5.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  6.4 KB  |  361 lines
  1. # include "stdio.h"
  2. # include "ctype.h"
  3. /*
  4.  * fgrep -- print all lines containing any of a set of keywords
  5.  *
  6.  *    status returns:
  7.  *        0 - ok, and some matches
  8.  *        1 - ok, but no matches
  9.  *        2 - some error
  10.  */
  11. #define    MAXSIZ 700
  12. #define QSIZE 400
  13. struct words {
  14.     char     inp;
  15.     char    out;
  16.     struct    words *nst;
  17.     struct    words *link;
  18.     struct    words *fail;
  19. } 
  20. *www, *smax, *q;
  21.  
  22. char    buf[1024];
  23. int    nsucc;
  24. int    need;
  25. char    *instr;
  26. int    inct;
  27. int    rflag;
  28. int    xargc;
  29. char    **xargv;
  30. int    numwords;
  31. int    nfound;
  32. static int flag 0;
  33.  
  34.  
  35. fgrep(argc, argv)
  36. char **argv;
  37. {
  38.     instr = nsucc = need = inct = rflag = numwords = nfound = 0;
  39.     flag = 0;
  40.     if (www==0)
  41.         www = zalloc(MAXSIZ, sizeof (*www));
  42.     if (www==NULL)
  43.         err("Can't get space for machines", 0);
  44.     for (q=www; q<www+MAXSIZ; q++)
  45.         q->inp = q->out = q->nst = q->link = q->fail =0;
  46.     xargc = argc-1;
  47.     xargv = argv+1;
  48.     while (xargc>0 && xargv[0][0]=='-')
  49.         {
  50.         switch(xargv[0][1])
  51.             {
  52.             case 'r': /* return value only */
  53.                 rflag++;
  54.                 break;
  55.             case 'n': /* number of answers needed */
  56.                 need = xargv[1];
  57.                 xargv++; xargc--;
  58.                 break;
  59.             case 'i':
  60.                 instr = xargv[1];
  61.                 inct = xargv[2]+2;
  62. # if D2
  63. fprintf(stderr,"inct %d xargv.2. %o %d\n",inct, xargv[2],xargv[2]);
  64. # endif
  65.                 xargv += 2; xargc -= 2;
  66.                 break;
  67.             }
  68.         xargv++; xargc--;
  69.         }
  70.     if (xargc<=0)
  71.         {
  72.         write (2, "bad fgrep call\n", 15);
  73.         exit(2);
  74.         }
  75. # if D1
  76.     fprintf(stderr, "before cgoto\n");
  77. # endif
  78.     cgotofn();
  79. # if D1
  80.     fprintf(stderr, "before cfail\n");
  81. # endif
  82.     cfail();
  83. # if D1
  84.     fprintf(stderr, "before execute instr %.20s\n", instr? instr: "");
  85.     fprintf(stderr, "end of string %d %c %c %c\n", inct, instr[inct-3],
  86.         instr[inct-2], instr[inct-1]);
  87. # endif
  88.     execute();
  89. # if D1
  90.     fprintf(stderr, "returning nsucc %d\n", nsucc);
  91.     fprintf(stderr, "fgrep done www %o\n",www);
  92. # endif
  93.     return(nsucc == 0);
  94. }
  95.  
  96. execute()
  97. {
  98.     register char *p;
  99.     register c;
  100.     register ch;
  101.     register ccount;
  102.     int f;
  103.     char *nlp;
  104.     f=0;
  105.     ccount = instr ? inct : 0;
  106.     nfound=0;
  107.     p = instr ? instr : buf;
  108.     if (need == 0) need = numwords;
  109.     nlp = p;
  110.     c = www;
  111. # if D2
  112. fprintf(stderr, "in execute ccount %d inct %d\n",ccount, inct );
  113. # endif
  114.     for (;;) {
  115. # if D3
  116. fprintf(stderr, "down ccount\n");
  117. # endif
  118.         if (--ccount <= 0) {
  119. # if D2
  120. fprintf(stderr, "ex loop ccount %d instr %o\n",ccount, instr);
  121. # endif
  122.             if (instr) break;
  123.             if (p == &buf[1024]) p = buf;
  124.             if (p > &buf[512]) {
  125.                 if ((ccount = read(f, p, &buf[1024] - p)) <= 0) break;
  126.             }
  127.             else if ((ccount = read(f, p, 512)) <= 0) break;
  128. # if D2
  129. fprintf(stderr, " normal read %d bytres\n", ccount);
  130. {char xx[20]; sprintf(xx, "they are %%.%ds\n", ccount);
  131. fprintf(stderr, xx, p);
  132. }
  133. # endif
  134.         }
  135. nstate:
  136.         ch = *p;
  137. # if D2
  138. fprintf(stderr, "roaming along in ex ch %c c %o\n",ch,c);
  139. # endif
  140.         if (isupper(ch)) ch |= 040;
  141.         if (c->inp == ch) {
  142.             c = c->nst;
  143.         }
  144.         else if (c->link != 0) {
  145.             c = c->link;
  146.             goto nstate;
  147.         }
  148.         else {
  149.             c = c->fail;
  150.             if (c==0) {
  151.                 c = www;
  152. istate:
  153.                 if (c->inp == ch) {
  154.                     c = c->nst;
  155.                 }
  156.                 else if (c->link != 0) {
  157.                     c = c->link;
  158.                     goto istate;
  159.                 }
  160.             }
  161.             else goto nstate;
  162.         }
  163.         if (c->out && new (c)) {
  164. # if D2
  165. fprintf(stderr, " found: nfound %d need %d\n",nfound,need);
  166. # endif
  167.             if (++nfound >= need)
  168.             {
  169. # if D1
  170. fprintf(stderr, "found, p %o nlp %o ccount %d buf %o buf[1024] %o\n",p,nlp,ccount,buf,buf+1024);
  171. # endif
  172.                 if (instr==0)
  173.                 while (*p++ != '\n') {
  174. # if D3
  175. fprintf(stderr, "down ccount2\n");
  176. # endif
  177.                     if (--ccount <= 0) {
  178.                         if (p == &buf[1024]) p = buf;
  179.                         if (p > &buf[512]) {
  180.                             if ((ccount = read(f, p, &buf[1024] - p)) <= 0) break;
  181.                         }
  182.                         else if ((ccount = read(f, p, 512)) <= 0) break;
  183. # if D2
  184. fprintf(stderr, " read %d bytes\n",ccount);
  185. { char xx[20]; sprintf(xx, "they are %%.%ds\n", ccount);
  186. fprintf(stderr, xx, p);
  187. }
  188. # endif
  189.                     }
  190.                 }
  191.                 nsucc = 1;
  192.                 if (rflag==0)
  193.                     {
  194. # if D2
  195. fprintf(stderr, "p %o nlp %o buf %o\n",p,nlp,buf);
  196. if (p>nlp)
  197. {write (2, "XX\n", 3); write (2, nlp, p-nlp); write (2, "XX\n", 3);}
  198. # endif
  199.                     if (p > nlp) write(1, nlp, p-nlp);
  200.                     else {
  201.                         write(1, nlp, &buf[1024] - nlp);
  202.                         write(1, buf, p-&buf[0]);
  203.                         }
  204.                     if (p[-1]!= '\n') write (1, "\n", 1);
  205.                     }
  206.                 if (instr==0)
  207.                     {
  208.                     nlp = p;
  209.                     c = www;
  210.                     nfound=0; 
  211.                     }
  212.             }
  213.             else
  214.                 ccount++;
  215.             continue;
  216.         }
  217. # if D2
  218. fprintf(stderr, "nr end loop p %o\n",p);
  219. # endif
  220.         if (instr)
  221.             p++;
  222.         else
  223.         if (*p++ == '\n')
  224.         {
  225.             nlp = p;
  226.             c = www;
  227.             nfound=0;
  228.         }
  229.     }
  230.     if (instr==0)
  231.         close(f);
  232. }
  233.  
  234. cgotofn() {
  235.     register c;
  236.     register s;
  237.     s = smax = www;
  238. nword:    
  239.     for(;;) {
  240. # if D1
  241.     fprintf(stderr, " in for loop c now %o %c\n",c, c>' ' ? c : ' ');
  242. # endif
  243.         if ((c = gch())==0) return;
  244.         else if (c == '\n') {
  245.             s->out = 1;
  246.             s = www;
  247.         }
  248.         else {
  249. loop:    
  250.             if (s->inp == c) {
  251.                 s = s->nst;
  252.                 continue;
  253.             }
  254.             if (s->inp == 0) goto enter;
  255.             if (s->link == 0) {
  256.                 if (smax >= &www[MAXSIZ - 1]) overflo();
  257.                 s->link = ++smax;
  258.                 s = smax;
  259.                 goto enter;
  260.             }
  261.             s = s->link;
  262.             goto loop;
  263.         }
  264.     }
  265.  
  266. enter:
  267.     do {
  268.         s->inp = c;
  269.         if (smax >= &www[MAXSIZ - 1]) overflo();
  270.         s->nst = ++smax;
  271.         s = smax;
  272.     } 
  273.     while ((c = gch()) != '\n');
  274.     smax->out = 1;
  275.     s = www;
  276.     numwords++;
  277.     goto nword;
  278.  
  279. }
  280.  
  281. gch()
  282. {
  283.     static char *s;
  284.     if (flag==0)
  285.     {
  286.         flag=1;
  287.         s = *xargv++;
  288. # if D1
  289.     fprintf(stderr, "next arg is %s xargc %d\n",s,xargc);
  290. # endif
  291.         if (xargc-- <=0) return(0);
  292.     }
  293.     if (*s) return(*s++);
  294.     for(flag=0; flag<1024; flag++)
  295.         buf[flag]=0;
  296.     flag=0;
  297.     return('\n');
  298. }
  299.  
  300. overflo() {
  301.     write(2,"wordlist too large\n", 19);
  302.     exit(2);
  303. }
  304. cfail() {
  305.     struct words *queue[QSIZE];
  306.     struct words **front, **rear;
  307.     struct words *state;
  308.     register char c;
  309.     register s;
  310.     s = www;
  311.     front = rear = queue;
  312. init:    
  313.     if ((s->inp) != 0) {
  314.         *rear++ = s->nst;
  315.         if (rear >= &queue[QSIZE - 1]) overflo();
  316.     }
  317.     if ((s = s->link) != 0) {
  318.         goto init;
  319.     }
  320.  
  321.     while (rear!=front) {
  322.         s = *front;
  323.         if (front == &queue[QSIZE-1])
  324.             front = queue;
  325.         else front++;
  326. cloop:    
  327.         if ((c = s->inp) != 0) {
  328.             *rear = (q = s->nst);
  329.             if (front < rear)
  330.                 if (rear >= &queue[QSIZE-1])
  331.                     if (front == queue) overflo();
  332.                     else rear = queue;
  333.             else rear++;
  334.             else
  335.                 if (++rear == front) overflo();
  336.             state = s->fail;
  337. floop:    
  338.             if (state == 0) state = www;
  339.             if (state->inp == c) {
  340.                 q->fail = state->nst;
  341.                 if ((state->nst)->out == 1) q->out = 1;
  342.                 continue;
  343.             }
  344.             else if ((state = state->link) != 0)
  345.                 goto floop;
  346.         }
  347.         if ((s = s->link) != 0)
  348.             goto cloop;
  349.     }
  350. }
  351. static int seen[50];
  352. new (x)
  353. {
  354.     int i;
  355.     for(i=0; i<nfound; i++)
  356.         if (seen[i]==x)
  357.             return(0);
  358.     seen[i]=x;
  359.     return(1);
  360. }
  361.