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