RPA Toolkit
Defined rexuword_t type.
[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 #ifndef REX_UWORD_TYPE
35 typedef unsigned long rexuword_t;
36 #else
37 typedef REX_UWORD_TYPE rexuword_t;
38 #endif
39
40 #ifndef REX_UINT_TYPE
41 typedef unsigned int rexuint_t;
42 #else
43 typedef REX_UINT_TYPE rexuint_t;
44 #endif
45
46
47 #ifndef REX_CHAR_TYPE
48 typedef unsigned int rexchar_t;
49 #else
50 typedef REX_CHAR_TYPE rexchar_t;
51 #endif
52 #define REX_CHAR_MAX ((rexchar_t)-1)
53 #define REX_CHAR_MIN ((rexchar_t)0)
54
55 typedef enum {
56         REX_STATETYPE_NONE = 0,
57         REX_STATETYPE_START = 1,
58         REX_STATETYPE_ACCEPT = 2,
59         REX_STATETYPE_DEAD = 3,
60 } rex_statetype_t;
61
62 #define REX_DFA_DEADSTATE (0)
63 #define REX_DFA_STARTSTATE (1)
64
65 #define REX_DFA_STATE(__dfa__, __nstate__)                                                      (&(__dfa__)->states[__nstate__])
66 #define REX_DFA_TRANSITION(__dfa__, __nstate__, __ntrans__)                     (&(__dfa__)->trans[(REX_DFA_STATE(__dfa__, __nstate__)->trans) + (__ntrans__)])
67 #define REX_DFA_SUBSTATE(__dfa__, __nstate__, __nsubstate__)            ((__dfa__)->substates ? &(__dfa__)->substates[REX_DFA_STATE(__dfa__, __nstate__)->substates + (__nsubstate__)] : ((void*)0))
68 #define REX_DFA_ACCSUBSTATE(__dfa__, __nstate__, __naccsubstate__)      ((__dfa__)->accsubstates ? &(__dfa__)->accsubstates[REX_DFA_STATE(__dfa__, __nstate__)->accsubstates + (__naccsubstate__)] : ((void*)0))
69 #define REX_DFA_NEXT(__dfa__, __nstate__, __input__) \
70                 ({ \
71                         rexdft_t *t; \
72                         rexuint_t mid, min = 0, max = REX_DFA_STATE(__dfa__, __nstate__)->ntrans; \
73                         while (max > min) { \
74                                 mid = (min + max)/2; \
75                                 t = REX_DFA_TRANSITION(dfa, nstate, mid); \
76                                 if ((__input__) >= t->lowin) { \
77                                         min = mid + 1; \
78                                 } else { \
79                                         max = mid; \
80                                 } \
81                         } \
82                         t = REX_DFA_TRANSITION(__dfa__, __nstate__, min-1); \
83                         (t->state); \
84                 })
85
86
87 /*
88  * Sub-state info definition
89  */
90 typedef struct rexdfss_s {
91         rexuint_t type;
92         rexuint_t uid;
93         rexuserdata_t userdata;
94 } rexdfss_t;
95
96
97 /*
98  * Transition definition
99  */
100 typedef struct rexdft_s {
101         rexchar_t lowin;
102         rexchar_t highin;
103         rexuint_t state;
104 } rexdft_t;
105
106
107 /*
108  * State definition
109  */
110 typedef struct rexdfs_s {
111         rexuint_t type;
112         rexuint_t trans;
113         rexuint_t ntrans;
114         rexuint_t accsubstates;
115         rexuint_t naccsubstates;
116         rexuint_t substates;
117         rexuint_t nsubstates;
118 } rexdfs_t;
119
120
121 /*
122  * Automata definition
123  */
124 typedef struct rexdfa_s {
125         rexuint_t nstates;
126         rexdfs_t *states;
127         rexuint_t ntrans;
128         rexdft_t *trans;
129         rexuint_t naccsubstates;
130         rexdfss_t *accsubstates;
131         rexuint_t nsubstates;
132         rexdfss_t *substates;
133         rexuword_t reserved[64];
134 } rexdfa_t;
135
136
137 rexdfa_t *rex_dfa_create(rexuint_t nstates, rexuint_t ntrans, rexuint_t naccsubstates, rexuint_t nsubstates);
138 void rex_dfa_destroy(rexdfa_t *dfa);
139 void rex_dfa_dumpstate(rexdfa_t *dfa, rexuint_t nstate);
140 rexdfs_t *rex_dfa_state(rexdfa_t *dfa, rexuint_t nstate);
141 rexdft_t *rex_dfa_transition(rexdfa_t *dfa, rexuint_t nstate, rexuint_t ntransition);
142 rexdfss_t *rex_dfa_substate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t nsubstate);
143 rexdfss_t *rex_dfa_accsubstate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t naccsubstate);
144 rexuint_t rex_dfa_next(rexdfa_t *dfa, rexuint_t nstate, rexchar_t input);
145
146 #ifdef __cplusplus
147 }
148 #endif
149
150
151 #endif /* _REXDFA_H_ */