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()
474 void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */ in cfoll() argument
482 f->re[info(v)].ltype = type(v); in cfoll()
483 f->re[info(v)].lval.np = right(v); in cfoll()
484 while (f->accept >= maxsetvec) { /* guessing here! */ in cfoll()
487 for (i = 0; i <= f->accept; i++) in cfoll()
492 f->re[info(v)].lfollow = p; in cfoll()
494 for (i = f->accept; i >= 0; i--) in cfoll()
499 cfoll(f,left(v)); in cfoll()
503 cfoll(f,left(v)); in cfoll()
504 cfoll(f,right(v)); in cfoll()
599 static void resize_gototab(fa *f, int state) in resize_gototab() argument
601 size_t new_size = f->gototab[state].allocated * 2; in resize_gototab()
602 gtte *p = (gtte *) realloc(f->gototab[state].entries, new_size * sizeof(gtte)); in resize_gototab()
607 size_t orig_size = f->gototab[state].allocated; // 2nd half of new mem is this size in resize_gototab()
610 f->gototab[state].allocated = new_size; // update gototab info in resize_gototab()
611 f->gototab[state].entries = p; in resize_gototab()
614 static int get_gototab(fa *f, int state, int ch) /* hide gototab implementation */ in get_gototab() argument
621 item = (gtte *) bsearch(& key, f->gototab[state].entries, in get_gototab()
622 f->gototab[state].inuse, sizeof(gtte), in get_gototab()
641 static int set_gototab(fa *f, int state, int ch, int val) /* hide gototab implementation */ in set_gototab() argument
643 if (f->gototab[state].inuse == 0) { in set_gototab()
644 f->gototab[state].entries[0].ch = ch; in set_gototab()
645 f->gototab[state].entries[0].state = val; in set_gototab()
646 f->gototab[state].inuse++; in set_gototab()
648 } else if (ch > f->gototab[state].entries[f->gototab[state].inuse-1].ch) { in set_gototab()
650 gtt *tab = & f->gototab[state]; in set_gototab()
652 resize_gototab(f, state); in set_gototab()
654 f->gototab[state].entries[f->gototab[state].inuse-1].ch = ch; in set_gototab()
655 f->gototab[state].entries[f->gototab[state].inuse-1].state = val; in set_gototab()
656 f->gototab[state].inuse++; in set_gototab()
665 item = (gtte *) bsearch(& key, f->gototab[state].entries, in set_gototab()
666 f->gototab[state].inuse, sizeof(gtte), in set_gototab()
677 gtt *tab = & f->gototab[state]; in set_gototab()
679 resize_gototab(f, state); in set_gototab()
681 f->gototab[state].entries[tab->inuse].ch = ch; in set_gototab()
682 f->gototab[state].entries[tab->inuse].state = val; in set_gototab()
684 qsort(f->gototab[state].entries, in set_gototab()
685 f->gototab[state].inuse, sizeof(gtte), entry_cmp); in set_gototab()
690 static void clear_gototab(fa *f, int state) in clear_gototab() argument
692 memset(f->gototab[state].entries, 0, in clear_gototab()
693 f->gototab[state].allocated * sizeof(gtte)); in clear_gototab()
694 f->gototab[state].inuse = 0; in clear_gototab()
697 int match(fa *f, const char *p0) /* shortest match ? */ in match() argument
706 s = f->initstat; in match()
707 assert (s < f->state_count); in match()
709 if (f->out[s]) in match()
714 if ((ns = get_gototab(f, s, rune)) != 0) in match()
717 s = cgoto(f, s, rune); in match()
718 if (f->out[s]) in match()
727 int pmatch(fa *f, const char *p0) /* longest match, for sub */ in pmatch() argument
735 s = f->initstat; in pmatch()
736 assert(s < f->state_count); in pmatch()
743 if (f->out[s]) /* final state */ in pmatch()
747 if ((ns = get_gototab(f, s, rune)) != 0) in pmatch()
750 s = cgoto(f, s, rune); in pmatch()
752 assert(s < f->state_count); in pmatch()
767 if (f->out[s]) in pmatch()
783 int nematch(fa *f, const char *p0) /* non-empty match, for sub */ in nematch() argument
791 s = f->initstat; in nematch()
792 assert(s < f->state_count); in nematch()
799 if (f->out[s]) /* final state */ in nematch()
803 if ((ns = get_gototab(f, s, rune)) != 0) in nematch()
806 s = cgoto(f, s, rune); in nematch()
819 if (f->out[s]) in nematch()
850 bool fnematch(fa *pfa, FILE *f, char **pbuf, int *pbufsize, int quantum) in fnematch() argument
881 *k++ = (c = getc(f)) != EOF ? c : 0; in fnematch()
883 if (ferror(f)) in fnematch()
934 if (*--k && ungetc(*k, f) == EOF) in fnematch()
1462 int cgoto(fa *f, int s, int c) in cgoto() argument
1468 while (f->accept >= maxsetvec) { /* guessing here! */ in cgoto()
1471 for (i = 0; i <= f->accept; i++) in cgoto()
1474 resize_state(f, s); in cgoto()
1476 p = f->posns[s]; in cgoto()
1478 if ((k = f->re[p[i]].ltype) != FINAL) { in cgoto()
1479 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) in cgoto()
1483 || (k == CCL && member(c, (int *) f->re[p[i]].lval.rp)) in cgoto()
1484 || (k == NCCL && !member(c, (int *) f->re[p[i]].lval.rp) && c != 0 && c != HAT)) { in cgoto()
1485 q = f->re[p[i]].lfollow; in cgoto()
1501 for (i = f->accept; i >= 0; i--) in cgoto()
1505 resize_state(f, f->curstat > s ? f->curstat : s); in cgoto()
1507 for (i = 1; i <= f->curstat; i++) { in cgoto()
1508 p = f->posns[i]; in cgoto()
1516 set_gototab(f, s, c, i); in cgoto()
1522 ++(f->curstat); in cgoto()
1523 resize_state(f, f->curstat); in cgoto()
1524 clear_gototab(f, f->curstat); in cgoto()
1525 xfree(f->posns[f->curstat]); in cgoto()
1528 f->posns[f->curstat] = p; in cgoto()
1530 set_gototab(f, s, c, f->curstat); in cgoto()
1533 if (setvec[f->accept]) in cgoto()
1534 f->out[f->curstat] = 1; in cgoto()
1536 f->out[f->curstat] = 0; in cgoto()
1537 return f->curstat; in cgoto()
1541 void freefa(fa *f) /* free a finite automaton */ in freefa() argument
1545 if (f == NULL) in freefa()
1547 for (i = 0; i < f->state_count; i++) in freefa()
1548 xfree(f->gototab[i].entries); in freefa()
1549 xfree(f->gototab); in freefa()
1550 for (i = 0; i <= f->curstat; i++) in freefa()
1551 xfree(f->posns[i]); in freefa()
1552 for (i = 0; i <= f->accept; i++) { in freefa()
1553 xfree(f->re[i].lfollow); in freefa()
1554 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL) in freefa()
1555 xfree(f->re[i].lval.np); in freefa()
1557 xfree(f->restr); in freefa()
1558 xfree(f->out); in freefa()
1559 xfree(f->posns); in freefa()
1560 xfree(f->gototab); in freefa()
1561 xfree(f); in freefa()