RPA Toolkit
Fixed windows build - 2
[rpatk.git] / rex / rexdfa.h
1 /*
2  *  Regular Pattern Analyzer Toolkit (RPA/Tk)
3  *  Copyright (c) 2009-2012 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 /**
22  * @file rex/rexdfa.h
23  * @brief Definition of DFA interface
24  *
25  *
26  * <h2>Synopsis</h2>
27  * This file defines the data structures and the macros for the DFA implementation.
28  */
29
30 #ifndef _REXDFA_H_
31 #define _REXDFA_H_
32
33 #ifdef __cplusplus
34 extern "C" {
35 #endif
36
37 #ifndef REX_USERDATA_TYPE
38 #ifdef WIN32
39 typedef size_t rexuserdata_t;
40 #else
41 typedef unsigned long rexuserdata_t;
42 #endif
43 #else
44 typedef REX_USERDATA_TYPE rexuserdata_t;
45 #endif
46
47 #ifndef REX_UWORD_TYPE
48 typedef unsigned long rexuword_t;
49 #else
50 typedef REX_UWORD_TYPE rexuword_t;
51 #endif
52
53 #ifndef REX_UINT_TYPE
54 typedef unsigned int rexuint_t;
55 #else
56 typedef REX_UINT_TYPE rexuint_t;
57 #endif
58
59
60 #ifndef REX_CHAR_TYPE
61 typedef unsigned int rexchar_t;
62 #else
63 typedef REX_CHAR_TYPE rexchar_t;
64 #endif
65 #define REX_CHAR_MAX ((rexchar_t)-1)
66 #define REX_CHAR_MIN ((rexchar_t)0)
67
68
69 /**
70  * Define DFA sub-state.
71  */
72 typedef struct rexdfss_s {
73         rexuint_t type;                                 /**< This is the original NFA state type(substate of a DFA state). */
74         rexuint_t uid;                                  /**< Unique ID of the NFA state(substate of a DFA state). */
75         rexuserdata_t userdata;                 /**< If this is an accepting sub-state, this parameter has the value specified in the @ref rex_db_addexpression call.
76                                                                                  This parameter is used to track which regular expression is matching, when the DFA gets to accepting state. */
77 } rexdfss_t;
78
79
80 /**
81  * Define DFA transition.
82  */
83 typedef struct rexdft_s {
84         rexchar_t lowin;                                /**< Low input boundary */
85         rexchar_t highin;                               /**< High input boundary */
86         rexuint_t state;                                /**< New state to go to if the input is within the boundary */
87 } rexdft_t;
88
89
90 /**
91  * State definition
92  */
93 typedef struct rexdfs_s {
94         rexuint_t type;                                 /**< Type of DFA state. */
95         rexuint_t trans;                                /**< The offset of the first transition for this state in the dfa->trans array. */
96         rexuint_t ntrans;                               /**< Total number of transitions. */
97         rexuint_t accsubstates;                 /**< The offset of the first accepting sub-state for this state in the dfa->accsubstates array. */
98         rexuint_t naccsubstates;                /**< Total number of accepting sub-states. */
99         rexuint_t substates;                    /**< The offset of the first sub-state for this state in the dfa->substates array. */
100         rexuint_t nsubstates;                   /**< Total number of sub-states. */
101 } rexdfs_t;
102
103
104 /**
105  * Define DFA.
106  */
107 typedef struct rexdfa_s {
108         rexuint_t nstates;                              /**< Total number of states. */
109         rexdfs_t *states;                               /**< Array of states */
110         rexuint_t ntrans;                               /**< Total number of transitions */
111         rexdft_t *trans;                                /**< Array of transitions, all states transitions are recorded here. Each state keeps the offset of its first transition it this array */
112         rexuint_t naccsubstates;                /**< Total number of accepting substates */
113         rexdfss_t *accsubstates;                /**< Array of accepting sub-states, all states accepting sub-states are recorded here. */
114         rexuint_t nsubstates;                   /**< Total number of substates */
115         rexdfss_t *substates;                   /**< Array of sub-states, all states sub-states are recorded here. */
116         rexuword_t reserved[64];
117 } rexdfa_t;
118
119
120 /**
121  * Definition of state types.
122  */
123 typedef enum {
124         REX_STATETYPE_NONE = 0,                 /**< There is nothing interesting about this state */
125         REX_STATETYPE_START = 1,                /**< This state is marked as starting point for the automaton */
126         REX_STATETYPE_ACCEPT = 2,               /**< This type indicates that one or more regular expressions compiled in the automaton matched. */
127         REX_STATETYPE_DEAD = 3,                 /**< The automaton is in the dead state(all transitions lead back to the same state) */
128 } rex_statetype_t;
129
130
131 #define REX_DFA_DEADSTATE (0)           /**< DFA Dead State ID, In rexdfa_t object the state at offset 0 is always the dead state  */
132 #define REX_DFA_STARTSTATE (1)          /**< DFA Start State ID, In rexdfa_t object the start state is always at offset 1  */
133
134
135 /**
136  * @def REX_DFA_STATE(__dfa__, __nstate__)
137  *
138  * Get a pointer to @ref rexdfa_t state.
139  * @param __dfa__ Pointer to @ref rexdfa_t object
140  * @param __nstate__ State ID returned from @ref REX_DFA_NEXT or @ref REX_DFA_DEADSTATE, @ref REX_DFA_STARTSTATE
141  * @return Pointer to @ref rexdfa_t
142  */
143 #define REX_DFA_STATE(__dfa__, __nstate__)                                                      (&(__dfa__)->states[__nstate__])
144
145 /**
146  * @def REX_DFA_TRANSITION(__dfa__, __nstate__, __ntrans__)
147  * Get a pointer to @ref rexdft_t transition. This macro is used internally to find
148  * a transition to the next state.
149  *
150  * @param __dfa__ Pointer to @ref rexdfa_t object
151  * @param __nstate__ State ID returned from @ref REX_DFA_NEXT or @ref REX_DFA_DEADSTATE, @ref REX_DFA_STARTSTATE
152  * @param __ntrans__ Transition offset in the array of transitions for the specified state. This parameter
153  * must be from 0 to rexdfs_t::ntrans - 1.
154  * @return Pointer to @ref rexdft_t transition
155  */
156 #define REX_DFA_TRANSITION(__dfa__, __nstate__, __ntrans__)                     (&(__dfa__)->trans[(REX_DFA_STATE(__dfa__, __nstate__)->trans) + (__ntrans__)])
157
158 /**
159  * @def REX_DFA_SUBSTATE(__dfa__, __nstate__, __nsubstate__)
160  * Get a pointer to @ref rexdfss_t sub-state. This macro would only work if the DFA
161  * is generated with its NFA sub-states.
162  *
163  * @param __dfa__ Pointer to @ref rexdfa_t object
164  * @param __nstate__ State ID returned from @ref REX_DFA_NEXT or @ref REX_DFA_STARTSTATE
165  * @param __nsubstate__ Sub-state offset in the array of sub-states for the specified state. This parameter
166  * must from 0 to rexdfs_t::nsubstates - 1.
167  * @return Pointer to @ref rexdfss_t substate.
168  */
169 #define REX_DFA_SUBSTATE(__dfa__, __nstate__, __nsubstate__)            ((__dfa__)->substates ? &(__dfa__)->substates[REX_DFA_STATE(__dfa__, __nstate__)->substates + (__nsubstate__)] : ((rexdfss_t*)0))
170
171 /**
172  * @def REX_DFA_ACCSUBSTATE(__dfa__, __nstate__, __naccsubstate__)
173  * Get a pointer to @ref rexdfss_t accepting sub-state.
174  *
175  * @param __dfa__ Pointer to @ref rexdfa_t object
176  * @param __nstate__ State ID returned from @ref REX_DFA_NEXT or @ref REX_DFA_STARTSTATE
177  * @param __naccsubstate__ Sub-state offset in the array of accepting sub-states for the specified state. This parameter
178  * must be from 0 to rexdfs_t::naccsubstates - 1.
179  * @return Pointer to @ref rexdfss_t accepting substate.
180  */
181 #define REX_DFA_ACCSUBSTATE(__dfa__, __nstate__, __naccsubstate__)      ((__dfa__)->accsubstates ? &(__dfa__)->accsubstates[REX_DFA_STATE(__dfa__, __nstate__)->accsubstates + (__naccsubstate__)] : ((rexdfss_t*)0))
182
183
184 /**
185  * @def REX_DFA_NEXT(__dfa__, __nstate__, __input__, __nextptr__)
186  *
187  * Get the next state ID in the DFA for the specified input. The macro will
188  * search through the transitions of the current state to find the next
189  * state of the DFA for the specified input. The next state will be assigned
190  * to *(__nextptr__).
191  *
192  * @param __dfa__ Pointer to @ref rexdfa_t object
193  * @param __nstate__ Current state of the DFA.
194  * @param __input__ Current input
195  * @param __nextptr__ Output the next state in here
196  * @return The next state of the DFA for the specified input is written in __nextptr__
197  */
198 #define REX_DFA_NEXT(__dfa__, __nstate__, __input__, __nextptr__) \
199                 do { \
200                         rexdft_t *t; \
201                         rexuint_t mid, min = 0, max = REX_DFA_STATE(__dfa__, __nstate__)->ntrans; \
202                         while (max > min) { \
203                                 mid = (min + max)/2; \
204                                 t = REX_DFA_TRANSITION(__dfa__, __nstate__, mid); \
205                                 if ((__input__) >= t->lowin) { \
206                                         min = mid + 1; \
207                                 } else { \
208                                         max = mid; \
209                                 } \
210                         } \
211                         t = REX_DFA_TRANSITION(__dfa__, __nstate__, min-1); \
212                         *(__nextptr__) = t->state; \
213                 } while (0)
214
215 rexdfa_t *rex_dfa_create(rexuint_t nstates, rexuint_t ntrans, rexuint_t naccsubstates, rexuint_t nsubstates);
216 void rex_dfa_destroy(rexdfa_t *dfa);
217 void rex_dfa_dumpstate(rexdfa_t *dfa, rexuint_t nstate);
218 rexdfs_t *rex_dfa_state(rexdfa_t *dfa, rexuint_t nstate);
219 rexdft_t *rex_dfa_transition(rexdfa_t *dfa, rexuint_t nstate, rexuint_t ntransition);
220 rexdfss_t *rex_dfa_substate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t nsubstate);
221 rexdfss_t *rex_dfa_accsubstate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t naccsubstate);
222 rexuint_t rex_dfa_next(rexdfa_t *dfa, rexuint_t nstate, rexchar_t input);
223
224 #ifdef __cplusplus
225 }
226 #endif
227
228
229 #endif /* _REXDFA_H_ */