1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 23 /* 24 * Copyright 2005 Sun Microsystems, Inc. All rights reserved. 25 * Use is subject to license terms. 26 */ 27 28 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */ 29 /* All Rights Reserved */ 30 31 #pragma ident "%Z%%M% %I% %E% SMI" 32 33 #define DEBUG 34 35 #include "awk.h" 36 #include "y.tab.h" 37 38 #define HAT (NCHARS-1) /* matches ^ in regular expr */ 39 /* NCHARS is 2**n */ 40 #define MAXLIN (3 * LINE_MAX) 41 42 #define type(v) (v)->nobj 43 #define left(v) (v)->narg[0] 44 #define right(v) (v)->narg[1] 45 #define parent(v) (v)->nnext 46 47 #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL: 48 #define UNARY case STAR: case PLUS: case QUEST: 49 50 /* 51 * encoding in tree Nodes: 52 * leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL): 53 * left is index, right contains value or pointer to value 54 * unary (STAR, PLUS, QUEST): left is child, right is null 55 * binary (CAT, OR): left and right are children 56 * parent contains pointer to parent 57 */ 58 59 int setvec[MAXLIN]; 60 int tmpset[MAXLIN]; 61 Node *point[MAXLIN]; 62 63 int rtok; /* next token in current re */ 64 int rlxval; 65 uchar *rlxstr; 66 uchar *prestr; /* current position in current re */ 67 uchar *lastre; /* origin of last re */ 68 69 static int setcnt; 70 static int poscnt; 71 72 uchar *patbeg; 73 int patlen; 74 75 #define NFA 20 /* cache this many dynamic fa's */ 76 fa *fatab[NFA]; 77 int nfatab = 0; /* entries in fatab */ 78 79 static fa *mkdfa(uchar *, int); 80 static int makeinit(fa *, int); 81 static void penter(Node *); 82 static void freetr(Node *); 83 static void overflo(char *); 84 static void cfoll(fa *, Node *); 85 static void follow(Node *); 86 static Node *reparse(uchar *); 87 static int relex(void); 88 static void freefa(fa *); 89 static int cgoto(fa *, int, int); 90 91 fa * 92 makedfa(uchar *s, int anchor) /* returns dfa for reg expr s */ 93 { 94 int i, use, nuse; 95 fa *pfa; 96 97 if (compile_time) /* a constant for sure */ 98 return (mkdfa(s, anchor)); 99 for (i = 0; i < nfatab; i++) { /* is it there already? */ 100 if (fatab[i]->anchor == anchor && 101 strcmp((char *)fatab[i]->restr, (char *)s) == 0) { 102 fatab[i]->use++; 103 return (fatab[i]); 104 } 105 } 106 pfa = mkdfa(s, anchor); 107 if (nfatab < NFA) { /* room for another */ 108 fatab[nfatab] = pfa; 109 fatab[nfatab]->use = 1; 110 nfatab++; 111 return (pfa); 112 } 113 use = fatab[0]->use; /* replace least-recently used */ 114 nuse = 0; 115 for (i = 1; i < nfatab; i++) 116 if (fatab[i]->use < use) { 117 use = fatab[i]->use; 118 nuse = i; 119 } 120 freefa(fatab[nuse]); 121 fatab[nuse] = pfa; 122 pfa->use = 1; 123 return (pfa); 124 } 125 126 fa * 127 mkdfa(uchar *s, int anchor) /* does the real work of making a dfa */ 128 /* anchor = 1 for anchored matches, else 0 */ 129 { 130 Node *p, *p1; 131 fa *f; 132 133 p = reparse(s); 134 p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p); 135 /* put ALL STAR in front of reg. exp. */ 136 p1 = op2(CAT, p1, op2(FINAL, NIL, NIL)); 137 /* put FINAL after reg. exp. */ 138 139 poscnt = 0; 140 penter(p1); /* enter parent pointers and leaf indices */ 141 if ((f = (fa *)calloc(1, sizeof (fa) + poscnt * sizeof (rrow))) == NULL) 142 overflo("no room for fa"); 143 /* penter has computed number of positions in re */ 144 f->accept = poscnt-1; 145 cfoll(f, p1); /* set up follow sets */ 146 freetr(p1); 147 if ((f->posns[0] = 148 (int *)calloc(1, *(f->re[0].lfollow) * sizeof (int))) == NULL) { 149 overflo("out of space in makedfa"); 150 } 151 if ((f->posns[1] = (int *)calloc(1, sizeof (int))) == NULL) 152 overflo("out of space in makedfa"); 153 *f->posns[1] = 0; 154 f->initstat = makeinit(f, anchor); 155 f->anchor = anchor; 156 f->restr = tostring(s); 157 return (f); 158 } 159 160 static int 161 makeinit(fa *f, int anchor) 162 { 163 register int i, k; 164 165 f->curstat = 2; 166 f->out[2] = 0; 167 f->reset = 0; 168 k = *(f->re[0].lfollow); 169 xfree(f->posns[2]); 170 if ((f->posns[2] = (int *)calloc(1, (k+1) * sizeof (int))) == NULL) 171 overflo("out of space in makeinit"); 172 for (i = 0; i <= k; i++) { 173 (f->posns[2])[i] = (f->re[0].lfollow)[i]; 174 } 175 if ((f->posns[2])[1] == f->accept) 176 f->out[2] = 1; 177 for (i = 0; i < NCHARS; i++) 178 f->gototab[2][i] = 0; 179 f->curstat = cgoto(f, 2, HAT); 180 if (anchor) { 181 *f->posns[2] = k-1; /* leave out position 0 */ 182 for (i = 0; i < k; i++) { 183 (f->posns[0])[i] = (f->posns[2])[i]; 184 } 185 186 f->out[0] = f->out[2]; 187 if (f->curstat != 2) 188 --(*f->posns[f->curstat]); 189 } 190 return (f->curstat); 191 } 192 193 void 194 penter(Node *p) /* set up parent pointers and leaf indices */ 195 { 196 switch (type(p)) { 197 LEAF 198 left(p) = (Node *) poscnt; 199 point[poscnt++] = p; 200 break; 201 UNARY 202 penter(left(p)); 203 parent(left(p)) = p; 204 break; 205 case CAT: 206 case OR: 207 penter(left(p)); 208 penter(right(p)); 209 parent(left(p)) = p; 210 parent(right(p)) = p; 211 break; 212 default: 213 ERROR "unknown type %d in penter", type(p) FATAL; 214 break; 215 } 216 } 217 218 static void 219 freetr(Node *p) /* free parse tree */ 220 { 221 switch (type(p)) { 222 LEAF 223 xfree(p); 224 break; 225 UNARY 226 freetr(left(p)); 227 xfree(p); 228 break; 229 case CAT: 230 case OR: 231 freetr(left(p)); 232 freetr(right(p)); 233 xfree(p); 234 break; 235 default: 236 ERROR "unknown type %d in freetr", type(p) FATAL; 237 break; 238 } 239 } 240 241 uchar * 242 cclenter(uchar *p) 243 { 244 register int i, c; 245 uchar *op, *chars, *ret; 246 size_t bsize; 247 248 init_buf(&chars, &bsize, LINE_INCR); 249 op = p; 250 i = 0; 251 while ((c = *p++) != 0) { 252 if (c == '\\') { 253 if ((c = *p++) == 't') 254 c = '\t'; 255 else if (c == 'n') 256 c = '\n'; 257 else if (c == 'f') 258 c = '\f'; 259 else if (c == 'r') 260 c = '\r'; 261 else if (c == 'b') 262 c = '\b'; 263 else if (c == '\\') 264 c = '\\'; 265 else if (isdigit(c)) { 266 int n = c - '0'; 267 if (isdigit(*p)) { 268 n = 8 * n + *p++ - '0'; 269 if (isdigit(*p)) 270 n = 8 * n + *p++ - '0'; 271 } 272 c = n; 273 } /* else */ 274 /* c = c; */ 275 } else if (c == '-' && i > 0 && chars[i-1] != 0) { 276 if (*p != 0) { 277 c = chars[i-1]; 278 while ((uchar)c < *p) { /* fails if *p is \\ */ 279 expand_buf(&chars, &bsize, i); 280 chars[i++] = ++c; 281 } 282 p++; 283 continue; 284 } 285 } 286 expand_buf(&chars, &bsize, i); 287 chars[i++] = c; 288 } 289 chars[i++] = '\0'; 290 dprintf(("cclenter: in = |%s|, out = |%s|\n", op, chars)); 291 xfree(op); 292 ret = tostring(chars); 293 free(chars); 294 return (ret); 295 } 296 297 static void 298 overflo(char *s) 299 { 300 ERROR "regular expression too big: %s", gettext((char *)s) FATAL; 301 } 302 303 /* enter follow set of each leaf of vertex v into lfollow[leaf] */ 304 static void 305 cfoll(fa *f, Node *v) 306 { 307 register int i; 308 register int *p; 309 310 switch (type(v)) { 311 LEAF 312 f->re[(int)left(v)].ltype = type(v); 313 f->re[(int)left(v)].lval = (int)right(v); 314 for (i = 0; i <= f->accept; i++) 315 setvec[i] = 0; 316 setcnt = 0; 317 follow(v); /* computes setvec and setcnt */ 318 if ((p = (int *)calloc(1, (setcnt+1) * sizeof (int))) == NULL) 319 overflo("follow set overflow"); 320 f->re[(int)left(v)].lfollow = p; 321 *p = setcnt; 322 for (i = f->accept; i >= 0; i--) { 323 if (setvec[i] == 1) 324 *++p = i; 325 } 326 break; 327 UNARY 328 cfoll(f, left(v)); 329 break; 330 case CAT: 331 case OR: 332 cfoll(f, left(v)); 333 cfoll(f, right(v)); 334 break; 335 default: 336 ERROR "unknown type %d in cfoll", type(v) FATAL; 337 } 338 } 339 340 /* 341 * collects initially active leaves of p into setvec 342 * returns 0 or 1 depending on whether p matches empty string 343 */ 344 static int 345 first(Node *p) 346 { 347 register int b; 348 349 switch (type(p)) { 350 LEAF 351 if (setvec[(int)left(p)] != 1) { 352 setvec[(int)left(p)] = 1; 353 setcnt++; 354 } 355 if (type(p) == CCL && (*(uchar *)right(p)) == '\0') 356 return (0); /* empty CCL */ 357 else 358 return (1); 359 case PLUS: 360 if (first(left(p)) == 0) 361 return (0); 362 return (1); 363 case STAR: 364 case QUEST: 365 (void) first(left(p)); 366 return (0); 367 case CAT: 368 if (first(left(p)) == 0 && first(right(p)) == 0) 369 return (0); 370 return (1); 371 case OR: 372 b = first(right(p)); 373 if (first(left(p)) == 0 || b == 0) 374 return (0); 375 return (1); 376 } 377 ERROR "unknown type %d in first", type(p) FATAL; 378 return (-1); 379 } 380 381 /* collects leaves that can follow v into setvec */ 382 static void 383 follow(Node *v) 384 { 385 Node *p; 386 387 if (type(v) == FINAL) 388 return; 389 p = parent(v); 390 switch (type(p)) { 391 case STAR: 392 case PLUS: 393 (void) first(v); 394 follow(p); 395 return; 396 397 case OR: 398 case QUEST: 399 follow(p); 400 return; 401 402 case CAT: 403 if (v == left(p)) { /* v is left child of p */ 404 if (first(right(p)) == 0) { 405 follow(p); 406 return; 407 } 408 } else /* v is right child */ 409 follow(p); 410 return; 411 default: 412 ERROR "unknown type %d in follow", type(p) FATAL; 413 break; 414 } 415 } 416 417 static int 418 member(uchar c, uchar *s) /* is c in s? */ 419 { 420 while (*s) 421 if (c == *s++) 422 return (1); 423 return (0); 424 } 425 426 427 int 428 match(fa *f, uchar *p) 429 { 430 register int s, ns; 431 432 s = f->reset ? makeinit(f, 0) : f->initstat; 433 if (f->out[s]) 434 return (1); 435 do { 436 if ((ns = f->gototab[s][*p]) != 0) 437 s = ns; 438 else 439 s = cgoto(f, s, *p); 440 if (f->out[s]) 441 return (1); 442 } while (*p++ != 0); 443 return (0); 444 } 445 446 int 447 pmatch(fa *f, uchar *p) 448 { 449 register int s, ns; 450 register uchar *q; 451 int i, k; 452 453 if (f->reset) { 454 f->initstat = s = makeinit(f, 1); 455 } else { 456 s = f->initstat; 457 } 458 patbeg = p; 459 patlen = -1; 460 do { 461 q = p; 462 do { 463 if (f->out[s]) /* final state */ 464 patlen = q-p; 465 if ((ns = f->gototab[s][*q]) != 0) 466 s = ns; 467 else 468 s = cgoto(f, s, *q); 469 if (s == 1) { /* no transition */ 470 if (patlen >= 0) { 471 patbeg = p; 472 return (1); 473 } else 474 goto nextin; /* no match */ 475 } 476 } while (*q++ != 0); 477 if (f->out[s]) 478 patlen = q - p - 1; /* don't count $ */ 479 if (patlen >= 0) { 480 patbeg = p; 481 return (1); 482 } 483 nextin: 484 s = 2; 485 if (f->reset) { 486 for (i = 2; i <= f->curstat; i++) 487 xfree(f->posns[i]); 488 k = *f->posns[0]; 489 if ((f->posns[2] = 490 (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) { 491 overflo("out of space in pmatch"); 492 } 493 for (i = 0; i <= k; i++) 494 (f->posns[2])[i] = (f->posns[0])[i]; 495 f->initstat = f->curstat = 2; 496 f->out[2] = f->out[0]; 497 for (i = 0; i < NCHARS; i++) 498 f->gototab[2][i] = 0; 499 } 500 } while (*p++ != 0); 501 return (0); 502 } 503 504 int 505 nematch(fa *f, uchar *p) 506 { 507 register int s, ns; 508 register uchar *q; 509 int i, k; 510 511 if (f->reset) { 512 f->initstat = s = makeinit(f, 1); 513 } else { 514 s = f->initstat; 515 } 516 patlen = -1; 517 while (*p) { 518 q = p; 519 do { 520 if (f->out[s]) /* final state */ 521 patlen = q-p; 522 if ((ns = f->gototab[s][*q]) != 0) 523 s = ns; 524 else 525 s = cgoto(f, s, *q); 526 if (s == 1) { /* no transition */ 527 if (patlen > 0) { 528 patbeg = p; 529 return (1); 530 } else 531 goto nnextin; /* no nonempty match */ 532 } 533 } while (*q++ != 0); 534 if (f->out[s]) 535 patlen = q - p - 1; /* don't count $ */ 536 if (patlen > 0) { 537 patbeg = p; 538 return (1); 539 } 540 nnextin: 541 s = 2; 542 if (f->reset) { 543 for (i = 2; i <= f->curstat; i++) 544 xfree(f->posns[i]); 545 k = *f->posns[0]; 546 if ((f->posns[2] = 547 (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) { 548 overflo("out of state space"); 549 } 550 for (i = 0; i <= k; i++) 551 (f->posns[2])[i] = (f->posns[0])[i]; 552 f->initstat = f->curstat = 2; 553 f->out[2] = f->out[0]; 554 for (i = 0; i < NCHARS; i++) 555 f->gototab[2][i] = 0; 556 } 557 p++; 558 } 559 return (0); 560 } 561 562 static Node *regexp(void), *primary(void), *concat(Node *); 563 static Node *alt(Node *), *unary(Node *); 564 565 static Node * 566 reparse(uchar *p) 567 { 568 /* parses regular expression pointed to by p */ 569 /* uses relex() to scan regular expression */ 570 Node *np; 571 572 dprintf(("reparse <%s>\n", p)); 573 lastre = prestr = p; /* prestr points to string to be parsed */ 574 rtok = relex(); 575 if (rtok == '\0') 576 ERROR "empty regular expression" FATAL; 577 np = regexp(); 578 if (rtok == '\0') { 579 return (np); 580 } else { 581 ERROR "syntax error in regular expression %s at %s", 582 lastre, prestr FATAL; 583 } 584 /*NOTREACHED*/ 585 return (NULL); 586 } 587 588 static Node * 589 regexp(void) 590 { 591 return (alt(concat(primary()))); 592 } 593 594 static Node * 595 primary(void) 596 { 597 Node *np; 598 599 switch (rtok) { 600 case CHAR: 601 np = op2(CHAR, NIL, (Node *)rlxval); 602 rtok = relex(); 603 return (unary(np)); 604 case ALL: 605 rtok = relex(); 606 return (unary(op2(ALL, NIL, NIL))); 607 case DOT: 608 rtok = relex(); 609 return (unary(op2(DOT, NIL, NIL))); 610 case CCL: 611 /*LINTED align*/ 612 np = op2(CCL, NIL, (Node *)cclenter(rlxstr)); 613 rtok = relex(); 614 return (unary(np)); 615 case NCCL: 616 /*LINTED align*/ 617 np = op2(NCCL, NIL, (Node *)cclenter(rlxstr)); 618 rtok = relex(); 619 return (unary(np)); 620 case '^': 621 rtok = relex(); 622 return (unary(op2(CHAR, NIL, (Node *)HAT))); 623 case '$': 624 rtok = relex(); 625 return (unary(op2(CHAR, NIL, NIL))); 626 case '(': 627 rtok = relex(); 628 if (rtok == ')') { /* special pleading for () */ 629 rtok = relex(); 630 return (unary(op2(CCL, NIL, 631 /*LINTED align*/ 632 (Node *)tostring((uchar *)"")))); 633 } 634 np = regexp(); 635 if (rtok == ')') { 636 rtok = relex(); 637 return (unary(np)); 638 } else { 639 ERROR "syntax error in regular expression %s at %s", 640 lastre, prestr FATAL; 641 } 642 default: 643 ERROR "illegal primary in regular expression %s at %s", 644 lastre, prestr FATAL; 645 } 646 /*NOTREACHED*/ 647 return (NULL); 648 } 649 650 static Node * 651 concat(Node *np) 652 { 653 switch (rtok) { 654 case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(': 655 return (concat(op2(CAT, np, primary()))); 656 default: 657 return (np); 658 } 659 } 660 661 static Node * 662 alt(Node *np) 663 { 664 if (rtok == OR) { 665 rtok = relex(); 666 return (alt(op2(OR, np, concat(primary())))); 667 } 668 return (np); 669 } 670 671 static Node * 672 unary(Node *np) 673 { 674 switch (rtok) { 675 case STAR: 676 rtok = relex(); 677 return (unary(op2(STAR, np, NIL))); 678 case PLUS: 679 rtok = relex(); 680 return (unary(op2(PLUS, np, NIL))); 681 case QUEST: 682 rtok = relex(); 683 return (unary(op2(QUEST, np, NIL))); 684 default: 685 return (np); 686 } 687 } 688 689 static int 690 relex(void) /* lexical analyzer for reparse */ 691 { 692 register int c; 693 uchar *cbuf; 694 int clen, cflag; 695 696 switch (c = *prestr++) { 697 case '|': return OR; 698 case '*': return STAR; 699 case '+': return PLUS; 700 case '?': return QUEST; 701 case '.': return DOT; 702 case '\0': prestr--; return '\0'; 703 case '^': 704 case '$': 705 case '(': 706 case ')': 707 return (c); 708 case '\\': 709 if ((c = *prestr++) == 't') 710 c = '\t'; 711 else if (c == 'n') 712 c = '\n'; 713 else if (c == 'f') 714 c = '\f'; 715 else if (c == 'r') 716 c = '\r'; 717 else if (c == 'b') 718 c = '\b'; 719 else if (c == '\\') 720 c = '\\'; 721 else if (isdigit(c)) { 722 int n = c - '0'; 723 if (isdigit(*prestr)) { 724 n = 8 * n + *prestr++ - '0'; 725 if (isdigit(*prestr)) 726 n = 8 * n + *prestr++ - '0'; 727 } 728 c = n; 729 } /* else it's now in c */ 730 rlxval = c; 731 return (CHAR); 732 default: 733 rlxval = c; 734 return (CHAR); 735 case '[': 736 clen = 0; 737 if (*prestr == '^') { 738 cflag = 1; 739 prestr++; 740 } else 741 cflag = 0; 742 init_buf(&cbuf, NULL, strlen((char *)prestr) * 2 + 1); 743 for (;;) { 744 if ((c = *prestr++) == '\\') { 745 cbuf[clen++] = '\\'; 746 if ((c = *prestr++) == '\0') { 747 ERROR 748 "nonterminated character class %s", lastre FATAL; 749 } 750 cbuf[clen++] = c; 751 } else if (c == ']') { 752 cbuf[clen] = 0; 753 rlxstr = tostring(cbuf); 754 free(cbuf); 755 if (cflag == 0) 756 return (CCL); 757 else 758 return (NCCL); 759 } else if (c == '\n') { 760 ERROR "newline in character class %s...", 761 lastre FATAL; 762 } else if (c == '\0') { 763 ERROR "nonterminated character class %s", 764 lastre FATAL; 765 } else 766 cbuf[clen++] = c; 767 } 768 /*NOTREACHED*/ 769 } 770 return (0); 771 } 772 773 static int 774 cgoto(fa *f, int s, int c) 775 { 776 register int i, j, k; 777 register int *p, *q; 778 779 for (i = 0; i <= f->accept; i++) 780 setvec[i] = 0; 781 setcnt = 0; 782 /* compute positions of gototab[s,c] into setvec */ 783 p = f->posns[s]; 784 for (i = 1; i <= *p; i++) { 785 if ((k = f->re[p[i]].ltype) != FINAL) { 786 if (k == CHAR && c == f->re[p[i]].lval || 787 k == DOT && c != 0 && c != HAT || 788 k == ALL && c != 0 || 789 k == CCL && 790 member(c, (uchar *)f->re[p[i]].lval) || 791 k == NCCL && 792 !member(c, (uchar *)f->re[p[i]].lval) && 793 c != 0 && c != HAT) { 794 q = f->re[p[i]].lfollow; 795 for (j = 1; j <= *q; j++) { 796 if (setvec[q[j]] == 0) { 797 setcnt++; 798 setvec[q[j]] = 1; 799 } 800 } 801 } 802 } 803 } 804 /* determine if setvec is a previous state */ 805 tmpset[0] = setcnt; 806 j = 1; 807 for (i = f->accept; i >= 0; i--) 808 if (setvec[i]) { 809 tmpset[j++] = i; 810 } 811 /* tmpset == previous state? */ 812 for (i = 1; i <= f->curstat; i++) { 813 p = f->posns[i]; 814 if ((k = tmpset[0]) != p[0]) 815 goto different; 816 for (j = 1; j <= k; j++) 817 if (tmpset[j] != p[j]) 818 goto different; 819 /* setvec is state i */ 820 f->gototab[s][c] = i; 821 return (i); 822 different:; 823 } 824 825 /* add tmpset to current set of states */ 826 if (f->curstat >= NSTATES-1) { 827 f->curstat = 2; 828 f->reset = 1; 829 for (i = 2; i < NSTATES; i++) 830 xfree(f->posns[i]); 831 } else 832 ++(f->curstat); 833 for (i = 0; i < NCHARS; i++) 834 f->gototab[f->curstat][i] = 0; 835 xfree(f->posns[f->curstat]); 836 if ((p = (int *)calloc(1, (setcnt + 1) * sizeof (int))) == NULL) 837 overflo("out of space in cgoto"); 838 839 f->posns[f->curstat] = p; 840 f->gototab[s][c] = f->curstat; 841 for (i = 0; i <= setcnt; i++) 842 p[i] = tmpset[i]; 843 if (setvec[f->accept]) 844 f->out[f->curstat] = 1; 845 else 846 f->out[f->curstat] = 0; 847 return (f->curstat); 848 } 849 850 static void 851 freefa(fa *f) 852 { 853 854 register int i; 855 856 if (f == NULL) 857 return; 858 for (i = 0; i <= f->curstat; i++) 859 xfree(f->posns[i]); 860 for (i = 0; i <= f->accept; i++) 861 xfree(f->re[i].lfollow); 862 xfree(f->restr); 863 xfree(f); 864 } 865