diff options
Diffstat (limited to 'src/regex/regex_internal.c')
-rw-r--r-- | src/regex/regex_internal.c | 3107 |
1 files changed, 1555 insertions, 1552 deletions
diff --git a/src/regex/regex_internal.c b/src/regex/regex_internal.c index 55d16129f..34f0d9c42 100644 --- a/src/regex/regex_internal.c +++ b/src/regex/regex_internal.c | |||
@@ -16,7 +16,7 @@ | |||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | 17 | ||
18 | SPDX-License-Identifier: AGPL3.0-or-later | 18 | SPDX-License-Identifier: AGPL3.0-or-later |
19 | */ | 19 | */ |
20 | /** | 20 | /** |
21 | * @file src/regex/regex_internal.c | 21 | * @file src/regex/regex_internal.c |
22 | * @brief library to create Deterministic Finite Automatons (DFAs) from regular | 22 | * @brief library to create Deterministic Finite Automatons (DFAs) from regular |
@@ -39,8 +39,7 @@ | |||
39 | /** | 39 | /** |
40 | * Set of states using MDLL API. | 40 | * Set of states using MDLL API. |
41 | */ | 41 | */ |
42 | struct REGEX_INTERNAL_StateSet_MDLL | 42 | struct REGEX_INTERNAL_StateSet_MDLL { |
43 | { | ||
44 | /** | 43 | /** |
45 | * MDLL of states. | 44 | * MDLL of states. |
46 | */ | 45 | */ |
@@ -65,11 +64,11 @@ struct REGEX_INTERNAL_StateSet_MDLL | |||
65 | * @param state state to be appended | 64 | * @param state state to be appended |
66 | */ | 65 | */ |
67 | static void | 66 | static void |
68 | state_set_append (struct REGEX_INTERNAL_StateSet *set, | 67 | state_set_append(struct REGEX_INTERNAL_StateSet *set, |
69 | struct REGEX_INTERNAL_State *state) | 68 | struct REGEX_INTERNAL_State *state) |
70 | { | 69 | { |
71 | if (set->off == set->size) | 70 | if (set->off == set->size) |
72 | GNUNET_array_grow (set->states, set->size, set->size * 2 + 4); | 71 | GNUNET_array_grow(set->states, set->size, set->size * 2 + 4); |
73 | set->states[set->off++] = state; | 72 | set->states[set->off++] = state; |
74 | } | 73 | } |
75 | 74 | ||
@@ -83,14 +82,14 @@ state_set_append (struct REGEX_INTERNAL_StateSet *set, | |||
83 | * @return 0 if the strings are the same or both NULL, 1 or -1 if not. | 82 | * @return 0 if the strings are the same or both NULL, 1 or -1 if not. |
84 | */ | 83 | */ |
85 | static int | 84 | static int |
86 | nullstrcmp (const char *str1, const char *str2) | 85 | nullstrcmp(const char *str1, const char *str2) |
87 | { | 86 | { |
88 | if ((NULL == str1) != (NULL == str2)) | 87 | if ((NULL == str1) != (NULL == str2)) |
89 | return -1; | 88 | return -1; |
90 | if ((NULL == str1) && (NULL == str2)) | 89 | if ((NULL == str1) && (NULL == str2)) |
91 | return 0; | 90 | return 0; |
92 | 91 | ||
93 | return strcmp (str1, str2); | 92 | return strcmp(str1, str2); |
94 | } | 93 | } |
95 | 94 | ||
96 | 95 | ||
@@ -104,40 +103,40 @@ nullstrcmp (const char *str1, const char *str2) | |||
104 | * @param to_state state to where the transition should point to | 103 | * @param to_state state to where the transition should point to |
105 | */ | 104 | */ |
106 | static void | 105 | static void |
107 | state_add_transition (struct REGEX_INTERNAL_Context *ctx, | 106 | state_add_transition(struct REGEX_INTERNAL_Context *ctx, |
108 | struct REGEX_INTERNAL_State *from_state, | 107 | struct REGEX_INTERNAL_State *from_state, |
109 | const char *label, | 108 | const char *label, |
110 | struct REGEX_INTERNAL_State *to_state) | 109 | struct REGEX_INTERNAL_State *to_state) |
111 | { | 110 | { |
112 | struct REGEX_INTERNAL_Transition *t; | 111 | struct REGEX_INTERNAL_Transition *t; |
113 | struct REGEX_INTERNAL_Transition *oth; | 112 | struct REGEX_INTERNAL_Transition *oth; |
114 | 113 | ||
115 | if (NULL == from_state) | 114 | if (NULL == from_state) |
116 | { | 115 | { |
117 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n"); | 116 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n"); |
118 | return; | 117 | return; |
119 | } | 118 | } |
120 | 119 | ||
121 | /* Do not add duplicate state transitions */ | 120 | /* Do not add duplicate state transitions */ |
122 | for (t = from_state->transitions_head; NULL != t; t = t->next) | 121 | for (t = from_state->transitions_head; NULL != t; t = t->next) |
123 | { | 122 | { |
124 | if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) && | 123 | if (t->to_state == to_state && 0 == nullstrcmp(t->label, label) && |
125 | t->from_state == from_state) | 124 | t->from_state == from_state) |
126 | return; | 125 | return; |
127 | } | 126 | } |
128 | 127 | ||
129 | /* sort transitions by label */ | 128 | /* sort transitions by label */ |
130 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) | 129 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) |
131 | { | 130 | { |
132 | if (0 < nullstrcmp (oth->label, label)) | 131 | if (0 < nullstrcmp(oth->label, label)) |
133 | break; | 132 | break; |
134 | } | 133 | } |
135 | 134 | ||
136 | t = GNUNET_new (struct REGEX_INTERNAL_Transition); | 135 | t = GNUNET_new(struct REGEX_INTERNAL_Transition); |
137 | if (NULL != ctx) | 136 | if (NULL != ctx) |
138 | t->id = ctx->transition_id++; | 137 | t->id = ctx->transition_id++; |
139 | if (NULL != label) | 138 | if (NULL != label) |
140 | t->label = GNUNET_strdup (label); | 139 | t->label = GNUNET_strdup(label); |
141 | else | 140 | else |
142 | t->label = NULL; | 141 | t->label = NULL; |
143 | t->to_state = to_state; | 142 | t->to_state = to_state; |
@@ -145,10 +144,10 @@ state_add_transition (struct REGEX_INTERNAL_Context *ctx, | |||
145 | 144 | ||
146 | /* Add outgoing transition to 'from_state' */ | 145 | /* Add outgoing transition to 'from_state' */ |
147 | from_state->transition_count++; | 146 | from_state->transition_count++; |
148 | GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head, | 147 | GNUNET_CONTAINER_DLL_insert_before(from_state->transitions_head, |
149 | from_state->transitions_tail, | 148 | from_state->transitions_tail, |
150 | oth, | 149 | oth, |
151 | t); | 150 | t); |
152 | } | 151 | } |
153 | 152 | ||
154 | 153 | ||
@@ -159,8 +158,8 @@ state_add_transition (struct REGEX_INTERNAL_Context *ctx, | |||
159 | * @param transition transition that should be removed from state 'state'. | 158 | * @param transition transition that should be removed from state 'state'. |
160 | */ | 159 | */ |
161 | static void | 160 | static void |
162 | state_remove_transition (struct REGEX_INTERNAL_State *state, | 161 | state_remove_transition(struct REGEX_INTERNAL_State *state, |
163 | struct REGEX_INTERNAL_Transition *transition) | 162 | struct REGEX_INTERNAL_Transition *transition) |
164 | { | 163 | { |
165 | if (NULL == state || NULL == transition) | 164 | if (NULL == state || NULL == transition) |
166 | return; | 165 | return; |
@@ -168,14 +167,14 @@ state_remove_transition (struct REGEX_INTERNAL_State *state, | |||
168 | if (transition->from_state != state) | 167 | if (transition->from_state != state) |
169 | return; | 168 | return; |
170 | 169 | ||
171 | GNUNET_free_non_null (transition->label); | 170 | GNUNET_free_non_null(transition->label); |
172 | 171 | ||
173 | state->transition_count--; | 172 | state->transition_count--; |
174 | GNUNET_CONTAINER_DLL_remove (state->transitions_head, | 173 | GNUNET_CONTAINER_DLL_remove(state->transitions_head, |
175 | state->transitions_tail, | 174 | state->transitions_tail, |
176 | transition); | 175 | transition); |
177 | 176 | ||
178 | GNUNET_free (transition); | 177 | GNUNET_free(transition); |
179 | } | 178 | } |
180 | 179 | ||
181 | 180 | ||
@@ -190,10 +189,10 @@ state_remove_transition (struct REGEX_INTERNAL_State *state, | |||
190 | * less than, equal to, or greater than the second. | 189 | * less than, equal to, or greater than the second. |
191 | */ | 190 | */ |
192 | static int | 191 | static int |
193 | state_compare (const void *a, const void *b) | 192 | state_compare(const void *a, const void *b) |
194 | { | 193 | { |
195 | struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **) a; | 194 | struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **)a; |
196 | struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **) b; | 195 | struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **)b; |
197 | 196 | ||
198 | return (*s1)->id - (*s2)->id; | 197 | return (*s1)->id - (*s2)->id; |
199 | } | 198 | } |
@@ -209,7 +208,7 @@ state_compare (const void *a, const void *b) | |||
209 | * @return number of edges. | 208 | * @return number of edges. |
210 | */ | 209 | */ |
211 | static unsigned int | 210 | static unsigned int |
212 | state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges) | 211 | state_get_edges(struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges) |
213 | { | 212 | { |
214 | struct REGEX_INTERNAL_Transition *t; | 213 | struct REGEX_INTERNAL_Transition *t; |
215 | unsigned int count; | 214 | unsigned int count; |
@@ -220,14 +219,14 @@ state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges) | |||
220 | count = 0; | 219 | count = 0; |
221 | 220 | ||
222 | for (t = s->transitions_head; NULL != t; t = t->next) | 221 | for (t = s->transitions_head; NULL != t; t = t->next) |
223 | { | ||
224 | if (NULL != t->to_state) | ||
225 | { | 222 | { |
226 | edges[count].label = t->label; | 223 | if (NULL != t->to_state) |
227 | edges[count].destination = t->to_state->hash; | 224 | { |
228 | count++; | 225 | edges[count].label = t->label; |
226 | edges[count].destination = t->to_state->hash; | ||
227 | count++; | ||
228 | } | ||
229 | } | 229 | } |
230 | } | ||
231 | return count; | 230 | return count; |
232 | } | 231 | } |
233 | 232 | ||
@@ -241,8 +240,8 @@ state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges) | |||
241 | * @return 0 if the sets are equal, otherwise non-zero | 240 | * @return 0 if the sets are equal, otherwise non-zero |
242 | */ | 241 | */ |
243 | static int | 242 | static int |
244 | state_set_compare (struct REGEX_INTERNAL_StateSet *sset1, | 243 | state_set_compare(struct REGEX_INTERNAL_StateSet *sset1, |
245 | struct REGEX_INTERNAL_StateSet *sset2) | 244 | struct REGEX_INTERNAL_StateSet *sset2) |
246 | { | 245 | { |
247 | int result; | 246 | int result; |
248 | unsigned int i; | 247 | unsigned int i; |
@@ -256,7 +255,7 @@ state_set_compare (struct REGEX_INTERNAL_StateSet *sset1, | |||
256 | if (result > 0) | 255 | if (result > 0) |
257 | return 1; | 256 | return 1; |
258 | for (i = 0; i < sset1->off; i++) | 257 | for (i = 0; i < sset1->off; i++) |
259 | if (0 != (result = state_compare (&sset1->states[i], &sset2->states[i]))) | 258 | if (0 != (result = state_compare(&sset1->states[i], &sset2->states[i]))) |
260 | break; | 259 | break; |
261 | return result; | 260 | return result; |
262 | } | 261 | } |
@@ -268,9 +267,9 @@ state_set_compare (struct REGEX_INTERNAL_StateSet *sset1, | |||
268 | * @param set set to be cleared | 267 | * @param set set to be cleared |
269 | */ | 268 | */ |
270 | static void | 269 | static void |
271 | state_set_clear (struct REGEX_INTERNAL_StateSet *set) | 270 | state_set_clear(struct REGEX_INTERNAL_StateSet *set) |
272 | { | 271 | { |
273 | GNUNET_array_grow (set->states, set->size, 0); | 272 | GNUNET_array_grow(set->states, set->size, 0); |
274 | set->off = 0; | 273 | set->off = 0; |
275 | } | 274 | } |
276 | 275 | ||
@@ -282,7 +281,7 @@ state_set_clear (struct REGEX_INTERNAL_StateSet *set) | |||
282 | * @param a automaton to be cleared | 281 | * @param a automaton to be cleared |
283 | */ | 282 | */ |
284 | static void | 283 | static void |
285 | automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a) | 284 | automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a) |
286 | { | 285 | { |
287 | if (NULL == a) | 286 | if (NULL == a) |
288 | return; | 287 | return; |
@@ -292,7 +291,7 @@ automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a) | |||
292 | a->states_head = NULL; | 291 | a->states_head = NULL; |
293 | a->states_tail = NULL; | 292 | a->states_tail = NULL; |
294 | a->state_count = 0; | 293 | a->state_count = 0; |
295 | GNUNET_free (a); | 294 | GNUNET_free(a); |
296 | } | 295 | } |
297 | 296 | ||
298 | 297 | ||
@@ -302,7 +301,7 @@ automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a) | |||
302 | * @param s state that should be destroyed | 301 | * @param s state that should be destroyed |
303 | */ | 302 | */ |
304 | static void | 303 | static void |
305 | automaton_destroy_state (struct REGEX_INTERNAL_State *s) | 304 | automaton_destroy_state(struct REGEX_INTERNAL_State *s) |
306 | { | 305 | { |
307 | struct REGEX_INTERNAL_Transition *t; | 306 | struct REGEX_INTERNAL_Transition *t; |
308 | struct REGEX_INTERNAL_Transition *next_t; | 307 | struct REGEX_INTERNAL_Transition *next_t; |
@@ -310,16 +309,16 @@ automaton_destroy_state (struct REGEX_INTERNAL_State *s) | |||
310 | if (NULL == s) | 309 | if (NULL == s) |
311 | return; | 310 | return; |
312 | 311 | ||
313 | GNUNET_free_non_null (s->name); | 312 | GNUNET_free_non_null(s->name); |
314 | GNUNET_free_non_null (s->proof); | 313 | GNUNET_free_non_null(s->proof); |
315 | state_set_clear (&s->nfa_set); | 314 | state_set_clear(&s->nfa_set); |
316 | for (t = s->transitions_head; NULL != t; t = next_t) | 315 | for (t = s->transitions_head; NULL != t; t = next_t) |
317 | { | 316 | { |
318 | next_t = t->next; | 317 | next_t = t->next; |
319 | state_remove_transition (s, t); | 318 | state_remove_transition(s, t); |
320 | } | 319 | } |
321 | 320 | ||
322 | GNUNET_free (s); | 321 | GNUNET_free(s); |
323 | } | 322 | } |
324 | 323 | ||
325 | 324 | ||
@@ -332,8 +331,8 @@ automaton_destroy_state (struct REGEX_INTERNAL_State *s) | |||
332 | * @param s state to remove | 331 | * @param s state to remove |
333 | */ | 332 | */ |
334 | static void | 333 | static void |
335 | automaton_remove_state (struct REGEX_INTERNAL_Automaton *a, | 334 | automaton_remove_state(struct REGEX_INTERNAL_Automaton *a, |
336 | struct REGEX_INTERNAL_State *s) | 335 | struct REGEX_INTERNAL_State *s) |
337 | { | 336 | { |
338 | struct REGEX_INTERNAL_State *s_check; | 337 | struct REGEX_INTERNAL_State *s_check; |
339 | struct REGEX_INTERNAL_Transition *t_check; | 338 | struct REGEX_INTERNAL_Transition *t_check; |
@@ -344,21 +343,21 @@ automaton_remove_state (struct REGEX_INTERNAL_Automaton *a, | |||
344 | 343 | ||
345 | /* remove all transitions leading to this state */ | 344 | /* remove all transitions leading to this state */ |
346 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 345 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
347 | { | ||
348 | for (t_check = s_check->transitions_head; NULL != t_check; | ||
349 | t_check = t_check_next) | ||
350 | { | 346 | { |
351 | t_check_next = t_check->next; | 347 | for (t_check = s_check->transitions_head; NULL != t_check; |
352 | if (t_check->to_state == s) | 348 | t_check = t_check_next) |
353 | state_remove_transition (s_check, t_check); | 349 | { |
350 | t_check_next = t_check->next; | ||
351 | if (t_check->to_state == s) | ||
352 | state_remove_transition(s_check, t_check); | ||
353 | } | ||
354 | } | 354 | } |
355 | } | ||
356 | 355 | ||
357 | /* remove state */ | 356 | /* remove state */ |
358 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | 357 | GNUNET_CONTAINER_DLL_remove(a->states_head, a->states_tail, s); |
359 | a->state_count--; | 358 | a->state_count--; |
360 | 359 | ||
361 | automaton_destroy_state (s); | 360 | automaton_destroy_state(s); |
362 | } | 361 | } |
363 | 362 | ||
364 | 363 | ||
@@ -372,10 +371,10 @@ automaton_remove_state (struct REGEX_INTERNAL_Automaton *a, | |||
372 | * @param s2 second state, will be destroyed | 371 | * @param s2 second state, will be destroyed |
373 | */ | 372 | */ |
374 | static void | 373 | static void |
375 | automaton_merge_states (struct REGEX_INTERNAL_Context *ctx, | 374 | automaton_merge_states(struct REGEX_INTERNAL_Context *ctx, |
376 | struct REGEX_INTERNAL_Automaton *a, | 375 | struct REGEX_INTERNAL_Automaton *a, |
377 | struct REGEX_INTERNAL_State *s1, | 376 | struct REGEX_INTERNAL_State *s1, |
378 | struct REGEX_INTERNAL_State *s2) | 377 | struct REGEX_INTERNAL_State *s2) |
379 | { | 378 | { |
380 | struct REGEX_INTERNAL_State *s_check; | 379 | struct REGEX_INTERNAL_State *s_check; |
381 | struct REGEX_INTERNAL_Transition *t_check; | 380 | struct REGEX_INTERNAL_Transition *t_check; |
@@ -389,47 +388,47 @@ automaton_merge_states (struct REGEX_INTERNAL_Context *ctx, | |||
389 | /* 1. Make all transitions pointing to s2 point to s1, unless this transition | 388 | /* 1. Make all transitions pointing to s2 point to s1, unless this transition |
390 | * does not already exists, if it already exists remove transition. */ | 389 | * does not already exists, if it already exists remove transition. */ |
391 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 390 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
392 | { | ||
393 | for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next) | ||
394 | { | 391 | { |
395 | t_next = t_check->next; | 392 | for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next) |
396 | |||
397 | if (s2 == t_check->to_state) | ||
398 | { | ||
399 | is_dup = GNUNET_NO; | ||
400 | for (t = t_check->from_state->transitions_head; NULL != t; t = t->next) | ||
401 | { | 393 | { |
402 | if (t->to_state == s1 && 0 == strcmp (t_check->label, t->label)) | 394 | t_next = t_check->next; |
403 | is_dup = GNUNET_YES; | 395 | |
396 | if (s2 == t_check->to_state) | ||
397 | { | ||
398 | is_dup = GNUNET_NO; | ||
399 | for (t = t_check->from_state->transitions_head; NULL != t; t = t->next) | ||
400 | { | ||
401 | if (t->to_state == s1 && 0 == strcmp(t_check->label, t->label)) | ||
402 | is_dup = GNUNET_YES; | ||
403 | } | ||
404 | if (GNUNET_NO == is_dup) | ||
405 | t_check->to_state = s1; | ||
406 | else | ||
407 | state_remove_transition(t_check->from_state, t_check); | ||
408 | } | ||
404 | } | 409 | } |
405 | if (GNUNET_NO == is_dup) | ||
406 | t_check->to_state = s1; | ||
407 | else | ||
408 | state_remove_transition (t_check->from_state, t_check); | ||
409 | } | ||
410 | } | 410 | } |
411 | } | ||
412 | 411 | ||
413 | /* 2. Add all transitions from s2 to sX to s1 */ | 412 | /* 2. Add all transitions from s2 to sX to s1 */ |
414 | for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next) | 413 | for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next) |
415 | { | 414 | { |
416 | if (t_check->to_state != s1) | 415 | if (t_check->to_state != s1) |
417 | state_add_transition (ctx, s1, t_check->label, t_check->to_state); | 416 | state_add_transition(ctx, s1, t_check->label, t_check->to_state); |
418 | } | 417 | } |
419 | 418 | ||
420 | /* 3. Rename s1 to {s1,s2} */ | 419 | /* 3. Rename s1 to {s1,s2} */ |
421 | #if REGEX_DEBUG_DFA | 420 | #if REGEX_DEBUG_DFA |
422 | char *new_name; | 421 | char *new_name; |
423 | 422 | ||
424 | new_name = s1->name; | 423 | new_name = s1->name; |
425 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); | 424 | GNUNET_asprintf(&s1->name, "{%s,%s}", new_name, s2->name); |
426 | GNUNET_free (new_name); | 425 | GNUNET_free(new_name); |
427 | #endif | 426 | #endif |
428 | 427 | ||
429 | /* remove state */ | 428 | /* remove state */ |
430 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s2); | 429 | GNUNET_CONTAINER_DLL_remove(a->states_head, a->states_tail, s2); |
431 | a->state_count--; | 430 | a->state_count--; |
432 | automaton_destroy_state (s2); | 431 | automaton_destroy_state(s2); |
433 | } | 432 | } |
434 | 433 | ||
435 | 434 | ||
@@ -441,10 +440,10 @@ automaton_merge_states (struct REGEX_INTERNAL_Context *ctx, | |||
441 | * @param s state that should be added | 440 | * @param s state that should be added |
442 | */ | 441 | */ |
443 | static void | 442 | static void |
444 | automaton_add_state (struct REGEX_INTERNAL_Automaton *a, | 443 | automaton_add_state(struct REGEX_INTERNAL_Automaton *a, |
445 | struct REGEX_INTERNAL_State *s) | 444 | struct REGEX_INTERNAL_State *s) |
446 | { | 445 | { |
447 | GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s); | 446 | GNUNET_CONTAINER_DLL_insert(a->states_head, a->states_tail, s); |
448 | a->state_count++; | 447 | a->state_count++; |
449 | } | 448 | } |
450 | 449 | ||
@@ -464,13 +463,13 @@ automaton_add_state (struct REGEX_INTERNAL_Automaton *a, | |||
464 | * @param action_cls closure for action. | 463 | * @param action_cls closure for action. |
465 | */ | 464 | */ |
466 | static void | 465 | static void |
467 | automaton_state_traverse (struct REGEX_INTERNAL_State *s, | 466 | automaton_state_traverse(struct REGEX_INTERNAL_State *s, |
468 | int *marks, | 467 | int *marks, |
469 | unsigned int *count, | 468 | unsigned int *count, |
470 | REGEX_INTERNAL_traverse_check check, | 469 | REGEX_INTERNAL_traverse_check check, |
471 | void *check_cls, | 470 | void *check_cls, |
472 | REGEX_INTERNAL_traverse_action action, | 471 | REGEX_INTERNAL_traverse_action action, |
473 | void *action_cls) | 472 | void *action_cls) |
474 | { | 473 | { |
475 | struct REGEX_INTERNAL_Transition *t; | 474 | struct REGEX_INTERNAL_Transition *t; |
476 | 475 | ||
@@ -480,24 +479,24 @@ automaton_state_traverse (struct REGEX_INTERNAL_State *s, | |||
480 | marks[s->traversal_id] = GNUNET_YES; | 479 | marks[s->traversal_id] = GNUNET_YES; |
481 | 480 | ||
482 | if (NULL != action) | 481 | if (NULL != action) |
483 | action (action_cls, *count, s); | 482 | action(action_cls, *count, s); |
484 | 483 | ||
485 | (*count)++; | 484 | (*count)++; |
486 | 485 | ||
487 | for (t = s->transitions_head; NULL != t; t = t->next) | 486 | for (t = s->transitions_head; NULL != t; t = t->next) |
488 | { | ||
489 | if (NULL == check || | ||
490 | (NULL != check && GNUNET_YES == check (check_cls, s, t))) | ||
491 | { | 487 | { |
492 | automaton_state_traverse (t->to_state, | 488 | if (NULL == check || |
493 | marks, | 489 | (NULL != check && GNUNET_YES == check(check_cls, s, t))) |
494 | count, | 490 | { |
495 | check, | 491 | automaton_state_traverse(t->to_state, |
496 | check_cls, | 492 | marks, |
497 | action, | 493 | count, |
498 | action_cls); | 494 | check, |
495 | check_cls, | ||
496 | action, | ||
497 | action_cls); | ||
498 | } | ||
499 | } | 499 | } |
500 | } | ||
501 | } | 500 | } |
502 | 501 | ||
503 | 502 | ||
@@ -515,12 +514,12 @@ automaton_state_traverse (struct REGEX_INTERNAL_State *s, | |||
515 | * @param action_cls closure for @a action | 514 | * @param action_cls closure for @a action |
516 | */ | 515 | */ |
517 | void | 516 | void |
518 | REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a, | 517 | REGEX_INTERNAL_automaton_traverse(const struct REGEX_INTERNAL_Automaton *a, |
519 | struct REGEX_INTERNAL_State *start, | 518 | struct REGEX_INTERNAL_State *start, |
520 | REGEX_INTERNAL_traverse_check check, | 519 | REGEX_INTERNAL_traverse_check check, |
521 | void *check_cls, | 520 | void *check_cls, |
522 | REGEX_INTERNAL_traverse_action action, | 521 | REGEX_INTERNAL_traverse_action action, |
523 | void *action_cls) | 522 | void *action_cls) |
524 | { | 523 | { |
525 | unsigned int count; | 524 | unsigned int count; |
526 | struct REGEX_INTERNAL_State *s; | 525 | struct REGEX_INTERNAL_State *s; |
@@ -532,10 +531,10 @@ REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a, | |||
532 | 531 | ||
533 | for (count = 0, s = a->states_head; NULL != s && count < a->state_count; | 532 | for (count = 0, s = a->states_head; NULL != s && count < a->state_count; |
534 | s = s->next, count++) | 533 | s = s->next, count++) |
535 | { | 534 | { |
536 | s->traversal_id = count; | 535 | s->traversal_id = count; |
537 | marks[s->traversal_id] = GNUNET_NO; | 536 | marks[s->traversal_id] = GNUNET_NO; |
538 | } | 537 | } |
539 | 538 | ||
540 | count = 0; | 539 | count = 0; |
541 | 540 | ||
@@ -544,21 +543,20 @@ REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a, | |||
544 | else | 543 | else |
545 | s = start; | 544 | s = start; |
546 | 545 | ||
547 | automaton_state_traverse (s, | 546 | automaton_state_traverse(s, |
548 | marks, | 547 | marks, |
549 | &count, | 548 | &count, |
550 | check, | 549 | check, |
551 | check_cls, | 550 | check_cls, |
552 | action, | 551 | action, |
553 | action_cls); | 552 | action_cls); |
554 | } | 553 | } |
555 | 554 | ||
556 | 555 | ||
557 | /** | 556 | /** |
558 | * String container for faster string operations. | 557 | * String container for faster string operations. |
559 | */ | 558 | */ |
560 | struct StringBuffer | 559 | struct StringBuffer { |
561 | { | ||
562 | /** | 560 | /** |
563 | * Buffer holding the string (may start in the middle!); | 561 | * Buffer holding the string (may start in the middle!); |
564 | * NOT 0-terminated! | 562 | * NOT 0-terminated! |
@@ -607,7 +605,7 @@ struct StringBuffer | |||
607 | * @return 0 if the strings are the same or both NULL, 1 or -1 if not. | 605 | * @return 0 if the strings are the same or both NULL, 1 or -1 if not. |
608 | */ | 606 | */ |
609 | static int | 607 | static int |
610 | sb_nullstrcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) | 608 | sb_nullstrcmp(const struct StringBuffer *s1, const struct StringBuffer *s2) |
611 | { | 609 | { |
612 | if ((GNUNET_YES == s1->null_flag) && (GNUNET_YES == s2->null_flag)) | 610 | if ((GNUNET_YES == s1->null_flag) && (GNUNET_YES == s2->null_flag)) |
613 | return 0; | 611 | return 0; |
@@ -617,7 +615,7 @@ sb_nullstrcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) | |||
617 | return -1; | 615 | return -1; |
618 | if (0 == s1->slen) | 616 | if (0 == s1->slen) |
619 | return 0; | 617 | return 0; |
620 | return memcmp (s1->sbuf, s2->sbuf, s1->slen); | 618 | return memcmp(s1->sbuf, s2->sbuf, s1->slen); |
621 | } | 619 | } |
622 | 620 | ||
623 | 621 | ||
@@ -630,13 +628,13 @@ sb_nullstrcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) | |||
630 | * @return 0 if the strings are the same, 1 or -1 if not. | 628 | * @return 0 if the strings are the same, 1 or -1 if not. |
631 | */ | 629 | */ |
632 | static int | 630 | static int |
633 | sb_strcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) | 631 | sb_strcmp(const struct StringBuffer *s1, const struct StringBuffer *s2) |
634 | { | 632 | { |
635 | if (s1->slen != s2->slen) | 633 | if (s1->slen != s2->slen) |
636 | return -1; | 634 | return -1; |
637 | if (0 == s1->slen) | 635 | if (0 == s1->slen) |
638 | return 0; | 636 | return 0; |
639 | return memcmp (s1->sbuf, s2->sbuf, s1->slen); | 637 | return memcmp(s1->sbuf, s2->sbuf, s1->slen); |
640 | } | 638 | } |
641 | 639 | ||
642 | 640 | ||
@@ -648,17 +646,17 @@ sb_strcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) | |||
648 | * @param nlen target length for the buffer, must be at least ret->slen | 646 | * @param nlen target length for the buffer, must be at least ret->slen |
649 | */ | 647 | */ |
650 | static void | 648 | static void |
651 | sb_realloc (struct StringBuffer *ret, size_t nlen) | 649 | sb_realloc(struct StringBuffer *ret, size_t nlen) |
652 | { | 650 | { |
653 | char *old; | 651 | char *old; |
654 | 652 | ||
655 | GNUNET_assert (nlen >= ret->slen); | 653 | GNUNET_assert(nlen >= ret->slen); |
656 | old = ret->abuf; | 654 | old = ret->abuf; |
657 | ret->abuf = GNUNET_malloc (nlen); | 655 | ret->abuf = GNUNET_malloc(nlen); |
658 | ret->blen = nlen; | 656 | ret->blen = nlen; |
659 | GNUNET_memcpy (ret->abuf, ret->sbuf, ret->slen); | 657 | GNUNET_memcpy(ret->abuf, ret->sbuf, ret->slen); |
660 | ret->sbuf = ret->abuf; | 658 | ret->sbuf = ret->abuf; |
661 | GNUNET_free_non_null (old); | 659 | GNUNET_free_non_null(old); |
662 | } | 660 | } |
663 | 661 | ||
664 | 662 | ||
@@ -669,14 +667,14 @@ sb_realloc (struct StringBuffer *ret, size_t nlen) | |||
669 | * @param sarg string to append | 667 | * @param sarg string to append |
670 | */ | 668 | */ |
671 | static void | 669 | static void |
672 | sb_append (struct StringBuffer *ret, const struct StringBuffer *sarg) | 670 | sb_append(struct StringBuffer *ret, const struct StringBuffer *sarg) |
673 | { | 671 | { |
674 | if (GNUNET_YES == ret->null_flag) | 672 | if (GNUNET_YES == ret->null_flag) |
675 | ret->slen = 0; | 673 | ret->slen = 0; |
676 | ret->null_flag = GNUNET_NO; | 674 | ret->null_flag = GNUNET_NO; |
677 | if (ret->blen < sarg->slen + ret->slen) | 675 | if (ret->blen < sarg->slen + ret->slen) |
678 | sb_realloc (ret, ret->blen + sarg->slen + 128); | 676 | sb_realloc(ret, ret->blen + sarg->slen + 128); |
679 | GNUNET_memcpy (&ret->sbuf[ret->slen], sarg->sbuf, sarg->slen); | 677 | GNUNET_memcpy(&ret->sbuf[ret->slen], sarg->sbuf, sarg->slen); |
680 | ret->slen += sarg->slen; | 678 | ret->slen += sarg->slen; |
681 | } | 679 | } |
682 | 680 | ||
@@ -688,16 +686,16 @@ sb_append (struct StringBuffer *ret, const struct StringBuffer *sarg) | |||
688 | * @param cstr string to append | 686 | * @param cstr string to append |
689 | */ | 687 | */ |
690 | static void | 688 | static void |
691 | sb_append_cstr (struct StringBuffer *ret, const char *cstr) | 689 | sb_append_cstr(struct StringBuffer *ret, const char *cstr) |
692 | { | 690 | { |
693 | size_t cstr_len = strlen (cstr); | 691 | size_t cstr_len = strlen(cstr); |
694 | 692 | ||
695 | if (GNUNET_YES == ret->null_flag) | 693 | if (GNUNET_YES == ret->null_flag) |
696 | ret->slen = 0; | 694 | ret->slen = 0; |
697 | ret->null_flag = GNUNET_NO; | 695 | ret->null_flag = GNUNET_NO; |
698 | if (ret->blen < cstr_len + ret->slen) | 696 | if (ret->blen < cstr_len + ret->slen) |
699 | sb_realloc (ret, ret->blen + cstr_len + 128); | 697 | sb_realloc(ret, ret->blen + cstr_len + 128); |
700 | GNUNET_memcpy (&ret->sbuf[ret->slen], cstr, cstr_len); | 698 | GNUNET_memcpy(&ret->sbuf[ret->slen], cstr, cstr_len); |
701 | ret->slen += cstr_len; | 699 | ret->slen += cstr_len; |
702 | } | 700 | } |
703 | 701 | ||
@@ -713,20 +711,20 @@ sb_append_cstr (struct StringBuffer *ret, const char *cstr) | |||
713 | * @param extra_chars how long will the result be, in addition to 'sarg' length | 711 | * @param extra_chars how long will the result be, in addition to 'sarg' length |
714 | */ | 712 | */ |
715 | static void | 713 | static void |
716 | sb_wrap (struct StringBuffer *ret, const char *format, size_t extra_chars) | 714 | sb_wrap(struct StringBuffer *ret, const char *format, size_t extra_chars) |
717 | { | 715 | { |
718 | char *temp; | 716 | char *temp; |
719 | 717 | ||
720 | if (GNUNET_YES == ret->null_flag) | 718 | if (GNUNET_YES == ret->null_flag) |
721 | ret->slen = 0; | 719 | ret->slen = 0; |
722 | ret->null_flag = GNUNET_NO; | 720 | ret->null_flag = GNUNET_NO; |
723 | temp = GNUNET_malloc (ret->slen + extra_chars + 1); | 721 | temp = GNUNET_malloc(ret->slen + extra_chars + 1); |
724 | GNUNET_snprintf (temp, | 722 | GNUNET_snprintf(temp, |
725 | ret->slen + extra_chars + 1, | 723 | ret->slen + extra_chars + 1, |
726 | format, | 724 | format, |
727 | (int) ret->slen, | 725 | (int)ret->slen, |
728 | ret->sbuf); | 726 | ret->sbuf); |
729 | GNUNET_free_non_null (ret->abuf); | 727 | GNUNET_free_non_null(ret->abuf); |
730 | ret->abuf = temp; | 728 | ret->abuf = temp; |
731 | ret->sbuf = temp; | 729 | ret->sbuf = temp; |
732 | ret->blen = ret->slen + extra_chars + 1; | 730 | ret->blen = ret->slen + extra_chars + 1; |
@@ -744,17 +742,17 @@ sb_wrap (struct StringBuffer *ret, const char *format, size_t extra_chars) | |||
744 | * @param sarg string to print into the format | 742 | * @param sarg string to print into the format |
745 | */ | 743 | */ |
746 | static void | 744 | static void |
747 | sb_printf1 (struct StringBuffer *ret, | 745 | sb_printf1(struct StringBuffer *ret, |
748 | const char *format, | 746 | const char *format, |
749 | size_t extra_chars, | 747 | size_t extra_chars, |
750 | const struct StringBuffer *sarg) | 748 | const struct StringBuffer *sarg) |
751 | { | 749 | { |
752 | if (ret->blen < sarg->slen + extra_chars + 1) | 750 | if (ret->blen < sarg->slen + extra_chars + 1) |
753 | sb_realloc (ret, sarg->slen + extra_chars + 1); | 751 | sb_realloc(ret, sarg->slen + extra_chars + 1); |
754 | ret->null_flag = GNUNET_NO; | 752 | ret->null_flag = GNUNET_NO; |
755 | ret->sbuf = ret->abuf; | 753 | ret->sbuf = ret->abuf; |
756 | ret->slen = sarg->slen + extra_chars; | 754 | ret->slen = sarg->slen + extra_chars; |
757 | GNUNET_snprintf (ret->sbuf, ret->blen, format, (int) sarg->slen, sarg->sbuf); | 755 | GNUNET_snprintf(ret->sbuf, ret->blen, format, (int)sarg->slen, sarg->sbuf); |
758 | } | 756 | } |
759 | 757 | ||
760 | 758 | ||
@@ -768,24 +766,24 @@ sb_printf1 (struct StringBuffer *ret, | |||
768 | * @param sarg2 second string to print into the format | 766 | * @param sarg2 second string to print into the format |
769 | */ | 767 | */ |
770 | static void | 768 | static void |
771 | sb_printf2 (struct StringBuffer *ret, | 769 | sb_printf2(struct StringBuffer *ret, |
772 | const char *format, | 770 | const char *format, |
773 | size_t extra_chars, | 771 | size_t extra_chars, |
774 | const struct StringBuffer *sarg1, | 772 | const struct StringBuffer *sarg1, |
775 | const struct StringBuffer *sarg2) | 773 | const struct StringBuffer *sarg2) |
776 | { | 774 | { |
777 | if (ret->blen < sarg1->slen + sarg2->slen + extra_chars + 1) | 775 | if (ret->blen < sarg1->slen + sarg2->slen + extra_chars + 1) |
778 | sb_realloc (ret, sarg1->slen + sarg2->slen + extra_chars + 1); | 776 | sb_realloc(ret, sarg1->slen + sarg2->slen + extra_chars + 1); |
779 | ret->null_flag = GNUNET_NO; | 777 | ret->null_flag = GNUNET_NO; |
780 | ret->slen = sarg1->slen + sarg2->slen + extra_chars; | 778 | ret->slen = sarg1->slen + sarg2->slen + extra_chars; |
781 | ret->sbuf = ret->abuf; | 779 | ret->sbuf = ret->abuf; |
782 | GNUNET_snprintf (ret->sbuf, | 780 | GNUNET_snprintf(ret->sbuf, |
783 | ret->blen, | 781 | ret->blen, |
784 | format, | 782 | format, |
785 | (int) sarg1->slen, | 783 | (int)sarg1->slen, |
786 | sarg1->sbuf, | 784 | sarg1->sbuf, |
787 | (int) sarg2->slen, | 785 | (int)sarg2->slen, |
788 | sarg2->sbuf); | 786 | sarg2->sbuf); |
789 | } | 787 | } |
790 | 788 | ||
791 | 789 | ||
@@ -801,27 +799,27 @@ sb_printf2 (struct StringBuffer *ret, | |||
801 | * @param sarg3 third string to print into the format | 799 | * @param sarg3 third string to print into the format |
802 | */ | 800 | */ |
803 | static void | 801 | static void |
804 | sb_printf3 (struct StringBuffer *ret, | 802 | sb_printf3(struct StringBuffer *ret, |
805 | const char *format, | 803 | const char *format, |
806 | size_t extra_chars, | 804 | size_t extra_chars, |
807 | const struct StringBuffer *sarg1, | 805 | const struct StringBuffer *sarg1, |
808 | const struct StringBuffer *sarg2, | 806 | const struct StringBuffer *sarg2, |
809 | const struct StringBuffer *sarg3) | 807 | const struct StringBuffer *sarg3) |
810 | { | 808 | { |
811 | if (ret->blen < sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1) | 809 | if (ret->blen < sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1) |
812 | sb_realloc (ret, sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1); | 810 | sb_realloc(ret, sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1); |
813 | ret->null_flag = GNUNET_NO; | 811 | ret->null_flag = GNUNET_NO; |
814 | ret->slen = sarg1->slen + sarg2->slen + sarg3->slen + extra_chars; | 812 | ret->slen = sarg1->slen + sarg2->slen + sarg3->slen + extra_chars; |
815 | ret->sbuf = ret->abuf; | 813 | ret->sbuf = ret->abuf; |
816 | GNUNET_snprintf (ret->sbuf, | 814 | GNUNET_snprintf(ret->sbuf, |
817 | ret->blen, | 815 | ret->blen, |
818 | format, | 816 | format, |
819 | (int) sarg1->slen, | 817 | (int)sarg1->slen, |
820 | sarg1->sbuf, | 818 | sarg1->sbuf, |
821 | (int) sarg2->slen, | 819 | (int)sarg2->slen, |
822 | sarg2->sbuf, | 820 | sarg2->sbuf, |
823 | (int) sarg3->slen, | 821 | (int)sarg3->slen, |
824 | sarg3->sbuf); | 822 | sarg3->sbuf); |
825 | } | 823 | } |
826 | 824 | ||
827 | 825 | ||
@@ -832,9 +830,9 @@ sb_printf3 (struct StringBuffer *ret, | |||
832 | * should not be individually allocated) | 830 | * should not be individually allocated) |
833 | */ | 831 | */ |
834 | static void | 832 | static void |
835 | sb_free (struct StringBuffer *sb) | 833 | sb_free(struct StringBuffer *sb) |
836 | { | 834 | { |
837 | GNUNET_array_grow (sb->abuf, sb->blen, 0); | 835 | GNUNET_array_grow(sb->abuf, sb->blen, 0); |
838 | sb->slen = 0; | 836 | sb->slen = 0; |
839 | sb->sbuf = NULL; | 837 | sb->sbuf = NULL; |
840 | sb->null_flag = GNUNET_YES; | 838 | sb->null_flag = GNUNET_YES; |
@@ -848,19 +846,19 @@ sb_free (struct StringBuffer *sb) | |||
848 | * @param out output string | 846 | * @param out output string |
849 | */ | 847 | */ |
850 | static void | 848 | static void |
851 | sb_strdup (struct StringBuffer *out, const struct StringBuffer *in) | 849 | sb_strdup(struct StringBuffer *out, const struct StringBuffer *in) |
852 | 850 | ||
853 | { | 851 | { |
854 | out->null_flag = in->null_flag; | 852 | out->null_flag = in->null_flag; |
855 | if (GNUNET_YES == out->null_flag) | 853 | if (GNUNET_YES == out->null_flag) |
856 | return; | 854 | return; |
857 | if (out->blen < in->slen) | 855 | if (out->blen < in->slen) |
858 | { | 856 | { |
859 | GNUNET_array_grow (out->abuf, out->blen, in->slen); | 857 | GNUNET_array_grow(out->abuf, out->blen, in->slen); |
860 | } | 858 | } |
861 | out->sbuf = out->abuf; | 859 | out->sbuf = out->abuf; |
862 | out->slen = in->slen; | 860 | out->slen = in->slen; |
863 | GNUNET_memcpy (out->sbuf, in->sbuf, out->slen); | 861 | GNUNET_memcpy(out->sbuf, in->sbuf, out->slen); |
864 | } | 862 | } |
865 | 863 | ||
866 | 864 | ||
@@ -871,21 +869,21 @@ sb_strdup (struct StringBuffer *out, const struct StringBuffer *in) | |||
871 | * @param out output string | 869 | * @param out output string |
872 | */ | 870 | */ |
873 | static void | 871 | static void |
874 | sb_strdup_cstr (struct StringBuffer *out, const char *cstr) | 872 | sb_strdup_cstr(struct StringBuffer *out, const char *cstr) |
875 | { | 873 | { |
876 | if (NULL == cstr) | 874 | if (NULL == cstr) |
877 | { | 875 | { |
878 | out->null_flag = GNUNET_YES; | 876 | out->null_flag = GNUNET_YES; |
879 | return; | 877 | return; |
880 | } | 878 | } |
881 | out->null_flag = GNUNET_NO; | 879 | out->null_flag = GNUNET_NO; |
882 | out->slen = strlen (cstr); | 880 | out->slen = strlen(cstr); |
883 | if (out->blen < out->slen) | 881 | if (out->blen < out->slen) |
884 | { | 882 | { |
885 | GNUNET_array_grow (out->abuf, out->blen, out->slen); | 883 | GNUNET_array_grow(out->abuf, out->blen, out->slen); |
886 | } | 884 | } |
887 | out->sbuf = out->abuf; | 885 | out->sbuf = out->abuf; |
888 | GNUNET_memcpy (out->sbuf, cstr, out->slen); | 886 | GNUNET_memcpy(out->sbuf, cstr, out->slen); |
889 | } | 887 | } |
890 | 888 | ||
891 | 889 | ||
@@ -898,7 +896,7 @@ sb_strdup_cstr (struct StringBuffer *out, const char *cstr) | |||
898 | * @return #GNUNET_YES if parentheses are needed, #GNUNET_NO otherwise | 896 | * @return #GNUNET_YES if parentheses are needed, #GNUNET_NO otherwise |
899 | */ | 897 | */ |
900 | static int | 898 | static int |
901 | needs_parentheses (const struct StringBuffer *str) | 899 | needs_parentheses(const struct StringBuffer *str) |
902 | { | 900 | { |
903 | size_t slen; | 901 | size_t slen; |
904 | const char *op; | 902 | const char *op; |
@@ -916,23 +914,23 @@ needs_parentheses (const struct StringBuffer *str) | |||
916 | cnt = 1; | 914 | cnt = 1; |
917 | pos++; | 915 | pos++; |
918 | while (cnt > 0) | 916 | while (cnt > 0) |
919 | { | ||
920 | cl = memchr (pos, ')', end - pos); | ||
921 | if (NULL == cl) | ||
922 | { | 917 | { |
923 | GNUNET_break (0); | 918 | cl = memchr(pos, ')', end - pos); |
924 | return GNUNET_YES; | 919 | if (NULL == cl) |
925 | } | 920 | { |
926 | /* while '(' before ')', count opening parens */ | 921 | GNUNET_break(0); |
927 | while ((NULL != (op = memchr (pos, '(', end - pos))) && (op < cl)) | 922 | return GNUNET_YES; |
928 | { | 923 | } |
929 | cnt++; | 924 | /* while '(' before ')', count opening parens */ |
930 | pos = op + 1; | 925 | while ((NULL != (op = memchr(pos, '(', end - pos))) && (op < cl)) |
926 | { | ||
927 | cnt++; | ||
928 | pos = op + 1; | ||
929 | } | ||
930 | /* got ')' first */ | ||
931 | cnt--; | ||
932 | pos = cl + 1; | ||
931 | } | 933 | } |
932 | /* got ')' first */ | ||
933 | cnt--; | ||
934 | pos = cl + 1; | ||
935 | } | ||
936 | return (*pos == '\0') ? GNUNET_NO : GNUNET_YES; | 934 | return (*pos == '\0') ? GNUNET_NO : GNUNET_YES; |
937 | } | 935 | } |
938 | 936 | ||
@@ -947,7 +945,7 @@ needs_parentheses (const struct StringBuffer *str) | |||
947 | * epsilon could be found, NULL if 'str' was NULL | 945 | * epsilon could be found, NULL if 'str' was NULL |
948 | */ | 946 | */ |
949 | static void | 947 | static void |
950 | remove_parentheses (struct StringBuffer *str) | 948 | remove_parentheses(struct StringBuffer *str) |
951 | { | 949 | { |
952 | size_t slen; | 950 | size_t slen; |
953 | const char *pos; | 951 | const char *pos; |
@@ -966,30 +964,30 @@ remove_parentheses (struct StringBuffer *str) | |||
966 | cnt = 0; | 964 | cnt = 0; |
967 | pos = &sbuf[1]; | 965 | pos = &sbuf[1]; |
968 | end = &sbuf[slen - 1]; | 966 | end = &sbuf[slen - 1]; |
969 | op = memchr (pos, '(', end - pos); | 967 | op = memchr(pos, '(', end - pos); |
970 | cp = memchr (pos, ')', end - pos); | 968 | cp = memchr(pos, ')', end - pos); |
971 | while (NULL != cp) | 969 | while (NULL != cp) |
972 | { | ||
973 | while ((NULL != op) && (op < cp)) | ||
974 | { | 970 | { |
975 | cnt++; | 971 | while ((NULL != op) && (op < cp)) |
976 | pos = op + 1; | 972 | { |
977 | op = memchr (pos, '(', end - pos); | 973 | cnt++; |
974 | pos = op + 1; | ||
975 | op = memchr(pos, '(', end - pos); | ||
976 | } | ||
977 | while ((NULL != cp) && ((NULL == op) || (cp < op))) | ||
978 | { | ||
979 | if (0 == cnt) | ||
980 | return; /* can't strip parens */ | ||
981 | cnt--; | ||
982 | pos = cp + 1; | ||
983 | cp = memchr(pos, ')', end - pos); | ||
984 | } | ||
978 | } | 985 | } |
979 | while ((NULL != cp) && ((NULL == op) || (cp < op))) | 986 | if (0 != cnt) |
980 | { | 987 | { |
981 | if (0 == cnt) | 988 | GNUNET_break(0); |
982 | return; /* can't strip parens */ | 989 | return; |
983 | cnt--; | ||
984 | pos = cp + 1; | ||
985 | cp = memchr (pos, ')', end - pos); | ||
986 | } | 990 | } |
987 | } | ||
988 | if (0 != cnt) | ||
989 | { | ||
990 | GNUNET_break (0); | ||
991 | return; | ||
992 | } | ||
993 | str->sbuf++; | 991 | str->sbuf++; |
994 | str->slen -= 2; | 992 | str->slen -= 2; |
995 | } | 993 | } |
@@ -1004,7 +1002,7 @@ remove_parentheses (struct StringBuffer *str) | |||
1004 | * @return 0 if str has no epsilon, 1 if str starts with '(|' and ends with ')' | 1002 | * @return 0 if str has no epsilon, 1 if str starts with '(|' and ends with ')' |
1005 | */ | 1003 | */ |
1006 | static int | 1004 | static int |
1007 | has_epsilon (const struct StringBuffer *str) | 1005 | has_epsilon(const struct StringBuffer *str) |
1008 | { | 1006 | { |
1009 | return (GNUNET_YES != str->null_flag) && (0 < str->slen) && | 1007 | return (GNUNET_YES != str->null_flag) && (0 < str->slen) && |
1010 | ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) && | 1008 | ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) && |
@@ -1022,27 +1020,27 @@ has_epsilon (const struct StringBuffer *str) | |||
1022 | * epsilon could be found, NULL if 'str' was NULL | 1020 | * epsilon could be found, NULL if 'str' was NULL |
1023 | */ | 1021 | */ |
1024 | static void | 1022 | static void |
1025 | remove_epsilon (const struct StringBuffer *str, struct StringBuffer *ret) | 1023 | remove_epsilon(const struct StringBuffer *str, struct StringBuffer *ret) |
1026 | { | 1024 | { |
1027 | if (GNUNET_YES == str->null_flag) | 1025 | if (GNUNET_YES == str->null_flag) |
1028 | { | 1026 | { |
1029 | ret->null_flag = GNUNET_YES; | 1027 | ret->null_flag = GNUNET_YES; |
1030 | return; | 1028 | return; |
1031 | } | 1029 | } |
1032 | if ((str->slen > 1) && ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) && | 1030 | if ((str->slen > 1) && ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) && |
1033 | (')' == str->sbuf[str->slen - 1])) | 1031 | (')' == str->sbuf[str->slen - 1])) |
1034 | { | ||
1035 | /* remove epsilon */ | ||
1036 | if (ret->blen < str->slen - 3) | ||
1037 | { | 1032 | { |
1038 | GNUNET_array_grow (ret->abuf, ret->blen, str->slen - 3); | 1033 | /* remove epsilon */ |
1034 | if (ret->blen < str->slen - 3) | ||
1035 | { | ||
1036 | GNUNET_array_grow(ret->abuf, ret->blen, str->slen - 3); | ||
1037 | } | ||
1038 | ret->sbuf = ret->abuf; | ||
1039 | ret->slen = str->slen - 3; | ||
1040 | GNUNET_memcpy(ret->sbuf, &str->sbuf[2], ret->slen); | ||
1041 | return; | ||
1039 | } | 1042 | } |
1040 | ret->sbuf = ret->abuf; | 1043 | sb_strdup(ret, str); |
1041 | ret->slen = str->slen - 3; | ||
1042 | GNUNET_memcpy (ret->sbuf, &str->sbuf[2], ret->slen); | ||
1043 | return; | ||
1044 | } | ||
1045 | sb_strdup (ret, str); | ||
1046 | } | 1044 | } |
1047 | 1045 | ||
1048 | 1046 | ||
@@ -1056,18 +1054,18 @@ remove_epsilon (const struct StringBuffer *str, struct StringBuffer *ret) | |||
1056 | * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise | 1054 | * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise |
1057 | */ | 1055 | */ |
1058 | static int | 1056 | static int |
1059 | sb_strncmp (const struct StringBuffer *str1, | 1057 | sb_strncmp(const struct StringBuffer *str1, |
1060 | const struct StringBuffer *str2, | 1058 | const struct StringBuffer *str2, |
1061 | size_t n) | 1059 | size_t n) |
1062 | { | 1060 | { |
1063 | size_t max; | 1061 | size_t max; |
1064 | 1062 | ||
1065 | if ((str1->slen != str2->slen) && ((str1->slen < n) || (str2->slen < n))) | 1063 | if ((str1->slen != str2->slen) && ((str1->slen < n) || (str2->slen < n))) |
1066 | return -1; | 1064 | return -1; |
1067 | max = GNUNET_MAX (str1->slen, str2->slen); | 1065 | max = GNUNET_MAX(str1->slen, str2->slen); |
1068 | if (max > n) | 1066 | if (max > n) |
1069 | max = n; | 1067 | max = n; |
1070 | return memcmp (str1->sbuf, str2->sbuf, max); | 1068 | return memcmp(str1->sbuf, str2->sbuf, max); |
1071 | } | 1069 | } |
1072 | 1070 | ||
1073 | 1071 | ||
@@ -1081,11 +1079,11 @@ sb_strncmp (const struct StringBuffer *str1, | |||
1081 | * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise | 1079 | * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise |
1082 | */ | 1080 | */ |
1083 | static int | 1081 | static int |
1084 | sb_strncmp_cstr (const struct StringBuffer *str1, const char *str2, size_t n) | 1082 | sb_strncmp_cstr(const struct StringBuffer *str1, const char *str2, size_t n) |
1085 | { | 1083 | { |
1086 | if (str1->slen < n) | 1084 | if (str1->slen < n) |
1087 | return -1; | 1085 | return -1; |
1088 | return memcmp (str1->sbuf, str2, n); | 1086 | return memcmp(str1->sbuf, str2, n); |
1089 | } | 1087 | } |
1090 | 1088 | ||
1091 | 1089 | ||
@@ -1097,10 +1095,10 @@ sb_strncmp_cstr (const struct StringBuffer *str1, const char *str2, size_t n) | |||
1097 | * @param n desired target length | 1095 | * @param n desired target length |
1098 | */ | 1096 | */ |
1099 | static void | 1097 | static void |
1100 | sb_init (struct StringBuffer *sb, size_t n) | 1098 | sb_init(struct StringBuffer *sb, size_t n) |
1101 | { | 1099 | { |
1102 | sb->null_flag = GNUNET_NO; | 1100 | sb->null_flag = GNUNET_NO; |
1103 | sb->abuf = sb->sbuf = (0 == n) ? NULL : GNUNET_malloc (n); | 1101 | sb->abuf = sb->sbuf = (0 == n) ? NULL : GNUNET_malloc(n); |
1104 | sb->blen = n; | 1102 | sb->blen = n; |
1105 | sb->slen = 0; | 1103 | sb->slen = 0; |
1106 | } | 1104 | } |
@@ -1116,14 +1114,14 @@ sb_init (struct StringBuffer *sb, size_t n) | |||
1116 | * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise | 1114 | * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise |
1117 | */ | 1115 | */ |
1118 | static int | 1116 | static int |
1119 | sb_strkcmp (const struct StringBuffer *str1, | 1117 | sb_strkcmp(const struct StringBuffer *str1, |
1120 | const struct StringBuffer *str2, | 1118 | const struct StringBuffer *str2, |
1121 | size_t k) | 1119 | size_t k) |
1122 | { | 1120 | { |
1123 | if ((GNUNET_YES == str1->null_flag) || (GNUNET_YES == str2->null_flag) || | 1121 | if ((GNUNET_YES == str1->null_flag) || (GNUNET_YES == str2->null_flag) || |
1124 | (k > str1->slen) || (str1->slen - k != str2->slen)) | 1122 | (k > str1->slen) || (str1->slen - k != str2->slen)) |
1125 | return -1; | 1123 | return -1; |
1126 | return memcmp (&str1->sbuf[k], str2->sbuf, str2->slen); | 1124 | return memcmp(&str1->sbuf[k], str2->sbuf, str2->slen); |
1127 | } | 1125 | } |
1128 | 1126 | ||
1129 | 1127 | ||
@@ -1136,9 +1134,9 @@ sb_strkcmp (const struct StringBuffer *str1, | |||
1136 | * @param s current state. | 1134 | * @param s current state. |
1137 | */ | 1135 | */ |
1138 | static void | 1136 | static void |
1139 | number_states (void *cls, | 1137 | number_states(void *cls, |
1140 | const unsigned int count, | 1138 | const unsigned int count, |
1141 | struct REGEX_INTERNAL_State *s) | 1139 | struct REGEX_INTERNAL_State *s) |
1142 | { | 1140 | { |
1143 | struct REGEX_INTERNAL_State **states = cls; | 1141 | struct REGEX_INTERNAL_State **states = cls; |
1144 | 1142 | ||
@@ -1149,8 +1147,8 @@ number_states (void *cls, | |||
1149 | 1147 | ||
1150 | 1148 | ||
1151 | #define PRIS(a) \ | 1149 | #define PRIS(a) \ |
1152 | ((GNUNET_YES == a.null_flag) ? 6 : (int) a.slen), \ | 1150 | ((GNUNET_YES == a.null_flag) ? 6 : (int)a.slen), \ |
1153 | ((GNUNET_YES == a.null_flag) ? "(null)" : a.sbuf) | 1151 | ((GNUNET_YES == a.null_flag) ? "(null)" : a.sbuf) |
1154 | 1152 | ||
1155 | 1153 | ||
1156 | /** | 1154 | /** |
@@ -1168,13 +1166,13 @@ number_states (void *cls, | |||
1168 | * @param R_cur_r optimization -- kept between iterations to avoid realloc | 1166 | * @param R_cur_r optimization -- kept between iterations to avoid realloc |
1169 | */ | 1167 | */ |
1170 | static void | 1168 | static void |
1171 | automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij, | 1169 | automaton_create_proofs_simplify(const struct StringBuffer *R_last_ij, |
1172 | const struct StringBuffer *R_last_ik, | 1170 | const struct StringBuffer *R_last_ik, |
1173 | const struct StringBuffer *R_last_kk, | 1171 | const struct StringBuffer *R_last_kk, |
1174 | const struct StringBuffer *R_last_kj, | 1172 | const struct StringBuffer *R_last_kj, |
1175 | struct StringBuffer *R_cur_ij, | 1173 | struct StringBuffer *R_cur_ij, |
1176 | struct StringBuffer *R_cur_l, | 1174 | struct StringBuffer *R_cur_l, |
1177 | struct StringBuffer *R_cur_r) | 1175 | struct StringBuffer *R_cur_r) |
1178 | { | 1176 | { |
1179 | struct StringBuffer R_temp_ij; | 1177 | struct StringBuffer R_temp_ij; |
1180 | struct StringBuffer R_temp_ik; | 1178 | struct StringBuffer R_temp_ik; |
@@ -1202,27 +1200,27 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij, | |||
1202 | if ((GNUNET_YES == R_last_ij->null_flag) && | 1200 | if ((GNUNET_YES == R_last_ij->null_flag) && |
1203 | ((GNUNET_YES == R_last_ik->null_flag) || | 1201 | ((GNUNET_YES == R_last_ik->null_flag) || |
1204 | (GNUNET_YES == R_last_kj->null_flag))) | 1202 | (GNUNET_YES == R_last_kj->null_flag))) |
1205 | { | 1203 | { |
1206 | /* R^{(k)}_{ij} = N | N */ | 1204 | /* R^{(k)}_{ij} = N | N */ |
1207 | R_cur_ij->null_flag = GNUNET_YES; | 1205 | R_cur_ij->null_flag = GNUNET_YES; |
1208 | R_cur_ij->synced = GNUNET_NO; | 1206 | R_cur_ij->synced = GNUNET_NO; |
1209 | return; | 1207 | return; |
1210 | } | 1208 | } |
1211 | 1209 | ||
1212 | if ((GNUNET_YES == R_last_ik->null_flag) || | 1210 | if ((GNUNET_YES == R_last_ik->null_flag) || |
1213 | (GNUNET_YES == R_last_kj->null_flag)) | 1211 | (GNUNET_YES == R_last_kj->null_flag)) |
1214 | { | ||
1215 | /* R^{(k)}_{ij} = R^{(k-1)}_{ij} | N */ | ||
1216 | if (GNUNET_YES == R_last_ij->synced) | ||
1217 | { | 1212 | { |
1213 | /* R^{(k)}_{ij} = R^{(k-1)}_{ij} | N */ | ||
1214 | if (GNUNET_YES == R_last_ij->synced) | ||
1215 | { | ||
1216 | R_cur_ij->synced = GNUNET_YES; | ||
1217 | R_cur_ij->null_flag = GNUNET_NO; | ||
1218 | return; | ||
1219 | } | ||
1218 | R_cur_ij->synced = GNUNET_YES; | 1220 | R_cur_ij->synced = GNUNET_YES; |
1219 | R_cur_ij->null_flag = GNUNET_NO; | 1221 | sb_strdup(R_cur_ij, R_last_ij); |
1220 | return; | 1222 | return; |
1221 | } | 1223 | } |
1222 | R_cur_ij->synced = GNUNET_YES; | ||
1223 | sb_strdup (R_cur_ij, R_last_ij); | ||
1224 | return; | ||
1225 | } | ||
1226 | R_cur_ij->synced = GNUNET_NO; | 1224 | R_cur_ij->synced = GNUNET_NO; |
1227 | 1225 | ||
1228 | /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR | 1226 | /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR |
@@ -1234,334 +1232,334 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij, | |||
1234 | R_cur_l->slen = 0; | 1232 | R_cur_l->slen = 0; |
1235 | 1233 | ||
1236 | /* cache results from strcmp, we might need these many times */ | 1234 | /* cache results from strcmp, we might need these many times */ |
1237 | ij_kj_cmp = sb_nullstrcmp (R_last_ij, R_last_kj); | 1235 | ij_kj_cmp = sb_nullstrcmp(R_last_ij, R_last_kj); |
1238 | ij_ik_cmp = sb_nullstrcmp (R_last_ij, R_last_ik); | 1236 | ij_ik_cmp = sb_nullstrcmp(R_last_ij, R_last_ik); |
1239 | ik_kk_cmp = sb_nullstrcmp (R_last_ik, R_last_kk); | 1237 | ik_kk_cmp = sb_nullstrcmp(R_last_ik, R_last_kk); |
1240 | kk_kj_cmp = sb_nullstrcmp (R_last_kk, R_last_kj); | 1238 | kk_kj_cmp = sb_nullstrcmp(R_last_kk, R_last_kj); |
1241 | 1239 | ||
1242 | /* Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well | 1240 | /* Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well |
1243 | * as parentheses, so we can better compare the contents */ | 1241 | * as parentheses, so we can better compare the contents */ |
1244 | 1242 | ||
1245 | memset (&R_temp_ij, 0, sizeof (struct StringBuffer)); | 1243 | memset(&R_temp_ij, 0, sizeof(struct StringBuffer)); |
1246 | memset (&R_temp_ik, 0, sizeof (struct StringBuffer)); | 1244 | memset(&R_temp_ik, 0, sizeof(struct StringBuffer)); |
1247 | memset (&R_temp_kk, 0, sizeof (struct StringBuffer)); | 1245 | memset(&R_temp_kk, 0, sizeof(struct StringBuffer)); |
1248 | memset (&R_temp_kj, 0, sizeof (struct StringBuffer)); | 1246 | memset(&R_temp_kj, 0, sizeof(struct StringBuffer)); |
1249 | remove_epsilon (R_last_ik, &R_temp_ik); | 1247 | remove_epsilon(R_last_ik, &R_temp_ik); |
1250 | remove_epsilon (R_last_kk, &R_temp_kk); | 1248 | remove_epsilon(R_last_kk, &R_temp_kk); |
1251 | remove_epsilon (R_last_kj, &R_temp_kj); | 1249 | remove_epsilon(R_last_kj, &R_temp_kj); |
1252 | remove_parentheses (&R_temp_ik); | 1250 | remove_parentheses(&R_temp_ik); |
1253 | remove_parentheses (&R_temp_kk); | 1251 | remove_parentheses(&R_temp_kk); |
1254 | remove_parentheses (&R_temp_kj); | 1252 | remove_parentheses(&R_temp_kj); |
1255 | clean_ik_kk_cmp = sb_nullstrcmp (R_last_ik, &R_temp_kk); | 1253 | clean_ik_kk_cmp = sb_nullstrcmp(R_last_ik, &R_temp_kk); |
1256 | clean_kk_kj_cmp = sb_nullstrcmp (&R_temp_kk, R_last_kj); | 1254 | clean_kk_kj_cmp = sb_nullstrcmp(&R_temp_kk, R_last_kj); |
1257 | 1255 | ||
1258 | /* construct R_cur_l (and, if necessary R_cur_r) */ | 1256 | /* construct R_cur_l (and, if necessary R_cur_r) */ |
1259 | if (GNUNET_YES != R_last_ij->null_flag) | 1257 | if (GNUNET_YES != R_last_ij->null_flag) |
1260 | { | ||
1261 | /* Assign R_temp_ij to R_last_ij and remove epsilon as well | ||
1262 | * as parentheses, so we can better compare the contents */ | ||
1263 | remove_epsilon (R_last_ij, &R_temp_ij); | ||
1264 | remove_parentheses (&R_temp_ij); | ||
1265 | |||
1266 | if ((0 == sb_strcmp (&R_temp_ij, &R_temp_ik)) && | ||
1267 | (0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) && | ||
1268 | (0 == sb_strcmp (&R_temp_kk, &R_temp_kj))) | ||
1269 | { | ||
1270 | if (0 == R_temp_ij.slen) | ||
1271 | { | ||
1272 | R_cur_r->null_flag = GNUNET_NO; | ||
1273 | } | ||
1274 | else if ((0 == sb_strncmp_cstr (R_last_ij, "(|", 2)) || | ||
1275 | (0 == sb_strncmp_cstr (R_last_ik, "(|", 2) && | ||
1276 | 0 == sb_strncmp_cstr (R_last_kj, "(|", 2))) | ||
1277 | { | ||
1278 | /* | ||
1279 | * a|(e|a)a*(e|a) = a* | ||
1280 | * a|(e|a)(e|a)*(e|a) = a* | ||
1281 | * (e|a)|aa*a = a* | ||
1282 | * (e|a)|aa*(e|a) = a* | ||
1283 | * (e|a)|(e|a)a*a = a* | ||
1284 | * (e|a)|(e|a)a*(e|a) = a* | ||
1285 | * (e|a)|(e|a)(e|a)*(e|a) = a* | ||
1286 | */ | ||
1287 | if (GNUNET_YES == needs_parentheses (&R_temp_ij)) | ||
1288 | sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_ij); | ||
1289 | else | ||
1290 | sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_ij); | ||
1291 | } | ||
1292 | else | ||
1293 | { | ||
1294 | /* | ||
1295 | * a|aa*a = a+ | ||
1296 | * a|(e|a)a*a = a+ | ||
1297 | * a|aa*(e|a) = a+ | ||
1298 | * a|(e|a)(e|a)*a = a+ | ||
1299 | * a|a(e|a)*(e|a) = a+ | ||
1300 | */ | ||
1301 | if (GNUNET_YES == needs_parentheses (&R_temp_ij)) | ||
1302 | sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_ij); | ||
1303 | else | ||
1304 | sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_ij); | ||
1305 | } | ||
1306 | } | ||
1307 | else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) && | ||
1308 | (0 != clean_ik_kk_cmp)) | ||
1309 | { | 1258 | { |
1310 | /* a|ab*b = ab* */ | 1259 | /* Assign R_temp_ij to R_last_ij and remove epsilon as well |
1311 | if (0 == R_last_kk->slen) | 1260 | * as parentheses, so we can better compare the contents */ |
1312 | sb_strdup (R_cur_r, R_last_ij); | 1261 | remove_epsilon(R_last_ij, &R_temp_ij); |
1313 | else if (GNUNET_YES == needs_parentheses (&R_temp_kk)) | 1262 | remove_parentheses(&R_temp_ij); |
1314 | sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk); | 1263 | |
1315 | else | 1264 | if ((0 == sb_strcmp(&R_temp_ij, &R_temp_ik)) && |
1316 | sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, R_last_kk); | 1265 | (0 == sb_strcmp(&R_temp_ik, &R_temp_kk)) && |
1317 | R_cur_l->null_flag = GNUNET_YES; | 1266 | (0 == sb_strcmp(&R_temp_kk, &R_temp_kj))) |
1318 | } | 1267 | { |
1319 | else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) && | 1268 | if (0 == R_temp_ij.slen) |
1320 | (0 != clean_kk_kj_cmp)) | 1269 | { |
1321 | { | 1270 | R_cur_r->null_flag = GNUNET_NO; |
1322 | /* a|bb*a = b*a */ | 1271 | } |
1323 | if (R_last_kk->slen < 1) | 1272 | else if ((0 == sb_strncmp_cstr(R_last_ij, "(|", 2)) || |
1324 | { | 1273 | (0 == sb_strncmp_cstr(R_last_ik, "(|", 2) && |
1325 | sb_strdup (R_cur_r, R_last_kj); | 1274 | 0 == sb_strncmp_cstr(R_last_kj, "(|", 2))) |
1326 | } | 1275 | { |
1327 | else if (GNUNET_YES == needs_parentheses (&R_temp_kk)) | 1276 | /* |
1328 | sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj); | 1277 | * a|(e|a)a*(e|a) = a* |
1329 | else | 1278 | * a|(e|a)(e|a)*(e|a) = a* |
1330 | sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj); | 1279 | * (e|a)|aa*a = a* |
1280 | * (e|a)|aa*(e|a) = a* | ||
1281 | * (e|a)|(e|a)a*a = a* | ||
1282 | * (e|a)|(e|a)a*(e|a) = a* | ||
1283 | * (e|a)|(e|a)(e|a)*(e|a) = a* | ||
1284 | */ | ||
1285 | if (GNUNET_YES == needs_parentheses(&R_temp_ij)) | ||
1286 | sb_printf1(R_cur_r, "(%.*s)*", 3, &R_temp_ij); | ||
1287 | else | ||
1288 | sb_printf1(R_cur_r, "%.*s*", 1, &R_temp_ij); | ||
1289 | } | ||
1290 | else | ||
1291 | { | ||
1292 | /* | ||
1293 | * a|aa*a = a+ | ||
1294 | * a|(e|a)a*a = a+ | ||
1295 | * a|aa*(e|a) = a+ | ||
1296 | * a|(e|a)(e|a)*a = a+ | ||
1297 | * a|a(e|a)*(e|a) = a+ | ||
1298 | */ | ||
1299 | if (GNUNET_YES == needs_parentheses(&R_temp_ij)) | ||
1300 | sb_printf1(R_cur_r, "(%.*s)+", 3, &R_temp_ij); | ||
1301 | else | ||
1302 | sb_printf1(R_cur_r, "%.*s+", 1, &R_temp_ij); | ||
1303 | } | ||
1304 | } | ||
1305 | else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) && | ||
1306 | (0 != clean_ik_kk_cmp)) | ||
1307 | { | ||
1308 | /* a|ab*b = ab* */ | ||
1309 | if (0 == R_last_kk->slen) | ||
1310 | sb_strdup(R_cur_r, R_last_ij); | ||
1311 | else if (GNUNET_YES == needs_parentheses(&R_temp_kk)) | ||
1312 | sb_printf2(R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk); | ||
1313 | else | ||
1314 | sb_printf2(R_cur_r, "%.*s%.*s*", 1, R_last_ij, R_last_kk); | ||
1315 | R_cur_l->null_flag = GNUNET_YES; | ||
1316 | } | ||
1317 | else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) && | ||
1318 | (0 != clean_kk_kj_cmp)) | ||
1319 | { | ||
1320 | /* a|bb*a = b*a */ | ||
1321 | if (R_last_kk->slen < 1) | ||
1322 | { | ||
1323 | sb_strdup(R_cur_r, R_last_kj); | ||
1324 | } | ||
1325 | else if (GNUNET_YES == needs_parentheses(&R_temp_kk)) | ||
1326 | sb_printf2(R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj); | ||
1327 | else | ||
1328 | sb_printf2(R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj); | ||
1331 | 1329 | ||
1332 | R_cur_l->null_flag = GNUNET_YES; | 1330 | R_cur_l->null_flag = GNUNET_YES; |
1333 | } | 1331 | } |
1334 | else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) && | 1332 | else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) && |
1335 | (! has_epsilon (R_last_ij)) && has_epsilon (R_last_kk)) | 1333 | (!has_epsilon(R_last_ij)) && has_epsilon(R_last_kk)) |
1336 | { | 1334 | { |
1337 | /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */ | 1335 | /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */ |
1338 | if (needs_parentheses (&R_temp_kk)) | 1336 | if (needs_parentheses(&R_temp_kk)) |
1339 | sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk); | 1337 | sb_printf2(R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk); |
1338 | else | ||
1339 | sb_printf2(R_cur_r, "%.*s%.*s*", 1, R_last_ij, &R_temp_kk); | ||
1340 | R_cur_l->null_flag = GNUNET_YES; | ||
1341 | } | ||
1342 | else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) && | ||
1343 | (!has_epsilon(R_last_ij)) && has_epsilon(R_last_kk)) | ||
1344 | { | ||
1345 | /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a */ | ||
1346 | if (needs_parentheses(&R_temp_kk)) | ||
1347 | sb_printf2(R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij); | ||
1348 | else | ||
1349 | sb_printf2(R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_ij); | ||
1350 | R_cur_l->null_flag = GNUNET_YES; | ||
1351 | } | ||
1340 | else | 1352 | else |
1341 | sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, &R_temp_kk); | 1353 | { |
1342 | R_cur_l->null_flag = GNUNET_YES; | 1354 | sb_strdup(R_cur_l, R_last_ij); |
1355 | remove_parentheses(R_cur_l); | ||
1356 | } | ||
1343 | } | 1357 | } |
1344 | else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) && | 1358 | else |
1345 | (! has_epsilon (R_last_ij)) && has_epsilon (R_last_kk)) | ||
1346 | { | 1359 | { |
1347 | /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a */ | 1360 | /* we have no left side */ |
1348 | if (needs_parentheses (&R_temp_kk)) | ||
1349 | sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij); | ||
1350 | else | ||
1351 | sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_ij); | ||
1352 | R_cur_l->null_flag = GNUNET_YES; | 1361 | R_cur_l->null_flag = GNUNET_YES; |
1353 | } | 1362 | } |
1354 | else | ||
1355 | { | ||
1356 | sb_strdup (R_cur_l, R_last_ij); | ||
1357 | remove_parentheses (R_cur_l); | ||
1358 | } | ||
1359 | } | ||
1360 | else | ||
1361 | { | ||
1362 | /* we have no left side */ | ||
1363 | R_cur_l->null_flag = GNUNET_YES; | ||
1364 | } | ||
1365 | 1363 | ||
1366 | /* construct R_cur_r, if not already constructed */ | 1364 | /* construct R_cur_r, if not already constructed */ |
1367 | if (GNUNET_YES == R_cur_r->null_flag) | 1365 | if (GNUNET_YES == R_cur_r->null_flag) |
1368 | { | ||
1369 | length = R_temp_kk.slen - R_last_ik->slen; | ||
1370 | |||
1371 | /* a(ba)*bx = (ab)+x */ | ||
1372 | if ((length > 0) && (GNUNET_YES != R_last_kk->null_flag) && | ||
1373 | (0 < R_last_kk->slen) && (GNUNET_YES != R_last_kj->null_flag) && | ||
1374 | (0 < R_last_kj->slen) && (GNUNET_YES != R_last_ik->null_flag) && | ||
1375 | (0 < R_last_ik->slen) && | ||
1376 | (0 == sb_strkcmp (&R_temp_kk, R_last_ik, length)) && | ||
1377 | (0 == sb_strncmp (&R_temp_kk, R_last_kj, length))) | ||
1378 | { | ||
1379 | struct StringBuffer temp_a; | ||
1380 | struct StringBuffer temp_b; | ||
1381 | |||
1382 | sb_init (&temp_a, length); | ||
1383 | sb_init (&temp_b, R_last_kj->slen - length); | ||
1384 | |||
1385 | length_l = length; | ||
1386 | temp_a.sbuf = temp_a.abuf; | ||
1387 | GNUNET_memcpy (temp_a.sbuf, R_last_kj->sbuf, length_l); | ||
1388 | temp_a.slen = length_l; | ||
1389 | |||
1390 | length_r = R_last_kj->slen - length; | ||
1391 | temp_b.sbuf = temp_b.abuf; | ||
1392 | GNUNET_memcpy (temp_b.sbuf, &R_last_kj->sbuf[length], length_r); | ||
1393 | temp_b.slen = length_r; | ||
1394 | |||
1395 | /* e|(ab)+ = (ab)* */ | ||
1396 | if ((GNUNET_YES != R_cur_l->null_flag) && (0 == R_cur_l->slen) && | ||
1397 | (0 == temp_b.slen)) | ||
1398 | { | ||
1399 | sb_printf2 (R_cur_r, "(%.*s%.*s)*", 3, R_last_ik, &temp_a); | ||
1400 | sb_free (R_cur_l); | ||
1401 | R_cur_l->null_flag = GNUNET_YES; | ||
1402 | } | ||
1403 | else | ||
1404 | { | ||
1405 | sb_printf3 (R_cur_r, "(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b); | ||
1406 | } | ||
1407 | sb_free (&temp_a); | ||
1408 | sb_free (&temp_b); | ||
1409 | } | ||
1410 | else if (0 == sb_strcmp (&R_temp_ik, &R_temp_kk) && | ||
1411 | 0 == sb_strcmp (&R_temp_kk, &R_temp_kj)) | ||
1412 | { | 1366 | { |
1367 | length = R_temp_kk.slen - R_last_ik->slen; | ||
1368 | |||
1369 | /* a(ba)*bx = (ab)+x */ | ||
1370 | if ((length > 0) && (GNUNET_YES != R_last_kk->null_flag) && | ||
1371 | (0 < R_last_kk->slen) && (GNUNET_YES != R_last_kj->null_flag) && | ||
1372 | (0 < R_last_kj->slen) && (GNUNET_YES != R_last_ik->null_flag) && | ||
1373 | (0 < R_last_ik->slen) && | ||
1374 | (0 == sb_strkcmp(&R_temp_kk, R_last_ik, length)) && | ||
1375 | (0 == sb_strncmp(&R_temp_kk, R_last_kj, length))) | ||
1376 | { | ||
1377 | struct StringBuffer temp_a; | ||
1378 | struct StringBuffer temp_b; | ||
1379 | |||
1380 | sb_init(&temp_a, length); | ||
1381 | sb_init(&temp_b, R_last_kj->slen - length); | ||
1382 | |||
1383 | length_l = length; | ||
1384 | temp_a.sbuf = temp_a.abuf; | ||
1385 | GNUNET_memcpy(temp_a.sbuf, R_last_kj->sbuf, length_l); | ||
1386 | temp_a.slen = length_l; | ||
1387 | |||
1388 | length_r = R_last_kj->slen - length; | ||
1389 | temp_b.sbuf = temp_b.abuf; | ||
1390 | GNUNET_memcpy(temp_b.sbuf, &R_last_kj->sbuf[length], length_r); | ||
1391 | temp_b.slen = length_r; | ||
1392 | |||
1393 | /* e|(ab)+ = (ab)* */ | ||
1394 | if ((GNUNET_YES != R_cur_l->null_flag) && (0 == R_cur_l->slen) && | ||
1395 | (0 == temp_b.slen)) | ||
1396 | { | ||
1397 | sb_printf2(R_cur_r, "(%.*s%.*s)*", 3, R_last_ik, &temp_a); | ||
1398 | sb_free(R_cur_l); | ||
1399 | R_cur_l->null_flag = GNUNET_YES; | ||
1400 | } | ||
1401 | else | ||
1402 | { | ||
1403 | sb_printf3(R_cur_r, "(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b); | ||
1404 | } | ||
1405 | sb_free(&temp_a); | ||
1406 | sb_free(&temp_b); | ||
1407 | } | ||
1408 | else if (0 == sb_strcmp(&R_temp_ik, &R_temp_kk) && | ||
1409 | 0 == sb_strcmp(&R_temp_kk, &R_temp_kj)) | ||
1410 | { | ||
1411 | /* | ||
1412 | * (e|a)a*(e|a) = a* | ||
1413 | * (e|a)(e|a)*(e|a) = a* | ||
1414 | */ | ||
1415 | if (has_epsilon(R_last_ik) && has_epsilon(R_last_kj)) | ||
1416 | { | ||
1417 | if (needs_parentheses(&R_temp_kk)) | ||
1418 | sb_printf1(R_cur_r, "(%.*s)*", 3, &R_temp_kk); | ||
1419 | else | ||
1420 | sb_printf1(R_cur_r, "%.*s*", 1, &R_temp_kk); | ||
1421 | } | ||
1422 | /* aa*a = a+a */ | ||
1423 | else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) && | ||
1424 | (!has_epsilon(R_last_ik))) | ||
1425 | { | ||
1426 | if (needs_parentheses(&R_temp_kk)) | ||
1427 | sb_printf2(R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk); | ||
1428 | else | ||
1429 | sb_printf2(R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk); | ||
1430 | } | ||
1431 | /* | ||
1432 | * (e|a)a*a = a+ | ||
1433 | * aa*(e|a) = a+ | ||
1434 | * a(e|a)*(e|a) = a+ | ||
1435 | * (e|a)a*a = a+ | ||
1436 | */ | ||
1437 | else | ||
1438 | { | ||
1439 | eps_check = (has_epsilon(R_last_ik) + has_epsilon(R_last_kk) + | ||
1440 | has_epsilon(R_last_kj)); | ||
1441 | |||
1442 | if (1 == eps_check) | ||
1443 | { | ||
1444 | if (needs_parentheses(&R_temp_kk)) | ||
1445 | sb_printf1(R_cur_r, "(%.*s)+", 3, &R_temp_kk); | ||
1446 | else | ||
1447 | sb_printf1(R_cur_r, "%.*s+", 1, &R_temp_kk); | ||
1448 | } | ||
1449 | } | ||
1450 | } | ||
1413 | /* | 1451 | /* |
1414 | * (e|a)a*(e|a) = a* | 1452 | * aa*b = a+b |
1415 | * (e|a)(e|a)*(e|a) = a* | 1453 | * (e|a)(e|a)*b = a*b |
1416 | */ | 1454 | */ |
1417 | if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj)) | 1455 | else if (0 == sb_strcmp(&R_temp_ik, &R_temp_kk)) |
1418 | { | 1456 | { |
1419 | if (needs_parentheses (&R_temp_kk)) | 1457 | if (has_epsilon(R_last_ik)) |
1420 | sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_kk); | 1458 | { |
1421 | else | 1459 | if (needs_parentheses(&R_temp_kk)) |
1422 | sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_kk); | 1460 | sb_printf2(R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj); |
1423 | } | 1461 | else |
1424 | /* aa*a = a+a */ | 1462 | sb_printf2(R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj); |
1425 | else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) && | 1463 | } |
1426 | (! has_epsilon (R_last_ik))) | 1464 | else |
1427 | { | 1465 | { |
1428 | if (needs_parentheses (&R_temp_kk)) | 1466 | if (needs_parentheses(&R_temp_kk)) |
1429 | sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk); | 1467 | sb_printf2(R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj); |
1430 | else | 1468 | else |
1431 | sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk); | 1469 | sb_printf2(R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, R_last_kj); |
1432 | } | 1470 | } |
1471 | } | ||
1433 | /* | 1472 | /* |
1434 | * (e|a)a*a = a+ | 1473 | * ba*a = ba+ |
1435 | * aa*(e|a) = a+ | 1474 | * b(e|a)*(e|a) = ba* |
1436 | * a(e|a)*(e|a) = a+ | ||
1437 | * (e|a)a*a = a+ | ||
1438 | */ | 1475 | */ |
1439 | else | 1476 | else if (0 == sb_strcmp(&R_temp_kk, &R_temp_kj)) |
1440 | { | ||
1441 | eps_check = (has_epsilon (R_last_ik) + has_epsilon (R_last_kk) + | ||
1442 | has_epsilon (R_last_kj)); | ||
1443 | |||
1444 | if (1 == eps_check) | ||
1445 | { | 1477 | { |
1446 | if (needs_parentheses (&R_temp_kk)) | 1478 | if (has_epsilon(R_last_kj)) |
1447 | sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_kk); | 1479 | { |
1480 | if (needs_parentheses(&R_temp_kk)) | ||
1481 | sb_printf2(R_cur_r, "%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk); | ||
1482 | else | ||
1483 | sb_printf2(R_cur_r, "%.*s%.*s*", 1, R_last_ik, &R_temp_kk); | ||
1484 | } | ||
1448 | else | 1485 | else |
1449 | sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_kk); | 1486 | { |
1487 | if (needs_parentheses(&R_temp_kk)) | ||
1488 | sb_printf2(R_cur_r, "(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk); | ||
1489 | else | ||
1490 | sb_printf2(R_cur_r, "%.*s+%.*s", 1, R_last_ik, &R_temp_kk); | ||
1491 | } | ||
1450 | } | 1492 | } |
1451 | } | ||
1452 | } | ||
1453 | /* | ||
1454 | * aa*b = a+b | ||
1455 | * (e|a)(e|a)*b = a*b | ||
1456 | */ | ||
1457 | else if (0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) | ||
1458 | { | ||
1459 | if (has_epsilon (R_last_ik)) | ||
1460 | { | ||
1461 | if (needs_parentheses (&R_temp_kk)) | ||
1462 | sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj); | ||
1463 | else | ||
1464 | sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj); | ||
1465 | } | ||
1466 | else | 1493 | else |
1467 | { | ||
1468 | if (needs_parentheses (&R_temp_kk)) | ||
1469 | sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj); | ||
1470 | else | ||
1471 | sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, R_last_kj); | ||
1472 | } | ||
1473 | } | ||
1474 | /* | ||
1475 | * ba*a = ba+ | ||
1476 | * b(e|a)*(e|a) = ba* | ||
1477 | */ | ||
1478 | else if (0 == sb_strcmp (&R_temp_kk, &R_temp_kj)) | ||
1479 | { | ||
1480 | if (has_epsilon (R_last_kj)) | ||
1481 | { | ||
1482 | if (needs_parentheses (&R_temp_kk)) | ||
1483 | sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk); | ||
1484 | else | ||
1485 | sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ik, &R_temp_kk); | ||
1486 | } | ||
1487 | else | ||
1488 | { | ||
1489 | if (needs_parentheses (&R_temp_kk)) | ||
1490 | sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk); | ||
1491 | else | ||
1492 | sb_printf2 (R_cur_r, "%.*s+%.*s", 1, R_last_ik, &R_temp_kk); | ||
1493 | } | ||
1494 | } | ||
1495 | else | ||
1496 | { | ||
1497 | if (0 < R_temp_kk.slen) | ||
1498 | { | ||
1499 | if (needs_parentheses (&R_temp_kk)) | ||
1500 | { | 1494 | { |
1501 | sb_printf3 (R_cur_r, | 1495 | if (0 < R_temp_kk.slen) |
1502 | "%.*s(%.*s)*%.*s", | 1496 | { |
1503 | 3, | 1497 | if (needs_parentheses(&R_temp_kk)) |
1504 | R_last_ik, | 1498 | { |
1505 | &R_temp_kk, | 1499 | sb_printf3(R_cur_r, |
1506 | R_last_kj); | 1500 | "%.*s(%.*s)*%.*s", |
1507 | } | 1501 | 3, |
1508 | else | 1502 | R_last_ik, |
1509 | { | 1503 | &R_temp_kk, |
1510 | sb_printf3 (R_cur_r, | 1504 | R_last_kj); |
1511 | "%.*s%.*s*%.*s", | 1505 | } |
1512 | 1, | 1506 | else |
1513 | R_last_ik, | 1507 | { |
1514 | &R_temp_kk, | 1508 | sb_printf3(R_cur_r, |
1515 | R_last_kj); | 1509 | "%.*s%.*s*%.*s", |
1510 | 1, | ||
1511 | R_last_ik, | ||
1512 | &R_temp_kk, | ||
1513 | R_last_kj); | ||
1514 | } | ||
1515 | } | ||
1516 | else | ||
1517 | { | ||
1518 | sb_printf2(R_cur_r, "%.*s%.*s", 0, R_last_ik, R_last_kj); | ||
1519 | } | ||
1516 | } | 1520 | } |
1517 | } | ||
1518 | else | ||
1519 | { | ||
1520 | sb_printf2 (R_cur_r, "%.*s%.*s", 0, R_last_ik, R_last_kj); | ||
1521 | } | ||
1522 | } | 1521 | } |
1523 | } | 1522 | sb_free(&R_temp_ij); |
1524 | sb_free (&R_temp_ij); | 1523 | sb_free(&R_temp_ik); |
1525 | sb_free (&R_temp_ik); | 1524 | sb_free(&R_temp_kk); |
1526 | sb_free (&R_temp_kk); | 1525 | sb_free(&R_temp_kj); |
1527 | sb_free (&R_temp_kj); | ||
1528 | 1526 | ||
1529 | if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag)) | 1527 | if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag)) |
1530 | { | 1528 | { |
1531 | R_cur_ij->null_flag = GNUNET_YES; | 1529 | R_cur_ij->null_flag = GNUNET_YES; |
1532 | return; | 1530 | return; |
1533 | } | 1531 | } |
1534 | 1532 | ||
1535 | if ((GNUNET_YES != R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag)) | 1533 | if ((GNUNET_YES != R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag)) |
1536 | { | 1534 | { |
1537 | struct StringBuffer tmp; | 1535 | struct StringBuffer tmp; |
1538 | 1536 | ||
1539 | tmp = *R_cur_ij; | 1537 | tmp = *R_cur_ij; |
1540 | *R_cur_ij = *R_cur_l; | 1538 | *R_cur_ij = *R_cur_l; |
1541 | *R_cur_l = tmp; | 1539 | *R_cur_l = tmp; |
1542 | return; | 1540 | return; |
1543 | } | 1541 | } |
1544 | 1542 | ||
1545 | if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES != R_cur_r->null_flag)) | 1543 | if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES != R_cur_r->null_flag)) |
1546 | { | 1544 | { |
1547 | struct StringBuffer tmp; | 1545 | struct StringBuffer tmp; |
1548 | 1546 | ||
1549 | tmp = *R_cur_ij; | 1547 | tmp = *R_cur_ij; |
1550 | *R_cur_ij = *R_cur_r; | 1548 | *R_cur_ij = *R_cur_r; |
1551 | *R_cur_r = tmp; | 1549 | *R_cur_r = tmp; |
1552 | return; | 1550 | return; |
1553 | } | 1551 | } |
1554 | 1552 | ||
1555 | if (0 == sb_nullstrcmp (R_cur_l, R_cur_r)) | 1553 | if (0 == sb_nullstrcmp(R_cur_l, R_cur_r)) |
1556 | { | 1554 | { |
1557 | struct StringBuffer tmp; | 1555 | struct StringBuffer tmp; |
1558 | 1556 | ||
1559 | tmp = *R_cur_ij; | 1557 | tmp = *R_cur_ij; |
1560 | *R_cur_ij = *R_cur_l; | 1558 | *R_cur_ij = *R_cur_l; |
1561 | *R_cur_l = tmp; | 1559 | *R_cur_l = tmp; |
1562 | return; | 1560 | return; |
1563 | } | 1561 | } |
1564 | sb_printf2 (R_cur_ij, "(%.*s|%.*s)", 3, R_cur_l, R_cur_r); | 1562 | sb_printf2(R_cur_ij, "(%.*s|%.*s)", 3, R_cur_l, R_cur_r); |
1565 | } | 1563 | } |
1566 | 1564 | ||
1567 | 1565 | ||
@@ -1577,7 +1575,7 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij, | |||
1577 | * @param a automaton for which to assign proofs and hashes, must not be NULL | 1575 | * @param a automaton for which to assign proofs and hashes, must not be NULL |
1578 | */ | 1576 | */ |
1579 | static int | 1577 | static int |
1580 | automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a) | 1578 | automaton_create_proofs(struct REGEX_INTERNAL_Automaton *a) |
1581 | { | 1579 | { |
1582 | unsigned int n = a->state_count; | 1580 | unsigned int n = a->state_count; |
1583 | struct REGEX_INTERNAL_State *states[n]; | 1581 | struct REGEX_INTERNAL_State *states[n]; |
@@ -1592,143 +1590,143 @@ automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a) | |||
1592 | unsigned int j; | 1590 | unsigned int j; |
1593 | unsigned int k; | 1591 | unsigned int k; |
1594 | 1592 | ||
1595 | R_last = GNUNET_malloc_large (sizeof (struct StringBuffer) * n * n); | 1593 | R_last = GNUNET_malloc_large(sizeof(struct StringBuffer) * n * n); |
1596 | R_cur = GNUNET_malloc_large (sizeof (struct StringBuffer) * n * n); | 1594 | R_cur = GNUNET_malloc_large(sizeof(struct StringBuffer) * n * n); |
1597 | if ((NULL == R_last) || (NULL == R_cur)) | 1595 | if ((NULL == R_last) || (NULL == R_cur)) |
1598 | { | 1596 | { |
1599 | GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc"); | 1597 | GNUNET_log_strerror(GNUNET_ERROR_TYPE_ERROR, "malloc"); |
1600 | GNUNET_free_non_null (R_cur); | 1598 | GNUNET_free_non_null(R_cur); |
1601 | GNUNET_free_non_null (R_last); | 1599 | GNUNET_free_non_null(R_last); |
1602 | return GNUNET_SYSERR; | 1600 | return GNUNET_SYSERR; |
1603 | } | 1601 | } |
1604 | 1602 | ||
1605 | /* create depth-first numbering of the states, initializes 'state' */ | 1603 | /* create depth-first numbering of the states, initializes 'state' */ |
1606 | REGEX_INTERNAL_automaton_traverse (a, | 1604 | REGEX_INTERNAL_automaton_traverse(a, |
1607 | a->start, | 1605 | a->start, |
1608 | NULL, | 1606 | NULL, |
1609 | NULL, | 1607 | NULL, |
1610 | &number_states, | 1608 | &number_states, |
1611 | states); | 1609 | states); |
1612 | 1610 | ||
1613 | for (i = 0; i < n; i++) | 1611 | for (i = 0; i < n; i++) |
1614 | GNUNET_assert (NULL != states[i]); | 1612 | GNUNET_assert(NULL != states[i]); |
1615 | for (i = 0; i < n; i++) | 1613 | for (i = 0; i < n; i++) |
1616 | for (j = 0; j < n; j++) | 1614 | for (j = 0; j < n; j++) |
1617 | R_last[i * n + j].null_flag = GNUNET_YES; | 1615 | R_last[i * n + j].null_flag = GNUNET_YES; |
1618 | 1616 | ||
1619 | /* Compute regular expressions of length "1" between each pair of states */ | 1617 | /* Compute regular expressions of length "1" between each pair of states */ |
1620 | for (i = 0; i < n; i++) | 1618 | for (i = 0; i < n; i++) |
1621 | { | ||
1622 | for (t = states[i]->transitions_head; NULL != t; t = t->next) | ||
1623 | { | 1619 | { |
1624 | j = t->to_state->dfs_id; | 1620 | for (t = states[i]->transitions_head; NULL != t; t = t->next) |
1625 | if (GNUNET_YES == R_last[i * n + j].null_flag) | 1621 | { |
1626 | { | 1622 | j = t->to_state->dfs_id; |
1627 | sb_strdup_cstr (&R_last[i * n + j], t->label); | 1623 | if (GNUNET_YES == R_last[i * n + j].null_flag) |
1628 | } | 1624 | { |
1625 | sb_strdup_cstr(&R_last[i * n + j], t->label); | ||
1626 | } | ||
1627 | else | ||
1628 | { | ||
1629 | sb_append_cstr(&R_last[i * n + j], "|"); | ||
1630 | sb_append_cstr(&R_last[i * n + j], t->label); | ||
1631 | } | ||
1632 | } | ||
1633 | /* add self-loop: i is reachable from i via epsilon-transition */ | ||
1634 | if (GNUNET_YES == R_last[i * n + i].null_flag) | ||
1635 | { | ||
1636 | R_last[i * n + i].slen = 0; | ||
1637 | R_last[i * n + i].null_flag = GNUNET_NO; | ||
1638 | } | ||
1629 | else | 1639 | else |
1630 | { | 1640 | { |
1631 | sb_append_cstr (&R_last[i * n + j], "|"); | 1641 | sb_wrap(&R_last[i * n + i], "(|%.*s)", 3); |
1632 | sb_append_cstr (&R_last[i * n + j], t->label); | 1642 | } |
1633 | } | ||
1634 | } | ||
1635 | /* add self-loop: i is reachable from i via epsilon-transition */ | ||
1636 | if (GNUNET_YES == R_last[i * n + i].null_flag) | ||
1637 | { | ||
1638 | R_last[i * n + i].slen = 0; | ||
1639 | R_last[i * n + i].null_flag = GNUNET_NO; | ||
1640 | } | ||
1641 | else | ||
1642 | { | ||
1643 | sb_wrap (&R_last[i * n + i], "(|%.*s)", 3); | ||
1644 | } | 1643 | } |
1645 | } | ||
1646 | for (i = 0; i < n; i++) | 1644 | for (i = 0; i < n; i++) |
1647 | for (j = 0; j < n; j++) | 1645 | for (j = 0; j < n; j++) |
1648 | if (needs_parentheses (&R_last[i * n + j])) | 1646 | if (needs_parentheses(&R_last[i * n + j])) |
1649 | sb_wrap (&R_last[i * n + j], "(%.*s)", 2); | 1647 | sb_wrap(&R_last[i * n + j], "(%.*s)", 2); |
1650 | /* Compute regular expressions of length "k" between each pair of states per | 1648 | /* Compute regular expressions of length "k" between each pair of states per |
1651 | * induction */ | 1649 | * induction */ |
1652 | memset (&R_cur_l, 0, sizeof (struct StringBuffer)); | 1650 | memset(&R_cur_l, 0, sizeof(struct StringBuffer)); |
1653 | memset (&R_cur_r, 0, sizeof (struct StringBuffer)); | 1651 | memset(&R_cur_r, 0, sizeof(struct StringBuffer)); |
1654 | for (k = 0; k < n; k++) | 1652 | for (k = 0; k < n; k++) |
1655 | { | ||
1656 | for (i = 0; i < n; i++) | ||
1657 | { | 1653 | { |
1658 | for (j = 0; j < n; j++) | 1654 | for (i = 0; i < n; i++) |
1659 | { | 1655 | { |
1660 | /* Basis for the recursion: | 1656 | for (j = 0; j < n; j++) |
1661 | * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} | 1657 | { |
1662 | * R_last == R^{(k-1)}, R_cur == R^{(k)} | 1658 | /* Basis for the recursion: |
1663 | */ | 1659 | * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} |
1664 | 1660 | * R_last == R^{(k-1)}, R_cur == R^{(k)} | |
1665 | /* Create R_cur[i][j] and simplify the expression */ | 1661 | */ |
1666 | automaton_create_proofs_simplify (&R_last[i * n + j], | 1662 | |
1667 | &R_last[i * n + k], | 1663 | /* Create R_cur[i][j] and simplify the expression */ |
1668 | &R_last[k * n + k], | 1664 | automaton_create_proofs_simplify(&R_last[i * n + j], |
1669 | &R_last[k * n + j], | 1665 | &R_last[i * n + k], |
1670 | &R_cur[i * n + j], | 1666 | &R_last[k * n + k], |
1671 | &R_cur_l, | 1667 | &R_last[k * n + j], |
1672 | &R_cur_r); | 1668 | &R_cur[i * n + j], |
1673 | } | 1669 | &R_cur_l, |
1670 | &R_cur_r); | ||
1671 | } | ||
1672 | } | ||
1673 | /* set R_last = R_cur */ | ||
1674 | R_swap = R_last; | ||
1675 | R_last = R_cur; | ||
1676 | R_cur = R_swap; | ||
1677 | /* clear 'R_cur' for next iteration */ | ||
1678 | for (i = 0; i < n; i++) | ||
1679 | for (j = 0; j < n; j++) | ||
1680 | R_cur[i * n + j].null_flag = GNUNET_YES; | ||
1674 | } | 1681 | } |
1675 | /* set R_last = R_cur */ | 1682 | sb_free(&R_cur_l); |
1676 | R_swap = R_last; | 1683 | sb_free(&R_cur_r); |
1677 | R_last = R_cur; | ||
1678 | R_cur = R_swap; | ||
1679 | /* clear 'R_cur' for next iteration */ | ||
1680 | for (i = 0; i < n; i++) | ||
1681 | for (j = 0; j < n; j++) | ||
1682 | R_cur[i * n + j].null_flag = GNUNET_YES; | ||
1683 | } | ||
1684 | sb_free (&R_cur_l); | ||
1685 | sb_free (&R_cur_r); | ||
1686 | /* assign proofs and hashes */ | 1684 | /* assign proofs and hashes */ |
1687 | for (i = 0; i < n; i++) | 1685 | for (i = 0; i < n; i++) |
1688 | { | ||
1689 | if (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) | ||
1690 | { | 1686 | { |
1691 | states[i]->proof = GNUNET_strndup (R_last[a->start->dfs_id * n + i].sbuf, | 1687 | if (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) |
1692 | R_last[a->start->dfs_id * n + i].slen); | 1688 | { |
1693 | GNUNET_CRYPTO_hash (states[i]->proof, | 1689 | states[i]->proof = GNUNET_strndup(R_last[a->start->dfs_id * n + i].sbuf, |
1694 | strlen (states[i]->proof), | 1690 | R_last[a->start->dfs_id * n + i].slen); |
1695 | &states[i]->hash); | 1691 | GNUNET_CRYPTO_hash(states[i]->proof, |
1692 | strlen(states[i]->proof), | ||
1693 | &states[i]->hash); | ||
1694 | } | ||
1696 | } | 1695 | } |
1697 | } | ||
1698 | 1696 | ||
1699 | /* complete regex for whole DFA: union of all pairs (start state/accepting | 1697 | /* complete regex for whole DFA: union of all pairs (start state/accepting |
1700 | * state(s)). */ | 1698 | * state(s)). */ |
1701 | sb_init (&complete_regex, 16 * n); | 1699 | sb_init(&complete_regex, 16 * n); |
1702 | for (i = 0; i < n; i++) | 1700 | for (i = 0; i < n; i++) |
1703 | { | ||
1704 | if (states[i]->accepting) | ||
1705 | { | 1701 | { |
1706 | if ((0 == complete_regex.slen) && | 1702 | if (states[i]->accepting) |
1707 | (0 < R_last[a->start->dfs_id * n + i].slen)) | 1703 | { |
1708 | { | 1704 | if ((0 == complete_regex.slen) && |
1709 | sb_append (&complete_regex, &R_last[a->start->dfs_id * n + i]); | 1705 | (0 < R_last[a->start->dfs_id * n + i].slen)) |
1710 | } | 1706 | { |
1711 | else if ((GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) && | 1707 | sb_append(&complete_regex, &R_last[a->start->dfs_id * n + i]); |
1712 | (0 < R_last[a->start->dfs_id * n + i].slen)) | 1708 | } |
1713 | { | 1709 | else if ((GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) && |
1714 | sb_append_cstr (&complete_regex, "|"); | 1710 | (0 < R_last[a->start->dfs_id * n + i].slen)) |
1715 | sb_append (&complete_regex, &R_last[a->start->dfs_id * n + i]); | 1711 | { |
1716 | } | 1712 | sb_append_cstr(&complete_regex, "|"); |
1713 | sb_append(&complete_regex, &R_last[a->start->dfs_id * n + i]); | ||
1714 | } | ||
1715 | } | ||
1717 | } | 1716 | } |
1718 | } | ||
1719 | a->canonical_regex = | 1717 | a->canonical_regex = |
1720 | GNUNET_strndup (complete_regex.sbuf, complete_regex.slen); | 1718 | GNUNET_strndup(complete_regex.sbuf, complete_regex.slen); |
1721 | 1719 | ||
1722 | /* cleanup */ | 1720 | /* cleanup */ |
1723 | sb_free (&complete_regex); | 1721 | sb_free(&complete_regex); |
1724 | for (i = 0; i < n; i++) | 1722 | for (i = 0; i < n; i++) |
1725 | for (j = 0; j < n; j++) | 1723 | for (j = 0; j < n; j++) |
1726 | { | 1724 | { |
1727 | sb_free (&R_cur[i * n + j]); | 1725 | sb_free(&R_cur[i * n + j]); |
1728 | sb_free (&R_last[i * n + j]); | 1726 | sb_free(&R_last[i * n + j]); |
1729 | } | 1727 | } |
1730 | GNUNET_free (R_cur); | 1728 | GNUNET_free(R_cur); |
1731 | GNUNET_free (R_last); | 1729 | GNUNET_free(R_last); |
1732 | return GNUNET_OK; | 1730 | return GNUNET_OK; |
1733 | } | 1731 | } |
1734 | 1732 | ||
@@ -1743,8 +1741,8 @@ automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a) | |||
1743 | * @return new DFA state | 1741 | * @return new DFA state |
1744 | */ | 1742 | */ |
1745 | static struct REGEX_INTERNAL_State * | 1743 | static struct REGEX_INTERNAL_State * |
1746 | dfa_state_create (struct REGEX_INTERNAL_Context *ctx, | 1744 | dfa_state_create(struct REGEX_INTERNAL_Context *ctx, |
1747 | struct REGEX_INTERNAL_StateSet *nfa_states) | 1745 | struct REGEX_INTERNAL_StateSet *nfa_states) |
1748 | { | 1746 | { |
1749 | struct REGEX_INTERNAL_State *s; | 1747 | struct REGEX_INTERNAL_State *s; |
1750 | char *pos; | 1748 | char *pos; |
@@ -1753,16 +1751,16 @@ dfa_state_create (struct REGEX_INTERNAL_Context *ctx, | |||
1753 | struct REGEX_INTERNAL_Transition *ctran; | 1751 | struct REGEX_INTERNAL_Transition *ctran; |
1754 | unsigned int i; | 1752 | unsigned int i; |
1755 | 1753 | ||
1756 | s = GNUNET_new (struct REGEX_INTERNAL_State); | 1754 | s = GNUNET_new(struct REGEX_INTERNAL_State); |
1757 | s->id = ctx->state_id++; | 1755 | s->id = ctx->state_id++; |
1758 | s->index = -1; | 1756 | s->index = -1; |
1759 | s->lowlink = -1; | 1757 | s->lowlink = -1; |
1760 | 1758 | ||
1761 | if (NULL == nfa_states) | 1759 | if (NULL == nfa_states) |
1762 | { | 1760 | { |
1763 | GNUNET_asprintf (&s->name, "s%i", s->id); | 1761 | GNUNET_asprintf(&s->name, "s%i", s->id); |
1764 | return s; | 1762 | return s; |
1765 | } | 1763 | } |
1766 | 1764 | ||
1767 | s->nfa_set = *nfa_states; | 1765 | s->nfa_set = *nfa_states; |
1768 | 1766 | ||
@@ -1771,30 +1769,30 @@ dfa_state_create (struct REGEX_INTERNAL_Context *ctx, | |||
1771 | 1769 | ||
1772 | /* Create a name based on 'nfa_states' */ | 1770 | /* Create a name based on 'nfa_states' */ |
1773 | len = nfa_states->off * 14 + 4; | 1771 | len = nfa_states->off * 14 + 4; |
1774 | s->name = GNUNET_malloc (len); | 1772 | s->name = GNUNET_malloc(len); |
1775 | strcat (s->name, "{"); | 1773 | strcat(s->name, "{"); |
1776 | pos = s->name + 1; | 1774 | pos = s->name + 1; |
1777 | 1775 | ||
1778 | for (i = 0; i < nfa_states->off; i++) | 1776 | for (i = 0; i < nfa_states->off; i++) |
1779 | { | 1777 | { |
1780 | cstate = nfa_states->states[i]; | 1778 | cstate = nfa_states->states[i]; |
1781 | GNUNET_snprintf (pos, pos - s->name + len, "%i,", cstate->id); | 1779 | GNUNET_snprintf(pos, pos - s->name + len, "%i,", cstate->id); |
1782 | pos += strlen (pos); | 1780 | pos += strlen(pos); |
1783 | 1781 | ||
1784 | /* Add a transition for each distinct label to NULL state */ | 1782 | /* Add a transition for each distinct label to NULL state */ |
1785 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) | 1783 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) |
1786 | if (NULL != ctran->label) | 1784 | if (NULL != ctran->label) |
1787 | state_add_transition (ctx, s, ctran->label, NULL); | 1785 | state_add_transition(ctx, s, ctran->label, NULL); |
1788 | 1786 | ||
1789 | /* If the nfa_states contain an accepting state, the new dfa state is also | 1787 | /* If the nfa_states contain an accepting state, the new dfa state is also |
1790 | * accepting. */ | 1788 | * accepting. */ |
1791 | if (cstate->accepting) | 1789 | if (cstate->accepting) |
1792 | s->accepting = 1; | 1790 | s->accepting = 1; |
1793 | } | 1791 | } |
1794 | pos[-1] = '}'; | 1792 | pos[-1] = '}'; |
1795 | s->name = GNUNET_realloc (s->name, strlen (s->name) + 1); | 1793 | s->name = GNUNET_realloc(s->name, strlen(s->name) + 1); |
1796 | 1794 | ||
1797 | memset (nfa_states, 0, sizeof (struct REGEX_INTERNAL_StateSet)); | 1795 | memset(nfa_states, 0, sizeof(struct REGEX_INTERNAL_StateSet)); |
1798 | return s; | 1796 | return s; |
1799 | } | 1797 | } |
1800 | 1798 | ||
@@ -1813,7 +1811,7 @@ dfa_state_create (struct REGEX_INTERNAL_Context *ctx, | |||
1813 | * @return length of the substring comsumed from 'str' | 1811 | * @return length of the substring comsumed from 'str' |
1814 | */ | 1812 | */ |
1815 | static unsigned int | 1813 | static unsigned int |
1816 | dfa_move (struct REGEX_INTERNAL_State **s, const char *str) | 1814 | dfa_move(struct REGEX_INTERNAL_State **s, const char *str) |
1817 | { | 1815 | { |
1818 | struct REGEX_INTERNAL_Transition *t; | 1816 | struct REGEX_INTERNAL_Transition *t; |
1819 | struct REGEX_INTERNAL_State *new_s; | 1817 | struct REGEX_INTERNAL_State *new_s; |
@@ -1826,18 +1824,18 @@ dfa_move (struct REGEX_INTERNAL_State **s, const char *str) | |||
1826 | new_s = NULL; | 1824 | new_s = NULL; |
1827 | max_len = 0; | 1825 | max_len = 0; |
1828 | for (t = (*s)->transitions_head; NULL != t; t = t->next) | 1826 | for (t = (*s)->transitions_head; NULL != t; t = t->next) |
1829 | { | ||
1830 | len = strlen (t->label); | ||
1831 | |||
1832 | if (0 == strncmp (t->label, str, len)) | ||
1833 | { | 1827 | { |
1834 | if (len >= max_len) | 1828 | len = strlen(t->label); |
1835 | { | 1829 | |
1836 | max_len = len; | 1830 | if (0 == strncmp(t->label, str, len)) |
1837 | new_s = t->to_state; | 1831 | { |
1838 | } | 1832 | if (len >= max_len) |
1833 | { | ||
1834 | max_len = len; | ||
1835 | new_s = t->to_state; | ||
1836 | } | ||
1837 | } | ||
1839 | } | 1838 | } |
1840 | } | ||
1841 | 1839 | ||
1842 | *s = new_s; | 1840 | *s = new_s; |
1843 | return max_len; | 1841 | return max_len; |
@@ -1854,9 +1852,9 @@ dfa_move (struct REGEX_INTERNAL_State **s, const char *str) | |||
1854 | * @param s state where the marked attribute will be set to #GNUNET_YES. | 1852 | * @param s state where the marked attribute will be set to #GNUNET_YES. |
1855 | */ | 1853 | */ |
1856 | static void | 1854 | static void |
1857 | mark_states (void *cls, | 1855 | mark_states(void *cls, |
1858 | const unsigned int count, | 1856 | const unsigned int count, |
1859 | struct REGEX_INTERNAL_State *s) | 1857 | struct REGEX_INTERNAL_State *s) |
1860 | { | 1858 | { |
1861 | s->marked = GNUNET_YES; | 1859 | s->marked = GNUNET_YES; |
1862 | } | 1860 | } |
@@ -1869,7 +1867,7 @@ mark_states (void *cls, | |||
1869 | * @param a DFA automaton | 1867 | * @param a DFA automaton |
1870 | */ | 1868 | */ |
1871 | static void | 1869 | static void |
1872 | dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a) | 1870 | dfa_remove_unreachable_states(struct REGEX_INTERNAL_Automaton *a) |
1873 | { | 1871 | { |
1874 | struct REGEX_INTERNAL_State *s; | 1872 | struct REGEX_INTERNAL_State *s; |
1875 | struct REGEX_INTERNAL_State *s_next; | 1873 | struct REGEX_INTERNAL_State *s_next; |
@@ -1879,20 +1877,20 @@ dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a) | |||
1879 | s->marked = GNUNET_NO; | 1877 | s->marked = GNUNET_NO; |
1880 | 1878 | ||
1881 | /* 2. traverse dfa from start state and mark all visited states */ | 1879 | /* 2. traverse dfa from start state and mark all visited states */ |
1882 | REGEX_INTERNAL_automaton_traverse (a, | 1880 | REGEX_INTERNAL_automaton_traverse(a, |
1883 | a->start, | 1881 | a->start, |
1884 | NULL, | 1882 | NULL, |
1885 | NULL, | 1883 | NULL, |
1886 | &mark_states, | 1884 | &mark_states, |
1887 | NULL); | 1885 | NULL); |
1888 | 1886 | ||
1889 | /* 3. delete all states that were not visited */ | 1887 | /* 3. delete all states that were not visited */ |
1890 | for (s = a->states_head; NULL != s; s = s_next) | 1888 | for (s = a->states_head; NULL != s; s = s_next) |
1891 | { | 1889 | { |
1892 | s_next = s->next; | 1890 | s_next = s->next; |
1893 | if (GNUNET_NO == s->marked) | 1891 | if (GNUNET_NO == s->marked) |
1894 | automaton_remove_state (a, s); | 1892 | automaton_remove_state(a, s); |
1895 | } | 1893 | } |
1896 | } | 1894 | } |
1897 | 1895 | ||
1898 | 1896 | ||
@@ -1903,38 +1901,38 @@ dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a) | |||
1903 | * @param a DFA automaton | 1901 | * @param a DFA automaton |
1904 | */ | 1902 | */ |
1905 | static void | 1903 | static void |
1906 | dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a) | 1904 | dfa_remove_dead_states(struct REGEX_INTERNAL_Automaton *a) |
1907 | { | 1905 | { |
1908 | struct REGEX_INTERNAL_State *s; | 1906 | struct REGEX_INTERNAL_State *s; |
1909 | struct REGEX_INTERNAL_State *s_next; | 1907 | struct REGEX_INTERNAL_State *s_next; |
1910 | struct REGEX_INTERNAL_Transition *t; | 1908 | struct REGEX_INTERNAL_Transition *t; |
1911 | int dead; | 1909 | int dead; |
1912 | 1910 | ||
1913 | GNUNET_assert (DFA == a->type); | 1911 | GNUNET_assert(DFA == a->type); |
1914 | 1912 | ||
1915 | for (s = a->states_head; NULL != s; s = s_next) | 1913 | for (s = a->states_head; NULL != s; s = s_next) |
1916 | { | 1914 | { |
1917 | s_next = s->next; | 1915 | s_next = s->next; |
1918 | 1916 | ||
1919 | if (s->accepting) | 1917 | if (s->accepting) |
1920 | continue; | 1918 | continue; |
1921 | 1919 | ||
1922 | dead = 1; | 1920 | dead = 1; |
1923 | for (t = s->transitions_head; NULL != t; t = t->next) | 1921 | for (t = s->transitions_head; NULL != t; t = t->next) |
1924 | { | 1922 | { |
1925 | if (NULL != t->to_state && t->to_state != s) | 1923 | if (NULL != t->to_state && t->to_state != s) |
1926 | { | 1924 | { |
1927 | dead = 0; | 1925 | dead = 0; |
1928 | break; | 1926 | break; |
1929 | } | 1927 | } |
1930 | } | 1928 | } |
1931 | 1929 | ||
1932 | if (0 == dead) | 1930 | if (0 == dead) |
1933 | continue; | 1931 | continue; |
1934 | 1932 | ||
1935 | /* state s is dead, remove it */ | 1933 | /* state s is dead, remove it */ |
1936 | automaton_remove_state (a, s); | 1934 | automaton_remove_state(a, s); |
1937 | } | 1935 | } |
1938 | } | 1936 | } |
1939 | 1937 | ||
1940 | 1938 | ||
@@ -1946,8 +1944,8 @@ dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a) | |||
1946 | * @return #GNUNET_OK on success | 1944 | * @return #GNUNET_OK on success |
1947 | */ | 1945 | */ |
1948 | static int | 1946 | static int |
1949 | dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx, | 1947 | dfa_merge_nondistinguishable_states(struct REGEX_INTERNAL_Context *ctx, |
1950 | struct REGEX_INTERNAL_Automaton *a) | 1948 | struct REGEX_INTERNAL_Automaton *a) |
1951 | { | 1949 | { |
1952 | uint32_t *table; | 1950 | uint32_t *table; |
1953 | struct REGEX_INTERNAL_State *s1; | 1951 | struct REGEX_INTERNAL_State *s1; |
@@ -1964,20 +1962,20 @@ dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx, | |||
1964 | unsigned long long idx1; | 1962 | unsigned long long idx1; |
1965 | 1963 | ||
1966 | if ((NULL == a) || (0 == a->state_count)) | 1964 | if ((NULL == a) || (0 == a->state_count)) |
1967 | { | 1965 | { |
1968 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 1966 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
1969 | "Could not merge nondistinguishable states, automaton was NULL.\n"); | 1967 | "Could not merge nondistinguishable states, automaton was NULL.\n"); |
1970 | return GNUNET_SYSERR; | 1968 | return GNUNET_SYSERR; |
1971 | } | 1969 | } |
1972 | 1970 | ||
1973 | state_cnt = a->state_count; | 1971 | state_cnt = a->state_count; |
1974 | table = GNUNET_malloc_large ( | 1972 | table = GNUNET_malloc_large( |
1975 | (sizeof (uint32_t) * state_cnt * state_cnt / 32) + sizeof (uint32_t)); | 1973 | (sizeof(uint32_t) * state_cnt * state_cnt / 32) + sizeof(uint32_t)); |
1976 | if (NULL == table) | 1974 | if (NULL == table) |
1977 | { | 1975 | { |
1978 | GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc"); | 1976 | GNUNET_log_strerror(GNUNET_ERROR_TYPE_ERROR, "malloc"); |
1979 | return GNUNET_SYSERR; | 1977 | return GNUNET_SYSERR; |
1980 | } | 1978 | } |
1981 | 1979 | ||
1982 | for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next) | 1980 | for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next) |
1983 | s1->marked = i++; | 1981 | s1->marked = i++; |
@@ -1985,74 +1983,74 @@ dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx, | |||
1985 | /* Mark all pairs of accepting/!accepting states */ | 1983 | /* Mark all pairs of accepting/!accepting states */ |
1986 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) | 1984 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) |
1987 | for (s2 = a->states_head; NULL != s2; s2 = s2->next) | 1985 | for (s2 = a->states_head; NULL != s2; s2 = s2->next) |
1988 | if ((s1->accepting && ! s2->accepting) || | 1986 | if ((s1->accepting && !s2->accepting) || |
1989 | (! s1->accepting && s2->accepting)) | 1987 | (!s1->accepting && s2->accepting)) |
1990 | { | 1988 | { |
1991 | idx = (unsigned long long) s1->marked * state_cnt + s2->marked; | 1989 | idx = (unsigned long long)s1->marked * state_cnt + s2->marked; |
1992 | table[idx / 32] |= (1U << (idx % 32)); | 1990 | table[idx / 32] |= (1U << (idx % 32)); |
1993 | } | 1991 | } |
1994 | 1992 | ||
1995 | /* Find all equal states */ | 1993 | /* Find all equal states */ |
1996 | change = 1; | 1994 | change = 1; |
1997 | while (0 != change) | 1995 | while (0 != change) |
1998 | { | ||
1999 | change = 0; | ||
2000 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) | ||
2001 | { | 1996 | { |
2002 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next) | 1997 | change = 0; |
2003 | { | 1998 | for (s1 = a->states_head; NULL != s1; s1 = s1->next) |
2004 | idx = (unsigned long long) s1->marked * state_cnt + s2->marked; | ||
2005 | if (0 != (table[idx / 32] & (1U << (idx % 32)))) | ||
2006 | continue; | ||
2007 | num_equal_edges = 0; | ||
2008 | for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next) | ||
2009 | { | 1999 | { |
2010 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) | 2000 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next) |
2011 | { | ||
2012 | if (0 == strcmp (t1->label, t2->label)) | ||
2013 | { | 2001 | { |
2014 | num_equal_edges++; | 2002 | idx = (unsigned long long)s1->marked * state_cnt + s2->marked; |
2015 | /* same edge, but targets definitively different, so we're different | 2003 | if (0 != (table[idx / 32] & (1U << (idx % 32)))) |
2016 | as well */ | 2004 | continue; |
2017 | if (t1->to_state->marked > t2->to_state->marked) | 2005 | num_equal_edges = 0; |
2018 | idx1 = (unsigned long long) t1->to_state->marked * state_cnt + | 2006 | for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next) |
2019 | t2->to_state->marked; | 2007 | { |
2020 | else | 2008 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) |
2021 | idx1 = (unsigned long long) t2->to_state->marked * state_cnt + | 2009 | { |
2022 | t1->to_state->marked; | 2010 | if (0 == strcmp(t1->label, t2->label)) |
2023 | if (0 != (table[idx1 / 32] & (1U << (idx1 % 32)))) | 2011 | { |
2024 | { | 2012 | num_equal_edges++; |
2025 | table[idx / 32] |= (1U << (idx % 32)); | 2013 | /* same edge, but targets definitively different, so we're different |
2026 | change = 1; /* changed a marker, need to run again */ | 2014 | as well */ |
2027 | } | 2015 | if (t1->to_state->marked > t2->to_state->marked) |
2016 | idx1 = (unsigned long long)t1->to_state->marked * state_cnt + | ||
2017 | t2->to_state->marked; | ||
2018 | else | ||
2019 | idx1 = (unsigned long long)t2->to_state->marked * state_cnt + | ||
2020 | t1->to_state->marked; | ||
2021 | if (0 != (table[idx1 / 32] & (1U << (idx1 % 32)))) | ||
2022 | { | ||
2023 | table[idx / 32] |= (1U << (idx % 32)); | ||
2024 | change = 1; /* changed a marker, need to run again */ | ||
2025 | } | ||
2026 | } | ||
2027 | } | ||
2028 | } | ||
2029 | if ((num_equal_edges != s1->transition_count) || | ||
2030 | (num_equal_edges != s2->transition_count)) | ||
2031 | { | ||
2032 | /* Make sure ALL edges of possible equal states are the same */ | ||
2033 | table[idx / 32] |= (1U << (idx % 32)); | ||
2034 | change = 1; /* changed a marker, need to run again */ | ||
2035 | } | ||
2028 | } | 2036 | } |
2029 | } | ||
2030 | } | 2037 | } |
2031 | if ((num_equal_edges != s1->transition_count) || | ||
2032 | (num_equal_edges != s2->transition_count)) | ||
2033 | { | ||
2034 | /* Make sure ALL edges of possible equal states are the same */ | ||
2035 | table[idx / 32] |= (1U << (idx % 32)); | ||
2036 | change = 1; /* changed a marker, need to run again */ | ||
2037 | } | ||
2038 | } | ||
2039 | } | 2038 | } |
2040 | } | ||
2041 | 2039 | ||
2042 | /* Merge states that are equal */ | 2040 | /* Merge states that are equal */ |
2043 | for (s1 = a->states_head; NULL != s1; s1 = s1_next) | 2041 | for (s1 = a->states_head; NULL != s1; s1 = s1_next) |
2044 | { | ||
2045 | s1_next = s1->next; | ||
2046 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next) | ||
2047 | { | 2042 | { |
2048 | s2_next = s2->next; | 2043 | s1_next = s1->next; |
2049 | idx = (unsigned long long) s1->marked * state_cnt + s2->marked; | 2044 | for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next) |
2050 | if (0 == (table[idx / 32] & (1U << (idx % 32)))) | 2045 | { |
2051 | automaton_merge_states (ctx, a, s1, s2); | 2046 | s2_next = s2->next; |
2047 | idx = (unsigned long long)s1->marked * state_cnt + s2->marked; | ||
2048 | if (0 == (table[idx / 32] & (1U << (idx % 32)))) | ||
2049 | automaton_merge_states(ctx, a, s1, s2); | ||
2050 | } | ||
2052 | } | 2051 | } |
2053 | } | ||
2054 | 2052 | ||
2055 | GNUNET_free (table); | 2053 | GNUNET_free(table); |
2056 | return GNUNET_OK; | 2054 | return GNUNET_OK; |
2057 | } | 2055 | } |
2058 | 2056 | ||
@@ -2066,22 +2064,22 @@ dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx, | |||
2066 | * @return GNUNET_OK on success | 2064 | * @return GNUNET_OK on success |
2067 | */ | 2065 | */ |
2068 | static int | 2066 | static int |
2069 | dfa_minimize (struct REGEX_INTERNAL_Context *ctx, | 2067 | dfa_minimize(struct REGEX_INTERNAL_Context *ctx, |
2070 | struct REGEX_INTERNAL_Automaton *a) | 2068 | struct REGEX_INTERNAL_Automaton *a) |
2071 | { | 2069 | { |
2072 | if (NULL == a) | 2070 | if (NULL == a) |
2073 | return GNUNET_SYSERR; | 2071 | return GNUNET_SYSERR; |
2074 | 2072 | ||
2075 | GNUNET_assert (DFA == a->type); | 2073 | GNUNET_assert(DFA == a->type); |
2076 | 2074 | ||
2077 | /* 1. remove unreachable states */ | 2075 | /* 1. remove unreachable states */ |
2078 | dfa_remove_unreachable_states (a); | 2076 | dfa_remove_unreachable_states(a); |
2079 | 2077 | ||
2080 | /* 2. remove dead states */ | 2078 | /* 2. remove dead states */ |
2081 | dfa_remove_dead_states (a); | 2079 | dfa_remove_dead_states(a); |
2082 | 2080 | ||
2083 | /* 3. Merge nondistinguishable states */ | 2081 | /* 3. Merge nondistinguishable states */ |
2084 | if (GNUNET_OK != dfa_merge_nondistinguishable_states (ctx, a)) | 2082 | if (GNUNET_OK != dfa_merge_nondistinguishable_states(ctx, a)) |
2085 | return GNUNET_SYSERR; | 2083 | return GNUNET_SYSERR; |
2086 | return GNUNET_OK; | 2084 | return GNUNET_OK; |
2087 | } | 2085 | } |
@@ -2090,8 +2088,7 @@ dfa_minimize (struct REGEX_INTERNAL_Context *ctx, | |||
2090 | /** | 2088 | /** |
2091 | * Context for adding strided transitions to a DFA. | 2089 | * Context for adding strided transitions to a DFA. |
2092 | */ | 2090 | */ |
2093 | struct REGEX_INTERNAL_Strided_Context | 2091 | struct REGEX_INTERNAL_Strided_Context { |
2094 | { | ||
2095 | /** | 2092 | /** |
2096 | * Length of the strides. | 2093 | * Length of the strides. |
2097 | */ | 2094 | */ |
@@ -2121,50 +2118,50 @@ struct REGEX_INTERNAL_Strided_Context | |||
2121 | * @param s current state in the depth-first traversal | 2118 | * @param s current state in the depth-first traversal |
2122 | */ | 2119 | */ |
2123 | static void | 2120 | static void |
2124 | dfa_add_multi_strides_helper (void *cls, | 2121 | dfa_add_multi_strides_helper(void *cls, |
2125 | const unsigned int depth, | 2122 | const unsigned int depth, |
2126 | char *label, | 2123 | char *label, |
2127 | struct REGEX_INTERNAL_State *start, | 2124 | struct REGEX_INTERNAL_State *start, |
2128 | struct REGEX_INTERNAL_State *s) | 2125 | struct REGEX_INTERNAL_State *s) |
2129 | { | 2126 | { |
2130 | struct REGEX_INTERNAL_Strided_Context *ctx = cls; | 2127 | struct REGEX_INTERNAL_Strided_Context *ctx = cls; |
2131 | struct REGEX_INTERNAL_Transition *t; | 2128 | struct REGEX_INTERNAL_Transition *t; |
2132 | char *new_label; | 2129 | char *new_label; |
2133 | 2130 | ||
2134 | if (depth == ctx->stride) | 2131 | if (depth == ctx->stride) |
2135 | { | 2132 | { |
2136 | t = GNUNET_new (struct REGEX_INTERNAL_Transition); | 2133 | t = GNUNET_new(struct REGEX_INTERNAL_Transition); |
2137 | t->label = GNUNET_strdup (label); | 2134 | t->label = GNUNET_strdup(label); |
2138 | t->to_state = s; | 2135 | t->to_state = s; |
2139 | t->from_state = start; | 2136 | t->from_state = start; |
2140 | GNUNET_CONTAINER_DLL_insert (ctx->transitions_head, | 2137 | GNUNET_CONTAINER_DLL_insert(ctx->transitions_head, |
2141 | ctx->transitions_tail, | 2138 | ctx->transitions_tail, |
2142 | t); | 2139 | t); |
2143 | } | 2140 | } |
2144 | else | 2141 | else |
2145 | { | ||
2146 | for (t = s->transitions_head; NULL != t; t = t->next) | ||
2147 | { | 2142 | { |
2148 | /* Do not consider self-loops, because it end's up in too many | 2143 | for (t = s->transitions_head; NULL != t; t = t->next) |
2149 | * transitions */ | 2144 | { |
2150 | if (t->to_state == t->from_state) | 2145 | /* Do not consider self-loops, because it end's up in too many |
2151 | continue; | 2146 | * transitions */ |
2147 | if (t->to_state == t->from_state) | ||
2148 | continue; | ||
2152 | 2149 | ||
2153 | if (NULL != label) | 2150 | if (NULL != label) |
2154 | { | 2151 | { |
2155 | GNUNET_asprintf (&new_label, "%s%s", label, t->label); | 2152 | GNUNET_asprintf(&new_label, "%s%s", label, t->label); |
2156 | } | 2153 | } |
2157 | else | 2154 | else |
2158 | new_label = GNUNET_strdup (t->label); | 2155 | new_label = GNUNET_strdup(t->label); |
2159 | 2156 | ||
2160 | dfa_add_multi_strides_helper (cls, | 2157 | dfa_add_multi_strides_helper(cls, |
2161 | (depth + 1), | 2158 | (depth + 1), |
2162 | new_label, | 2159 | new_label, |
2163 | start, | 2160 | start, |
2164 | t->to_state); | 2161 | t->to_state); |
2162 | } | ||
2165 | } | 2163 | } |
2166 | } | 2164 | GNUNET_free_non_null(label); |
2167 | GNUNET_free_non_null (label); | ||
2168 | } | 2165 | } |
2169 | 2166 | ||
2170 | 2167 | ||
@@ -2177,11 +2174,11 @@ dfa_add_multi_strides_helper (void *cls, | |||
2177 | * @param s current state. | 2174 | * @param s current state. |
2178 | */ | 2175 | */ |
2179 | static void | 2176 | static void |
2180 | dfa_add_multi_strides (void *cls, | 2177 | dfa_add_multi_strides(void *cls, |
2181 | const unsigned int count, | 2178 | const unsigned int count, |
2182 | struct REGEX_INTERNAL_State *s) | 2179 | struct REGEX_INTERNAL_State *s) |
2183 | { | 2180 | { |
2184 | dfa_add_multi_strides_helper (cls, 0, NULL, s, s); | 2181 | dfa_add_multi_strides_helper(cls, 0, NULL, s, s); |
2185 | } | 2182 | } |
2186 | 2183 | ||
2187 | 2184 | ||
@@ -2193,11 +2190,11 @@ dfa_add_multi_strides (void *cls, | |||
2193 | * @param stride_len length of the strides. | 2190 | * @param stride_len length of the strides. |
2194 | */ | 2191 | */ |
2195 | void | 2192 | void |
2196 | REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx, | 2193 | REGEX_INTERNAL_dfa_add_multi_strides(struct REGEX_INTERNAL_Context *regex_ctx, |
2197 | struct REGEX_INTERNAL_Automaton *dfa, | 2194 | struct REGEX_INTERNAL_Automaton *dfa, |
2198 | const unsigned int stride_len) | 2195 | const unsigned int stride_len) |
2199 | { | 2196 | { |
2200 | struct REGEX_INTERNAL_Strided_Context ctx = {stride_len, NULL, NULL}; | 2197 | struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL }; |
2201 | struct REGEX_INTERNAL_Transition *t; | 2198 | struct REGEX_INTERNAL_Transition *t; |
2202 | struct REGEX_INTERNAL_Transition *t_next; | 2199 | struct REGEX_INTERNAL_Transition *t_next; |
2203 | 2200 | ||
@@ -2205,22 +2202,22 @@ REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx, | |||
2205 | return; | 2202 | return; |
2206 | 2203 | ||
2207 | /* Compute the new transitions of given stride_len */ | 2204 | /* Compute the new transitions of given stride_len */ |
2208 | REGEX_INTERNAL_automaton_traverse (dfa, | 2205 | REGEX_INTERNAL_automaton_traverse(dfa, |
2209 | dfa->start, | 2206 | dfa->start, |
2210 | NULL, | 2207 | NULL, |
2211 | NULL, | 2208 | NULL, |
2212 | &dfa_add_multi_strides, | 2209 | &dfa_add_multi_strides, |
2213 | &ctx); | 2210 | &ctx); |
2214 | 2211 | ||
2215 | /* Add all the new transitions to the automaton. */ | 2212 | /* Add all the new transitions to the automaton. */ |
2216 | for (t = ctx.transitions_head; NULL != t; t = t_next) | 2213 | for (t = ctx.transitions_head; NULL != t; t = t_next) |
2217 | { | 2214 | { |
2218 | t_next = t->next; | 2215 | t_next = t->next; |
2219 | state_add_transition (regex_ctx, t->from_state, t->label, t->to_state); | 2216 | state_add_transition(regex_ctx, t->from_state, t->label, t->to_state); |
2220 | GNUNET_CONTAINER_DLL_remove (ctx.transitions_head, ctx.transitions_tail, t); | 2217 | GNUNET_CONTAINER_DLL_remove(ctx.transitions_head, ctx.transitions_tail, t); |
2221 | GNUNET_free_non_null (t->label); | 2218 | GNUNET_free_non_null(t->label); |
2222 | GNUNET_free (t); | 2219 | GNUNET_free(t); |
2223 | } | 2220 | } |
2224 | 2221 | ||
2225 | /* Mark this automaton as multistrided */ | 2222 | /* Mark this automaton as multistrided */ |
2226 | dfa->is_multistrided = GNUNET_YES; | 2223 | dfa->is_multistrided = GNUNET_YES; |
@@ -2240,13 +2237,13 @@ REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx, | |||
2240 | * @param transitions_tail transitions DLL. | 2237 | * @param transitions_tail transitions DLL. |
2241 | */ | 2238 | */ |
2242 | void | 2239 | void |
2243 | dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa, | 2240 | dfa_compress_paths_helper(struct REGEX_INTERNAL_Automaton *dfa, |
2244 | struct REGEX_INTERNAL_State *start, | 2241 | struct REGEX_INTERNAL_State *start, |
2245 | struct REGEX_INTERNAL_State *cur, | 2242 | struct REGEX_INTERNAL_State *cur, |
2246 | char *label, | 2243 | char *label, |
2247 | unsigned int max_len, | 2244 | unsigned int max_len, |
2248 | struct REGEX_INTERNAL_Transition **transitions_head, | 2245 | struct REGEX_INTERNAL_Transition **transitions_head, |
2249 | struct REGEX_INTERNAL_Transition **transitions_tail) | 2246 | struct REGEX_INTERNAL_Transition **transitions_tail) |
2250 | { | 2247 | { |
2251 | struct REGEX_INTERNAL_Transition *t; | 2248 | struct REGEX_INTERNAL_Transition *t; |
2252 | char *new_label; | 2249 | char *new_label; |
@@ -2255,27 +2252,27 @@ dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa, | |||
2255 | if (NULL != label && | 2252 | if (NULL != label && |
2256 | ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting || | 2253 | ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting || |
2257 | GNUNET_YES == cur->marked) || | 2254 | GNUNET_YES == cur->marked) || |
2258 | (start != dfa->start && max_len > 0 && max_len == strlen (label)) || | 2255 | (start != dfa->start && max_len > 0 && max_len == strlen(label)) || |
2259 | (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label)))) | 2256 | (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen(label)))) |
2260 | { | 2257 | { |
2261 | t = GNUNET_new (struct REGEX_INTERNAL_Transition); | 2258 | t = GNUNET_new(struct REGEX_INTERNAL_Transition); |
2262 | t->label = GNUNET_strdup (label); | 2259 | t->label = GNUNET_strdup(label); |
2263 | t->to_state = cur; | 2260 | t->to_state = cur; |
2264 | t->from_state = start; | 2261 | t->from_state = start; |
2265 | GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t); | 2262 | GNUNET_CONTAINER_DLL_insert(*transitions_head, *transitions_tail, t); |
2266 | 2263 | ||
2267 | if (GNUNET_NO == cur->marked) | 2264 | if (GNUNET_NO == cur->marked) |
2268 | { | 2265 | { |
2269 | dfa_compress_paths_helper (dfa, | 2266 | dfa_compress_paths_helper(dfa, |
2270 | cur, | 2267 | cur, |
2271 | cur, | 2268 | cur, |
2272 | NULL, | 2269 | NULL, |
2273 | max_len, | 2270 | max_len, |
2274 | transitions_head, | 2271 | transitions_head, |
2275 | transitions_tail); | 2272 | transitions_tail); |
2273 | } | ||
2274 | return; | ||
2276 | } | 2275 | } |
2277 | return; | ||
2278 | } | ||
2279 | else if (cur != start) | 2276 | else if (cur != start) |
2280 | cur->contained = GNUNET_YES; | 2277 | cur->contained = GNUNET_YES; |
2281 | 2278 | ||
@@ -2286,24 +2283,24 @@ dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa, | |||
2286 | 2283 | ||
2287 | 2284 | ||
2288 | for (t = cur->transitions_head; NULL != t; t = t->next) | 2285 | for (t = cur->transitions_head; NULL != t; t = t->next) |
2289 | { | ||
2290 | if (NULL != label) | ||
2291 | GNUNET_asprintf (&new_label, "%s%s", label, t->label); | ||
2292 | else | ||
2293 | new_label = GNUNET_strdup (t->label); | ||
2294 | |||
2295 | if (t->to_state != cur) | ||
2296 | { | 2286 | { |
2297 | dfa_compress_paths_helper (dfa, | 2287 | if (NULL != label) |
2298 | start, | 2288 | GNUNET_asprintf(&new_label, "%s%s", label, t->label); |
2299 | t->to_state, | 2289 | else |
2300 | new_label, | 2290 | new_label = GNUNET_strdup(t->label); |
2301 | max_len, | 2291 | |
2302 | transitions_head, | 2292 | if (t->to_state != cur) |
2303 | transitions_tail); | 2293 | { |
2294 | dfa_compress_paths_helper(dfa, | ||
2295 | start, | ||
2296 | t->to_state, | ||
2297 | new_label, | ||
2298 | max_len, | ||
2299 | transitions_head, | ||
2300 | transitions_tail); | ||
2301 | } | ||
2302 | GNUNET_free(new_label); | ||
2304 | } | 2303 | } |
2305 | GNUNET_free (new_label); | ||
2306 | } | ||
2307 | } | 2304 | } |
2308 | 2305 | ||
2309 | 2306 | ||
@@ -2316,9 +2313,9 @@ dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa, | |||
2316 | * @param max_len maximal length of the compressed paths. | 2313 | * @param max_len maximal length of the compressed paths. |
2317 | */ | 2314 | */ |
2318 | static void | 2315 | static void |
2319 | dfa_compress_paths (struct REGEX_INTERNAL_Context *regex_ctx, | 2316 | dfa_compress_paths(struct REGEX_INTERNAL_Context *regex_ctx, |
2320 | struct REGEX_INTERNAL_Automaton *dfa, | 2317 | struct REGEX_INTERNAL_Automaton *dfa, |
2321 | unsigned int max_len) | 2318 | unsigned int max_len) |
2322 | { | 2319 | { |
2323 | struct REGEX_INTERNAL_State *s; | 2320 | struct REGEX_INTERNAL_State *s; |
2324 | struct REGEX_INTERNAL_State *s_next; | 2321 | struct REGEX_INTERNAL_State *s_next; |
@@ -2332,47 +2329,47 @@ dfa_compress_paths (struct REGEX_INTERNAL_Context *regex_ctx, | |||
2332 | 2329 | ||
2333 | /* Count the incoming transitions on each state. */ | 2330 | /* Count the incoming transitions on each state. */ |
2334 | for (s = dfa->states_head; NULL != s; s = s->next) | 2331 | for (s = dfa->states_head; NULL != s; s = s->next) |
2335 | { | ||
2336 | for (t = s->transitions_head; NULL != t; t = t->next) | ||
2337 | { | 2332 | { |
2338 | if (NULL != t->to_state) | 2333 | for (t = s->transitions_head; NULL != t; t = t->next) |
2339 | t->to_state->incoming_transition_count++; | 2334 | { |
2335 | if (NULL != t->to_state) | ||
2336 | t->to_state->incoming_transition_count++; | ||
2337 | } | ||
2340 | } | 2338 | } |
2341 | } | ||
2342 | 2339 | ||
2343 | /* Unmark all states. */ | 2340 | /* Unmark all states. */ |
2344 | for (s = dfa->states_head; NULL != s; s = s->next) | 2341 | for (s = dfa->states_head; NULL != s; s = s->next) |
2345 | { | 2342 | { |
2346 | s->marked = GNUNET_NO; | 2343 | s->marked = GNUNET_NO; |
2347 | s->contained = GNUNET_NO; | 2344 | s->contained = GNUNET_NO; |
2348 | } | 2345 | } |
2349 | 2346 | ||
2350 | /* Add strides and mark states that can be deleted. */ | 2347 | /* Add strides and mark states that can be deleted. */ |
2351 | dfa_compress_paths_helper (dfa, | 2348 | dfa_compress_paths_helper(dfa, |
2352 | dfa->start, | 2349 | dfa->start, |
2353 | dfa->start, | 2350 | dfa->start, |
2354 | NULL, | 2351 | NULL, |
2355 | max_len, | 2352 | max_len, |
2356 | &transitions_head, | 2353 | &transitions_head, |
2357 | &transitions_tail); | 2354 | &transitions_tail); |
2358 | 2355 | ||
2359 | /* Add all the new transitions to the automaton. */ | 2356 | /* Add all the new transitions to the automaton. */ |
2360 | for (t = transitions_head; NULL != t; t = t_next) | 2357 | for (t = transitions_head; NULL != t; t = t_next) |
2361 | { | 2358 | { |
2362 | t_next = t->next; | 2359 | t_next = t->next; |
2363 | state_add_transition (regex_ctx, t->from_state, t->label, t->to_state); | 2360 | state_add_transition(regex_ctx, t->from_state, t->label, t->to_state); |
2364 | GNUNET_CONTAINER_DLL_remove (transitions_head, transitions_tail, t); | 2361 | GNUNET_CONTAINER_DLL_remove(transitions_head, transitions_tail, t); |
2365 | GNUNET_free_non_null (t->label); | 2362 | GNUNET_free_non_null(t->label); |
2366 | GNUNET_free (t); | 2363 | GNUNET_free(t); |
2367 | } | 2364 | } |
2368 | 2365 | ||
2369 | /* Remove marked states (including their incoming and outgoing transitions). */ | 2366 | /* Remove marked states (including their incoming and outgoing transitions). */ |
2370 | for (s = dfa->states_head; NULL != s; s = s_next) | 2367 | for (s = dfa->states_head; NULL != s; s = s_next) |
2371 | { | 2368 | { |
2372 | s_next = s->next; | 2369 | s_next = s->next; |
2373 | if (GNUNET_YES == s->contained) | 2370 | if (GNUNET_YES == s->contained) |
2374 | automaton_remove_state (dfa, s); | 2371 | automaton_remove_state(dfa, s); |
2375 | } | 2372 | } |
2376 | } | 2373 | } |
2377 | 2374 | ||
2378 | 2375 | ||
@@ -2386,12 +2383,12 @@ dfa_compress_paths (struct REGEX_INTERNAL_Context *regex_ctx, | |||
2386 | * @return new NFA fragment | 2383 | * @return new NFA fragment |
2387 | */ | 2384 | */ |
2388 | static struct REGEX_INTERNAL_Automaton * | 2385 | static struct REGEX_INTERNAL_Automaton * |
2389 | nfa_fragment_create (struct REGEX_INTERNAL_State *start, | 2386 | nfa_fragment_create(struct REGEX_INTERNAL_State *start, |
2390 | struct REGEX_INTERNAL_State *end) | 2387 | struct REGEX_INTERNAL_State *end) |
2391 | { | 2388 | { |
2392 | struct REGEX_INTERNAL_Automaton *n; | 2389 | struct REGEX_INTERNAL_Automaton *n; |
2393 | 2390 | ||
2394 | n = GNUNET_new (struct REGEX_INTERNAL_Automaton); | 2391 | n = GNUNET_new(struct REGEX_INTERNAL_Automaton); |
2395 | 2392 | ||
2396 | n->type = NFA; | 2393 | n->type = NFA; |
2397 | n->start = NULL; | 2394 | n->start = NULL; |
@@ -2401,8 +2398,8 @@ nfa_fragment_create (struct REGEX_INTERNAL_State *start, | |||
2401 | if (NULL == start || NULL == end) | 2398 | if (NULL == start || NULL == end) |
2402 | return n; | 2399 | return n; |
2403 | 2400 | ||
2404 | automaton_add_state (n, end); | 2401 | automaton_add_state(n, end); |
2405 | automaton_add_state (n, start); | 2402 | automaton_add_state(n, start); |
2406 | 2403 | ||
2407 | n->state_count = 2; | 2404 | n->state_count = 2; |
2408 | 2405 | ||
@@ -2421,30 +2418,30 @@ nfa_fragment_create (struct REGEX_INTERNAL_State *start, | |||
2421 | * @param states_tail tail of the DLL of states | 2418 | * @param states_tail tail of the DLL of states |
2422 | */ | 2419 | */ |
2423 | static void | 2420 | static void |
2424 | nfa_add_states (struct REGEX_INTERNAL_Automaton *n, | 2421 | nfa_add_states(struct REGEX_INTERNAL_Automaton *n, |
2425 | struct REGEX_INTERNAL_State *states_head, | 2422 | struct REGEX_INTERNAL_State *states_head, |
2426 | struct REGEX_INTERNAL_State *states_tail) | 2423 | struct REGEX_INTERNAL_State *states_tail) |
2427 | { | 2424 | { |
2428 | struct REGEX_INTERNAL_State *s; | 2425 | struct REGEX_INTERNAL_State *s; |
2429 | 2426 | ||
2430 | if (NULL == n || NULL == states_head) | 2427 | if (NULL == n || NULL == states_head) |
2431 | { | 2428 | { |
2432 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n"); | 2429 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not add states\n"); |
2433 | return; | 2430 | return; |
2434 | } | 2431 | } |
2435 | 2432 | ||
2436 | if (NULL == n->states_head) | 2433 | if (NULL == n->states_head) |
2437 | { | 2434 | { |
2438 | n->states_head = states_head; | 2435 | n->states_head = states_head; |
2439 | n->states_tail = states_tail; | 2436 | n->states_tail = states_tail; |
2440 | return; | 2437 | return; |
2441 | } | 2438 | } |
2442 | 2439 | ||
2443 | if (NULL != states_head) | 2440 | if (NULL != states_head) |
2444 | { | 2441 | { |
2445 | n->states_tail->next = states_head; | 2442 | n->states_tail->next = states_head; |
2446 | n->states_tail = states_tail; | 2443 | n->states_tail = states_tail; |
2447 | } | 2444 | } |
2448 | 2445 | ||
2449 | for (s = states_head; NULL != s; s = s->next) | 2446 | for (s = states_head; NULL != s; s = s->next) |
2450 | n->state_count++; | 2447 | n->state_count++; |
@@ -2460,11 +2457,11 @@ nfa_add_states (struct REGEX_INTERNAL_Automaton *n, | |||
2460 | * @return new NFA state | 2457 | * @return new NFA state |
2461 | */ | 2458 | */ |
2462 | static struct REGEX_INTERNAL_State * | 2459 | static struct REGEX_INTERNAL_State * |
2463 | nfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting) | 2460 | nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting) |
2464 | { | 2461 | { |
2465 | struct REGEX_INTERNAL_State *s; | 2462 | struct REGEX_INTERNAL_State *s; |
2466 | 2463 | ||
2467 | s = GNUNET_new (struct REGEX_INTERNAL_State); | 2464 | s = GNUNET_new(struct REGEX_INTERNAL_State); |
2468 | s->id = ctx->state_id++; | 2465 | s->id = ctx->state_id++; |
2469 | s->accepting = accepting; | 2466 | s->accepting = accepting; |
2470 | s->marked = GNUNET_NO; | 2467 | s->marked = GNUNET_NO; |
@@ -2473,7 +2470,7 @@ nfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting) | |||
2473 | s->lowlink = -1; | 2470 | s->lowlink = -1; |
2474 | s->scc_id = 0; | 2471 | s->scc_id = 0; |
2475 | s->name = NULL; | 2472 | s->name = NULL; |
2476 | GNUNET_asprintf (&s->name, "s%i", s->id); | 2473 | GNUNET_asprintf(&s->name, "s%i", s->id); |
2477 | 2474 | ||
2478 | return s; | 2475 | return s; |
2479 | } | 2476 | } |
@@ -2489,10 +2486,10 @@ nfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting) | |||
2489 | * pass NULL for epsilon transition | 2486 | * pass NULL for epsilon transition |
2490 | */ | 2487 | */ |
2491 | static void | 2488 | static void |
2492 | nfa_closure_set_create (struct REGEX_INTERNAL_StateSet *ret, | 2489 | nfa_closure_set_create(struct REGEX_INTERNAL_StateSet *ret, |
2493 | struct REGEX_INTERNAL_Automaton *nfa, | 2490 | struct REGEX_INTERNAL_Automaton *nfa, |
2494 | struct REGEX_INTERNAL_StateSet *states, | 2491 | struct REGEX_INTERNAL_StateSet *states, |
2495 | const char *label) | 2492 | const char *label) |
2496 | { | 2493 | { |
2497 | struct REGEX_INTERNAL_State *s; | 2494 | struct REGEX_INTERNAL_State *s; |
2498 | unsigned int i; | 2495 | unsigned int i; |
@@ -2501,58 +2498,58 @@ nfa_closure_set_create (struct REGEX_INTERNAL_StateSet *ret, | |||
2501 | struct REGEX_INTERNAL_State *currentstate; | 2498 | struct REGEX_INTERNAL_State *currentstate; |
2502 | struct REGEX_INTERNAL_Transition *ctran; | 2499 | struct REGEX_INTERNAL_Transition *ctran; |
2503 | 2500 | ||
2504 | memset (ret, 0, sizeof (struct REGEX_INTERNAL_StateSet)); | 2501 | memset(ret, 0, sizeof(struct REGEX_INTERNAL_StateSet)); |
2505 | if (NULL == states) | 2502 | if (NULL == states) |
2506 | return; | 2503 | return; |
2507 | 2504 | ||
2508 | for (i = 0; i < states->off; i++) | 2505 | for (i = 0; i < states->off; i++) |
2509 | { | 2506 | { |
2510 | s = states->states[i]; | 2507 | s = states->states[i]; |
2511 | 2508 | ||
2512 | /* Add start state to closure only for epsilon closure */ | 2509 | /* Add start state to closure only for epsilon closure */ |
2513 | if (NULL == label) | 2510 | if (NULL == label) |
2514 | state_set_append (ret, s); | 2511 | state_set_append(ret, s); |
2515 | 2512 | ||
2516 | /* initialize work stack */ | 2513 | /* initialize work stack */ |
2517 | cls_stack.head = NULL; | 2514 | cls_stack.head = NULL; |
2518 | cls_stack.tail = NULL; | 2515 | cls_stack.tail = NULL; |
2519 | GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s); | 2516 | GNUNET_CONTAINER_MDLL_insert(ST, cls_stack.head, cls_stack.tail, s); |
2520 | cls_stack.len = 1; | 2517 | cls_stack.len = 1; |
2521 | 2518 | ||
2522 | while (NULL != (currentstate = cls_stack.tail)) | 2519 | while (NULL != (currentstate = cls_stack.tail)) |
2523 | { | 2520 | { |
2524 | GNUNET_CONTAINER_MDLL_remove (ST, | 2521 | GNUNET_CONTAINER_MDLL_remove(ST, |
2525 | cls_stack.head, | 2522 | cls_stack.head, |
2526 | cls_stack.tail, | 2523 | cls_stack.tail, |
2527 | currentstate); | 2524 | currentstate); |
2528 | cls_stack.len--; | 2525 | cls_stack.len--; |
2529 | for (ctran = currentstate->transitions_head; NULL != ctran; | 2526 | for (ctran = currentstate->transitions_head; NULL != ctran; |
2530 | ctran = ctran->next) | 2527 | ctran = ctran->next) |
2531 | { | 2528 | { |
2532 | if (NULL == (clsstate = ctran->to_state)) | 2529 | if (NULL == (clsstate = ctran->to_state)) |
2533 | continue; | 2530 | continue; |
2534 | if (0 != clsstate->contained) | 2531 | if (0 != clsstate->contained) |
2535 | continue; | 2532 | continue; |
2536 | if (0 != nullstrcmp (label, ctran->label)) | 2533 | if (0 != nullstrcmp(label, ctran->label)) |
2537 | continue; | 2534 | continue; |
2538 | state_set_append (ret, clsstate); | 2535 | state_set_append(ret, clsstate); |
2539 | GNUNET_CONTAINER_MDLL_insert_tail (ST, | 2536 | GNUNET_CONTAINER_MDLL_insert_tail(ST, |
2540 | cls_stack.head, | 2537 | cls_stack.head, |
2541 | cls_stack.tail, | 2538 | cls_stack.tail, |
2542 | clsstate); | 2539 | clsstate); |
2543 | cls_stack.len++; | 2540 | cls_stack.len++; |
2544 | clsstate->contained = 1; | 2541 | clsstate->contained = 1; |
2545 | } | 2542 | } |
2543 | } | ||
2546 | } | 2544 | } |
2547 | } | ||
2548 | for (i = 0; i < ret->off; i++) | 2545 | for (i = 0; i < ret->off; i++) |
2549 | ret->states[i]->contained = 0; | 2546 | ret->states[i]->contained = 0; |
2550 | 2547 | ||
2551 | if (ret->off > 1) | 2548 | if (ret->off > 1) |
2552 | qsort (ret->states, | 2549 | qsort(ret->states, |
2553 | ret->off, | 2550 | ret->off, |
2554 | sizeof (struct REGEX_INTERNAL_State *), | 2551 | sizeof(struct REGEX_INTERNAL_State *), |
2555 | &state_compare); | 2552 | &state_compare); |
2556 | } | 2553 | } |
2557 | 2554 | ||
2558 | 2555 | ||
@@ -2562,33 +2559,33 @@ nfa_closure_set_create (struct REGEX_INTERNAL_StateSet *ret, | |||
2562 | * @param ctx context | 2559 | * @param ctx context |
2563 | */ | 2560 | */ |
2564 | static void | 2561 | static void |
2565 | nfa_add_concatenation (struct REGEX_INTERNAL_Context *ctx) | 2562 | nfa_add_concatenation(struct REGEX_INTERNAL_Context *ctx) |
2566 | { | 2563 | { |
2567 | struct REGEX_INTERNAL_Automaton *a; | 2564 | struct REGEX_INTERNAL_Automaton *a; |
2568 | struct REGEX_INTERNAL_Automaton *b; | 2565 | struct REGEX_INTERNAL_Automaton *b; |
2569 | struct REGEX_INTERNAL_Automaton *new_nfa; | 2566 | struct REGEX_INTERNAL_Automaton *new_nfa; |
2570 | 2567 | ||
2571 | b = ctx->stack_tail; | 2568 | b = ctx->stack_tail; |
2572 | GNUNET_assert (NULL != b); | 2569 | GNUNET_assert(NULL != b); |
2573 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b); | 2570 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, b); |
2574 | a = ctx->stack_tail; | 2571 | a = ctx->stack_tail; |
2575 | GNUNET_assert (NULL != a); | 2572 | GNUNET_assert(NULL != a); |
2576 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 2573 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, a); |
2577 | 2574 | ||
2578 | state_add_transition (ctx, a->end, NULL, b->start); | 2575 | state_add_transition(ctx, a->end, NULL, b->start); |
2579 | a->end->accepting = 0; | 2576 | a->end->accepting = 0; |
2580 | b->end->accepting = 1; | 2577 | b->end->accepting = 1; |
2581 | 2578 | ||
2582 | new_nfa = nfa_fragment_create (NULL, NULL); | 2579 | new_nfa = nfa_fragment_create(NULL, NULL); |
2583 | nfa_add_states (new_nfa, a->states_head, a->states_tail); | 2580 | nfa_add_states(new_nfa, a->states_head, a->states_tail); |
2584 | nfa_add_states (new_nfa, b->states_head, b->states_tail); | 2581 | nfa_add_states(new_nfa, b->states_head, b->states_tail); |
2585 | new_nfa->start = a->start; | 2582 | new_nfa->start = a->start; |
2586 | new_nfa->end = b->end; | 2583 | new_nfa->end = b->end; |
2587 | new_nfa->state_count += a->state_count + b->state_count; | 2584 | new_nfa->state_count += a->state_count + b->state_count; |
2588 | automaton_fragment_clear (a); | 2585 | automaton_fragment_clear(a); |
2589 | automaton_fragment_clear (b); | 2586 | automaton_fragment_clear(b); |
2590 | 2587 | ||
2591 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa); | 2588 | GNUNET_CONTAINER_DLL_insert_tail(ctx->stack_head, ctx->stack_tail, new_nfa); |
2592 | } | 2589 | } |
2593 | 2590 | ||
2594 | 2591 | ||
@@ -2598,7 +2595,7 @@ nfa_add_concatenation (struct REGEX_INTERNAL_Context *ctx) | |||
2598 | * @param ctx context | 2595 | * @param ctx context |
2599 | */ | 2596 | */ |
2600 | static void | 2597 | static void |
2601 | nfa_add_star_op (struct REGEX_INTERNAL_Context *ctx) | 2598 | nfa_add_star_op(struct REGEX_INTERNAL_Context *ctx) |
2602 | { | 2599 | { |
2603 | struct REGEX_INTERNAL_Automaton *a; | 2600 | struct REGEX_INTERNAL_Automaton *a; |
2604 | struct REGEX_INTERNAL_Automaton *new_nfa; | 2601 | struct REGEX_INTERNAL_Automaton *new_nfa; |
@@ -2608,31 +2605,31 @@ nfa_add_star_op (struct REGEX_INTERNAL_Context *ctx) | |||
2608 | a = ctx->stack_tail; | 2605 | a = ctx->stack_tail; |
2609 | 2606 | ||
2610 | if (NULL == a) | 2607 | if (NULL == a) |
2611 | { | 2608 | { |
2612 | GNUNET_log ( | 2609 | GNUNET_log( |
2613 | GNUNET_ERROR_TYPE_ERROR, | 2610 | GNUNET_ERROR_TYPE_ERROR, |
2614 | "nfa_add_star_op failed, because there was no element on the stack"); | 2611 | "nfa_add_star_op failed, because there was no element on the stack"); |
2615 | return; | 2612 | return; |
2616 | } | 2613 | } |
2617 | 2614 | ||
2618 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 2615 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, a); |
2619 | 2616 | ||
2620 | start = nfa_state_create (ctx, 0); | 2617 | start = nfa_state_create(ctx, 0); |
2621 | end = nfa_state_create (ctx, 1); | 2618 | end = nfa_state_create(ctx, 1); |
2622 | 2619 | ||
2623 | state_add_transition (ctx, start, NULL, a->start); | 2620 | state_add_transition(ctx, start, NULL, a->start); |
2624 | state_add_transition (ctx, start, NULL, end); | 2621 | state_add_transition(ctx, start, NULL, end); |
2625 | state_add_transition (ctx, a->end, NULL, a->start); | 2622 | state_add_transition(ctx, a->end, NULL, a->start); |
2626 | state_add_transition (ctx, a->end, NULL, end); | 2623 | state_add_transition(ctx, a->end, NULL, end); |
2627 | 2624 | ||
2628 | a->end->accepting = 0; | 2625 | a->end->accepting = 0; |
2629 | end->accepting = 1; | 2626 | end->accepting = 1; |
2630 | 2627 | ||
2631 | new_nfa = nfa_fragment_create (start, end); | 2628 | new_nfa = nfa_fragment_create(start, end); |
2632 | nfa_add_states (new_nfa, a->states_head, a->states_tail); | 2629 | nfa_add_states(new_nfa, a->states_head, a->states_tail); |
2633 | automaton_fragment_clear (a); | 2630 | automaton_fragment_clear(a); |
2634 | 2631 | ||
2635 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa); | 2632 | GNUNET_CONTAINER_DLL_insert_tail(ctx->stack_head, ctx->stack_tail, new_nfa); |
2636 | } | 2633 | } |
2637 | 2634 | ||
2638 | 2635 | ||
@@ -2642,25 +2639,25 @@ nfa_add_star_op (struct REGEX_INTERNAL_Context *ctx) | |||
2642 | * @param ctx context | 2639 | * @param ctx context |
2643 | */ | 2640 | */ |
2644 | static void | 2641 | static void |
2645 | nfa_add_plus_op (struct REGEX_INTERNAL_Context *ctx) | 2642 | nfa_add_plus_op(struct REGEX_INTERNAL_Context *ctx) |
2646 | { | 2643 | { |
2647 | struct REGEX_INTERNAL_Automaton *a; | 2644 | struct REGEX_INTERNAL_Automaton *a; |
2648 | 2645 | ||
2649 | a = ctx->stack_tail; | 2646 | a = ctx->stack_tail; |
2650 | 2647 | ||
2651 | if (NULL == a) | 2648 | if (NULL == a) |
2652 | { | 2649 | { |
2653 | GNUNET_log ( | 2650 | GNUNET_log( |
2654 | GNUNET_ERROR_TYPE_ERROR, | 2651 | GNUNET_ERROR_TYPE_ERROR, |
2655 | "nfa_add_plus_op failed, because there was no element on the stack"); | 2652 | "nfa_add_plus_op failed, because there was no element on the stack"); |
2656 | return; | 2653 | return; |
2657 | } | 2654 | } |
2658 | 2655 | ||
2659 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 2656 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, a); |
2660 | 2657 | ||
2661 | state_add_transition (ctx, a->end, NULL, a->start); | 2658 | state_add_transition(ctx, a->end, NULL, a->start); |
2662 | 2659 | ||
2663 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a); | 2660 | GNUNET_CONTAINER_DLL_insert_tail(ctx->stack_head, ctx->stack_tail, a); |
2664 | } | 2661 | } |
2665 | 2662 | ||
2666 | 2663 | ||
@@ -2670,7 +2667,7 @@ nfa_add_plus_op (struct REGEX_INTERNAL_Context *ctx) | |||
2670 | * @param ctx context | 2667 | * @param ctx context |
2671 | */ | 2668 | */ |
2672 | static void | 2669 | static void |
2673 | nfa_add_question_op (struct REGEX_INTERNAL_Context *ctx) | 2670 | nfa_add_question_op(struct REGEX_INTERNAL_Context *ctx) |
2674 | { | 2671 | { |
2675 | struct REGEX_INTERNAL_Automaton *a; | 2672 | struct REGEX_INTERNAL_Automaton *a; |
2676 | struct REGEX_INTERNAL_Automaton *new_nfa; | 2673 | struct REGEX_INTERNAL_Automaton *new_nfa; |
@@ -2679,28 +2676,28 @@ nfa_add_question_op (struct REGEX_INTERNAL_Context *ctx) | |||
2679 | 2676 | ||
2680 | a = ctx->stack_tail; | 2677 | a = ctx->stack_tail; |
2681 | if (NULL == a) | 2678 | if (NULL == a) |
2682 | { | 2679 | { |
2683 | GNUNET_log ( | 2680 | GNUNET_log( |
2684 | GNUNET_ERROR_TYPE_ERROR, | 2681 | GNUNET_ERROR_TYPE_ERROR, |
2685 | "nfa_add_question_op failed, because there was no element on the stack"); | 2682 | "nfa_add_question_op failed, because there was no element on the stack"); |
2686 | return; | 2683 | return; |
2687 | } | 2684 | } |
2688 | 2685 | ||
2689 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 2686 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, a); |
2690 | 2687 | ||
2691 | start = nfa_state_create (ctx, 0); | 2688 | start = nfa_state_create(ctx, 0); |
2692 | end = nfa_state_create (ctx, 1); | 2689 | end = nfa_state_create(ctx, 1); |
2693 | 2690 | ||
2694 | state_add_transition (ctx, start, NULL, a->start); | 2691 | state_add_transition(ctx, start, NULL, a->start); |
2695 | state_add_transition (ctx, start, NULL, end); | 2692 | state_add_transition(ctx, start, NULL, end); |
2696 | state_add_transition (ctx, a->end, NULL, end); | 2693 | state_add_transition(ctx, a->end, NULL, end); |
2697 | 2694 | ||
2698 | a->end->accepting = 0; | 2695 | a->end->accepting = 0; |
2699 | 2696 | ||
2700 | new_nfa = nfa_fragment_create (start, end); | 2697 | new_nfa = nfa_fragment_create(start, end); |
2701 | nfa_add_states (new_nfa, a->states_head, a->states_tail); | 2698 | nfa_add_states(new_nfa, a->states_head, a->states_tail); |
2702 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa); | 2699 | GNUNET_CONTAINER_DLL_insert_tail(ctx->stack_head, ctx->stack_tail, new_nfa); |
2703 | automaton_fragment_clear (a); | 2700 | automaton_fragment_clear(a); |
2704 | } | 2701 | } |
2705 | 2702 | ||
2706 | 2703 | ||
@@ -2711,7 +2708,7 @@ nfa_add_question_op (struct REGEX_INTERNAL_Context *ctx) | |||
2711 | * @param ctx context | 2708 | * @param ctx context |
2712 | */ | 2709 | */ |
2713 | static void | 2710 | static void |
2714 | nfa_add_alternation (struct REGEX_INTERNAL_Context *ctx) | 2711 | nfa_add_alternation(struct REGEX_INTERNAL_Context *ctx) |
2715 | { | 2712 | { |
2716 | struct REGEX_INTERNAL_Automaton *a; | 2713 | struct REGEX_INTERNAL_Automaton *a; |
2717 | struct REGEX_INTERNAL_Automaton *b; | 2714 | struct REGEX_INTERNAL_Automaton *b; |
@@ -2720,31 +2717,31 @@ nfa_add_alternation (struct REGEX_INTERNAL_Context *ctx) | |||
2720 | struct REGEX_INTERNAL_State *end; | 2717 | struct REGEX_INTERNAL_State *end; |
2721 | 2718 | ||
2722 | b = ctx->stack_tail; | 2719 | b = ctx->stack_tail; |
2723 | GNUNET_assert (NULL != b); | 2720 | GNUNET_assert(NULL != b); |
2724 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b); | 2721 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, b); |
2725 | a = ctx->stack_tail; | 2722 | a = ctx->stack_tail; |
2726 | GNUNET_assert (NULL != a); | 2723 | GNUNET_assert(NULL != a); |
2727 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | 2724 | GNUNET_CONTAINER_DLL_remove(ctx->stack_head, ctx->stack_tail, a); |
2728 | 2725 | ||
2729 | start = nfa_state_create (ctx, 0); | 2726 | start = nfa_state_create(ctx, 0); |
2730 | end = nfa_state_create (ctx, 1); | 2727 | end = nfa_state_create(ctx, 1); |
2731 | state_add_transition (ctx, start, NULL, a->start); | 2728 | state_add_transition(ctx, start, NULL, a->start); |
2732 | state_add_transition (ctx, start, NULL, b->start); | 2729 | state_add_transition(ctx, start, NULL, b->start); |
2733 | 2730 | ||
2734 | state_add_transition (ctx, a->end, NULL, end); | 2731 | state_add_transition(ctx, a->end, NULL, end); |
2735 | state_add_transition (ctx, b->end, NULL, end); | 2732 | state_add_transition(ctx, b->end, NULL, end); |
2736 | 2733 | ||
2737 | a->end->accepting = 0; | 2734 | a->end->accepting = 0; |
2738 | b->end->accepting = 0; | 2735 | b->end->accepting = 0; |
2739 | end->accepting = 1; | 2736 | end->accepting = 1; |
2740 | 2737 | ||
2741 | new_nfa = nfa_fragment_create (start, end); | 2738 | new_nfa = nfa_fragment_create(start, end); |
2742 | nfa_add_states (new_nfa, a->states_head, a->states_tail); | 2739 | nfa_add_states(new_nfa, a->states_head, a->states_tail); |
2743 | nfa_add_states (new_nfa, b->states_head, b->states_tail); | 2740 | nfa_add_states(new_nfa, b->states_head, b->states_tail); |
2744 | automaton_fragment_clear (a); | 2741 | automaton_fragment_clear(a); |
2745 | automaton_fragment_clear (b); | 2742 | automaton_fragment_clear(b); |
2746 | 2743 | ||
2747 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa); | 2744 | GNUNET_CONTAINER_DLL_insert_tail(ctx->stack_head, ctx->stack_tail, new_nfa); |
2748 | } | 2745 | } |
2749 | 2746 | ||
2750 | 2747 | ||
@@ -2755,20 +2752,20 @@ nfa_add_alternation (struct REGEX_INTERNAL_Context *ctx) | |||
2755 | * @param label label for nfa transition | 2752 | * @param label label for nfa transition |
2756 | */ | 2753 | */ |
2757 | static void | 2754 | static void |
2758 | nfa_add_label (struct REGEX_INTERNAL_Context *ctx, const char *label) | 2755 | nfa_add_label(struct REGEX_INTERNAL_Context *ctx, const char *label) |
2759 | { | 2756 | { |
2760 | struct REGEX_INTERNAL_Automaton *n; | 2757 | struct REGEX_INTERNAL_Automaton *n; |
2761 | struct REGEX_INTERNAL_State *start; | 2758 | struct REGEX_INTERNAL_State *start; |
2762 | struct REGEX_INTERNAL_State *end; | 2759 | struct REGEX_INTERNAL_State *end; |
2763 | 2760 | ||
2764 | GNUNET_assert (NULL != ctx); | 2761 | GNUNET_assert(NULL != ctx); |
2765 | 2762 | ||
2766 | start = nfa_state_create (ctx, 0); | 2763 | start = nfa_state_create(ctx, 0); |
2767 | end = nfa_state_create (ctx, 1); | 2764 | end = nfa_state_create(ctx, 1); |
2768 | state_add_transition (ctx, start, label, end); | 2765 | state_add_transition(ctx, start, label, end); |
2769 | n = nfa_fragment_create (start, end); | 2766 | n = nfa_fragment_create(start, end); |
2770 | GNUNET_assert (NULL != n); | 2767 | GNUNET_assert(NULL != n); |
2771 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n); | 2768 | GNUNET_CONTAINER_DLL_insert_tail(ctx->stack_head, ctx->stack_tail, n); |
2772 | } | 2769 | } |
2773 | 2770 | ||
2774 | 2771 | ||
@@ -2778,13 +2775,13 @@ nfa_add_label (struct REGEX_INTERNAL_Context *ctx, const char *label) | |||
2778 | * @param ctx context | 2775 | * @param ctx context |
2779 | */ | 2776 | */ |
2780 | static void | 2777 | static void |
2781 | REGEX_INTERNAL_context_init (struct REGEX_INTERNAL_Context *ctx) | 2778 | REGEX_INTERNAL_context_init(struct REGEX_INTERNAL_Context *ctx) |
2782 | { | 2779 | { |
2783 | if (NULL == ctx) | 2780 | if (NULL == ctx) |
2784 | { | 2781 | { |
2785 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!"); | 2782 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Context was NULL!"); |
2786 | return; | 2783 | return; |
2787 | } | 2784 | } |
2788 | ctx->state_id = 0; | 2785 | ctx->state_id = 0; |
2789 | ctx->transition_id = 0; | 2786 | ctx->transition_id = 0; |
2790 | ctx->stack_head = NULL; | 2787 | ctx->stack_head = NULL; |
@@ -2801,7 +2798,7 @@ REGEX_INTERNAL_context_init (struct REGEX_INTERNAL_Context *ctx) | |||
2801 | * @return NFA, needs to be freed using REGEX_INTERNAL_destroy_automaton | 2798 | * @return NFA, needs to be freed using REGEX_INTERNAL_destroy_automaton |
2802 | */ | 2799 | */ |
2803 | struct REGEX_INTERNAL_Automaton * | 2800 | struct REGEX_INTERNAL_Automaton * |
2804 | REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len) | 2801 | REGEX_INTERNAL_construct_nfa(const char *regex, const size_t len) |
2805 | { | 2802 | { |
2806 | struct REGEX_INTERNAL_Context ctx; | 2803 | struct REGEX_INTERNAL_Context ctx; |
2807 | struct REGEX_INTERNAL_Automaton *nfa; | 2804 | struct REGEX_INTERNAL_Automaton *nfa; |
@@ -2813,20 +2810,20 @@ REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len) | |||
2813 | unsigned int atomcount; | 2810 | unsigned int atomcount; |
2814 | unsigned int poff; | 2811 | unsigned int poff; |
2815 | unsigned int psize; | 2812 | unsigned int psize; |
2816 | struct | 2813 | |
2817 | { | 2814 | struct { |
2818 | int altcount; | 2815 | int altcount; |
2819 | int atomcount; | 2816 | int atomcount; |
2820 | } * p; | 2817 | } * p; |
2821 | 2818 | ||
2822 | if (NULL == regex || 0 == strlen (regex) || 0 == len) | 2819 | if (NULL == regex || 0 == strlen(regex) || 0 == len) |
2823 | { | 2820 | { |
2824 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 2821 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
2825 | "Could not parse regex. Empty regex string provided.\n"); | 2822 | "Could not parse regex. Empty regex string provided.\n"); |
2826 | 2823 | ||
2827 | return NULL; | 2824 | return NULL; |
2828 | } | 2825 | } |
2829 | REGEX_INTERNAL_context_init (&ctx); | 2826 | REGEX_INTERNAL_context_init(&ctx); |
2830 | 2827 | ||
2831 | regexp = regex; | 2828 | regexp = regex; |
2832 | curlabel[1] = '\0'; | 2829 | curlabel[1] = '\0'; |
@@ -2838,123 +2835,129 @@ REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len) | |||
2838 | psize = 0; | 2835 | psize = 0; |
2839 | 2836 | ||
2840 | for (count = 0; count < len && *regexp; count++, regexp++) | 2837 | for (count = 0; count < len && *regexp; count++, regexp++) |
2841 | { | ||
2842 | switch (*regexp) | ||
2843 | { | 2838 | { |
2844 | case '(': | 2839 | switch (*regexp) |
2845 | if (atomcount > 1) | 2840 | { |
2846 | { | 2841 | case '(': |
2847 | --atomcount; | 2842 | if (atomcount > 1) |
2848 | nfa_add_concatenation (&ctx); | 2843 | { |
2849 | } | 2844 | --atomcount; |
2850 | if (poff == psize) | 2845 | nfa_add_concatenation(&ctx); |
2851 | GNUNET_array_grow (p, psize, psize * 2 + 4); /* FIXME why *2 +4? */ | 2846 | } |
2852 | p[poff].altcount = altcount; | 2847 | if (poff == psize) |
2853 | p[poff].atomcount = atomcount; | 2848 | GNUNET_array_grow(p, psize, psize * 2 + 4); /* FIXME why *2 +4? */ |
2854 | poff++; | 2849 | p[poff].altcount = altcount; |
2855 | altcount = 0; | 2850 | p[poff].atomcount = atomcount; |
2856 | atomcount = 0; | 2851 | poff++; |
2857 | break; | 2852 | altcount = 0; |
2858 | case '|': | 2853 | atomcount = 0; |
2859 | if (0 == atomcount) | 2854 | break; |
2860 | { | 2855 | |
2861 | error_msg = "Cannot append '|' to nothing"; | 2856 | case '|': |
2862 | goto error; | 2857 | if (0 == atomcount) |
2863 | } | 2858 | { |
2864 | while (--atomcount > 0) | 2859 | error_msg = "Cannot append '|' to nothing"; |
2865 | nfa_add_concatenation (&ctx); | 2860 | goto error; |
2866 | altcount++; | 2861 | } |
2867 | break; | 2862 | while (--atomcount > 0) |
2868 | case ')': | 2863 | nfa_add_concatenation(&ctx); |
2869 | if (0 == poff) | 2864 | altcount++; |
2870 | { | 2865 | break; |
2871 | error_msg = "Missing opening '('"; | 2866 | |
2872 | goto error; | 2867 | case ')': |
2873 | } | 2868 | if (0 == poff) |
2874 | if (0 == atomcount) | 2869 | { |
2875 | { | 2870 | error_msg = "Missing opening '('"; |
2876 | /* Ignore this: "()" */ | 2871 | goto error; |
2877 | poff--; | 2872 | } |
2878 | altcount = p[poff].altcount; | 2873 | if (0 == atomcount) |
2879 | atomcount = p[poff].atomcount; | 2874 | { |
2880 | break; | 2875 | /* Ignore this: "()" */ |
2881 | } | 2876 | poff--; |
2882 | while (--atomcount > 0) | 2877 | altcount = p[poff].altcount; |
2883 | nfa_add_concatenation (&ctx); | 2878 | atomcount = p[poff].atomcount; |
2884 | for (; altcount > 0; altcount--) | 2879 | break; |
2885 | nfa_add_alternation (&ctx); | 2880 | } |
2886 | poff--; | 2881 | while (--atomcount > 0) |
2887 | altcount = p[poff].altcount; | 2882 | nfa_add_concatenation(&ctx); |
2888 | atomcount = p[poff].atomcount; | 2883 | for (; altcount > 0; altcount--) |
2889 | atomcount++; | 2884 | nfa_add_alternation(&ctx); |
2890 | break; | 2885 | poff--; |
2891 | case '*': | 2886 | altcount = p[poff].altcount; |
2892 | if (atomcount == 0) | 2887 | atomcount = p[poff].atomcount; |
2893 | { | 2888 | atomcount++; |
2894 | error_msg = "Cannot append '*' to nothing"; | 2889 | break; |
2895 | goto error; | 2890 | |
2896 | } | 2891 | case '*': |
2897 | nfa_add_star_op (&ctx); | 2892 | if (atomcount == 0) |
2898 | break; | 2893 | { |
2899 | case '+': | 2894 | error_msg = "Cannot append '*' to nothing"; |
2900 | if (atomcount == 0) | 2895 | goto error; |
2901 | { | 2896 | } |
2902 | error_msg = "Cannot append '+' to nothing"; | 2897 | nfa_add_star_op(&ctx); |
2903 | goto error; | 2898 | break; |
2904 | } | 2899 | |
2905 | nfa_add_plus_op (&ctx); | 2900 | case '+': |
2906 | break; | 2901 | if (atomcount == 0) |
2907 | case '?': | 2902 | { |
2908 | if (atomcount == 0) | 2903 | error_msg = "Cannot append '+' to nothing"; |
2909 | { | 2904 | goto error; |
2910 | error_msg = "Cannot append '?' to nothing"; | 2905 | } |
2911 | goto error; | 2906 | nfa_add_plus_op(&ctx); |
2912 | } | 2907 | break; |
2913 | nfa_add_question_op (&ctx); | 2908 | |
2914 | break; | 2909 | case '?': |
2915 | default: | 2910 | if (atomcount == 0) |
2916 | if (atomcount > 1) | 2911 | { |
2917 | { | 2912 | error_msg = "Cannot append '?' to nothing"; |
2918 | --atomcount; | 2913 | goto error; |
2919 | nfa_add_concatenation (&ctx); | 2914 | } |
2920 | } | 2915 | nfa_add_question_op(&ctx); |
2921 | curlabel[0] = *regexp; | 2916 | break; |
2922 | nfa_add_label (&ctx, curlabel); | 2917 | |
2923 | atomcount++; | 2918 | default: |
2924 | break; | 2919 | if (atomcount > 1) |
2920 | { | ||
2921 | --atomcount; | ||
2922 | nfa_add_concatenation(&ctx); | ||
2923 | } | ||
2924 | curlabel[0] = *regexp; | ||
2925 | nfa_add_label(&ctx, curlabel); | ||
2926 | atomcount++; | ||
2927 | break; | ||
2928 | } | ||
2925 | } | 2929 | } |
2926 | } | ||
2927 | if (0 != poff) | 2930 | if (0 != poff) |
2928 | { | 2931 | { |
2929 | error_msg = "Unbalanced parenthesis"; | 2932 | error_msg = "Unbalanced parenthesis"; |
2930 | goto error; | 2933 | goto error; |
2931 | } | 2934 | } |
2932 | while (--atomcount > 0) | 2935 | while (--atomcount > 0) |
2933 | nfa_add_concatenation (&ctx); | 2936 | nfa_add_concatenation(&ctx); |
2934 | for (; altcount > 0; altcount--) | 2937 | for (; altcount > 0; altcount--) |
2935 | nfa_add_alternation (&ctx); | 2938 | nfa_add_alternation(&ctx); |
2936 | 2939 | ||
2937 | GNUNET_array_grow (p, psize, 0); | 2940 | GNUNET_array_grow(p, psize, 0); |
2938 | 2941 | ||
2939 | nfa = ctx.stack_tail; | 2942 | nfa = ctx.stack_tail; |
2940 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); | 2943 | GNUNET_CONTAINER_DLL_remove(ctx.stack_head, ctx.stack_tail, nfa); |
2941 | 2944 | ||
2942 | if (NULL != ctx.stack_head) | 2945 | if (NULL != ctx.stack_head) |
2943 | { | 2946 | { |
2944 | error_msg = "Creating the NFA failed. NFA stack was not empty!"; | 2947 | error_msg = "Creating the NFA failed. NFA stack was not empty!"; |
2945 | goto error; | 2948 | goto error; |
2946 | } | 2949 | } |
2947 | 2950 | ||
2948 | /* Remember the regex that was used to generate this NFA */ | 2951 | /* Remember the regex that was used to generate this NFA */ |
2949 | nfa->regex = GNUNET_strdup (regex); | 2952 | nfa->regex = GNUNET_strdup(regex); |
2950 | 2953 | ||
2951 | /* create depth-first numbering of the states for pretty printing */ | 2954 | /* create depth-first numbering of the states for pretty printing */ |
2952 | REGEX_INTERNAL_automaton_traverse (nfa, | 2955 | REGEX_INTERNAL_automaton_traverse(nfa, |
2953 | NULL, | 2956 | NULL, |
2954 | NULL, | 2957 | NULL, |
2955 | NULL, | 2958 | NULL, |
2956 | &number_states, | 2959 | &number_states, |
2957 | NULL); | 2960 | NULL); |
2958 | 2961 | ||
2959 | /* No multistriding added so far */ | 2962 | /* No multistriding added so far */ |
2960 | nfa->is_multistrided = GNUNET_NO; | 2963 | nfa->is_multistrided = GNUNET_NO; |
@@ -2962,17 +2965,17 @@ REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len) | |||
2962 | return nfa; | 2965 | return nfa; |
2963 | 2966 | ||
2964 | error: | 2967 | error: |
2965 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex); | 2968 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex); |
2966 | if (NULL != error_msg) | 2969 | if (NULL != error_msg) |
2967 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg); | 2970 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg); |
2968 | 2971 | ||
2969 | GNUNET_free_non_null (p); | 2972 | GNUNET_free_non_null(p); |
2970 | 2973 | ||
2971 | while (NULL != (nfa = ctx.stack_head)) | 2974 | while (NULL != (nfa = ctx.stack_head)) |
2972 | { | 2975 | { |
2973 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); | 2976 | GNUNET_CONTAINER_DLL_remove(ctx.stack_head, ctx.stack_tail, nfa); |
2974 | REGEX_INTERNAL_automaton_destroy (nfa); | 2977 | REGEX_INTERNAL_automaton_destroy(nfa); |
2975 | } | 2978 | } |
2976 | 2979 | ||
2977 | return NULL; | 2980 | return NULL; |
2978 | } | 2981 | } |
@@ -2988,10 +2991,10 @@ error: | |||
2988 | * for starting. | 2991 | * for starting. |
2989 | */ | 2992 | */ |
2990 | static void | 2993 | static void |
2991 | construct_dfa_states (struct REGEX_INTERNAL_Context *ctx, | 2994 | construct_dfa_states(struct REGEX_INTERNAL_Context *ctx, |
2992 | struct REGEX_INTERNAL_Automaton *nfa, | 2995 | struct REGEX_INTERNAL_Automaton *nfa, |
2993 | struct REGEX_INTERNAL_Automaton *dfa, | 2996 | struct REGEX_INTERNAL_Automaton *dfa, |
2994 | struct REGEX_INTERNAL_State *dfa_state) | 2997 | struct REGEX_INTERNAL_State *dfa_state) |
2995 | { | 2998 | { |
2996 | struct REGEX_INTERNAL_Transition *ctran; | 2999 | struct REGEX_INTERNAL_Transition *ctran; |
2997 | struct REGEX_INTERNAL_State *new_dfa_state; | 3000 | struct REGEX_INTERNAL_State *new_dfa_state; |
@@ -3001,37 +3004,37 @@ construct_dfa_states (struct REGEX_INTERNAL_Context *ctx, | |||
3001 | struct REGEX_INTERNAL_StateSet nfa_set; | 3004 | struct REGEX_INTERNAL_StateSet nfa_set; |
3002 | 3005 | ||
3003 | for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next) | 3006 | for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next) |
3004 | { | 3007 | { |
3005 | if (NULL == ctran->label || NULL != ctran->to_state) | 3008 | if (NULL == ctran->label || NULL != ctran->to_state) |
3006 | continue; | 3009 | continue; |
3007 | 3010 | ||
3008 | nfa_closure_set_create (&tmp, nfa, &dfa_state->nfa_set, ctran->label); | 3011 | nfa_closure_set_create(&tmp, nfa, &dfa_state->nfa_set, ctran->label); |
3009 | nfa_closure_set_create (&nfa_set, nfa, &tmp, NULL); | 3012 | nfa_closure_set_create(&nfa_set, nfa, &tmp, NULL); |
3010 | state_set_clear (&tmp); | 3013 | state_set_clear(&tmp); |
3011 | 3014 | ||
3012 | state_contains = NULL; | 3015 | state_contains = NULL; |
3013 | for (state_iter = dfa->states_head; NULL != state_iter; | 3016 | for (state_iter = dfa->states_head; NULL != state_iter; |
3014 | state_iter = state_iter->next) | 3017 | state_iter = state_iter->next) |
3015 | { | 3018 | { |
3016 | if (0 == state_set_compare (&state_iter->nfa_set, &nfa_set)) | 3019 | if (0 == state_set_compare(&state_iter->nfa_set, &nfa_set)) |
3017 | { | 3020 | { |
3018 | state_contains = state_iter; | 3021 | state_contains = state_iter; |
3019 | break; | 3022 | break; |
3020 | } | 3023 | } |
3021 | } | 3024 | } |
3022 | if (NULL == state_contains) | 3025 | if (NULL == state_contains) |
3023 | { | 3026 | { |
3024 | new_dfa_state = dfa_state_create (ctx, &nfa_set); | 3027 | new_dfa_state = dfa_state_create(ctx, &nfa_set); |
3025 | automaton_add_state (dfa, new_dfa_state); | 3028 | automaton_add_state(dfa, new_dfa_state); |
3026 | ctran->to_state = new_dfa_state; | 3029 | ctran->to_state = new_dfa_state; |
3027 | construct_dfa_states (ctx, nfa, dfa, new_dfa_state); | 3030 | construct_dfa_states(ctx, nfa, dfa, new_dfa_state); |
3028 | } | 3031 | } |
3029 | else | 3032 | else |
3030 | { | 3033 | { |
3031 | ctran->to_state = state_contains; | 3034 | ctran->to_state = state_contains; |
3032 | state_set_clear (&nfa_set); | 3035 | state_set_clear(&nfa_set); |
3036 | } | ||
3033 | } | 3037 | } |
3034 | } | ||
3035 | } | 3038 | } |
3036 | 3039 | ||
3037 | 3040 | ||
@@ -3053,9 +3056,9 @@ construct_dfa_states (struct REGEX_INTERNAL_Context *ctx, | |||
3053 | * @return DFA, needs to be freed using REGEX_INTERNAL_automaton_destroy. | 3056 | * @return DFA, needs to be freed using REGEX_INTERNAL_automaton_destroy. |
3054 | */ | 3057 | */ |
3055 | struct REGEX_INTERNAL_Automaton * | 3058 | struct REGEX_INTERNAL_Automaton * |
3056 | REGEX_INTERNAL_construct_dfa (const char *regex, | 3059 | REGEX_INTERNAL_construct_dfa(const char *regex, |
3057 | const size_t len, | 3060 | const size_t len, |
3058 | unsigned int max_path_len) | 3061 | unsigned int max_path_len) |
3059 | { | 3062 | { |
3060 | struct REGEX_INTERNAL_Context ctx; | 3063 | struct REGEX_INTERNAL_Context ctx; |
3061 | struct REGEX_INTERNAL_Automaton *dfa; | 3064 | struct REGEX_INTERNAL_Automaton *dfa; |
@@ -3063,50 +3066,50 @@ REGEX_INTERNAL_construct_dfa (const char *regex, | |||
3063 | struct REGEX_INTERNAL_StateSet nfa_start_eps_cls; | 3066 | struct REGEX_INTERNAL_StateSet nfa_start_eps_cls; |
3064 | struct REGEX_INTERNAL_StateSet singleton_set; | 3067 | struct REGEX_INTERNAL_StateSet singleton_set; |
3065 | 3068 | ||
3066 | REGEX_INTERNAL_context_init (&ctx); | 3069 | REGEX_INTERNAL_context_init(&ctx); |
3067 | 3070 | ||
3068 | /* Create NFA */ | 3071 | /* Create NFA */ |
3069 | nfa = REGEX_INTERNAL_construct_nfa (regex, len); | 3072 | nfa = REGEX_INTERNAL_construct_nfa(regex, len); |
3070 | 3073 | ||
3071 | if (NULL == nfa) | 3074 | if (NULL == nfa) |
3072 | { | 3075 | { |
3073 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 3076 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
3074 | "Could not create DFA, because NFA creation failed\n"); | 3077 | "Could not create DFA, because NFA creation failed\n"); |
3075 | return NULL; | 3078 | return NULL; |
3076 | } | 3079 | } |
3077 | 3080 | ||
3078 | dfa = GNUNET_new (struct REGEX_INTERNAL_Automaton); | 3081 | dfa = GNUNET_new(struct REGEX_INTERNAL_Automaton); |
3079 | dfa->type = DFA; | 3082 | dfa->type = DFA; |
3080 | dfa->regex = GNUNET_strdup (regex); | 3083 | dfa->regex = GNUNET_strdup(regex); |
3081 | 3084 | ||
3082 | /* Create DFA start state from epsilon closure */ | 3085 | /* Create DFA start state from epsilon closure */ |
3083 | memset (&singleton_set, 0, sizeof (struct REGEX_INTERNAL_StateSet)); | 3086 | memset(&singleton_set, 0, sizeof(struct REGEX_INTERNAL_StateSet)); |
3084 | state_set_append (&singleton_set, nfa->start); | 3087 | state_set_append(&singleton_set, nfa->start); |
3085 | nfa_closure_set_create (&nfa_start_eps_cls, nfa, &singleton_set, NULL); | 3088 | nfa_closure_set_create(&nfa_start_eps_cls, nfa, &singleton_set, NULL); |
3086 | state_set_clear (&singleton_set); | 3089 | state_set_clear(&singleton_set); |
3087 | dfa->start = dfa_state_create (&ctx, &nfa_start_eps_cls); | 3090 | dfa->start = dfa_state_create(&ctx, &nfa_start_eps_cls); |
3088 | automaton_add_state (dfa, dfa->start); | 3091 | automaton_add_state(dfa, dfa->start); |
3089 | 3092 | ||
3090 | construct_dfa_states (&ctx, nfa, dfa, dfa->start); | 3093 | construct_dfa_states(&ctx, nfa, dfa, dfa->start); |
3091 | REGEX_INTERNAL_automaton_destroy (nfa); | 3094 | REGEX_INTERNAL_automaton_destroy(nfa); |
3092 | 3095 | ||
3093 | /* Minimize DFA */ | 3096 | /* Minimize DFA */ |
3094 | if (GNUNET_OK != dfa_minimize (&ctx, dfa)) | 3097 | if (GNUNET_OK != dfa_minimize(&ctx, dfa)) |
3095 | { | 3098 | { |
3096 | REGEX_INTERNAL_automaton_destroy (dfa); | 3099 | REGEX_INTERNAL_automaton_destroy(dfa); |
3097 | return NULL; | 3100 | return NULL; |
3098 | } | 3101 | } |
3099 | 3102 | ||
3100 | /* Create proofs and hashes for all states */ | 3103 | /* Create proofs and hashes for all states */ |
3101 | if (GNUNET_OK != automaton_create_proofs (dfa)) | 3104 | if (GNUNET_OK != automaton_create_proofs(dfa)) |
3102 | { | 3105 | { |
3103 | REGEX_INTERNAL_automaton_destroy (dfa); | 3106 | REGEX_INTERNAL_automaton_destroy(dfa); |
3104 | return NULL; | 3107 | return NULL; |
3105 | } | 3108 | } |
3106 | 3109 | ||
3107 | /* Compress linear DFA paths */ | 3110 | /* Compress linear DFA paths */ |
3108 | if (1 != max_path_len) | 3111 | if (1 != max_path_len) |
3109 | dfa_compress_paths (&ctx, dfa, max_path_len); | 3112 | dfa_compress_paths(&ctx, dfa, max_path_len); |
3110 | 3113 | ||
3111 | return dfa; | 3114 | return dfa; |
3112 | } | 3115 | } |
@@ -3119,7 +3122,7 @@ REGEX_INTERNAL_construct_dfa (const char *regex, | |||
3119 | * @param a automaton to be destroyed | 3122 | * @param a automaton to be destroyed |
3120 | */ | 3123 | */ |
3121 | void | 3124 | void |
3122 | REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a) | 3125 | REGEX_INTERNAL_automaton_destroy(struct REGEX_INTERNAL_Automaton *a) |
3123 | { | 3126 | { |
3124 | struct REGEX_INTERNAL_State *s; | 3127 | struct REGEX_INTERNAL_State *s; |
3125 | struct REGEX_INTERNAL_State *next_state; | 3128 | struct REGEX_INTERNAL_State *next_state; |
@@ -3127,17 +3130,17 @@ REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a) | |||
3127 | if (NULL == a) | 3130 | if (NULL == a) |
3128 | return; | 3131 | return; |
3129 | 3132 | ||
3130 | GNUNET_free_non_null (a->regex); | 3133 | GNUNET_free_non_null(a->regex); |
3131 | GNUNET_free_non_null (a->canonical_regex); | 3134 | GNUNET_free_non_null(a->canonical_regex); |
3132 | 3135 | ||
3133 | for (s = a->states_head; NULL != s; s = next_state) | 3136 | for (s = a->states_head; NULL != s; s = next_state) |
3134 | { | 3137 | { |
3135 | next_state = s->next; | 3138 | next_state = s->next; |
3136 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | 3139 | GNUNET_CONTAINER_DLL_remove(a->states_head, a->states_tail, s); |
3137 | automaton_destroy_state (s); | 3140 | automaton_destroy_state(s); |
3138 | } | 3141 | } |
3139 | 3142 | ||
3140 | GNUNET_free (a); | 3143 | GNUNET_free(a); |
3141 | } | 3144 | } |
3142 | 3145 | ||
3143 | 3146 | ||
@@ -3150,32 +3153,32 @@ REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a) | |||
3150 | * @return 0 if string matches, non-0 otherwise | 3153 | * @return 0 if string matches, non-0 otherwise |
3151 | */ | 3154 | */ |
3152 | static int | 3155 | static int |
3153 | evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string) | 3156 | evaluate_dfa(struct REGEX_INTERNAL_Automaton *a, const char *string) |
3154 | { | 3157 | { |
3155 | const char *strp; | 3158 | const char *strp; |
3156 | struct REGEX_INTERNAL_State *s; | 3159 | struct REGEX_INTERNAL_State *s; |
3157 | unsigned int step_len; | 3160 | unsigned int step_len; |
3158 | 3161 | ||
3159 | if (DFA != a->type) | 3162 | if (DFA != a->type) |
3160 | { | 3163 | { |
3161 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 3164 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
3162 | "Tried to evaluate DFA, but NFA automaton given"); | 3165 | "Tried to evaluate DFA, but NFA automaton given"); |
3163 | return -1; | 3166 | return -1; |
3164 | } | 3167 | } |
3165 | 3168 | ||
3166 | s = a->start; | 3169 | s = a->start; |
3167 | 3170 | ||
3168 | /* If the string is empty but the starting state is accepting, we accept. */ | 3171 | /* If the string is empty but the starting state is accepting, we accept. */ |
3169 | if ((NULL == string || 0 == strlen (string)) && s->accepting) | 3172 | if ((NULL == string || 0 == strlen(string)) && s->accepting) |
3170 | return 0; | 3173 | return 0; |
3171 | 3174 | ||
3172 | for (strp = string; NULL != strp && *strp; strp += step_len) | 3175 | for (strp = string; NULL != strp && *strp; strp += step_len) |
3173 | { | 3176 | { |
3174 | step_len = dfa_move (&s, strp); | 3177 | step_len = dfa_move(&s, strp); |
3175 | 3178 | ||
3176 | if (NULL == s) | 3179 | if (NULL == s) |
3177 | break; | 3180 | break; |
3178 | } | 3181 | } |
3179 | 3182 | ||
3180 | if (NULL != s && s->accepting) | 3183 | if (NULL != s && s->accepting) |
3181 | return 0; | 3184 | return 0; |
@@ -3192,7 +3195,7 @@ evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string) | |||
3192 | * @return 0 if string matches, non-0 otherwise | 3195 | * @return 0 if string matches, non-0 otherwise |
3193 | */ | 3196 | */ |
3194 | static int | 3197 | static int |
3195 | evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string) | 3198 | evaluate_nfa(struct REGEX_INTERNAL_Automaton *a, const char *string) |
3196 | { | 3199 | { |
3197 | const char *strp; | 3200 | const char *strp; |
3198 | char str[2]; | 3201 | char str[2]; |
@@ -3204,43 +3207,43 @@ evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string) | |||
3204 | int result; | 3207 | int result; |
3205 | 3208 | ||
3206 | if (NFA != a->type) | 3209 | if (NFA != a->type) |
3207 | { | 3210 | { |
3208 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 3211 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
3209 | "Tried to evaluate NFA, but DFA automaton given"); | 3212 | "Tried to evaluate NFA, but DFA automaton given"); |
3210 | return -1; | 3213 | return -1; |
3211 | } | 3214 | } |
3212 | 3215 | ||
3213 | /* If the string is empty but the starting state is accepting, we accept. */ | 3216 | /* If the string is empty but the starting state is accepting, we accept. */ |
3214 | if ((NULL == string || 0 == strlen (string)) && a->start->accepting) | 3217 | if ((NULL == string || 0 == strlen(string)) && a->start->accepting) |
3215 | return 0; | 3218 | return 0; |
3216 | 3219 | ||
3217 | result = 1; | 3220 | result = 1; |
3218 | memset (&singleton_set, 0, sizeof (struct REGEX_INTERNAL_StateSet)); | 3221 | memset(&singleton_set, 0, sizeof(struct REGEX_INTERNAL_StateSet)); |
3219 | state_set_append (&singleton_set, a->start); | 3222 | state_set_append(&singleton_set, a->start); |
3220 | nfa_closure_set_create (&sset, a, &singleton_set, NULL); | 3223 | nfa_closure_set_create(&sset, a, &singleton_set, NULL); |
3221 | state_set_clear (&singleton_set); | 3224 | state_set_clear(&singleton_set); |
3222 | 3225 | ||
3223 | str[1] = '\0'; | 3226 | str[1] = '\0'; |
3224 | for (strp = string; NULL != strp && *strp; strp++) | 3227 | for (strp = string; NULL != strp && *strp; strp++) |
3225 | { | 3228 | { |
3226 | str[0] = *strp; | 3229 | str[0] = *strp; |
3227 | nfa_closure_set_create (&new_sset, a, &sset, str); | 3230 | nfa_closure_set_create(&new_sset, a, &sset, str); |
3228 | state_set_clear (&sset); | 3231 | state_set_clear(&sset); |
3229 | nfa_closure_set_create (&sset, a, &new_sset, 0); | 3232 | nfa_closure_set_create(&sset, a, &new_sset, 0); |
3230 | state_set_clear (&new_sset); | 3233 | state_set_clear(&new_sset); |
3231 | } | 3234 | } |
3232 | 3235 | ||
3233 | for (i = 0; i < sset.off; i++) | 3236 | for (i = 0; i < sset.off; i++) |
3234 | { | ||
3235 | s = sset.states[i]; | ||
3236 | if ((NULL != s) && (s->accepting)) | ||
3237 | { | 3237 | { |
3238 | result = 0; | 3238 | s = sset.states[i]; |
3239 | break; | 3239 | if ((NULL != s) && (s->accepting)) |
3240 | { | ||
3241 | result = 0; | ||
3242 | break; | ||
3243 | } | ||
3240 | } | 3244 | } |
3241 | } | ||
3242 | 3245 | ||
3243 | state_set_clear (&sset); | 3246 | state_set_clear(&sset); |
3244 | return result; | 3247 | return result; |
3245 | } | 3248 | } |
3246 | 3249 | ||
@@ -3253,24 +3256,26 @@ evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string) | |||
3253 | * @return 0 if string matches, non-0 otherwise | 3256 | * @return 0 if string matches, non-0 otherwise |
3254 | */ | 3257 | */ |
3255 | int | 3258 | int |
3256 | REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string) | 3259 | REGEX_INTERNAL_eval(struct REGEX_INTERNAL_Automaton *a, const char *string) |
3257 | { | 3260 | { |
3258 | int result; | 3261 | int result; |
3259 | 3262 | ||
3260 | switch (a->type) | 3263 | switch (a->type) |
3261 | { | 3264 | { |
3262 | case DFA: | 3265 | case DFA: |
3263 | result = evaluate_dfa (a, string); | 3266 | result = evaluate_dfa(a, string); |
3264 | break; | 3267 | break; |
3265 | case NFA: | 3268 | |
3266 | result = evaluate_nfa (a, string); | 3269 | case NFA: |
3267 | break; | 3270 | result = evaluate_nfa(a, string); |
3268 | default: | 3271 | break; |
3269 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 3272 | |
3270 | "Evaluating regex failed, automaton has no type!\n"); | 3273 | default: |
3271 | result = GNUNET_SYSERR; | 3274 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, |
3272 | break; | 3275 | "Evaluating regex failed, automaton has no type!\n"); |
3273 | } | 3276 | result = GNUNET_SYSERR; |
3277 | break; | ||
3278 | } | ||
3274 | 3279 | ||
3275 | return result; | 3280 | return result; |
3276 | } | 3281 | } |
@@ -3288,7 +3293,7 @@ REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string) | |||
3288 | * @return | 3293 | * @return |
3289 | */ | 3294 | */ |
3290 | const char * | 3295 | const char * |
3291 | REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a) | 3296 | REGEX_INTERNAL_get_canonical_regex(struct REGEX_INTERNAL_Automaton *a) |
3292 | { | 3297 | { |
3293 | if (NULL == a) | 3298 | if (NULL == a) |
3294 | return NULL; | 3299 | return NULL; |
@@ -3305,7 +3310,7 @@ REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a) | |||
3305 | * @return number of transitions in the given automaton. | 3310 | * @return number of transitions in the given automaton. |
3306 | */ | 3311 | */ |
3307 | unsigned int | 3312 | unsigned int |
3308 | REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a) | 3313 | REGEX_INTERNAL_get_transition_count(struct REGEX_INTERNAL_Automaton *a) |
3309 | { | 3314 | { |
3310 | unsigned int t_count; | 3315 | unsigned int t_count; |
3311 | struct REGEX_INTERNAL_State *s; | 3316 | struct REGEX_INTERNAL_State *s; |
@@ -3332,20 +3337,20 @@ REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a) | |||
3332 | * to construct the key | 3337 | * to construct the key |
3333 | */ | 3338 | */ |
3334 | size_t | 3339 | size_t |
3335 | REGEX_INTERNAL_get_first_key (const char *input_string, | 3340 | REGEX_INTERNAL_get_first_key(const char *input_string, |
3336 | size_t string_len, | 3341 | size_t string_len, |
3337 | struct GNUNET_HashCode *key) | 3342 | struct GNUNET_HashCode *key) |
3338 | { | 3343 | { |
3339 | size_t size; | 3344 | size_t size; |
3340 | 3345 | ||
3341 | size = string_len < GNUNET_REGEX_INITIAL_BYTES ? string_len | 3346 | size = string_len < GNUNET_REGEX_INITIAL_BYTES ? string_len |
3342 | : GNUNET_REGEX_INITIAL_BYTES; | 3347 | : GNUNET_REGEX_INITIAL_BYTES; |
3343 | if (NULL == input_string) | 3348 | if (NULL == input_string) |
3344 | { | 3349 | { |
3345 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n"); | 3350 | GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n"); |
3346 | return 0; | 3351 | return 0; |
3347 | } | 3352 | } |
3348 | GNUNET_CRYPTO_hash (input_string, size, key); | 3353 | GNUNET_CRYPTO_hash(input_string, size, key); |
3349 | 3354 | ||
3350 | return size; | 3355 | return size; |
3351 | } | 3356 | } |
@@ -3362,12 +3367,12 @@ REGEX_INTERNAL_get_first_key (const char *input_string, | |||
3362 | * @param iterator_cls closure for the @a iterator function. | 3367 | * @param iterator_cls closure for the @a iterator function. |
3363 | */ | 3368 | */ |
3364 | static void | 3369 | static void |
3365 | iterate_initial_edge (unsigned int min_len, | 3370 | iterate_initial_edge(unsigned int min_len, |
3366 | unsigned int max_len, | 3371 | unsigned int max_len, |
3367 | char *consumed_string, | 3372 | char *consumed_string, |
3368 | struct REGEX_INTERNAL_State *state, | 3373 | struct REGEX_INTERNAL_State *state, |
3369 | REGEX_INTERNAL_KeyIterator iterator, | 3374 | REGEX_INTERNAL_KeyIterator iterator, |
3370 | void *iterator_cls) | 3375 | void *iterator_cls) |
3371 | { | 3376 | { |
3372 | char *temp; | 3377 | char *temp; |
3373 | struct REGEX_INTERNAL_Transition *t; | 3378 | struct REGEX_INTERNAL_Transition *t; |
@@ -3379,91 +3384,91 @@ iterate_initial_edge (unsigned int min_len, | |||
3379 | unsigned int cur_len; | 3384 | unsigned int cur_len; |
3380 | 3385 | ||
3381 | if (NULL != consumed_string) | 3386 | if (NULL != consumed_string) |
3382 | cur_len = strlen (consumed_string); | 3387 | cur_len = strlen(consumed_string); |
3383 | else | 3388 | else |
3384 | cur_len = 0; | 3389 | cur_len = 0; |
3385 | 3390 | ||
3386 | if (((cur_len >= min_len) || (GNUNET_YES == state->accepting)) && | 3391 | if (((cur_len >= min_len) || (GNUNET_YES == state->accepting)) && |
3387 | (cur_len > 0) && (NULL != consumed_string)) | 3392 | (cur_len > 0) && (NULL != consumed_string)) |
3388 | { | ||
3389 | if (cur_len <= max_len) | ||
3390 | { | 3393 | { |
3391 | if ((NULL != state->proof) && | 3394 | if (cur_len <= max_len) |
3392 | (0 != strcmp (consumed_string, state->proof))) | 3395 | { |
3393 | { | 3396 | if ((NULL != state->proof) && |
3394 | (void) state_get_edges (state, edges); | 3397 | (0 != strcmp(consumed_string, state->proof))) |
3395 | GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash); | 3398 | { |
3396 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 3399 | (void)state_get_edges(state, edges); |
3397 | "Start state for string `%s' is %s\n", | 3400 | GNUNET_CRYPTO_hash(consumed_string, strlen(consumed_string), &hash); |
3398 | consumed_string, | 3401 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
3399 | GNUNET_h2s (&hash)); | 3402 | "Start state for string `%s' is %s\n", |
3400 | iterator (iterator_cls, | 3403 | consumed_string, |
3401 | &hash, | 3404 | GNUNET_h2s(&hash)); |
3402 | consumed_string, | 3405 | iterator(iterator_cls, |
3403 | state->accepting, | 3406 | &hash, |
3404 | num_edges, | 3407 | consumed_string, |
3405 | edges); | 3408 | state->accepting, |
3406 | } | 3409 | num_edges, |
3410 | edges); | ||
3411 | } | ||
3407 | 3412 | ||
3408 | if ((GNUNET_YES == state->accepting) && (cur_len > 1) && | 3413 | if ((GNUNET_YES == state->accepting) && (cur_len > 1) && |
3409 | (state->transition_count < 1) && (cur_len < max_len)) | 3414 | (state->transition_count < 1) && (cur_len < max_len)) |
3410 | { | 3415 | { |
3411 | /* Special case for regex consisting of just a string that is shorter than | 3416 | /* Special case for regex consisting of just a string that is shorter than |
3412 | * max_len */ | 3417 | * max_len */ |
3413 | edge[0].label = &consumed_string[cur_len - 1]; | 3418 | edge[0].label = &consumed_string[cur_len - 1]; |
3414 | edge[0].destination = state->hash; | 3419 | edge[0].destination = state->hash; |
3415 | temp = GNUNET_strdup (consumed_string); | 3420 | temp = GNUNET_strdup(consumed_string); |
3416 | temp[cur_len - 1] = '\0'; | 3421 | temp[cur_len - 1] = '\0'; |
3417 | GNUNET_CRYPTO_hash (temp, cur_len - 1, &hash_new); | 3422 | GNUNET_CRYPTO_hash(temp, cur_len - 1, &hash_new); |
3418 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 3423 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
3419 | "Start state for short string `%s' is %s\n", | 3424 | "Start state for short string `%s' is %s\n", |
3420 | temp, | 3425 | temp, |
3421 | GNUNET_h2s (&hash_new)); | 3426 | GNUNET_h2s(&hash_new)); |
3422 | iterator (iterator_cls, &hash_new, temp, GNUNET_NO, 1, edge); | 3427 | iterator(iterator_cls, &hash_new, temp, GNUNET_NO, 1, edge); |
3423 | GNUNET_free (temp); | 3428 | GNUNET_free(temp); |
3424 | } | 3429 | } |
3425 | } | 3430 | } |
3426 | else /* cur_len > max_len */ | 3431 | else /* cur_len > max_len */ |
3427 | { | 3432 | { |
3428 | /* Case where the concatenated labels are longer than max_len, then split. */ | 3433 | /* Case where the concatenated labels are longer than max_len, then split. */ |
3429 | edge[0].label = &consumed_string[max_len]; | 3434 | edge[0].label = &consumed_string[max_len]; |
3430 | edge[0].destination = state->hash; | 3435 | edge[0].destination = state->hash; |
3431 | temp = GNUNET_strdup (consumed_string); | 3436 | temp = GNUNET_strdup(consumed_string); |
3432 | temp[max_len] = '\0'; | 3437 | temp[max_len] = '\0'; |
3433 | GNUNET_CRYPTO_hash (temp, max_len, &hash); | 3438 | GNUNET_CRYPTO_hash(temp, max_len, &hash); |
3434 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 3439 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
3435 | "Start state at split edge `%s'-`%s` is %s\n", | 3440 | "Start state at split edge `%s'-`%s` is %s\n", |
3436 | temp, | 3441 | temp, |
3437 | edge[0].label, | 3442 | edge[0].label, |
3438 | GNUNET_h2s (&hash_new)); | 3443 | GNUNET_h2s(&hash_new)); |
3439 | iterator (iterator_cls, &hash, temp, GNUNET_NO, 1, edge); | 3444 | iterator(iterator_cls, &hash, temp, GNUNET_NO, 1, edge); |
3440 | GNUNET_free (temp); | 3445 | GNUNET_free(temp); |
3446 | } | ||
3441 | } | 3447 | } |
3442 | } | ||
3443 | 3448 | ||
3444 | if (cur_len < max_len) | 3449 | if (cur_len < max_len) |
3445 | { | ||
3446 | for (t = state->transitions_head; NULL != t; t = t->next) | ||
3447 | { | 3450 | { |
3448 | if (NULL != strchr (t->label, (int) '.')) | 3451 | for (t = state->transitions_head; NULL != t; t = t->next) |
3449 | { | 3452 | { |
3450 | /* Wildcards not allowed during starting states */ | 3453 | if (NULL != strchr(t->label, (int)'.')) |
3451 | GNUNET_break (0); | 3454 | { |
3452 | continue; | 3455 | /* Wildcards not allowed during starting states */ |
3453 | } | 3456 | GNUNET_break(0); |
3454 | if (NULL != consumed_string) | 3457 | continue; |
3455 | GNUNET_asprintf (&temp, "%s%s", consumed_string, t->label); | 3458 | } |
3456 | else | 3459 | if (NULL != consumed_string) |
3457 | GNUNET_asprintf (&temp, "%s", t->label); | 3460 | GNUNET_asprintf(&temp, "%s%s", consumed_string, t->label); |
3458 | iterate_initial_edge (min_len, | 3461 | else |
3459 | max_len, | 3462 | GNUNET_asprintf(&temp, "%s", t->label); |
3460 | temp, | 3463 | iterate_initial_edge(min_len, |
3461 | t->to_state, | 3464 | max_len, |
3462 | iterator, | 3465 | temp, |
3463 | iterator_cls); | 3466 | t->to_state, |
3464 | GNUNET_free (temp); | 3467 | iterator, |
3468 | iterator_cls); | ||
3469 | GNUNET_free(temp); | ||
3470 | } | ||
3465 | } | 3471 | } |
3466 | } | ||
3467 | } | 3472 | } |
3468 | 3473 | ||
3469 | 3474 | ||
@@ -3476,41 +3481,41 @@ iterate_initial_edge (unsigned int min_len, | |||
3476 | * @param iterator_cls closure. | 3481 | * @param iterator_cls closure. |
3477 | */ | 3482 | */ |
3478 | void | 3483 | void |
3479 | REGEX_INTERNAL_iterate_all_edges (struct REGEX_INTERNAL_Automaton *a, | 3484 | REGEX_INTERNAL_iterate_all_edges(struct REGEX_INTERNAL_Automaton *a, |
3480 | REGEX_INTERNAL_KeyIterator iterator, | 3485 | REGEX_INTERNAL_KeyIterator iterator, |
3481 | void *iterator_cls) | 3486 | void *iterator_cls) |
3482 | { | 3487 | { |
3483 | struct REGEX_INTERNAL_State *s; | 3488 | struct REGEX_INTERNAL_State *s; |
3484 | 3489 | ||
3485 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating over starting edges\n"); | 3490 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Iterating over starting edges\n"); |
3486 | iterate_initial_edge (GNUNET_REGEX_INITIAL_BYTES, | 3491 | iterate_initial_edge(GNUNET_REGEX_INITIAL_BYTES, |
3487 | GNUNET_REGEX_INITIAL_BYTES, | 3492 | GNUNET_REGEX_INITIAL_BYTES, |
3488 | NULL, | 3493 | NULL, |
3489 | a->start, | 3494 | a->start, |
3490 | iterator, | 3495 | iterator, |
3491 | iterator_cls); | 3496 | iterator_cls); |
3492 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating over DFA edges\n"); | 3497 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Iterating over DFA edges\n"); |
3493 | for (s = a->states_head; NULL != s; s = s->next) | 3498 | for (s = a->states_head; NULL != s; s = s->next) |
3494 | { | 3499 | { |
3495 | struct REGEX_BLOCK_Edge edges[s->transition_count]; | 3500 | struct REGEX_BLOCK_Edge edges[s->transition_count]; |
3496 | unsigned int num_edges; | 3501 | unsigned int num_edges; |
3497 | 3502 | ||
3498 | num_edges = state_get_edges (s, edges); | 3503 | num_edges = state_get_edges(s, edges); |
3499 | if (((NULL != s->proof) && (0 < strlen (s->proof))) || s->accepting) | 3504 | if (((NULL != s->proof) && (0 < strlen(s->proof))) || s->accepting) |
3500 | { | 3505 | { |
3501 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 3506 | GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, |
3502 | "Creating DFA edges at `%s' under key %s\n", | 3507 | "Creating DFA edges at `%s' under key %s\n", |
3503 | s->proof, | 3508 | s->proof, |
3504 | GNUNET_h2s (&s->hash)); | 3509 | GNUNET_h2s(&s->hash)); |
3505 | iterator (iterator_cls, | 3510 | iterator(iterator_cls, |
3506 | &s->hash, | 3511 | &s->hash, |
3507 | s->proof, | 3512 | s->proof, |
3508 | s->accepting, | 3513 | s->accepting, |
3509 | num_edges, | 3514 | num_edges, |
3510 | edges); | 3515 | edges); |
3516 | } | ||
3517 | s->marked = GNUNET_NO; | ||
3511 | } | 3518 | } |
3512 | s->marked = GNUNET_NO; | ||
3513 | } | ||
3514 | } | 3519 | } |
3515 | 3520 | ||
3516 | 3521 | ||
@@ -3520,8 +3525,7 @@ REGEX_INTERNAL_iterate_all_edges (struct REGEX_INTERNAL_Automaton *a, | |||
3520 | * Contains the same info as the Regex Iterator parametes except the key, | 3525 | * Contains the same info as the Regex Iterator parametes except the key, |
3521 | * which comes directly from the HashMap iterator. | 3526 | * which comes directly from the HashMap iterator. |
3522 | */ | 3527 | */ |
3523 | struct temporal_state_store | 3528 | struct temporal_state_store { |
3524 | { | ||
3525 | int reachable; | 3529 | int reachable; |
3526 | char *proof; | 3530 | char *proof; |
3527 | int accepting; | 3531 | int accepting; |
@@ -3533,8 +3537,7 @@ struct temporal_state_store | |||
3533 | /** | 3537 | /** |
3534 | * Store regex iterator and cls in one place to pass to the hashmap iterator. | 3538 | * Store regex iterator and cls in one place to pass to the hashmap iterator. |
3535 | */ | 3539 | */ |
3536 | struct client_iterator | 3540 | struct client_iterator { |
3537 | { | ||
3538 | REGEX_INTERNAL_KeyIterator iterator; | 3541 | REGEX_INTERNAL_KeyIterator iterator; |
3539 | void *iterator_cls; | 3542 | void *iterator_cls; |
3540 | }; | 3543 | }; |
@@ -3552,31 +3555,31 @@ struct client_iterator | |||
3552 | * @param edges edges leaving current state. | 3555 | * @param edges edges leaving current state. |
3553 | */ | 3556 | */ |
3554 | static void | 3557 | static void |
3555 | store_all_states (void *cls, | 3558 | store_all_states(void *cls, |
3556 | const struct GNUNET_HashCode *key, | 3559 | const struct GNUNET_HashCode *key, |
3557 | const char *proof, | 3560 | const char *proof, |
3558 | int accepting, | 3561 | int accepting, |
3559 | unsigned int num_edges, | 3562 | unsigned int num_edges, |
3560 | const struct REGEX_BLOCK_Edge *edges) | 3563 | const struct REGEX_BLOCK_Edge *edges) |
3561 | { | 3564 | { |
3562 | struct GNUNET_CONTAINER_MultiHashMap *hm = cls; | 3565 | struct GNUNET_CONTAINER_MultiHashMap *hm = cls; |
3563 | struct temporal_state_store *tmp; | 3566 | struct temporal_state_store *tmp; |
3564 | size_t edges_size; | 3567 | size_t edges_size; |
3565 | 3568 | ||
3566 | tmp = GNUNET_new (struct temporal_state_store); | 3569 | tmp = GNUNET_new(struct temporal_state_store); |
3567 | tmp->reachable = GNUNET_NO; | 3570 | tmp->reachable = GNUNET_NO; |
3568 | tmp->proof = GNUNET_strdup (proof); | 3571 | tmp->proof = GNUNET_strdup(proof); |
3569 | tmp->accepting = accepting; | 3572 | tmp->accepting = accepting; |
3570 | tmp->num_edges = num_edges; | 3573 | tmp->num_edges = num_edges; |
3571 | edges_size = sizeof (struct REGEX_BLOCK_Edge) * num_edges; | 3574 | edges_size = sizeof(struct REGEX_BLOCK_Edge) * num_edges; |
3572 | tmp->edges = GNUNET_malloc (edges_size); | 3575 | tmp->edges = GNUNET_malloc(edges_size); |
3573 | GNUNET_memcpy (tmp->edges, edges, edges_size); | 3576 | GNUNET_memcpy(tmp->edges, edges, edges_size); |
3574 | GNUNET_assert (GNUNET_YES == | 3577 | GNUNET_assert(GNUNET_YES == |
3575 | GNUNET_CONTAINER_multihashmap_put ( | 3578 | GNUNET_CONTAINER_multihashmap_put( |
3576 | hm, | 3579 | hm, |
3577 | key, | 3580 | key, |
3578 | tmp, | 3581 | tmp, |
3579 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)); | 3582 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)); |
3580 | } | 3583 | } |
3581 | 3584 | ||
3582 | 3585 | ||
@@ -3589,8 +3592,8 @@ store_all_states (void *cls, | |||
3589 | * @param hm HashMap which stores all the states indexed by key. | 3592 | * @param hm HashMap which stores all the states indexed by key. |
3590 | */ | 3593 | */ |
3591 | static void | 3594 | static void |
3592 | mark_as_reachable (struct temporal_state_store *state, | 3595 | mark_as_reachable(struct temporal_state_store *state, |
3593 | struct GNUNET_CONTAINER_MultiHashMap *hm) | 3596 | struct GNUNET_CONTAINER_MultiHashMap *hm) |
3594 | { | 3597 | { |
3595 | struct temporal_state_store *child; | 3598 | struct temporal_state_store *child; |
3596 | unsigned int i; | 3599 | unsigned int i; |
@@ -3601,16 +3604,16 @@ mark_as_reachable (struct temporal_state_store *state, | |||
3601 | 3604 | ||
3602 | state->reachable = GNUNET_YES; | 3605 | state->reachable = GNUNET_YES; |
3603 | for (i = 0; i < state->num_edges; i++) | 3606 | for (i = 0; i < state->num_edges; i++) |
3604 | { | ||
3605 | child = | ||
3606 | GNUNET_CONTAINER_multihashmap_get (hm, &state->edges[i].destination); | ||
3607 | if (NULL == child) | ||
3608 | { | 3607 | { |
3609 | GNUNET_break (0); | 3608 | child = |
3610 | continue; | 3609 | GNUNET_CONTAINER_multihashmap_get(hm, &state->edges[i].destination); |
3610 | if (NULL == child) | ||
3611 | { | ||
3612 | GNUNET_break(0); | ||
3613 | continue; | ||
3614 | } | ||
3615 | mark_as_reachable(child, hm); | ||
3611 | } | 3616 | } |
3612 | mark_as_reachable (child, hm); | ||
3613 | } | ||
3614 | } | 3617 | } |
3615 | 3618 | ||
3616 | 3619 | ||
@@ -3624,9 +3627,9 @@ mark_as_reachable (struct temporal_state_store *state, | |||
3624 | * #GNUNET_NO if not. | 3627 | * #GNUNET_NO if not. |
3625 | */ | 3628 | */ |
3626 | static int | 3629 | static int |
3627 | reachability_iterator (void *cls, | 3630 | reachability_iterator(void *cls, |
3628 | const struct GNUNET_HashCode *key, | 3631 | const struct GNUNET_HashCode *key, |
3629 | void *value) | 3632 | void *value) |
3630 | { | 3633 | { |
3631 | struct GNUNET_CONTAINER_MultiHashMap *hm = cls; | 3634 | struct GNUNET_CONTAINER_MultiHashMap *hm = cls; |
3632 | struct temporal_state_store *state = value; | 3635 | struct temporal_state_store *state = value; |
@@ -3635,12 +3638,12 @@ reachability_iterator (void *cls, | |||
3635 | /* already visited and marked */ | 3638 | /* already visited and marked */ |
3636 | return GNUNET_YES; | 3639 | return GNUNET_YES; |
3637 | 3640 | ||
3638 | if (GNUNET_REGEX_INITIAL_BYTES > strlen (state->proof) && | 3641 | if (GNUNET_REGEX_INITIAL_BYTES > strlen(state->proof) && |
3639 | GNUNET_NO == state->accepting) | 3642 | GNUNET_NO == state->accepting) |
3640 | /* not directly reachable */ | 3643 | /* not directly reachable */ |
3641 | return GNUNET_YES; | 3644 | return GNUNET_YES; |
3642 | 3645 | ||
3643 | mark_as_reachable (state, hm); | 3646 | mark_as_reachable(state, hm); |
3644 | return GNUNET_YES; | 3647 | return GNUNET_YES; |
3645 | } | 3648 | } |
3646 | 3649 | ||
@@ -3656,23 +3659,23 @@ reachability_iterator (void *cls, | |||
3656 | * #GNUNET_NO if not. | 3659 | * #GNUNET_NO if not. |
3657 | */ | 3660 | */ |
3658 | static int | 3661 | static int |
3659 | iterate_reachables (void *cls, const struct GNUNET_HashCode *key, void *value) | 3662 | iterate_reachables(void *cls, const struct GNUNET_HashCode *key, void *value) |
3660 | { | 3663 | { |
3661 | struct client_iterator *ci = cls; | 3664 | struct client_iterator *ci = cls; |
3662 | struct temporal_state_store *state = value; | 3665 | struct temporal_state_store *state = value; |
3663 | 3666 | ||
3664 | if (GNUNET_YES == state->reachable) | 3667 | if (GNUNET_YES == state->reachable) |
3665 | { | 3668 | { |
3666 | ci->iterator (ci->iterator_cls, | 3669 | ci->iterator(ci->iterator_cls, |
3667 | key, | 3670 | key, |
3668 | state->proof, | 3671 | state->proof, |
3669 | state->accepting, | 3672 | state->accepting, |
3670 | state->num_edges, | 3673 | state->num_edges, |
3671 | state->edges); | 3674 | state->edges); |
3672 | } | 3675 | } |
3673 | GNUNET_free (state->edges); | 3676 | GNUNET_free(state->edges); |
3674 | GNUNET_free (state->proof); | 3677 | GNUNET_free(state->proof); |
3675 | GNUNET_free (state); | 3678 | GNUNET_free(state); |
3676 | return GNUNET_YES; | 3679 | return GNUNET_YES; |
3677 | } | 3680 | } |
3678 | 3681 | ||
@@ -3687,22 +3690,22 @@ iterate_reachables (void *cls, const struct GNUNET_HashCode *key, void *value) | |||
3687 | * @param iterator_cls closure. | 3690 | * @param iterator_cls closure. |
3688 | */ | 3691 | */ |
3689 | void | 3692 | void |
3690 | REGEX_INTERNAL_iterate_reachable_edges (struct REGEX_INTERNAL_Automaton *a, | 3693 | REGEX_INTERNAL_iterate_reachable_edges(struct REGEX_INTERNAL_Automaton *a, |
3691 | REGEX_INTERNAL_KeyIterator iterator, | 3694 | REGEX_INTERNAL_KeyIterator iterator, |
3692 | void *iterator_cls) | 3695 | void *iterator_cls) |
3693 | { | 3696 | { |
3694 | struct GNUNET_CONTAINER_MultiHashMap *hm; | 3697 | struct GNUNET_CONTAINER_MultiHashMap *hm; |
3695 | struct client_iterator ci; | 3698 | struct client_iterator ci; |
3696 | 3699 | ||
3697 | hm = GNUNET_CONTAINER_multihashmap_create (a->state_count * 2, GNUNET_NO); | 3700 | hm = GNUNET_CONTAINER_multihashmap_create(a->state_count * 2, GNUNET_NO); |
3698 | ci.iterator = iterator; | 3701 | ci.iterator = iterator; |
3699 | ci.iterator_cls = iterator_cls; | 3702 | ci.iterator_cls = iterator_cls; |
3700 | 3703 | ||
3701 | REGEX_INTERNAL_iterate_all_edges (a, &store_all_states, hm); | 3704 | REGEX_INTERNAL_iterate_all_edges(a, &store_all_states, hm); |
3702 | GNUNET_CONTAINER_multihashmap_iterate (hm, &reachability_iterator, hm); | 3705 | GNUNET_CONTAINER_multihashmap_iterate(hm, &reachability_iterator, hm); |
3703 | GNUNET_CONTAINER_multihashmap_iterate (hm, &iterate_reachables, &ci); | 3706 | GNUNET_CONTAINER_multihashmap_iterate(hm, &iterate_reachables, &ci); |
3704 | 3707 | ||
3705 | GNUNET_CONTAINER_multihashmap_destroy (hm); | 3708 | GNUNET_CONTAINER_multihashmap_destroy(hm); |
3706 | } | 3709 | } |
3707 | 3710 | ||
3708 | 3711 | ||