Lines Matching refs:f
122 intalloc(size_t n, const char *f) in intalloc() argument
126 overflo(f); in intalloc()
131 resizesetvec(const char *f) in resizesetvec() argument
140 overflo(f); in resizesetvec()
144 resize_state(fa *f, int state) in resize_state() argument
151 if (++state < f->state_count) in resize_state()
156 p = (gtt *) realloc(f->gototab, new_count * sizeof(gtt)); in resize_state()
159 f->gototab = p; in resize_state()
161 p2 = (uschar *) realloc(f->out, new_count * sizeof(f->out[0])); in resize_state()
164 f->out = p2; in resize_state()
166 p3 = (int **) realloc(f->posns, new_count * sizeof(f->posns[0])); in resize_state()
169 f->posns = p3; in resize_state()
171 for (i = f->state_count; i < new_count; ++i) { in resize_state()
172 f->gototab[i].entries = (gtte *) calloc(NCHARS, sizeof(gtte)); in resize_state()
173 if (f->gototab[i].entries == NULL) in resize_state()
175 f->gototab[i].allocated = NCHARS; in resize_state()
176 f->gototab[i].inuse = 0; in resize_state()
177 f->out[i] = 0; in resize_state()
178 f->posns[i] = NULL; in resize_state()
180 f->state_count = new_count; in resize_state()
228 fa *f; in mkdfa() local
240 if ((f = (fa *) calloc(1, sizeof(fa) + poscnt * sizeof(rrow))) == NULL) in mkdfa()
242 f->accept = poscnt-1; /* penter has computed number of positions in re */ in mkdfa()
243 cfoll(f, p1); /* set up follow sets */ in mkdfa()
245 resize_state(f, 1); in mkdfa()
246 f->posns[0] = intalloc(*(f->re[0].lfollow), __func__); in mkdfa()
247 f->posns[1] = intalloc(1, __func__); in mkdfa()
248 *f->posns[1] = 0; in mkdfa()
249 f->initstat = makeinit(f, anchor); in mkdfa()
250 f->anchor = anchor; in mkdfa()
251 f->restr = (uschar *) tostring(s); in mkdfa()
256 return f; in mkdfa()
259 int makeinit(fa *f, bool anchor) in makeinit() argument
263 f->curstat = 2; in makeinit()
264 f->out[2] = 0; in makeinit()
265 k = *(f->re[0].lfollow); in makeinit()
266 xfree(f->posns[2]); in makeinit()
267 f->posns[2] = intalloc(k + 1, __func__); in makeinit()
269 (f->posns[2])[i] = (f->re[0].lfollow)[i]; in makeinit()
271 if ((f->posns[2])[1] == f->accept) in makeinit()
272 f->out[2] = 1; in makeinit()
273 clear_gototab(f, 2); in makeinit()
274 f->curstat = cgoto(f, 2, HAT); in makeinit()
276 *f->posns[2] = k-1; /* leave out position 0 */ in makeinit()
278 (f->posns[0])[i] = (f->posns[2])[i]; in makeinit()
281 f->out[0] = f->out[2]; in makeinit()
282 if (f->curstat != 2) in makeinit()
283 --(*f->posns[f->curstat]); in makeinit()
285 return f->curstat; in makeinit()
487 void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */ in cfoll() argument
495 f->re[info(v)].ltype = type(v); in cfoll()
496 f->re[info(v)].lval.np = right(v); in cfoll()
497 while (f->accept >= maxsetvec) { /* guessing here! */ in cfoll()
500 for (i = 0; i <= f->accept; i++) in cfoll()
505 f->re[info(v)].lfollow = p; in cfoll()
507 for (i = f->accept; i >= 0; i--) in cfoll()
512 cfoll(f,left(v)); in cfoll()
516 cfoll(f,left(v)); in cfoll()
517 cfoll(f,right(v)); in cfoll()
612 static void resize_gototab(fa *f, int state) in resize_gototab() argument
614 size_t new_size = f->gototab[state].allocated * 2; in resize_gototab()
615 gtte *p = (gtte *) realloc(f->gototab[state].entries, new_size * sizeof(gtte)); in resize_gototab()
620 size_t orig_size = f->gototab[state].allocated; // 2nd half of new mem is this size in resize_gototab()
623 f->gototab[state].allocated = new_size; // update gototab info in resize_gototab()
624 f->gototab[state].entries = p; in resize_gototab()
627 static int get_gototab(fa *f, int state, int ch) /* hide gototab implementation */ in get_gototab() argument
634 item = (gtte *) bsearch(& key, f->gototab[state].entries, in get_gototab()
635 f->gototab[state].inuse, sizeof(gtte), in get_gototab()
654 static int set_gototab(fa *f, int state, int ch, int val) /* hide gototab implementation */ in set_gototab() argument
656 if (f->gototab[state].inuse == 0) { in set_gototab()
657 f->gototab[state].entries[0].ch = ch; in set_gototab()
658 f->gototab[state].entries[0].state = val; in set_gototab()
659 f->gototab[state].inuse++; in set_gototab()
661 } else if ((unsigned)ch > f->gototab[state].entries[f->gototab[state].inuse-1].ch) { in set_gototab()
663 gtt *tab = & f->gototab[state]; in set_gototab()
665 resize_gototab(f, state); in set_gototab()
667 f->gototab[state].entries[f->gototab[state].inuse].ch = ch; in set_gototab()
668 f->gototab[state].entries[f->gototab[state].inuse].state = val; in set_gototab()
669 f->gototab[state].inuse++; in set_gototab()
678 item = (gtte *) bsearch(& key, f->gototab[state].entries, in set_gototab()
679 f->gototab[state].inuse, sizeof(gtte), in set_gototab()
690 gtt *tab = & f->gototab[state]; in set_gototab()
692 resize_gototab(f, state); in set_gototab()
693 f->gototab[state].entries[tab->inuse].ch = ch; in set_gototab()
694 f->gototab[state].entries[tab->inuse].state = val; in set_gototab()
697 qsort(f->gototab[state].entries, in set_gototab()
698 f->gototab[state].inuse, sizeof(gtte), entry_cmp); in set_gototab()
703 static void clear_gototab(fa *f, int state) in clear_gototab() argument
705 memset(f->gototab[state].entries, 0, in clear_gototab()
706 f->gototab[state].allocated * sizeof(gtte)); in clear_gototab()
707 f->gototab[state].inuse = 0; in clear_gototab()
710 int match(fa *f, const char *p0) /* shortest match ? */ in match() argument
719 s = f->initstat; in match()
720 assert (s < f->state_count); in match()
722 if (f->out[s]) in match()
727 if ((ns = get_gototab(f, s, rune)) != 0) in match()
730 s = cgoto(f, s, rune); in match()
731 if (f->out[s]) in match()
740 int pmatch(fa *f, const char *p0) /* longest match, for sub */ in pmatch() argument
748 s = f->initstat; in pmatch()
749 assert(s < f->state_count); in pmatch()
756 if (f->out[s]) /* final state */ in pmatch()
760 if ((ns = get_gototab(f, s, rune)) != 0) in pmatch()
763 s = cgoto(f, s, rune); in pmatch()
765 assert(s < f->state_count); in pmatch()
780 if (f->out[s]) in pmatch()
796 int nematch(fa *f, const char *p0) /* non-empty match, for sub */ in nematch() argument
804 s = f->initstat; in nematch()
805 assert(s < f->state_count); in nematch()
812 if (f->out[s]) /* final state */ in nematch()
816 if ((ns = get_gototab(f, s, rune)) != 0) in nematch()
819 s = cgoto(f, s, rune); in nematch()
832 if (f->out[s]) in nematch()
861 bool fnematch(fa *pfa, FILE *f, char **pbuf, int *pbufsize, int quantum) in fnematch() argument
904 *k++ = (c = getc(f)) != EOF ? c : 0; in fnematch()
906 if (ferror(f)) in fnematch()
953 if (*--k && ungetc(*k, f) == EOF) in fnematch()
1481 int cgoto(fa *f, int s, int c) in cgoto() argument
1487 while (f->accept >= maxsetvec) { /* guessing here! */ in cgoto()
1490 for (i = 0; i <= f->accept; i++) in cgoto()
1493 resize_state(f, s); in cgoto()
1495 p = f->posns[s]; in cgoto()
1497 if ((k = f->re[p[i]].ltype) != FINAL) { in cgoto()
1498 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) in cgoto()
1502 || (k == CCL && member(c, (int *) f->re[p[i]].lval.rp)) in cgoto()
1503 || (k == NCCL && !member(c, (int *) f->re[p[i]].lval.rp) && c != 0 && c != HAT)) { in cgoto()
1504 q = f->re[p[i]].lfollow; in cgoto()
1520 for (i = f->accept; i >= 0; i--) in cgoto()
1524 resize_state(f, f->curstat > s ? f->curstat : s); in cgoto()
1526 for (i = 1; i <= f->curstat; i++) { in cgoto()
1527 p = f->posns[i]; in cgoto()
1535 set_gototab(f, s, c, i); in cgoto()
1541 ++(f->curstat); in cgoto()
1542 resize_state(f, f->curstat); in cgoto()
1543 clear_gototab(f, f->curstat); in cgoto()
1544 xfree(f->posns[f->curstat]); in cgoto()
1547 f->posns[f->curstat] = p; in cgoto()
1549 set_gototab(f, s, c, f->curstat); in cgoto()
1552 if (setvec[f->accept]) in cgoto()
1553 f->out[f->curstat] = 1; in cgoto()
1555 f->out[f->curstat] = 0; in cgoto()
1556 return f->curstat; in cgoto()
1560 void freefa(fa *f) /* free a finite automaton */ in freefa() argument
1564 if (f == NULL) in freefa()
1566 for (i = 0; i < f->state_count; i++) in freefa()
1567 xfree(f->gototab[i].entries); in freefa()
1568 xfree(f->gototab); in freefa()
1569 for (i = 0; i <= f->curstat; i++) in freefa()
1570 xfree(f->posns[i]); in freefa()
1571 for (i = 0; i <= f->accept; i++) { in freefa()
1572 xfree(f->re[i].lfollow); in freefa()
1573 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL) in freefa()
1574 xfree(f->re[i].lval.np); in freefa()
1576 xfree(f->restr); in freefa()
1577 xfree(f->out); in freefa()
1578 xfree(f->posns); in freefa()
1579 xfree(f->gototab); in freefa()
1580 xfree(f); in freefa()