4.3BSD - /usr/src/old/sdb/re.c

   1: static  char sccsid[] = "@(#)re.c 4.2 8/17/82";
   2: #include "head.h"
   3: #define CBRA    1
   4: #define CCHR    2
   5: #define CDOT    4
   6: #define CCL 6
   7: #define NCCL    8
   8: #define CDOL    10
   9: #define CEOF    11
  10: #define CKET    12
  11: #define CBACK   18
  12: 
  13: #define CSTAR   01
  14: 
  15: #define LBSIZE  512
  16: #define ESIZE   256
  17: #define NBRA    9
  18: 
  19: char    expbuf[ESIZE];
  20: int circf;
  21: char    *braslist[NBRA];
  22: char    *braelist[NBRA];
  23: char    bittab[] = {
  24:     1,
  25:     2,
  26:     4,
  27:     8,
  28:     16,
  29:     32,
  30:     64,
  31:     128
  32: };
  33: 
  34: dore() {
  35:     register int line;
  36:     register char *p;
  37: 
  38:     circf = 0;
  39:     line = fline;
  40:     compile(re);
  41:     do {
  42:         if (redir) fnext();
  43:         else fprev();
  44:         p = fbuf;
  45:         while(*p++ != '\n')
  46:             ;
  47:         *--p = '\0';
  48:         if (match(fbuf)) goto l1;
  49:     } while (fline != line);
  50:     error("No match");
  51: l1: *p = '\n';
  52:     fprint();
  53: }
  54: 
  55: 
  56: compile(astr)
  57: char *astr;
  58: {
  59:     register c;
  60:     register char *ep, *sp;
  61:     char *cstart;
  62:     char *lastep;
  63:     int cclcnt;
  64:     char bracket[NBRA], *bracketp;
  65:     int closed;
  66:     char numbra;
  67:     char neg;
  68: 
  69:     ep = expbuf;
  70:     sp = astr;
  71:     lastep = 0;
  72:     bracketp = bracket;
  73:     closed = numbra = 0;
  74:     if (*sp == '^') {
  75:         circf++;
  76:         sp++;
  77:     }
  78:     for (;;) {
  79:         if (ep >= &expbuf[ESIZE])
  80:             goto cerror;
  81:         if ((c = *sp++) != '*')
  82:             lastep = ep;
  83:         switch (c) {
  84: 
  85:         case '\0':
  86:             *ep++ = CEOF;
  87:             return;
  88: 
  89:         case '.':
  90:             *ep++ = CDOT;
  91:             continue;
  92: 
  93:         case '*':
  94:             if (lastep==0 || *lastep==CBRA || *lastep==CKET)
  95:                 goto defchar;
  96:             *lastep |= CSTAR;
  97:             continue;
  98: 
  99:         case '$':
 100:             if (*sp != '\0')
 101:                 goto defchar;
 102:             *ep++ = CDOL;
 103:             continue;
 104: 
 105:         case '[':
 106:             if(&ep[17] >= &expbuf[ESIZE])
 107:                 goto cerror;
 108:             *ep++ = CCL;
 109:             neg = 0;
 110:             if((c = *sp++) == '^') {
 111:                 neg = 1;
 112:                 c = *sp++;
 113:             }
 114:             cstart = sp;
 115:             do {
 116:                 if (c=='\0')
 117:                     goto cerror;
 118:                 if (c=='-' && sp>cstart && *sp!=']') {
 119:                     for (c = sp[-2]; c<*sp; c++)
 120:                         ep[c>>3] |= bittab[c&07];
 121:                     sp++;
 122:                 }
 123:                 ep[c>>3] |= bittab[c&07];
 124:             } while((c = *sp++) != ']');
 125:             if(neg) {
 126:                 for(cclcnt = 0; cclcnt < 16; cclcnt++)
 127:                     ep[cclcnt] ^= -1;
 128:                 ep[0] &= 0376;
 129:             }
 130: 
 131:             ep += 16;
 132: 
 133:             continue;
 134: 
 135:         case '\\':
 136:             if((c = *sp++) == '(') {
 137:                 if(numbra >= NBRA) {
 138:                     goto cerror;
 139:                 }
 140:                 *bracketp++ = numbra;
 141:                 *ep++ = CBRA;
 142:                 *ep++ = numbra++;
 143:                 continue;
 144:             }
 145:             if(c == ')') {
 146:                 if(bracketp <= bracket) {
 147:                     goto cerror;
 148:                 }
 149:                 *ep++ = CKET;
 150:                 *ep++ = *--bracketp;
 151:                 closed++;
 152:                 continue;
 153:             }
 154: 
 155:             if(c >= '1' && c <= '9') {
 156:                 if((c -= '1') >= closed)
 157:                     goto cerror;
 158:                 *ep++ = CBACK;
 159:                 *ep++ = c;
 160:                 continue;
 161:             }
 162: 
 163:         defchar:
 164:         default:
 165:             *ep++ = CCHR;
 166:             *ep++ = c;
 167:         }
 168:     }
 169:     cerror:
 170:     errexit("RE error\n", (char *)NULL);
 171: }
 172: 
 173: match(p1)
 174: register char *p1; {
 175:     register char *p2;
 176:     register c;
 177:         p2 = expbuf;
 178:         if (circf) {
 179:             if (advance(p1, p2))
 180:                 goto found;
 181:             goto nfound;
 182:         }
 183:         /* fast check for first character */
 184:         if (*p2==CCHR) {
 185:             c = p2[1];
 186:             do {
 187:                 if (*p1!=c)
 188:                     continue;
 189:                 if (advance(p1, p2))
 190:                     goto found;
 191:             } while (*p1++);
 192:             goto nfound;
 193:         }
 194:         /* regular algorithm */
 195:         do {
 196:             if (advance(p1, p2))
 197:                 goto found;
 198:         } while (*p1++);
 199:     nfound:
 200:         return(0);
 201:     found:
 202:         return(1);
 203: }
 204: 
 205: advance(lp, ep)
 206: register char *lp, *ep;
 207: {
 208:     register char *curlp;
 209:     char c;
 210:     char *bbeg;
 211:     int ct;
 212: 
 213:     for (;;) switch (*ep++) {
 214: 
 215:     case CCHR:
 216:         if (*ep++ == *lp++)
 217:             continue;
 218:         return(0);
 219: 
 220:     case CDOT:
 221:         if (*lp++)
 222:             continue;
 223:         return(0);
 224: 
 225:     case CDOL:
 226:         if (*lp=='\0')
 227:             continue;
 228:         return(0);
 229: 
 230:     case CEOF:
 231:         return(1);
 232: 
 233:     case CCL:
 234:         c = *lp++ & 0177;
 235:         if(ep[c>>3] & bittab[c & 07]) {
 236:             ep += 16;
 237:             continue;
 238:         }
 239:         return(0);
 240:     case CBRA:
 241:         braslist[*ep++] = lp;
 242:         continue;
 243: 
 244:     case CKET:
 245:         braelist[*ep++] = lp;
 246:         continue;
 247: 
 248:     case CBACK:
 249:         bbeg = braslist[*ep];
 250:         if (braelist[*ep]==0)
 251:             return(0);
 252:         ct = braelist[*ep++] - bbeg;
 253:         if(ecmp(bbeg, lp, ct)) {
 254:             lp += ct;
 255:             continue;
 256:         }
 257:         return(0);
 258: 
 259:     case CBACK|CSTAR:
 260:         bbeg = braslist[*ep];
 261:         if (braelist[*ep]==0)
 262:             return(0);
 263:         ct = braelist[*ep++] - bbeg;
 264:         curlp = lp;
 265:         while(ecmp(bbeg, lp, ct))
 266:             lp += ct;
 267:         while(lp >= curlp) {
 268:             if(advance(lp, ep)) return(1);
 269:             lp -= ct;
 270:         }
 271:         return(0);
 272: 
 273: 
 274:     case CDOT|CSTAR:
 275:         curlp = lp;
 276:         while (*lp++);
 277:         goto star;
 278: 
 279:     case CCHR|CSTAR:
 280:         curlp = lp;
 281:         while (*lp++ == *ep);
 282:         ep++;
 283:         goto star;
 284: 
 285:     case CCL|CSTAR:
 286:         curlp = lp;
 287:         do {
 288:             c = *lp++ & 0177;
 289:         } while(ep[c>>3] & bittab[c & 07]);
 290:         ep += 16;
 291:         goto star;
 292: 
 293:     star:
 294:         if(--lp == curlp) {
 295:             continue;
 296:         }
 297: 
 298:         if(*ep == CCHR) {
 299:             c = ep[1];
 300:             do {
 301:                 if(*lp != c)
 302:                     continue;
 303:                 if(advance(lp, ep))
 304:                     return(1);
 305:             } while(lp-- > curlp);
 306:             return(0);
 307:         }
 308: 
 309:         do {
 310:             if (advance(lp, ep))
 311:                 return(1);
 312:         } while (lp-- > curlp);
 313:         return(0);
 314: 
 315:     default:
 316:         errexit("RE botch\n", (char *)NULL);
 317:     }
 318: }
 319: ecmp(a, b, count)
 320: char    *a, *b;
 321: {
 322:     register cc = count;
 323:     while(cc--)
 324:         if(*a++ != *b++)    return(0);
 325:     return(1);
 326: }
 327: 
 328: 
 329: errexit(s)
 330: char *s; {
 331:     error(s);
 332:     return;
 333: }

Defined functions

Defined variables

Defined macros