diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-11 15:30:16 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-11 15:30:16 +0000 |
commit | 33c2e452d34d3334cf6b189e41b4487b85a01b50 (patch) | |
tree | 0a9df304d301bbef47e53a4d34a2da441db821c6 /src/regex/regex.c | |
parent | 086884b58e7324dd4b237f189ddd6965534ff874 (diff) | |
download | gnunet-33c2e452d34d3334cf6b189e41b4487b85a01b50.tar.gz gnunet-33c2e452d34d3334cf6b189e41b4487b85a01b50.zip |
comments
Diffstat (limited to 'src/regex/regex.c')
-rw-r--r-- | src/regex/regex.c | 116 |
1 files changed, 112 insertions, 4 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index b99be1bdd..7d943160e 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -33,16 +33,30 @@ | |||
33 | */ | 33 | */ |
34 | struct GNUNET_REGEX_Context | 34 | struct GNUNET_REGEX_Context |
35 | { | 35 | { |
36 | /** | ||
37 | * Unique state id. | ||
38 | */ | ||
36 | unsigned int state_id; | 39 | unsigned int state_id; |
40 | |||
41 | /** | ||
42 | * Unique transition id. | ||
43 | */ | ||
37 | unsigned int transition_id; | 44 | unsigned int transition_id; |
38 | 45 | ||
39 | /** | 46 | /** |
40 | * DLL of GNUNET_REGEX_Automaton's used as a stack | 47 | * DLL of GNUNET_REGEX_Automaton's used as a stack. |
41 | */ | 48 | */ |
42 | struct GNUNET_REGEX_Automaton *stack_head; | 49 | struct GNUNET_REGEX_Automaton *stack_head; |
50 | |||
51 | /** | ||
52 | * DLL of GNUNET_REGEX_Automaton's used as a stack. | ||
53 | */ | ||
43 | struct GNUNET_REGEX_Automaton *stack_tail; | 54 | struct GNUNET_REGEX_Automaton *stack_tail; |
44 | }; | 55 | }; |
45 | 56 | ||
57 | /** | ||
58 | * Type of an automaton. | ||
59 | */ | ||
46 | enum GNUNET_REGEX_automaton_type | 60 | enum GNUNET_REGEX_automaton_type |
47 | { | 61 | { |
48 | NFA, | 62 | NFA, |
@@ -50,20 +64,51 @@ enum GNUNET_REGEX_automaton_type | |||
50 | }; | 64 | }; |
51 | 65 | ||
52 | /** | 66 | /** |
53 | * Automaton representation | 67 | * Automaton representation. |
54 | */ | 68 | */ |
55 | struct GNUNET_REGEX_Automaton | 69 | struct GNUNET_REGEX_Automaton |
56 | { | 70 | { |
71 | /** | ||
72 | * This is a linked list. | ||
73 | */ | ||
57 | struct GNUNET_REGEX_Automaton *prev; | 74 | struct GNUNET_REGEX_Automaton *prev; |
75 | |||
76 | /** | ||
77 | * This is a linked list. | ||
78 | */ | ||
58 | struct GNUNET_REGEX_Automaton *next; | 79 | struct GNUNET_REGEX_Automaton *next; |
59 | 80 | ||
81 | /** | ||
82 | * First state of the automaton. This is mainly | ||
83 | * used for constructing an NFA, where each NFA | ||
84 | * itself consists of one or more NFAs linked | ||
85 | * together. | ||
86 | */ | ||
60 | struct State *start; | 87 | struct State *start; |
88 | |||
89 | /** | ||
90 | * End state of the automaton. | ||
91 | */ | ||
61 | struct State *end; | 92 | struct State *end; |
62 | 93 | ||
94 | /** | ||
95 | * Number of states in the automaton. | ||
96 | */ | ||
63 | unsigned int state_count; | 97 | unsigned int state_count; |
98 | |||
99 | /** | ||
100 | * DLL of states. | ||
101 | */ | ||
64 | struct State *states_head; | 102 | struct State *states_head; |
103 | |||
104 | /** | ||
105 | * DLL of states | ||
106 | */ | ||
65 | struct State *states_tail; | 107 | struct State *states_tail; |
66 | 108 | ||
109 | /** | ||
110 | * Type of the automaton. | ||
111 | */ | ||
67 | enum GNUNET_REGEX_automaton_type type; | 112 | enum GNUNET_REGEX_automaton_type type; |
68 | }; | 113 | }; |
69 | 114 | ||
@@ -72,18 +117,58 @@ struct GNUNET_REGEX_Automaton | |||
72 | */ | 117 | */ |
73 | struct State | 118 | struct State |
74 | { | 119 | { |
120 | /** | ||
121 | * This is a linked list. | ||
122 | */ | ||
75 | struct State *prev; | 123 | struct State *prev; |
124 | |||
125 | /** | ||
126 | * This is a linked list. | ||
127 | */ | ||
76 | struct State *next; | 128 | struct State *next; |
77 | 129 | ||
130 | /** | ||
131 | * Unique state id. | ||
132 | */ | ||
78 | unsigned int id; | 133 | unsigned int id; |
134 | |||
135 | /** | ||
136 | * If this is an accepting state or not. | ||
137 | */ | ||
79 | int accepting; | 138 | int accepting; |
139 | |||
140 | /** | ||
141 | * Marking of the state. This is used for marking all visited | ||
142 | * states when traversing all states of an automaton and for | ||
143 | * cases where the state id cannot be used (dfa minimization). | ||
144 | */ | ||
80 | int marked; | 145 | int marked; |
146 | |||
147 | /** | ||
148 | * Human readable name of the automaton. Used for debugging | ||
149 | * and graph creation. | ||
150 | */ | ||
81 | char *name; | 151 | char *name; |
82 | 152 | ||
153 | /** | ||
154 | * Number of transitions from this state to other states. | ||
155 | */ | ||
83 | unsigned int transition_count; | 156 | unsigned int transition_count; |
157 | |||
158 | /** | ||
159 | * DLL of transitions. | ||
160 | */ | ||
84 | struct Transition *transitions_head; | 161 | struct Transition *transitions_head; |
162 | |||
163 | /** | ||
164 | * DLL of transitions. | ||
165 | */ | ||
85 | struct Transition *transitions_tail; | 166 | struct Transition *transitions_tail; |
86 | 167 | ||
168 | /** | ||
169 | * Set of states on which this state is based on. Used when | ||
170 | * creating a DFA out of several NFA states. | ||
171 | */ | ||
87 | struct StateSet *nfa_set; | 172 | struct StateSet *nfa_set; |
88 | }; | 173 | }; |
89 | 174 | ||
@@ -93,23 +178,46 @@ struct State | |||
93 | */ | 178 | */ |
94 | struct Transition | 179 | struct Transition |
95 | { | 180 | { |
181 | /** | ||
182 | * This is a linked list. | ||
183 | */ | ||
96 | struct Transition *prev; | 184 | struct Transition *prev; |
185 | |||
186 | /** | ||
187 | * This is a linked list. | ||
188 | */ | ||
97 | struct Transition *next; | 189 | struct Transition *next; |
98 | 190 | ||
191 | /** | ||
192 | * Unique id of this transition. | ||
193 | */ | ||
99 | unsigned int id; | 194 | unsigned int id; |
195 | |||
196 | /** | ||
197 | * Literal for this transition. This is basically the edge label for | ||
198 | * the graph. | ||
199 | */ | ||
100 | char literal; | 200 | char literal; |
201 | |||
202 | /** | ||
203 | * State to which this transition leads. | ||
204 | */ | ||
101 | struct State *state; | 205 | struct State *state; |
102 | }; | 206 | }; |
103 | 207 | ||
104 | /** | 208 | /** |
105 | * Set of states | 209 | * Set of states. |
106 | */ | 210 | */ |
107 | struct StateSet | 211 | struct StateSet |
108 | { | 212 | { |
109 | /** | 213 | /** |
110 | * Array of states | 214 | * Array of states. |
111 | */ | 215 | */ |
112 | struct State **states; | 216 | struct State **states; |
217 | |||
218 | /** | ||
219 | * Length of the 'states' array. | ||
220 | */ | ||
113 | unsigned int len; | 221 | unsigned int len; |
114 | }; | 222 | }; |
115 | 223 | ||