RPA Toolkit
48088c1ca990f60b3227d3c35d204087e19acd6a
[rpatk.git] / rex / rexdfa.h
1 /*
2  *  Regular Pattern Analyzer (RPA)
3  *  Copyright (c) 2009-2010 Martin Stoilov
4  *
5  *  This program is free software: you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation, either version 3 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  *
18  *  Martin Stoilov <martin@rpasearch.com>
19  */
20
21 #ifndef _REXDFA_H_
22 #define _REXDFA_H_
23
24 #ifdef __cplusplus
25 extern "C" {
26 #endif
27
28 #ifndef REX_USERDATA_TYPE
29 typedef unsigned long rexuserdata_t;
30 #else
31 typedef REX_USERDATA_TYPE rexuserdata_t;
32 #endif
33
34
35 #ifndef REX_UINT_TYPE
36 typedef unsigned int rexuint_t;
37 #else
38 typedef REX_UINT_TYPE rexuint_t;
39 #endif
40
41
42 #ifndef REX_CHAR_TYPE
43 typedef unsigned int rexchar_t;
44 #else
45 typedef REX_CHAR_TYPE rexchar_t;
46 #endif
47 #define REX_CHAR_MAX ((rexchar_t)-1)
48 #define REX_CHAR_MIN ((rexchar_t)0)
49
50 typedef enum {
51         REX_STATETYPE_NONE = 0,
52         REX_STATETYPE_START = 1,
53         REX_STATETYPE_ACCEPT = 2,
54         REX_STATETYPE_DEAD = 3,
55 } rex_statetype_t;
56
57 #define REX_DFA_DEADSTATE (0)
58 #define REX_DFA_STARTSTATE (1)
59
60 #define REX_DFA_STATE(__dfa__, __nstate__)                                                      (&(__dfa__)->states[__nstate__])
61 #define REX_DFA_TRANSITION(__dfa__, __nstate__, __ntrans__)                     (&(__dfa__)->trans[(REX_DFA_STATE(__dfa__, __nstate__)->trans) + (__ntrans__)])
62 #define REX_DFA_SUBSTATE(__dfa__, __nstate__, __nsubstate__)            ((__dfa__)->substates ? &(__dfa__)->substates[REX_DFA_STATE(__dfa__, __nstate__)->substates + (__nsubstate__)] : ((void*)0))
63 #define REX_DFA_ACCSUBSTATE(__dfa__, __nstate__, __naccsubstate__)      ((__dfa__)->accsubstates ? &(__dfa__)->accsubstates[REX_DFA_STATE(__dfa__, __nstate__)->accsubstates + (__naccsubstate__)] : ((void*)0))
64 #define REX_DFA_NEXT(__dfa__, __nstate__, __input__) \
65                 ({ \
66                         rexdft_t *t; \
67                         rexuint_t mid, min = 0, max = REX_DFA_STATE(__dfa__, __nstate__)->ntrans; \
68                         while (max > min) { \
69                                 mid = (min + max)/2; \
70                                 t = REX_DFA_TRANSITION(dfa, nstate, mid); \
71                                 if ((__input__) >= t->lowin) { \
72                                         min = mid + 1; \
73                                 } else { \
74                                         max = mid; \
75                                 } \
76                         } \
77                         t = REX_DFA_TRANSITION(__dfa__, __nstate__, min-1); \
78                         (t->state); \
79                 })
80
81
82 /*
83  * Sub-state info definition
84  */
85 typedef struct rexdfss_s {
86         rexuint_t type;
87         rexuint_t uid;
88         rexuserdata_t userdata;
89 } rexdfss_t;
90
91
92 /*
93  * Transition definition
94  */
95 typedef struct rexdft_s {
96         rexchar_t lowin;
97         rexchar_t highin;
98         rexuint_t state;
99 } rexdft_t;
100
101
102 /*
103  * State definition
104  */
105 typedef struct rexdfs_s {
106         rexuint_t type;
107         rexuint_t trans;
108         rexuint_t ntrans;
109         rexuint_t accsubstates;
110         rexuint_t naccsubstates;
111         rexuint_t substates;
112         rexuint_t nsubstates;
113 } rexdfs_t;
114
115
116 /*
117  * Automata definition
118  */
119 typedef struct rexdfa_s {
120         rexuint_t nstates;
121         rexdfs_t *states;
122         rexuint_t ntrans;
123         rexdft_t *trans;
124         rexuint_t naccsubstates;
125         rexdfss_t *accsubstates;
126         rexuint_t nsubstates;
127         rexdfss_t *substates;
128 } rexdfa_t;
129
130
131 rexdfa_t *rex_dfa_create(rexuint_t nstates, rexuint_t ntrans, rexuint_t naccsubstates, rexuint_t nsubstates);
132 void rex_dfa_destroy(rexdfa_t *dfa);
133 void rex_dfa_dumpstate(rexdfa_t *dfa, rexuint_t nstate);
134 rexdfs_t *rex_dfa_state(rexdfa_t *dfa, rexuint_t nstate);
135 rexdft_t *rex_dfa_transition(rexdfa_t *dfa, rexuint_t nstate, rexuint_t ntransition);
136 rexdfss_t *rex_dfa_substate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t nsubstate);
137 rexdfss_t *rex_dfa_accsubstate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t naccsubstate);
138 rexuint_t rex_dfa_next(rexdfa_t *dfa, rexuint_t nstate, rexchar_t input);
139
140 #ifdef __cplusplus
141 }
142 #endif
143
144
145 #endif /* _REXDFA_H_ */