summaryrefslogtreecommitdiff
path: root/src/regex/regex_internal.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/regex/regex_internal.c')
-rw-r--r--src/regex/regex_internal.c3107
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 */
42struct REGEX_INTERNAL_StateSet_MDLL 42struct 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 */
67static void 66static void
68state_set_append (struct REGEX_INTERNAL_StateSet *set, 67state_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 */
85static int 84static int
86nullstrcmp (const char *str1, const char *str2) 85nullstrcmp(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 */
106static void 105static void
107state_add_transition (struct REGEX_INTERNAL_Context *ctx, 106state_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 */
161static void 160static void
162state_remove_transition (struct REGEX_INTERNAL_State *state, 161state_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 */
192static int 191static int
193state_compare (const void *a, const void *b) 192state_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 */
211static unsigned int 210static unsigned int
212state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges) 211state_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 */
243static int 242static int
244state_set_compare (struct REGEX_INTERNAL_StateSet *sset1, 243state_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 */
270static void 269static void
271state_set_clear (struct REGEX_INTERNAL_StateSet *set) 270state_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 */
284static void 283static void
285automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a) 284automaton_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 */
304static void 303static void
305automaton_destroy_state (struct REGEX_INTERNAL_State *s) 304automaton_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 */
334static void 333static void
335automaton_remove_state (struct REGEX_INTERNAL_Automaton *a, 334automaton_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 */
374static void 373static void
375automaton_merge_states (struct REGEX_INTERNAL_Context *ctx, 374automaton_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 */
443static void 442static void
444automaton_add_state (struct REGEX_INTERNAL_Automaton *a, 443automaton_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 */
466static void 465static void
467automaton_state_traverse (struct REGEX_INTERNAL_State *s, 466automaton_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 */
517void 516void
518REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a, 517REGEX_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 */
560struct StringBuffer 559struct 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 */
609static int 607static int
610sb_nullstrcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) 608sb_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 */
632static int 630static int
633sb_strcmp (const struct StringBuffer *s1, const struct StringBuffer *s2) 631sb_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 */
650static void 648static void
651sb_realloc (struct StringBuffer *ret, size_t nlen) 649sb_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 */
671static void 669static void
672sb_append (struct StringBuffer *ret, const struct StringBuffer *sarg) 670sb_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 */
690static void 688static void
691sb_append_cstr (struct StringBuffer *ret, const char *cstr) 689sb_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 */
715static void 713static void
716sb_wrap (struct StringBuffer *ret, const char *format, size_t extra_chars) 714sb_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 */
746static void 744static void
747sb_printf1 (struct StringBuffer *ret, 745sb_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 */
770static void 768static void
771sb_printf2 (struct StringBuffer *ret, 769sb_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 */
803static void 801static void
804sb_printf3 (struct StringBuffer *ret, 802sb_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 */
834static void 832static void
835sb_free (struct StringBuffer *sb) 833sb_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 */
850static void 848static void
851sb_strdup (struct StringBuffer *out, const struct StringBuffer *in) 849sb_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 */
873static void 871static void
874sb_strdup_cstr (struct StringBuffer *out, const char *cstr) 872sb_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 */
900static int 898static int
901needs_parentheses (const struct StringBuffer *str) 899needs_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 */
949static void 947static void
950remove_parentheses (struct StringBuffer *str) 948remove_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 */
1006static int 1004static int
1007has_epsilon (const struct StringBuffer *str) 1005has_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 */
1024static void 1022static void
1025remove_epsilon (const struct StringBuffer *str, struct StringBuffer *ret) 1023remove_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 */
1058static int 1056static int
1059sb_strncmp (const struct StringBuffer *str1, 1057sb_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 */
1083static int 1081static int
1084sb_strncmp_cstr (const struct StringBuffer *str1, const char *str2, size_t n) 1082sb_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 */
1099static void 1097static void
1100sb_init (struct StringBuffer *sb, size_t n) 1098sb_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 */
1118static int 1116static int
1119sb_strkcmp (const struct StringBuffer *str1, 1117sb_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 */
1138static void 1136static void
1139number_states (void *cls, 1137number_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 */
1170static void 1168static void
1171automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij, 1169automaton_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 */
1579static int 1577static int
1580automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a) 1578automaton_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 */
1745static struct REGEX_INTERNAL_State * 1743static struct REGEX_INTERNAL_State *
1746dfa_state_create (struct REGEX_INTERNAL_Context *ctx, 1744dfa_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 */
1815static unsigned int 1813static unsigned int
1816dfa_move (struct REGEX_INTERNAL_State **s, const char *str) 1814dfa_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 */
1856static void 1854static void
1857mark_states (void *cls, 1855mark_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 */
1871static void 1869static void
1872dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a) 1870dfa_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 */
1905static void 1903static void
1906dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a) 1904dfa_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 */
1948static int 1946static int
1949dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx, 1947dfa_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 */
2068static int 2066static int
2069dfa_minimize (struct REGEX_INTERNAL_Context *ctx, 2067dfa_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 */
2093struct REGEX_INTERNAL_Strided_Context 2091struct 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 */
2123static void 2120static void
2124dfa_add_multi_strides_helper (void *cls, 2121dfa_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 */
2179static void 2176static void
2180dfa_add_multi_strides (void *cls, 2177dfa_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 */
2195void 2192void
2196REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx, 2193REGEX_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 */
2242void 2239void
2243dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa, 2240dfa_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 */
2318static void 2315static void
2319dfa_compress_paths (struct REGEX_INTERNAL_Context *regex_ctx, 2316dfa_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 */
2388static struct REGEX_INTERNAL_Automaton * 2385static struct REGEX_INTERNAL_Automaton *
2389nfa_fragment_create (struct REGEX_INTERNAL_State *start, 2386nfa_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 */
2423static void 2420static void
2424nfa_add_states (struct REGEX_INTERNAL_Automaton *n, 2421nfa_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 */
2462static struct REGEX_INTERNAL_State * 2459static struct REGEX_INTERNAL_State *
2463nfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting) 2460nfa_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 */
2491static void 2488static void
2492nfa_closure_set_create (struct REGEX_INTERNAL_StateSet *ret, 2489nfa_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 */
2564static void 2561static void
2565nfa_add_concatenation (struct REGEX_INTERNAL_Context *ctx) 2562nfa_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 */
2600static void 2597static void
2601nfa_add_star_op (struct REGEX_INTERNAL_Context *ctx) 2598nfa_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 */
2644static void 2641static void
2645nfa_add_plus_op (struct REGEX_INTERNAL_Context *ctx) 2642nfa_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 */
2672static void 2669static void
2673nfa_add_question_op (struct REGEX_INTERNAL_Context *ctx) 2670nfa_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 */
2713static void 2710static void
2714nfa_add_alternation (struct REGEX_INTERNAL_Context *ctx) 2711nfa_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 */
2757static void 2754static void
2758nfa_add_label (struct REGEX_INTERNAL_Context *ctx, const char *label) 2755nfa_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 */
2780static void 2777static void
2781REGEX_INTERNAL_context_init (struct REGEX_INTERNAL_Context *ctx) 2778REGEX_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 */
2803struct REGEX_INTERNAL_Automaton * 2800struct REGEX_INTERNAL_Automaton *
2804REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len) 2801REGEX_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
2964error: 2967error:
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 */
2990static void 2993static void
2991construct_dfa_states (struct REGEX_INTERNAL_Context *ctx, 2994construct_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 */
3055struct REGEX_INTERNAL_Automaton * 3058struct REGEX_INTERNAL_Automaton *
3056REGEX_INTERNAL_construct_dfa (const char *regex, 3059REGEX_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 */
3121void 3124void
3122REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a) 3125REGEX_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 */
3152static int 3155static int
3153evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string) 3156evaluate_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 */
3194static int 3197static int
3195evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string) 3198evaluate_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 */
3255int 3258int
3256REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string) 3259REGEX_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 */
3290const char * 3295const char *
3291REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a) 3296REGEX_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 */
3307unsigned int 3312unsigned int
3308REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a) 3313REGEX_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 */
3334size_t 3339size_t
3335REGEX_INTERNAL_get_first_key (const char *input_string, 3340REGEX_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 */
3364static void 3369static void
3365iterate_initial_edge (unsigned int min_len, 3370iterate_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 */
3478void 3483void
3479REGEX_INTERNAL_iterate_all_edges (struct REGEX_INTERNAL_Automaton *a, 3484REGEX_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 */
3523struct temporal_state_store 3528struct 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 */
3536struct client_iterator 3540struct 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 */
3554static void 3557static void
3555store_all_states (void *cls, 3558store_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 */
3591static void 3594static void
3592mark_as_reachable (struct temporal_state_store *state, 3595mark_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 */
3626static int 3629static int
3627reachability_iterator (void *cls, 3630reachability_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 */
3658static int 3661static int
3659iterate_reachables (void *cls, const struct GNUNET_HashCode *key, void *value) 3662iterate_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 */
3689void 3692void
3690REGEX_INTERNAL_iterate_reachable_edges (struct REGEX_INTERNAL_Automaton *a, 3693REGEX_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
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-19 16:49:09 +0000