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