usr.bin/grep/dfa.c

0 /* dfa.c - deterministic extended regexp routines for GNU
118 #include "dfa.h"
129 static void dfamust PARAMS ((struct dfa *dfa));
268 /* A pointer to the current dfa is kept here during parsing. */
269 static struct dfa *dfa;
271 /* Find the index of charclass s in dfa->charclasses, or allocate a new charclass. */
277   for (i = 0; i < dfa->cindex; ++i)
278     if (equal(s, dfa->charclasses[i]))
280   REALLOC_IF_NECESSARY(dfa->charclasses, charclass, dfa->calloc, dfa->cindex);
281   ++dfa->cindex;
282   copyset(s, dfa->charclasses[i]);
472   REALLOC_IF_NECESSARY(dfa->mbcsets, struct mb_char_classes,
473 		       dfa->mbcsets_alloc, dfa->nmbcsets + 1);
474   /* dfa->multibyte_prop[] hold the index of dfa->mbcsets.
475      We will update dfa->multibyte_prop in addtok(), because we can't
476      decide the index in dfa->tokens[].  */
479   work_mbc = &(dfa->mbcsets[dfa->nmbcsets++]);
507 	 dfa is ever called. */
1019 		 dfa is ever called. */
1125       REALLOC_IF_NECESSARY(dfa->multibyte_prop, int, dfa->nmultibyte_prop,
1126 			   dfa->tindex);
1127       /* Set dfa->multibyte_prop.  See struct dfa in dfa.h.  */
1129 	dfa->multibyte_prop[dfa->tindex] = ((dfa->nmbcsets - 1) << 2) + 3;
1131 	dfa->multibyte_prop[dfa->tindex]
1138 	dfa->multibyte_prop[dfa->tindex] = 3;
1142   REALLOC_IF_NECESSARY(dfa->tokens, token, dfa->talloc, dfa->tindex);
1143   dfa->tokens[dfa->tindex++] = t;
1159       ++dfa->nleaves;
1164   if (depth > dfa->depth)
1165     dfa->depth = depth;
1269   switch (dfa->tokens[tindex - 1])
1292     addtok(dfa->tokens[tindex + i]);
1304 	ntokens = nsubtoks(dfa->tindex);
1305 	tindex = dfa->tindex - ntokens;
1358    the struct dfa to parse into. */
1360 dfaparse (char const *s, size_t len, struct dfa *d)
1362   dfa = d;
1481 state_index (struct dfa *d, position_set const *s, int newline, int letter)
1551 epsclosure (position_set *s, struct dfa const *d)
1667 dfaanalyze (struct dfa *d, int searchflag)
1932 dfastate (int s, struct dfa *d, int trans[])
2223 /* Some routines for manipulating a compiled dfa's transition tables.
2231 build_state (int s, struct dfa *d)
2304 build_state_zero (struct dfa *d)
2341 realloc_trans_if_necessary(struct dfa *d, int new_state)
2377 transit_state_singlebyte (struct dfa *d, int s, unsigned char const *p,
2421 match_anychar (struct dfa *d, int s, position pos, int index)
2461 match_mb_charset (struct dfa *d, int s, position pos, int index)
2578 check_matching_with_multibyte_ops (struct dfa *d, int s, int index)
2609 transit_state_consume_1char (struct dfa *d, int s, unsigned char const **pp,
2659 transit_state (struct dfa *d, int s, unsigned char const **pp)
2743 /* Search through a buffer looking for a match to the given struct dfa.
2753 dfaexec (struct dfa *d, char const *begin, size_t size, int *backref)
2919 /* Initialize the components of a dfa that the other routines don't
2922 dfainit (struct dfa *d)
2950 dfacomp (char const *s, size_t len, struct dfa *d, int searchflag)
2987 /* Free the storage held by the components of a dfa. */
2989 dfafree (struct dfa *d)
3342 dfamust (struct dfa *dfa)
3357   musts = (must *) malloc((dfa->tindex + 1) * sizeof *musts);
3361   for (i = 0; i <= dfa->tindex; ++i)
3363   for (i = 0; i <= dfa->tindex; ++i)
3377   for (i = 0; i < dfa->tindex; ++i)
3380       prtok(dfa->tokens[i]);
3384   for (ri = 0; ri < dfa->tindex; ++ri)
3386       switch (t = dfa->tokens[ri])
3555       prtok(dfa->tokens[ri]);
3572       dm->next = dfa->musts;
3573       dfa->musts = dm;
3576   for (i = 0; i <= dfa->tindex; ++i)