diplodocus.org Git - nmh/blob - docs/historical/mh-jun-1982/progs/grep.c

   1 #ifdef COMMENT
   2         Proprietary Rand Corporation, 1981.
   3         Further distribution of this software
   4         subject to the terms of the Rand
   5         license agreement.
   6 #endif
   7
   8 #include <stdio.h>
   9 #define CCHR    2
  10 #define CDOT    4
  11 #define CCL     6
  12 #define NCCL    8
  13 #define CDOL    10
  14 #define CEOF    11
  15
  16 #define STAR    01
  17
  18 #define LBSIZE  1024
  19 #define ESIZE   256
  20
  21 char    ibuf[BUFSIZ];
  22 char    expbuf[ESIZE];
  23 char    linebuf[LBSIZE+1];
  24 int     circf;
  25
  26 char cc[] = {
  27         0000,0001,0002,0003,0004,0005,0006,0007,
  28         0010,0011,0012,0013,0014,0015,0016,0017,
  29         0020,0021,0022,0023,0024,0025,0026,0027,
  30         0030,0031,0032,0033,0034,0035,0036,0037,
  31         0040,0041,0042,0043,0044,0045,0046,0047,
  32         0050,0051,0052,0053,0054,0055,0056,0057,
  33         0060,0061,0062,0063,0064,0065,0066,0067,
  34         0070,0071,0072,0073,0074,0075,0076,0077,
  35         0100,0141,0142,0143,0144,0145,0146,0147,
  36         0150,0151,0152,0153,0154,0155,0156,0157,
  37         0160,0161,0162,0163,0164,0165,0166,0167,
  38         0170,0171,0172,0133,0134,0135,0136,0137,
  39         0140,0141,0142,0143,0144,0145,0146,0147,
  40         0150,0151,0152,0153,0154,0155,0156,0157,
  41         0160,0161,0162,0163,0164,0165,0166,0167,
  42         0170,0171,0172,0173,0174,0175,0176,0177,
  43 };
  44
  45
  46 compile(astr)
  47 char *astr;
  48 {
  49         register c;
  50         register char *ep, *sp;
  51         char *lastep;
  52         int cclcnt;
  53
  54         ep = expbuf;
  55         sp = astr;
  56         if (*sp == '^') {
  57                 circf++;
  58                 sp++;
  59         }
  60         for (;;) {
  61                 if (ep >= &expbuf[ESIZE])
  62                         goto cerror;
  63                 if ((c = *sp++) != '*')
  64                         lastep = ep;
  65                 switch (c) {
  66
  67                 case '\0':
  68                         *ep++ = CEOF;
  69                         return(1);
  70
  71                 case '.':
  72                         *ep++ = CDOT;
  73                         continue;
  74
  75                 case '*':
  76                         if (lastep==0)
  77                                 goto defchar;
  78                         *lastep |= STAR;
  79                         continue;
  80
  81                 case '$':
  82                         if (*sp != '\0')
  83                                 goto defchar;
  84                         *ep++ = CDOL;
  85                         continue;
  86
  87                 case '[':
  88                         *ep++ = CCL;
  89                         *ep++ = 0;
  90                         cclcnt = 1;
  91                         if ((c = *sp++) == '^') {
  92                                 c = *sp++;
  93                                 ep[-2] = NCCL;
  94                         }
  95                         do {
  96                                 *ep++ = c;
  97                                 cclcnt++;
  98                                 if (c=='\0' || ep >= &expbuf[ESIZE])
  99                                         goto cerror;
 100                         } while ((c = *sp++) != ']');
 101                         lastep[1] = cclcnt;
 102                         continue;
 103
 104                 case '\\':
 105                         if ((c = *sp++) == '\0')
 106                                 goto cerror;
 107                 defchar:
 108                 default:
 109                         *ep++ = CCHR;
 110                         *ep++ = c;
 111                 }
 112         }
 113     cerror:
 114         return(0);
 115 }
 116
 117
 118 execute(file)
 119 char *file;
 120 {
 121         register char *p1, *p2;
 122         register c;
 123         int f, body, lf;
 124         char *ebp, *cbp;
 125
 126         if ((f = open(file, 0)) < 0) {
 127                 fprintf(stderr, "Grep: Can't open %s\n", file);
 128                 return(0);
 129         }
 130         body = 0;
 131         ebp = ibuf;
 132         cbp = ibuf;
 133         for (;;) {
 134                 p1 = linebuf;
 135                 p2 = cbp;
 136                 lf = 0;
 137                 for (;;) {
 138                         if (p2 >= ebp) {
 139                                 if ((c = read(f, ibuf, sizeof ibuf)) <= 0) {
 140                                         close(f);
 141                                         if(lf) break; /* bodyless comp! */
 142                                         return(0);
 143                                 }
 144                                 p2 = ibuf;
 145                                 ebp = ibuf+c;
 146                         }
 147                         c = *p2++;
 148                         if(lf) if(c != ' ' && c != '\t') {
 149                                 --p2;
 150                                 break;
 151                         } else
 152                                 lf = 0;
 153                         if (c == '\n')
 154                                 if(body)
 155                                         break;
 156                                 else {
 157                                         if(lf) {
 158                                                 body++;
 159                                                 break;
 160                                         }
 161                                         lf++;
 162                                         c = ' ';
 163                                 }
 164                         if(c && p1 < &linebuf[LBSIZE-1])
 165                                 *p1++ = c;
 166                 }
 167                 *p1++ = 0;
 168                 cbp = p2;
 169                 p1 = linebuf;
 170                 p2 = expbuf;
 171                 if (circf) {
 172                         if (advance(p1, p2))
 173                                 goto found;
 174                         continue;
 175                 }
 176                 /* fast check for first character */
 177                 if (*p2==CCHR) {
 178                         c = p2[1];
 179                         do {
 180                                 if(*p1==c || cc[*p1]==c)
 181                                         if (advance(p1, p2))
 182                                                 goto found;
 183                         } while (*p1++);
 184                         continue;
 185                 }
 186                 /* regular algorithm */
 187                 do {
 188                         if (advance(p1, p2))
 189                                 goto found;
 190                 } while (*p1++);
 191                 continue;
 192         found:
 193                 close(f);
 194                 return(1);
 195         }
 196 }
 197
 198
 199 advance(alp, aep)
 200 char *alp, *aep;
 201 {
 202         register char *lp, *ep, *curlp;
 203
 204         lp = alp;
 205         ep = aep;
 206         for (;;) switch (*ep++) {
 207
 208         case CCHR:
 209                 if (*ep++ == *lp++ || ep[-1] == cc[lp[-1]])
 210                         continue;
 211                 return(0);
 212
 213         case CDOT:
 214                 if (*lp++)
 215                         continue;
 216                 return(0);
 217
 218         case CDOL:
 219                 if (*lp==0)
 220                         continue;
 221                 return(0);
 222
 223         case CEOF:
 224                 return(1);
 225
 226         case CCL:
 227                 if (cclass(ep, *lp++, 1)) {
 228                         ep += *ep;
 229                         continue;
 230                 }
 231                 return(0);
 232
 233         case NCCL:
 234                 if (cclass(ep, *lp++, 0)) {
 235                         ep += *ep;
 236                         continue;
 237                 }
 238                 return(0);
 239
 240         case CDOT|STAR:
 241                 curlp = lp;
 242                 while (*lp++);
 243                 goto star;
 244
 245         case CCHR|STAR:
 246                 curlp = lp;
 247                 while (*lp++ == *ep || cc[lp[-1]] == *ep) ;
 248                 ep++;
 249                 goto star;
 250
 251         case CCL|STAR:
 252         case NCCL|STAR:
 253                 curlp = lp;
 254                 while (cclass(ep, *lp++, ep[-1]==(CCL|STAR)));
 255                 ep += *ep;
 256                 goto star;
 257
 258         star:
 259                 do {
 260                         lp--;
 261                         if (advance(lp, ep))
 262                                 return(1);
 263                 } while (lp > curlp);
 264                 return(0);
 265
 266         default:
 267                 printf("RE botch\n");
 268                 return(0);
 269         }
 270 }
 271
 272
 273 cclass(aset, ac, af)
 274 char *aset;
 275 {
 276         register char *set, c;
 277         register n;
 278
 279         set = aset;
 280         if ((c = ac) == 0)
 281                 return(0);
 282         n = *set++;
 283         while (--n)
 284                 if (*set++ == c)
 285                         return(af);
 286         return(!af);
 287 }