regdfa.h (2591B)
1 /* 2 * Changes by Gunnar Ritter, Freiburg i. Br., Germany, November 2002. 3 * 4 * Sccsid @(#)regdfa.h 1.3 (gritter) 9/22/03 5 */ 6 /* UNIX(R) Regular Expresssion Library 7 * 8 * Note: Code is released under the GNU LGPL 9 * 10 * Copyright (C) 2001 Caldera International, Inc. 11 * 12 * This library is free software; you can redistribute it and/or 13 * modify it under the terms of the GNU Lesser General Public 14 * License as published by the Free Software Foundation; either 15 * version 2 of the License, or (at your option) any later version. 16 * 17 * This library is distributed in the hope that it will be useful, 18 * but WITHOUT ANY WARRANTY; without even the implied warranty of 19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 20 * Lesser General Public License for more details. 21 * 22 * You should have received a copy of the GNU Lesser General Public 23 * License along with this library; if not, write to: 24 * Free Software Foundation, Inc. 25 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 26 */ 27 28 /* #include "synonyms.h" */ 29 30 /* 31 * Deterministic Finite Automata. 32 */ 33 34 #ifndef LIBUXRE_REGDFA_H 35 #define LIBUXRE_REGDFA_H 36 37 #include <re.h> 38 39 typedef struct 40 { 41 Bracket *bkt; /* extra info for ROP_BKT */ 42 size_t nset; /* number of items in the follow set */ 43 size_t seti; /* index into the follow set strip */ 44 w_type op; /* the leaf match operation */ 45 } Posn; 46 47 #define CACHESZ 32 /* max. states to remember (must fit in uchar) */ 48 #define NCHAR (1 << CHAR_BIT) 49 50 struct re_dfa_ /*Dfa*/ 51 { 52 unsigned char *posset; /* signatures built here */ 53 size_t *posfoll; /* follow strip for posn[] */ 54 size_t *sigfoll; /* follow strip for sigi[] */ 55 size_t *cursig; /* current state's signature */ 56 Posn *posn; /* important positions */ 57 size_t nposn; /* length of posn,cursig,posset */ 58 size_t used; /* used portion of follow strip */ 59 size_t avail; /* unused part of follow strip */ 60 size_t nset; /* # items nonzero in posset[] */ 61 size_t nsig[CACHESZ]; /* number of items in signature */ 62 size_t sigi[CACHESZ]; /* index into sigfoll[] */ 63 unsigned char acc[CACHESZ]; /* nonzero for accepting states */ 64 unsigned char leftmost; /* leftmost() start, not BOL */ 65 unsigned char leftbol; /* leftmost() start, w/BOL */ 66 unsigned char anybol; /* any match start, w/BOL */ 67 unsigned char nfix; /* number of invariant states */ 68 unsigned char top; /* next state index available */ 69 unsigned char flags; /* interesting flags */ 70 unsigned char trans[CACHESZ][NCHAR]; /* goto table */ 71 }; 72 73 extern int regtrans(Dfa *, int, w_type, int); 74 75 #endif /* !LIBUXRE_REGDFA_H */