missing fi
[oweals/gnunet.git] / src / regex / regex_internal.c
1 /*
2      This file is part of GNUnet
3      (C) 2012 Christian Grothoff (and other contributing authors)
4
5      GNUnet is free software; you can redistribute it and/or modify
6      it under the terms of the GNU General Public License as published
7      by the Free Software Foundation; either version 3, or (at your
8      option) any later version.
9
10      GNUnet is distributed in the hope that it will be useful, but
11      WITHOUT ANY WARRANTY; without even the implied warranty of
12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13      General Public License for more details.
14
15      You should have received a copy of the GNU General Public License
16      along with GNUnet; see the file COPYING.  If not, write to the
17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18      Boston, MA 02111-1307, USA.
19 */
20 /**
21  * @file src/regex/regex_internal.c
22  * @brief library to create Deterministic Finite Automatons (DFAs) from regular
23  * expressions (regexes).
24  * @author Maximilian Szengel
25  */
26 #include "platform.h"
27 #include "gnunet_util_lib.h"
28 #include "gnunet_regex_service.h"
29 #include "regex_internal_lib.h"
30 #include "regex_internal.h"
31
32
33 /**
34  * Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA
35  * creation. Disabled by default for better performance.
36  */
37 #define REGEX_DEBUG_DFA GNUNET_NO
38
39 /**
40  * Set of states using MDLL API.
41  */
42 struct REGEX_INTERNAL_StateSet_MDLL
43 {
44   /**
45    * MDLL of states.
46    */
47   struct REGEX_INTERNAL_State *head;
48
49   /**
50    * MDLL of states.
51    */
52   struct REGEX_INTERNAL_State *tail;
53
54   /**
55    * Length of the MDLL.
56    */
57   unsigned int len;
58 };
59
60
61 /**
62  * Append state to the given StateSet '
63  *
64  * @param set set to be modified
65  * @param state state to be appended
66  */
67 static void
68 state_set_append (struct REGEX_INTERNAL_StateSet *set,
69                   struct REGEX_INTERNAL_State *state)
70 {
71   if (set->off == set->size)
72     GNUNET_array_grow (set->states, set->size, set->size * 2 + 4);
73   set->states[set->off++] = state;
74 }
75
76
77 /**
78  * Compare two strings for equality. If either is NULL they are not equal.
79  *
80  * @param str1 first string for comparison.
81  * @param str2 second string for comparison.
82  *
83  * @return 0 if the strings are the same or both NULL, 1 or -1 if not.
84  */
85 static int
86 nullstrcmp (const char *str1, const char *str2)
87 {
88   if ((NULL == str1) != (NULL == str2))
89     return -1;
90   if ((NULL == str1) && (NULL == str2))
91     return 0;
92
93   return strcmp (str1, str2);
94 }
95
96
97 /**
98  * Adds a transition from one state to another on 'label'. Does not add
99  * duplicate states.
100  *
101  * @param ctx context
102  * @param from_state starting state for the transition
103  * @param label transition label
104  * @param to_state state to where the transition should point to
105  */
106 static void
107 state_add_transition (struct REGEX_INTERNAL_Context *ctx,
108                       struct REGEX_INTERNAL_State *from_state, const char *label,
109                       struct REGEX_INTERNAL_State *to_state)
110 {
111   struct REGEX_INTERNAL_Transition *t;
112   struct REGEX_INTERNAL_Transition *oth;
113
114   if (NULL == from_state)
115   {
116     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
117     return;
118   }
119
120   /* Do not add duplicate state transitions */
121   for (t = from_state->transitions_head; NULL != t; t = t->next)
122   {
123     if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) &&
124         t->from_state == from_state)
125       return;
126   }
127
128   /* sort transitions by label */
129   for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
130   {
131     if (0 < nullstrcmp (oth->label, label))
132       break;
133   }
134
135   t = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Transition));
136   if (NULL != ctx)
137     t->id = ctx->transition_id++;
138   if (NULL != label)
139     t->label = GNUNET_strdup (label);
140   else
141     t->label = NULL;
142   t->to_state = to_state;
143   t->from_state = from_state;
144
145   /* Add outgoing transition to 'from_state' */
146   from_state->transition_count++;
147   GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head,
148                                       from_state->transitions_tail, oth, t);
149 }
150
151
152 /**
153  * Remove a 'transition' from 'state'.
154  *
155  * @param state state from which the to-be-removed transition originates.
156  * @param transition transition that should be removed from state 'state'.
157  */
158 static void
159 state_remove_transition (struct REGEX_INTERNAL_State *state,
160                          struct REGEX_INTERNAL_Transition *transition)
161 {
162   if (NULL == state || NULL == transition)
163     return;
164
165   if (transition->from_state != state)
166     return;
167
168   GNUNET_free_non_null (transition->label);
169
170   state->transition_count--;
171   GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail,
172                                transition);
173
174   GNUNET_free (transition);
175 }
176
177
178 /**
179  * Compare two states. Used for sorting.
180  *
181  * @param a first state
182  * @param b second state
183  *
184  * @return an integer less than, equal to, or greater than zero
185  *         if the first argument is considered to be respectively
186  *         less than, equal to, or greater than the second.
187  */
188 static int
189 state_compare (const void *a, const void *b)
190 {
191   struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **) a;
192   struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **) b;
193
194   return (*s1)->id - (*s2)->id;
195 }
196
197
198 /**
199  * Get all edges leaving state 's'.
200  *
201  * @param s state.
202  * @param edges all edges leaving 's', expected to be allocated and have enough
203  *        space for s->transitions_count elements.
204  *
205  * @return number of edges.
206  */
207 static unsigned int
208 state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges)
209 {
210   struct REGEX_INTERNAL_Transition *t;
211   unsigned int count;
212
213   if (NULL == s)
214     return 0;
215
216   count = 0;
217
218   for (t = s->transitions_head; NULL != t; t = t->next)
219   {
220     if (NULL != t->to_state)
221     {
222       edges[count].label = t->label;
223       edges[count].destination = t->to_state->hash;
224       count++;
225     }
226   }
227   return count;
228 }
229
230
231 /**
232  * Compare to state sets by comparing the id's of the states that are contained
233  * in each set. Both sets are expected to be sorted by id!
234  *
235  * @param sset1 first state set
236  * @param sset2 second state set
237  * @return 0 if the sets are equal, otherwise non-zero
238  */
239 static int
240 state_set_compare (struct REGEX_INTERNAL_StateSet *sset1,
241                    struct REGEX_INTERNAL_StateSet *sset2)
242 {
243   int result;
244   unsigned int i;
245
246   if (NULL == sset1 || NULL == sset2)
247     return 1;
248
249   result = sset1->off - sset2->off;
250   if (result < 0)
251     return -1;
252   if (result > 0)
253     return 1;
254   for (i = 0; i < sset1->off; i++)
255     if (0 != (result = state_compare (&sset1->states[i], &sset2->states[i])))
256       break;
257   return result;
258 }
259
260
261 /**
262  * Clears the given StateSet 'set'
263  *
264  * @param set set to be cleared
265  */
266 static void
267 state_set_clear (struct REGEX_INTERNAL_StateSet *set)
268 {
269   GNUNET_array_grow (set->states, set->size, 0);
270   set->off = 0;
271 }
272
273
274 /**
275  * Clears an automaton fragment. Does not destroy the states inside the
276  * automaton.
277  *
278  * @param a automaton to be cleared
279  */
280 static void
281 automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a)
282 {
283   if (NULL == a)
284     return;
285
286   a->start = NULL;
287   a->end = NULL;
288   a->states_head = NULL;
289   a->states_tail = NULL;
290   a->state_count = 0;
291   GNUNET_free (a);
292 }
293
294
295 /**
296  * Frees the memory used by State 's'
297  *
298  * @param s state that should be destroyed
299  */
300 static void
301 automaton_destroy_state (struct REGEX_INTERNAL_State *s)
302 {
303   struct REGEX_INTERNAL_Transition *t;
304   struct REGEX_INTERNAL_Transition *next_t;
305
306   if (NULL == s)
307     return;
308
309   GNUNET_free_non_null (s->name);
310   GNUNET_free_non_null (s->proof);
311   state_set_clear (&s->nfa_set);
312   for (t = s->transitions_head; NULL != t; t = next_t)
313   {
314     next_t = t->next;
315     state_remove_transition (s, t);
316   }
317
318   GNUNET_free (s);
319 }
320
321
322 /**
323  * Remove a state from the given automaton 'a'. Always use this function when
324  * altering the states of an automaton. Will also remove all transitions leading
325  * to this state, before destroying it.
326  *
327  * @param a automaton
328  * @param s state to remove
329  */
330 static void
331 automaton_remove_state (struct REGEX_INTERNAL_Automaton *a,
332                         struct REGEX_INTERNAL_State *s)
333 {
334   struct REGEX_INTERNAL_State *s_check;
335   struct REGEX_INTERNAL_Transition *t_check;
336   struct REGEX_INTERNAL_Transition *t_check_next;
337
338   if (NULL == a || NULL == s)
339     return;
340
341   /* remove all transitions leading to this state */
342   for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
343   {
344     for (t_check = s_check->transitions_head; NULL != t_check;
345          t_check = t_check_next)
346     {
347       t_check_next = t_check->next;
348       if (t_check->to_state == s)
349         state_remove_transition (s_check, t_check);
350     }
351   }
352
353   /* remove state */
354   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
355   a->state_count--;
356
357   automaton_destroy_state (s);
358 }
359
360
361 /**
362  * Merge two states into one. Will merge 's1' and 's2' into 's1' and destroy
363  * 's2'. 's1' will contain all (non-duplicate) outgoing transitions of 's2'.
364  *
365  * @param ctx context
366  * @param a automaton
367  * @param s1 first state
368  * @param s2 second state, will be destroyed
369  */
370 static void
371 automaton_merge_states (struct REGEX_INTERNAL_Context *ctx,
372                         struct REGEX_INTERNAL_Automaton *a,
373                         struct REGEX_INTERNAL_State *s1,
374                         struct REGEX_INTERNAL_State *s2)
375 {
376   struct REGEX_INTERNAL_State *s_check;
377   struct REGEX_INTERNAL_Transition *t_check;
378   struct REGEX_INTERNAL_Transition *t;
379   struct REGEX_INTERNAL_Transition *t_next;
380   int is_dup;
381
382   if (s1 == s2)
383     return;
384
385   /* 1. Make all transitions pointing to s2 point to s1, unless this transition
386    * does not already exists, if it already exists remove transition. */
387   for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
388   {
389     for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next)
390     {
391       t_next = t_check->next;
392
393       if (s2 == t_check->to_state)
394       {
395         is_dup = GNUNET_NO;
396         for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
397         {
398           if (t->to_state == s1 && 0 == strcmp (t_check->label, t->label))
399             is_dup = GNUNET_YES;
400         }
401         if (GNUNET_NO == is_dup)
402           t_check->to_state = s1;
403         else
404           state_remove_transition (t_check->from_state, t_check);
405       }
406     }
407   }
408
409   /* 2. Add all transitions from s2 to sX to s1 */
410   for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next)
411   {
412     if (t_check->to_state != s1)
413       state_add_transition (ctx, s1, t_check->label, t_check->to_state);
414   }
415
416   /* 3. Rename s1 to {s1,s2} */
417 #if REGEX_DEBUG_DFA
418   char *new_name;
419
420   new_name = s1->name;
421   GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name);
422   GNUNET_free (new_name);
423 #endif
424
425   /* remove state */
426   GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s2);
427   a->state_count--;
428   automaton_destroy_state (s2);
429 }
430
431
432 /**
433  * Add a state to the automaton 'a', always use this function to alter the
434  * states DLL of the automaton.
435  *
436  * @param a automaton to add the state to
437  * @param s state that should be added
438  */
439 static void
440 automaton_add_state (struct REGEX_INTERNAL_Automaton *a,
441                      struct REGEX_INTERNAL_State *s)
442 {
443   GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
444   a->state_count++;
445 }
446
447
448 /**
449  * Depth-first traversal (DFS) of all states that are reachable from state
450  * 's'. Performs 'action' on each visited state.
451  *
452  * @param s start state.
453  * @param marks an array of size a->state_count to remember which state was
454  *        already visited.
455  * @param count current count of the state.
456  * @param check function that is checked before advancing on each transition
457  *              in the DFS.
458  * @param check_cls closure for check.
459  * @param action action to be performed on each state.
460  * @param action_cls closure for action.
461  */
462 static void
463 automaton_state_traverse (struct REGEX_INTERNAL_State *s, int *marks,
464                           unsigned int *count,
465                           REGEX_INTERNAL_traverse_check check, void *check_cls,
466                           REGEX_INTERNAL_traverse_action action, void *action_cls)
467 {
468   struct REGEX_INTERNAL_Transition *t;
469
470   if (GNUNET_YES == marks[s->traversal_id])
471     return;
472
473   marks[s->traversal_id] = GNUNET_YES;
474
475   if (NULL != action)
476     action (action_cls, *count, s);
477
478   (*count)++;
479
480   for (t = s->transitions_head; NULL != t; t = t->next)
481   {
482     if (NULL == check ||
483         (NULL != check && GNUNET_YES == check (check_cls, s, t)))
484     {
485       automaton_state_traverse (t->to_state, marks, count, check, check_cls,
486                                 action, action_cls);
487     }
488   }
489 }
490
491
492 /**
493  * Traverses the given automaton using depth-first-search (DFS) from it's start
494  * state, visiting all reachable states and calling 'action' on each one of
495  * them.
496  *
497  * @param a automaton to be traversed.
498  * @param start start state, pass a->start or NULL to traverse the whole automaton.
499  * @param check function that is checked before advancing on each transition
500  *              in the DFS.
501  * @param check_cls closure for check.
502  * @param action action to be performed on each state.
503  * @param action_cls closure for action
504  */
505 void
506 REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a,
507                                  struct REGEX_INTERNAL_State *start,
508                                  REGEX_INTERNAL_traverse_check check,
509                                  void *check_cls,
510                                  REGEX_INTERNAL_traverse_action action,
511                                  void *action_cls)
512 {
513   unsigned int count;
514   struct REGEX_INTERNAL_State *s;
515
516   if (NULL == a || 0 == a->state_count)
517     return;
518
519   int marks[a->state_count];
520
521   for (count = 0, s = a->states_head; NULL != s && count < a->state_count;
522        s = s->next, count++)
523   {
524     s->traversal_id = count;
525     marks[s->traversal_id] = GNUNET_NO;
526   }
527
528   count = 0;
529
530   if (NULL == start)
531     s = a->start;
532   else
533     s = start;
534
535   automaton_state_traverse (s, marks, &count, check, check_cls, action,
536                             action_cls);
537 }
538
539
540 /**
541  * String container for faster string operations.
542  */
543 struct StringBuffer
544 {
545   /**
546    * Buffer holding the string (may start in the middle!);
547    * NOT 0-terminated!
548    */
549   char *sbuf;
550
551   /**
552    * Allocated buffer.
553    */
554   char *abuf;
555
556   /**
557    * Length of the string in the buffer.
558    */
559   size_t slen;
560
561   /**
562    * Number of bytes allocated for 'sbuf'
563    */
564   unsigned int blen;
565
566   /**
567    * Buffer currently represents "NULL" (not the empty string!)
568    */
569   int16_t null_flag;
570
571   /**
572    * If this entry is part of the last/current generation array,
573    * this flag is GNUNET_YES if the last and current generation are
574    * identical (and thus copying is unnecessary if the value didn't
575    * change).  This is used in an optimization that improves
576    * performance by about 1% --- if we use int16_t here.  With just
577    * "int" for both flags, performance drops (on my system) significantly,
578    * most likely due to increased cache misses.
579    */
580   int16_t synced;
581
582 };
583
584
585 /**
586  * Compare two strings for equality. If either is NULL they are not equal.
587  *
588  * @param s1 first string for comparison.
589  * @param s2 second string for comparison.
590  *
591  * @return 0 if the strings are the same or both NULL, 1 or -1 if not.
592  */
593 static int
594 sb_nullstrcmp (const struct StringBuffer *s1,
595                const struct StringBuffer *s2)
596 {
597   if ( (GNUNET_YES == s1->null_flag) &&
598        (GNUNET_YES == s2->null_flag) )
599     return 0;
600   if ( (GNUNET_YES == s1->null_flag) ||
601        (GNUNET_YES == s2->null_flag) )
602     return -1;
603   if (s1->slen != s2->slen)
604     return -1;
605   return memcmp (s1->sbuf, s2->sbuf, s1->slen);
606 }
607         
608
609 /**
610  * Compare two strings for equality.
611  *
612  * @param s1 first string for comparison.
613  * @param s2 second string for comparison.
614  *
615  * @return 0 if the strings are the same, 1 or -1 if not.
616  */
617 static int
618 sb_strcmp (const struct StringBuffer *s1,
619            const struct StringBuffer *s2)
620 {
621   if (s1->slen != s2->slen)
622     return -1;
623   return memcmp (s1->sbuf, s2->sbuf, s1->slen);
624 }
625         
626
627 /**
628  * Reallocate the buffer of 'ret' to fit 'nlen' characters;
629  * move the existing string to the beginning of the new buffer.
630  *
631  * @param ret current buffer, to be updated
632  * @param nlen target length for the buffer, must be at least ret->slen
633  */
634 static void
635 sb_realloc (struct StringBuffer *ret,
636             size_t nlen)
637 {
638   char *old;
639
640   GNUNET_assert (nlen >= ret->slen);
641   old = ret->abuf;
642   ret->abuf = GNUNET_malloc (nlen);
643   ret->blen = nlen;
644   memcpy (ret->abuf,
645           ret->sbuf,
646           ret->slen);
647   ret->sbuf = ret->abuf;
648   GNUNET_free_non_null (old);
649 }
650
651
652 /**
653  * Append a string.
654  *
655  * @param ret where to write the result
656  * @param sarg string to append
657  */
658 static void
659 sb_append (struct StringBuffer *ret,
660            const struct StringBuffer *sarg)
661 {
662   if (GNUNET_YES == ret->null_flag)
663     ret->slen = 0;
664   ret->null_flag = GNUNET_NO;
665   if (ret->blen < sarg->slen + ret->slen)
666     sb_realloc (ret, ret->blen + sarg->slen + 128);
667   memcpy (&ret->sbuf[ret->slen],
668           sarg->sbuf,
669           sarg->slen);
670   ret->slen += sarg->slen;
671 }
672         
673
674 /**
675  * Append a C string.
676  *
677  * @param ret where to write the result
678  * @param cstr string to append
679  */
680 static void
681 sb_append_cstr (struct StringBuffer *ret,
682                 const char *cstr)
683 {
684   size_t cstr_len = strlen (cstr);
685
686   if (GNUNET_YES == ret->null_flag)
687     ret->slen = 0;
688   ret->null_flag = GNUNET_NO;
689   if (ret->blen < cstr_len + ret->slen)
690     sb_realloc (ret, ret->blen + cstr_len + 128);
691   memcpy (&ret->sbuf[ret->slen],
692           cstr,
693           cstr_len);
694   ret->slen += cstr_len;
695 }
696         
697
698 /**
699  * Wrap a string buffer, that is, set ret to the format string
700  * which contains an "%s" which is to be replaced with the original
701  * content of 'ret'.  Note that optimizing this function is not
702  * really worth it, it is rarely called.
703  *
704  * @param ret where to write the result and take the input for %.*s from
705  * @param format format string, fprintf-style, with exactly one "%.*s"
706  * @param extra_chars how long will the result be, in addition to 'sarg' length
707  */
708 static void
709 sb_wrap (struct StringBuffer *ret,
710          const char *format,
711          size_t extra_chars)
712 {
713   char *temp;
714
715   if (GNUNET_YES == ret->null_flag)
716     ret->slen = 0;
717   ret->null_flag = GNUNET_NO;
718   temp = GNUNET_malloc (ret->slen + extra_chars + 1);
719   GNUNET_snprintf (temp,
720                    ret->slen + extra_chars + 1,
721                    format,
722                    (int) ret->slen,
723                    ret->sbuf);
724   GNUNET_free_non_null (ret->abuf);
725   ret->abuf = temp;
726   ret->sbuf = temp;
727   ret->blen = ret->slen + extra_chars + 1;
728   ret->slen = ret->slen + extra_chars;
729 }
730
731
732 /**
733  * Format a string buffer.    Note that optimizing this function is not
734  * really worth it, it is rarely called.
735  *
736  * @param ret where to write the result
737  * @param format format string, fprintf-style, with exactly one "%.*s"
738  * @param extra_chars how long will the result be, in addition to 'sarg' length
739  * @param sarg string to print into the format
740  */
741 static void
742 sb_printf1 (struct StringBuffer *ret,
743             const char *format,
744             size_t extra_chars,
745             const struct StringBuffer *sarg)
746 {
747   if (ret->blen < sarg->slen + extra_chars + 1)
748     sb_realloc (ret,
749                 sarg->slen + extra_chars + 1);
750   ret->null_flag = GNUNET_NO;
751   ret->sbuf = ret->abuf;
752   ret->slen = sarg->slen + extra_chars;
753   GNUNET_snprintf (ret->sbuf,
754                    ret->blen,
755                    format,
756                    (int) sarg->slen,
757                    sarg->sbuf);
758 }
759
760
761 /**
762  * Format a string buffer.
763  *
764  * @param ret where to write the result
765  * @param format format string, fprintf-style, with exactly two "%.*s"
766  * @param extra_chars how long will the result be, in addition to 'sarg1/2' length
767  * @param sarg1 first string to print into the format
768  * @param sarg2 second string to print into the format
769  */
770 static void
771 sb_printf2 (struct StringBuffer *ret,
772             const char *format,
773             size_t extra_chars,
774             const struct StringBuffer *sarg1,
775             const struct StringBuffer *sarg2)
776 {
777   if (ret->blen < sarg1->slen + sarg2->slen + extra_chars + 1)
778     sb_realloc (ret,
779                 sarg1->slen + sarg2->slen + extra_chars + 1);
780   ret->null_flag = GNUNET_NO;
781   ret->slen = sarg1->slen + sarg2->slen + extra_chars;
782   ret->sbuf = ret->abuf;
783   GNUNET_snprintf (ret->sbuf,
784                    ret->blen,
785                    format,
786                    (int) sarg1->slen,
787                    sarg1->sbuf,
788                    (int) sarg2->slen,
789                    sarg2->sbuf);
790 }
791
792
793 /**
794  * Format a string buffer.     Note that optimizing this function is not
795  * really worth it, it is rarely called.
796  *
797  * @param ret where to write the result
798  * @param format format string, fprintf-style, with exactly three "%.*s"
799  * @param extra_chars how long will the result be, in addition to 'sarg1/2/3' length
800  * @param sarg1 first string to print into the format
801  * @param sarg2 second string to print into the format
802  * @param sarg3 third string to print into the format
803  */
804 static void
805 sb_printf3 (struct StringBuffer *ret,
806             const char *format,
807             size_t extra_chars,
808             const struct StringBuffer *sarg1,
809             const struct StringBuffer *sarg2,
810             const struct StringBuffer *sarg3)
811 {
812   if (ret->blen < sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1)
813     sb_realloc (ret,
814                 sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1);
815   ret->null_flag = GNUNET_NO;
816   ret->slen = sarg1->slen + sarg2->slen + sarg3->slen + extra_chars;
817   ret->sbuf = ret->abuf;
818   GNUNET_snprintf (ret->sbuf,
819                    ret->blen,
820                    format,
821                    (int) sarg1->slen,
822                    sarg1->sbuf,
823                    (int) sarg2->slen,
824                    sarg2->sbuf,
825                    (int) sarg3->slen,
826                    sarg3->sbuf);
827 }
828
829
830 /**
831  * Free resources of the given string buffer.
832  *
833  * @param sb buffer to free (actual pointer is not freed, as they
834  *        should not be individually allocated)
835  */
836 static void
837 sb_free (struct StringBuffer *sb)
838 {
839   GNUNET_array_grow (sb->abuf,
840                      sb->blen,
841                      0);
842   sb->slen = 0;
843   sb->sbuf = NULL;
844   sb->null_flag= GNUNET_YES;
845 }
846
847
848 /**
849  * Copy the given string buffer from 'in' to 'out'.
850  *
851  * @param in input string
852  * @param out output string
853  */
854 static void
855 sb_strdup (struct StringBuffer *out,
856            const struct StringBuffer *in)
857         
858 {
859   out->null_flag = in->null_flag;
860   if (GNUNET_YES == out->null_flag)
861     return;
862   if (out->blen < in->slen)
863   {
864     GNUNET_array_grow (out->abuf,
865                        out->blen,
866                        in->slen);
867   }
868   out->sbuf = out->abuf;
869   out->slen = in->slen;
870   memcpy (out->sbuf, in->sbuf, out->slen);
871 }
872
873
874 /**
875  * Copy the given string buffer from 'in' to 'out'.
876  *
877  * @param cstr input string
878  * @param out output string
879  */
880 static void
881 sb_strdup_cstr (struct StringBuffer *out,
882                 const char *cstr)
883 {
884   if (NULL == cstr)
885   {
886     out->null_flag = GNUNET_YES;
887     return;
888   }
889   out->null_flag = GNUNET_NO;
890   out->slen = strlen (cstr);
891   if (out->blen < out->slen)
892   {
893     GNUNET_array_grow (out->abuf,
894                        out->blen,
895                        out->slen);
896   }
897   out->sbuf = out->abuf;
898   memcpy (out->sbuf, cstr, out->slen);
899 }
900
901
902 /**
903  * Check if the given string 'str' needs parentheses around it when
904  * using it to generate a regex.
905  *
906  * @param str string
907  *
908  * @return GNUNET_YES if parentheses are needed, GNUNET_NO otherwise
909  */
910 static int
911 needs_parentheses (const struct StringBuffer *str)
912 {
913   size_t slen;
914   const char *op;
915   const char *cl;
916   const char *pos;
917   const char *end;
918   unsigned int cnt;
919
920   if ((GNUNET_YES == str->null_flag) || ((slen = str->slen) < 2))
921     return GNUNET_NO;
922   pos = str->sbuf;
923   if ('(' != pos[0])
924     return GNUNET_YES;
925   end = str->sbuf + slen;
926   cnt = 1;
927   pos++;
928   while (cnt > 0)
929   {
930     cl = memchr (pos, ')', end - pos);
931     if (NULL == cl)
932     {
933       GNUNET_break (0);
934       return GNUNET_YES;
935     }
936     /* while '(' before ')', count opening parens */
937     while ( (NULL != (op = memchr (pos, '(', end - pos)))  &&
938             (op < cl) )
939     {
940       cnt++;
941       pos = op + 1;
942     }
943     /* got ')' first */
944     cnt--;
945     pos = cl + 1;
946   }
947   return (*pos == '\0') ? GNUNET_NO : GNUNET_YES;
948 }
949
950
951 /**
952  * Remove parentheses surrounding string 'str'.
953  * Example: "(a)" becomes "a", "(a|b)|(a|c)" stays the same.
954  * You need to GNUNET_free the returned string.
955  *
956  * @param str string, modified to contain a
957  * @return string without surrounding parentheses, string 'str' if no preceding
958  *         epsilon could be found, NULL if 'str' was NULL
959  */
960 static void
961 remove_parentheses (struct StringBuffer *str)
962 {
963   size_t slen;
964   const char *pos;
965   const char *end;
966   const char *sbuf;
967   const char *op;
968   const char *cp;
969   unsigned int cnt;
970
971   if (0)
972     return;
973   sbuf = str->sbuf;
974   if ( (GNUNET_YES == str->null_flag) ||
975        (1 >=  (slen = str->slen)) ||
976        ('(' != str->sbuf[0]) ||
977        (')' != str->sbuf[slen - 1]) )
978     return;
979   cnt = 0;
980   pos = &sbuf[1];
981   end = &sbuf[slen - 1];
982   op = memchr (pos, '(', end - pos);
983   cp = memchr (pos, ')', end - pos);
984   while (NULL != cp)
985   {
986     while ( (NULL != op) &&
987             (op < cp) )
988     {
989       cnt++;
990       pos = op + 1;
991       op = memchr (pos, '(', end - pos);
992     }
993     while ( (NULL != cp) &&
994             ( (NULL == op) ||
995               (cp < op) ) )
996     {
997       if (0 == cnt)
998         return; /* can't strip parens */
999       cnt--;
1000       pos = cp + 1;
1001       cp = memchr (pos, ')', end - pos);
1002     }
1003   }
1004   if (0 != cnt)
1005   {
1006     GNUNET_break (0);
1007     return;
1008   }
1009   str->sbuf++;
1010   str->slen -= 2;
1011 }
1012
1013
1014 /**
1015  * Check if the string 'str' starts with an epsilon (empty string).
1016  * Example: "(|a)" is starting with an epsilon.
1017  *
1018  * @param str string to test
1019  *
1020  * @return 0 if str has no epsilon, 1 if str starts with '(|' and ends with ')'
1021  */
1022 static int
1023 has_epsilon (const struct StringBuffer *str)
1024 {
1025   return
1026     (GNUNET_YES != str->null_flag) &&
1027     (0 < str->slen) &&
1028     ('(' == str->sbuf[0]) &&
1029     ('|' == str->sbuf[1]) &&
1030     (')' == str->sbuf[str->slen - 1]);
1031 }
1032
1033
1034 /**
1035  * Remove an epsilon from the string str. Where epsilon is an empty string
1036  * Example: str = "(|a|b|c)", result: "a|b|c"
1037  * The returned string needs to be freed.
1038  *
1039  * @param str original string
1040  * @param ret where to return string without preceding epsilon, string 'str' if no preceding
1041  *         epsilon could be found, NULL if 'str' was NULL
1042  */
1043 static void
1044 remove_epsilon (const struct StringBuffer *str,
1045                 struct StringBuffer *ret)
1046 {
1047   if (GNUNET_YES == str->null_flag)
1048   {
1049     ret->null_flag = GNUNET_YES;
1050     return;
1051   }
1052   if ( (str->slen > 1) &&
1053        ('(' == str->sbuf[0]) &&
1054        ('|' == str->sbuf[1]) &&
1055        (')' == str->sbuf[str->slen - 1]) )
1056   {
1057     /* remove epsilon */
1058     if (ret->blen < str->slen - 3)
1059     {
1060       GNUNET_array_grow (ret->abuf,
1061                          ret->blen,
1062                          str->slen - 3);
1063     }
1064     ret->sbuf = ret->abuf;
1065     ret->slen = str->slen - 3;
1066     memcpy (ret->sbuf, &str->sbuf[2], ret->slen);
1067     return;
1068   }
1069   sb_strdup (ret, str);
1070 }
1071
1072
1073 /**
1074  * Compare n bytes of 'str1' and 'str2'
1075  *
1076  * @param str1 first string to compare
1077  * @param str2 second string for comparison
1078  * @param n number of bytes to compare
1079  *
1080  * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
1081  */
1082 static int
1083 sb_strncmp (const struct StringBuffer *str1,
1084             const struct StringBuffer *str2, size_t n)
1085 {
1086   size_t max;
1087
1088   if ( (str1->slen != str2->slen) &&
1089        ( (str1->slen < n) ||
1090          (str2->slen < n) ) )
1091     return -1;
1092   max = GNUNET_MAX (str1->slen, str2->slen);
1093   if (max > n)
1094     max = n;
1095   return memcmp (str1->sbuf, str2->sbuf, max);
1096 }
1097
1098
1099 /**
1100  * Compare n bytes of 'str1' and 'str2'
1101  *
1102  * @param str1 first string to compare
1103  * @param str2 second C string for comparison
1104  * @param n number of bytes to compare (and length of str2)
1105  *
1106  * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
1107  */
1108 static int
1109 sb_strncmp_cstr (const struct StringBuffer *str1,
1110                  const char *str2, size_t n)
1111 {
1112   if (str1->slen < n)
1113     return -1;
1114   return memcmp (str1->sbuf, str2, n);
1115 }
1116
1117
1118 /**
1119  * Initialize string buffer for storing strings of up to n
1120  * characters.
1121  *
1122  * @param sb buffer to initialize
1123  * @param n desired target length
1124  */
1125 static void
1126 sb_init (struct StringBuffer *sb,
1127          size_t n)
1128 {
1129   sb->null_flag = GNUNET_NO;
1130   sb->abuf = sb->sbuf = (0 == n) ? NULL : GNUNET_malloc (n);
1131   sb->blen = n;
1132   sb->slen = 0;
1133 }
1134
1135
1136 /**
1137  * Compare 'str1', starting from position 'k',  with whole 'str2'
1138  *
1139  * @param str1 first string to compare, starting from position 'k'
1140  * @param str2 second string for comparison
1141  * @param k starting position in 'str1'
1142  *
1143  * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
1144  */
1145 static int
1146 sb_strkcmp (const struct StringBuffer *str1,
1147             const struct StringBuffer *str2, size_t k)
1148 {
1149   if ( (GNUNET_YES == str1->null_flag) ||
1150        (GNUNET_YES == str2->null_flag) ||
1151        (k > str1->slen) ||
1152        (str1->slen - k != str2->slen) )
1153     return -1;
1154   return memcmp (&str1->sbuf[k], str2->sbuf, str2->slen);
1155 }
1156
1157
1158 /**
1159  * Helper function used as 'action' in 'REGEX_INTERNAL_automaton_traverse'
1160  * function to create the depth-first numbering of the states.
1161  *
1162  * @param cls states array.
1163  * @param count current state counter.
1164  * @param s current state.
1165  */
1166 static void
1167 number_states (void *cls, const unsigned int count,
1168                struct REGEX_INTERNAL_State *s)
1169 {
1170   struct REGEX_INTERNAL_State **states = cls;
1171
1172   s->dfs_id = count;
1173   if (NULL != states)
1174     states[count] = s;
1175 }
1176
1177
1178
1179 #define PRIS(a) \
1180   ((GNUNET_YES == a.null_flag) ? 6 : (int) a.slen), \
1181   ((GNUNET_YES == a.null_flag) ? "(null)" : a.sbuf)
1182
1183
1184 /**
1185  * Construct the regular expression given the inductive step,
1186  * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^*
1187  * R^{(k-1)}_{kj}, and simplify the resulting expression saved in R_cur_ij.
1188  *
1189  * @param R_last_ij value of  $R^{(k-1)_{ij}.
1190  * @param R_last_ik value of  $R^{(k-1)_{ik}.
1191  * @param R_last_kk value of  $R^{(k-1)_{kk}.
1192  * @param R_last_kj value of  $R^{(k-1)_{kj}.
1193  * @param R_cur_ij result for this inductive step is saved in R_cur_ij, R_cur_ij
1194  *                 is expected to be NULL when called!
1195  * @param R_cur_l optimization -- kept between iterations to avoid realloc
1196  * @param R_cur_r optimization -- kept between iterations to avoid realloc
1197  */
1198 static void
1199 automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
1200                                   const struct StringBuffer *R_last_ik,
1201                                   const struct StringBuffer *R_last_kk,
1202                                   const struct StringBuffer *R_last_kj,
1203                                   struct StringBuffer *R_cur_ij,
1204                                   struct StringBuffer *R_cur_l,
1205                                   struct StringBuffer *R_cur_r)
1206 {
1207   struct StringBuffer R_temp_ij;
1208   struct StringBuffer R_temp_ik;
1209   struct StringBuffer R_temp_kj;
1210   struct StringBuffer R_temp_kk;
1211   int eps_check;
1212   int ij_ik_cmp;
1213   int ij_kj_cmp;
1214   int ik_kk_cmp;
1215   int kk_kj_cmp;
1216   int clean_ik_kk_cmp;
1217   int clean_kk_kj_cmp;
1218   size_t length;
1219   size_t length_l;
1220   size_t length_r;
1221
1222   /*
1223    * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1224    * R_last == R^{(k-1)}, R_cur == R^{(k)}
1225    * R_cur_ij = R_cur_l | R_cur_r
1226    * R_cur_l == R^{(k-1)}_{ij}
1227    * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1228    */
1229
1230   if ( (GNUNET_YES == R_last_ij->null_flag) &&
1231        ( (GNUNET_YES == R_last_ik->null_flag) ||
1232          (GNUNET_YES == R_last_kj->null_flag)))
1233   {
1234     /* R^{(k)}_{ij} = N | N */
1235     R_cur_ij->null_flag = GNUNET_YES;
1236     R_cur_ij->synced = GNUNET_NO;
1237     return;
1238   }
1239
1240   if ( (GNUNET_YES == R_last_ik->null_flag) ||
1241        (GNUNET_YES == R_last_kj->null_flag) )
1242   {
1243     /*  R^{(k)}_{ij} = R^{(k-1)}_{ij} | N */
1244     if (GNUNET_YES == R_last_ij->synced)
1245     {
1246       R_cur_ij->synced = GNUNET_YES;
1247       R_cur_ij->null_flag = GNUNET_NO;
1248       return;
1249     }
1250     R_cur_ij->synced = GNUNET_YES;
1251     sb_strdup (R_cur_ij, R_last_ij);
1252     return;
1253   }
1254   R_cur_ij->synced = GNUNET_NO;
1255
1256   /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
1257    * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} */
1258
1259   R_cur_r->null_flag = GNUNET_YES;
1260   R_cur_r->slen = 0;
1261   R_cur_l->null_flag = GNUNET_YES;
1262   R_cur_l->slen = 0;
1263
1264   /* cache results from strcmp, we might need these many times */
1265   ij_kj_cmp = sb_nullstrcmp (R_last_ij, R_last_kj);
1266   ij_ik_cmp = sb_nullstrcmp (R_last_ij, R_last_ik);
1267   ik_kk_cmp = sb_nullstrcmp (R_last_ik, R_last_kk);
1268   kk_kj_cmp = sb_nullstrcmp (R_last_kk, R_last_kj);
1269
1270   /* Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
1271    * as parentheses, so we can better compare the contents */
1272
1273   memset (&R_temp_ij, 0, sizeof (struct StringBuffer));
1274   memset (&R_temp_ik, 0, sizeof (struct StringBuffer));
1275   memset (&R_temp_kk, 0, sizeof (struct StringBuffer));
1276   memset (&R_temp_kj, 0, sizeof (struct StringBuffer));
1277   remove_epsilon (R_last_ik, &R_temp_ik);
1278   remove_epsilon (R_last_kk, &R_temp_kk);
1279   remove_epsilon (R_last_kj, &R_temp_kj);
1280   remove_parentheses (&R_temp_ik);
1281   remove_parentheses (&R_temp_kk);
1282   remove_parentheses (&R_temp_kj);
1283   clean_ik_kk_cmp = sb_nullstrcmp (R_last_ik, &R_temp_kk);
1284   clean_kk_kj_cmp = sb_nullstrcmp (&R_temp_kk, R_last_kj);
1285
1286   /* construct R_cur_l (and, if necessary R_cur_r) */
1287   if (GNUNET_YES != R_last_ij->null_flag)
1288   {
1289     /* Assign R_temp_ij to R_last_ij and remove epsilon as well
1290      * as parentheses, so we can better compare the contents */
1291     remove_epsilon (R_last_ij, &R_temp_ij);
1292     remove_parentheses (&R_temp_ij);
1293
1294     if ( (0 == sb_strcmp (&R_temp_ij, &R_temp_ik)) &&
1295          (0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1296          (0 == sb_strcmp (&R_temp_kk, &R_temp_kj)) )
1297     {
1298       if (0 == R_temp_ij.slen)
1299       {
1300         R_cur_r->null_flag = GNUNET_NO;
1301       }
1302       else if ((0 == sb_strncmp_cstr (R_last_ij, "(|", 2)) ||
1303                (0 == sb_strncmp_cstr (R_last_ik, "(|", 2) &&
1304                 0 == sb_strncmp_cstr (R_last_kj, "(|", 2)))
1305       {
1306         /*
1307          * a|(e|a)a*(e|a) = a*
1308          * a|(e|a)(e|a)*(e|a) = a*
1309          * (e|a)|aa*a = a*
1310          * (e|a)|aa*(e|a) = a*
1311          * (e|a)|(e|a)a*a = a*
1312          * (e|a)|(e|a)a*(e|a) = a*
1313          * (e|a)|(e|a)(e|a)*(e|a) = a*
1314          */
1315         if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1316           sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_ij);
1317         else
1318           sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_ij);
1319       }
1320       else
1321       {
1322         /*
1323          * a|aa*a = a+
1324          * a|(e|a)a*a = a+
1325          * a|aa*(e|a) = a+
1326          * a|(e|a)(e|a)*a = a+
1327          * a|a(e|a)*(e|a) = a+
1328          */
1329         if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1330           sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_ij);
1331         else
1332           sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_ij);
1333       }
1334     }
1335     else if ( (0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) && (0 != clean_ik_kk_cmp) )
1336     {
1337       /* a|ab*b = ab* */
1338       if (0 == R_last_kk->slen)
1339         sb_strdup (R_cur_r, R_last_ij);
1340       else if (GNUNET_YES == needs_parentheses (&R_temp_kk))
1341         sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1342       else
1343         sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, R_last_kk);
1344       R_cur_l->null_flag = GNUNET_YES;
1345     }
1346     else if ( (0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) && (0 != clean_kk_kj_cmp))
1347     {
1348       /* a|bb*a = b*a */
1349       if (R_last_kk->slen < 1)
1350       {
1351         sb_strdup (R_cur_r, R_last_kj);
1352       }
1353       else if (GNUNET_YES == needs_parentheses (&R_temp_kk))
1354         sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1355       else
1356         sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1357
1358       R_cur_l->null_flag = GNUNET_YES;
1359     }
1360     else if ( (0 == ij_ik_cmp) && (0 == kk_kj_cmp) && (! has_epsilon (R_last_ij)) &&
1361               has_epsilon (R_last_kk))
1362     {
1363       /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */
1364       if (needs_parentheses (&R_temp_kk))
1365         sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1366       else
1367         sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
1368       R_cur_l->null_flag = GNUNET_YES;
1369     }
1370     else if ( (0 == ij_kj_cmp) && (0 == ik_kk_cmp) && (! has_epsilon (R_last_ij)) &&
1371              has_epsilon (R_last_kk))
1372     {
1373       /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|...  = b*a */
1374       if (needs_parentheses (&R_temp_kk))
1375         sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
1376       else
1377         sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
1378       R_cur_l->null_flag = GNUNET_YES;
1379     }
1380     else
1381     {
1382       sb_strdup (R_cur_l, R_last_ij);
1383       remove_parentheses (R_cur_l);
1384     }
1385   }
1386   else
1387   {
1388     /* we have no left side */
1389     R_cur_l->null_flag = GNUNET_YES;
1390   }
1391
1392   /* construct R_cur_r, if not already constructed */
1393   if (GNUNET_YES == R_cur_r->null_flag)
1394   {
1395     length = R_temp_kk.slen - R_last_ik->slen;
1396
1397     /* a(ba)*bx = (ab)+x */
1398     if ( (length > 0) &&
1399          (GNUNET_YES != R_last_kk->null_flag) &&
1400          (0 < R_last_kk->slen) &&
1401          (GNUNET_YES != R_last_kj->null_flag) &&
1402          (0 < R_last_kj->slen) &&
1403          (GNUNET_YES != R_last_ik->null_flag) &&
1404          (0 < R_last_ik->slen) &&
1405          (0 == sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
1406          (0 == sb_strncmp (&R_temp_kk, R_last_kj, length)) )
1407     {
1408       struct StringBuffer temp_a;
1409       struct StringBuffer temp_b;
1410
1411       sb_init (&temp_a, length);
1412       sb_init (&temp_b, R_last_kj->slen - length);
1413
1414       length_l = length;
1415       temp_a.sbuf = temp_a.abuf;
1416       memcpy (temp_a.sbuf, R_last_kj->sbuf, length_l);
1417       temp_a.slen = length_l;
1418
1419       length_r = R_last_kj->slen - length;
1420       temp_b.sbuf = temp_b.abuf;
1421       memcpy (temp_b.sbuf, &R_last_kj->sbuf[length], length_r);
1422       temp_b.slen = length_r;
1423
1424       /* e|(ab)+ = (ab)* */
1425       if ( (GNUNET_YES != R_cur_l->null_flag) &&
1426            (0 == R_cur_l->slen) &&
1427            (0 == temp_b.slen) )
1428       {
1429         sb_printf2 (R_cur_r, "(%.*s%.*s)*", 3, R_last_ik, &temp_a);
1430         sb_free (R_cur_l);
1431         R_cur_l->null_flag = GNUNET_YES;
1432       }
1433       else
1434       {
1435         sb_printf3 (R_cur_r, "(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
1436       }
1437       sb_free (&temp_a);
1438       sb_free (&temp_b);
1439     }
1440     else if (0 == sb_strcmp (&R_temp_ik, &R_temp_kk) &&
1441              0 == sb_strcmp (&R_temp_kk, &R_temp_kj))
1442     {
1443       /*
1444        * (e|a)a*(e|a) = a*
1445        * (e|a)(e|a)*(e|a) = a*
1446        */
1447       if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj))
1448       {
1449         if (needs_parentheses (&R_temp_kk))
1450           sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_kk);
1451         else
1452           sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_kk);
1453       }
1454       /* aa*a = a+a */
1455       else if ( (0 == clean_ik_kk_cmp) &&
1456                 (0 == clean_kk_kj_cmp) &&
1457                 (! has_epsilon (R_last_ik)) )
1458       {
1459         if (needs_parentheses (&R_temp_kk))
1460           sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
1461         else
1462           sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
1463       }
1464       /*
1465        * (e|a)a*a = a+
1466        * aa*(e|a) = a+
1467        * a(e|a)*(e|a) = a+
1468        * (e|a)a*a = a+
1469        */
1470       else
1471       {
1472         eps_check =
1473           (has_epsilon (R_last_ik) + has_epsilon (R_last_kk) +
1474            has_epsilon (R_last_kj));
1475
1476         if (1 == eps_check)
1477         {
1478           if (needs_parentheses (&R_temp_kk))
1479             sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_kk);
1480           else
1481             sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_kk);
1482         }
1483       }
1484     }
1485     /*
1486      * aa*b = a+b
1487      * (e|a)(e|a)*b = a*b
1488      */
1489     else if (0 == sb_strcmp (&R_temp_ik, &R_temp_kk))
1490     {
1491       if (has_epsilon (R_last_ik))
1492       {
1493         if (needs_parentheses (&R_temp_kk))
1494           sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1495         else
1496           sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1497       }
1498       else
1499       {
1500         if (needs_parentheses (&R_temp_kk))
1501           sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
1502         else
1503           sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
1504       }
1505     }
1506     /*
1507      * ba*a = ba+
1508      * b(e|a)*(e|a) = ba*
1509      */
1510     else if (0 == sb_strcmp (&R_temp_kk, &R_temp_kj))
1511     {
1512       if (has_epsilon (R_last_kj))
1513       {
1514         if (needs_parentheses (&R_temp_kk))
1515           sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
1516         else
1517           sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
1518       }
1519       else
1520       {
1521         if (needs_parentheses (&R_temp_kk))
1522           sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
1523         else
1524           sb_printf2 (R_cur_r, "%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
1525       }
1526     }
1527     else
1528     {
1529       if (0 < R_temp_kk.slen)
1530       {
1531         if (needs_parentheses (&R_temp_kk))
1532         {
1533           sb_printf3 (R_cur_r, "%.*s(%.*s)*%.*s", 3, R_last_ik, &R_temp_kk,
1534                       R_last_kj);
1535         }
1536         else
1537         {
1538           sb_printf3 (R_cur_r, "%.*s%.*s*%.*s", 1, R_last_ik, &R_temp_kk,
1539                       R_last_kj);
1540         }
1541       }
1542       else
1543       {
1544         sb_printf2 (R_cur_r, "%.*s%.*s", 0, R_last_ik, R_last_kj);
1545       }
1546     }
1547   }
1548   sb_free (&R_temp_ij);
1549   sb_free (&R_temp_ik);
1550   sb_free (&R_temp_kk);
1551   sb_free (&R_temp_kj);
1552
1553   if ( (GNUNET_YES == R_cur_l->null_flag) &&
1554        (GNUNET_YES == R_cur_r->null_flag) )
1555   {
1556     R_cur_ij->null_flag = GNUNET_YES;
1557     return;
1558   }
1559
1560   if ( (GNUNET_YES != R_cur_l->null_flag) &&
1561        (GNUNET_YES == R_cur_r->null_flag) )
1562   {
1563     struct StringBuffer tmp;
1564
1565     tmp = *R_cur_ij;
1566     *R_cur_ij = *R_cur_l;
1567     *R_cur_l = tmp;
1568     return;
1569   }
1570
1571   if ( (GNUNET_YES == R_cur_l->null_flag) &&
1572        (GNUNET_YES != R_cur_r->null_flag) )
1573   {
1574     struct StringBuffer tmp;
1575
1576     tmp = *R_cur_ij;
1577     *R_cur_ij = *R_cur_r;
1578     *R_cur_r = tmp;
1579     return;
1580   }
1581
1582   if (0 == sb_nullstrcmp (R_cur_l, R_cur_r))
1583   {
1584     struct StringBuffer tmp;
1585
1586     tmp = *R_cur_ij;
1587     *R_cur_ij = *R_cur_l;
1588     *R_cur_l = tmp;
1589     return;
1590   }
1591   sb_printf2 (R_cur_ij, "(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
1592 }
1593
1594
1595 /**
1596  * Create proofs for all states in the given automaton. Implementation of the
1597  * algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and
1598  * Computation 3rd Edition" by Hopcroft, Motwani and Ullman.
1599  *
1600  * Each state in the automaton gets assigned 'proof' and 'hash' (hash of the
1601  * proof) fields. The starting state will only have a valid proof/hash if it has
1602  * any incoming transitions.
1603  *
1604  * @param a automaton for which to assign proofs and hashes, must not be NULL
1605  */
1606 static int
1607 automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a)
1608 {
1609   unsigned int n = a->state_count;
1610   struct REGEX_INTERNAL_State *states[n];
1611   struct StringBuffer *R_last;
1612   struct StringBuffer *R_cur;
1613   struct StringBuffer R_cur_r;
1614   struct StringBuffer R_cur_l;
1615   struct StringBuffer *R_swap;
1616   struct REGEX_INTERNAL_Transition *t;
1617   struct StringBuffer complete_regex;
1618   unsigned int i;
1619   unsigned int j;
1620   unsigned int k;
1621
1622   R_last = GNUNET_malloc_large (sizeof (struct StringBuffer) * n * n);
1623   R_cur = GNUNET_malloc_large (sizeof (struct StringBuffer) * n * n);
1624   if ( (NULL == R_last) ||
1625        (NULL == R_cur) )
1626   {
1627     GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc");
1628     GNUNET_free_non_null (R_cur);
1629     GNUNET_free_non_null (R_last);
1630     return GNUNET_SYSERR;
1631   }
1632
1633   /* create depth-first numbering of the states, initializes 'state' */
1634   REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL, &number_states,
1635                                    states);
1636
1637   for (i = 0; i < n; i++)
1638     GNUNET_assert (NULL != states[i]);
1639   for (i = 0; i < n; i++)
1640     for (j = 0; j < n; j++)
1641       R_last[i *n + j].null_flag = GNUNET_YES;
1642
1643   /* Compute regular expressions of length "1" between each pair of states */
1644   for (i = 0; i < n; i++)
1645   {
1646     for (t = states[i]->transitions_head; NULL != t; t = t->next)
1647     {
1648       j = t->to_state->dfs_id;
1649       if (GNUNET_YES == R_last[i * n + j].null_flag)
1650       {
1651         sb_strdup_cstr (&R_last[i * n + j], t->label);
1652       }
1653       else
1654       {
1655         sb_append_cstr (&R_last[i * n + j], "|");
1656         sb_append_cstr (&R_last[i * n + j], t->label);
1657       }
1658     }
1659     /* add self-loop: i is reachable from i via epsilon-transition */
1660     if (GNUNET_YES == R_last[i * n + i].null_flag)
1661     {
1662       R_last[i * n + i].slen = 0;
1663       R_last[i * n + i].null_flag = GNUNET_NO;
1664     }
1665     else
1666     {
1667       sb_wrap (&R_last[i * n + i], "(|%.*s)", 3);
1668     }
1669   }
1670   for (i = 0; i < n; i++)
1671     for (j = 0; j < n; j++)
1672       if (needs_parentheses (&R_last[i * n + j]))
1673         sb_wrap (&R_last[i * n + j], "(%.*s)", 2);
1674   /* Compute regular expressions of length "k" between each pair of states per
1675    * induction */
1676   memset (&R_cur_l, 0, sizeof (struct StringBuffer));
1677   memset (&R_cur_r, 0, sizeof (struct StringBuffer));
1678   for (k = 0; k < n; k++)
1679   {
1680     for (i = 0; i < n; i++)
1681     {
1682       for (j = 0; j < n; j++)
1683       {
1684         /* Basis for the recursion:
1685          * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1686          * R_last == R^{(k-1)}, R_cur == R^{(k)}
1687          */
1688
1689         /* Create R_cur[i][j] and simplify the expression */
1690         automaton_create_proofs_simplify (&R_last[i * n + j], &R_last[i * n + k],
1691                                           &R_last[k * n + k], &R_last[k * n + j],
1692                                           &R_cur[i * n + j],
1693                                           &R_cur_l, &R_cur_r);
1694       }
1695     }
1696     /* set R_last = R_cur */
1697     R_swap = R_last;
1698     R_last = R_cur;
1699     R_cur = R_swap;
1700     /* clear 'R_cur' for next iteration */
1701     for (i = 0; i < n; i++)
1702       for (j = 0; j < n; j++)
1703         R_cur[i * n + j].null_flag = GNUNET_YES;
1704   }
1705   sb_free (&R_cur_l);
1706   sb_free (&R_cur_r);
1707   /* assign proofs and hashes */
1708   for (i = 0; i < n; i++)
1709   {
1710     if (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag)
1711     {
1712       states[i]->proof = GNUNET_strndup (R_last[a->start->dfs_id * n + i].sbuf,
1713                                          R_last[a->start->dfs_id * n + i].slen);
1714       GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof),
1715                           &states[i]->hash);
1716     }
1717   }
1718
1719   /* complete regex for whole DFA: union of all pairs (start state/accepting
1720    * state(s)). */
1721   sb_init (&complete_regex, 16 * n);
1722   for (i = 0; i < n; i++)
1723   {
1724     if (states[i]->accepting)
1725     {
1726       if ( (0 == complete_regex.slen) &&
1727            (0 < R_last[a->start->dfs_id * n + i].slen) )
1728       {
1729         sb_append (&complete_regex,
1730                    &R_last[a->start->dfs_id * n + i]);
1731       }
1732       else if ( (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) &&
1733                 (0 < R_last[a->start->dfs_id * n + i].slen) )
1734       {
1735         sb_append_cstr (&complete_regex, "|");
1736         sb_append (&complete_regex,
1737                    &R_last[a->start->dfs_id * n + i]);
1738       }
1739     }
1740   }
1741   a->canonical_regex = GNUNET_strndup (complete_regex.sbuf, complete_regex.slen);
1742
1743   /* cleanup */
1744   sb_free (&complete_regex);
1745   for (i = 0; i < n; i++)
1746     for (j = 0; j < n; j++)
1747     {
1748       sb_free (&R_cur[i * n + j]);
1749       sb_free (&R_last[i * n + j]);
1750     }
1751   GNUNET_free (R_cur);
1752   GNUNET_free (R_last);
1753   return GNUNET_OK;
1754 }
1755
1756
1757 /**
1758  * Creates a new DFA state based on a set of NFA states. Needs to be freed using
1759  * automaton_destroy_state.
1760  *
1761  * @param ctx context
1762  * @param nfa_states set of NFA states on which the DFA should be based on
1763  *
1764  * @return new DFA state
1765  */
1766 static struct REGEX_INTERNAL_State *
1767 dfa_state_create (struct REGEX_INTERNAL_Context *ctx,
1768                   struct REGEX_INTERNAL_StateSet *nfa_states)
1769 {
1770   struct REGEX_INTERNAL_State *s;
1771   char *pos;
1772   size_t len;
1773   struct REGEX_INTERNAL_State *cstate;
1774   struct REGEX_INTERNAL_Transition *ctran;
1775   unsigned int i;
1776
1777   s = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_State));
1778   s->id = ctx->state_id++;
1779   s->index = -1;
1780   s->lowlink = -1;
1781
1782   if (NULL == nfa_states)
1783   {
1784     GNUNET_asprintf (&s->name, "s%i", s->id);
1785     return s;
1786   }
1787
1788   s->nfa_set = *nfa_states;
1789
1790   if (nfa_states->off < 1)
1791     return s;
1792
1793   /* Create a name based on 'nfa_states' */
1794   len = nfa_states->off * 14 + 4;
1795   s->name = GNUNET_malloc (len);
1796   strcat (s->name, "{");
1797   pos = s->name + 1;
1798
1799   for (i = 0; i < nfa_states->off; i++)
1800   {
1801     cstate = nfa_states->states[i];
1802     GNUNET_snprintf (pos, pos - s->name + len,
1803                      "%i,", cstate->id);
1804     pos += strlen (pos);
1805
1806     /* Add a transition for each distinct label to NULL state */
1807     for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
1808       if (NULL != ctran->label)
1809         state_add_transition (ctx, s, ctran->label, NULL);
1810
1811     /* If the nfa_states contain an accepting state, the new dfa state is also
1812      * accepting. */
1813     if (cstate->accepting)
1814       s->accepting = 1;
1815   }
1816   pos[-1] = '}';
1817   s->name = GNUNET_realloc (s->name, strlen (s->name) + 1);
1818
1819   memset (nfa_states, 0, sizeof (struct REGEX_INTERNAL_StateSet));
1820   return s;
1821 }
1822
1823
1824 /**
1825  * Move from the given state 's' to the next state on transition 'str'. Consumes
1826  * as much of the given 'str' as possible (usefull for strided DFAs). On return
1827  * 's' will point to the next state, and the length of the substring used for
1828  * this transition will be returned. If no transition possible 0 is returned and
1829  * 's' points to NULL.
1830  *
1831  * @param s starting state, will point to the next state or NULL (if no
1832  * transition possible)
1833  * @param str edge label to follow (will match longest common prefix)
1834  *
1835  * @return length of the substring comsumed from 'str'
1836  */
1837 static unsigned int
1838 dfa_move (struct REGEX_INTERNAL_State **s, const char *str)
1839 {
1840   struct REGEX_INTERNAL_Transition *t;
1841   struct REGEX_INTERNAL_State *new_s;
1842   unsigned int len;
1843   unsigned int max_len;
1844
1845   if (NULL == s)
1846     return 0;
1847
1848   new_s = NULL;
1849   max_len = 0;
1850   for (t = (*s)->transitions_head; NULL != t; t = t->next)
1851   {
1852     len = strlen (t->label);
1853
1854     if (0 == strncmp (t->label, str, len))
1855     {
1856       if (len >= max_len)
1857       {
1858         max_len = len;
1859         new_s = t->to_state;
1860       }
1861     }
1862   }
1863
1864   *s = new_s;
1865   return max_len;
1866 }
1867
1868
1869 /**
1870  * Set the given state 'marked' to GNUNET_YES. Used by the
1871  * 'dfa_remove_unreachable_states' function to detect unreachable states in the
1872  * automaton.
1873  *
1874  * @param cls closure, not used.
1875  * @param count count, not used.
1876  * @param s state where the marked attribute will be set to GNUNET_YES.
1877  */
1878 static void
1879 mark_states (void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
1880 {
1881   s->marked = GNUNET_YES;
1882 }
1883
1884
1885 /**
1886  * Remove all unreachable states from DFA 'a'. Unreachable states are those
1887  * states that are not reachable from the starting state.
1888  *
1889  * @param a DFA automaton
1890  */
1891 static void
1892 dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a)
1893 {
1894   struct REGEX_INTERNAL_State *s;
1895   struct REGEX_INTERNAL_State *s_next;
1896
1897   /* 1. unmark all states */
1898   for (s = a->states_head; NULL != s; s = s->next)
1899     s->marked = GNUNET_NO;
1900
1901   /* 2. traverse dfa from start state and mark all visited states */
1902   REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL);
1903
1904   /* 3. delete all states that were not visited */
1905   for (s = a->states_head; NULL != s; s = s_next)
1906   {
1907     s_next = s->next;
1908     if (GNUNET_NO == s->marked)
1909       automaton_remove_state (a, s);
1910   }
1911 }
1912
1913
1914 /**
1915  * Remove all dead states from the DFA 'a'. Dead states are those states that do
1916  * not transition to any other state but themselves.
1917  *
1918  * @param a DFA automaton
1919  */
1920 static void
1921 dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a)
1922 {
1923   struct REGEX_INTERNAL_State *s;
1924   struct REGEX_INTERNAL_State *s_next;
1925   struct REGEX_INTERNAL_Transition *t;
1926   int dead;
1927
1928   GNUNET_assert (DFA == a->type);
1929
1930   for (s = a->states_head; NULL != s; s = s_next)
1931   {
1932     s_next = s->next;
1933
1934     if (s->accepting)
1935       continue;
1936
1937     dead = 1;
1938     for (t = s->transitions_head; NULL != t; t = t->next)
1939     {
1940       if (NULL != t->to_state && t->to_state != s)
1941       {
1942         dead = 0;
1943         break;
1944       }
1945     }
1946
1947     if (0 == dead)
1948       continue;
1949
1950     /* state s is dead, remove it */
1951     automaton_remove_state (a, s);
1952   }
1953 }
1954
1955
1956 /**
1957  * Merge all non distinguishable states in the DFA 'a'
1958  *
1959  * @param ctx context
1960  * @param a DFA automaton
1961  * @return GNUNET_OK on success
1962  */
1963 static int
1964 dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx,
1965                                      struct REGEX_INTERNAL_Automaton *a)
1966 {
1967   uint32_t *table;
1968   struct REGEX_INTERNAL_State *s1;
1969   struct REGEX_INTERNAL_State *s2;
1970   struct REGEX_INTERNAL_Transition *t1;
1971   struct REGEX_INTERNAL_Transition *t2;
1972   struct REGEX_INTERNAL_State *s1_next;
1973   struct REGEX_INTERNAL_State *s2_next;
1974   int change;
1975   unsigned int num_equal_edges;
1976   unsigned int i;
1977   unsigned int state_cnt;
1978   unsigned long long idx;
1979   unsigned long long idx1;
1980
1981   if ( (NULL == a) || (0 == a->state_count) )
1982   {
1983     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1984                 "Could not merge nondistinguishable states, automaton was NULL.\n");
1985     return GNUNET_SYSERR;
1986   }
1987
1988   state_cnt = a->state_count;
1989   table = GNUNET_malloc_large ((sizeof (uint32_t) * state_cnt * state_cnt / 32)  + sizeof (uint32_t));
1990   if (NULL == table)
1991   {
1992     GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc");
1993     return GNUNET_SYSERR;
1994   }
1995
1996   for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next)
1997     s1->marked = i++;
1998
1999   /* Mark all pairs of accepting/!accepting states */
2000   for (s1 = a->states_head; NULL != s1; s1 = s1->next)
2001     for (s2 = a->states_head; NULL != s2; s2 = s2->next)
2002       if ( (s1->accepting && !s2->accepting) ||
2003            (!s1->accepting && s2->accepting) )
2004       {
2005         idx = s1->marked * state_cnt + s2->marked;
2006         table[idx / 32] |= (1 << (idx % 32));
2007       }
2008
2009   /* Find all equal states */
2010   change = 1;
2011   while (0 != change)
2012   {
2013     change = 0;
2014     for (s1 = a->states_head; NULL != s1; s1 = s1->next)
2015     {
2016       for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
2017       {
2018         idx = s1->marked * state_cnt + s2->marked;
2019         if (0 != (table[idx / 32] & (1 << (idx % 32))))
2020           continue;
2021         num_equal_edges = 0;
2022         for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
2023         {
2024           for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
2025           {
2026             if (0 == strcmp (t1->label, t2->label))
2027             {
2028               num_equal_edges++;
2029               /* same edge, but targets definitively different, so we're different
2030                  as well */
2031               if (t1->to_state->marked > t2->to_state->marked)
2032                 idx1 = t1->to_state->marked * state_cnt + t2->to_state->marked;
2033               else
2034                 idx1 = t2->to_state->marked * state_cnt + t1->to_state->marked;
2035               if (0 != (table[idx1 / 32] & (1 << (idx1 % 32))))
2036               {
2037                 table[idx / 32] |= (1 << (idx % 32));
2038                 change = 1; /* changed a marker, need to run again */
2039               }
2040             }
2041           }
2042         }
2043         if ( (num_equal_edges != s1->transition_count) ||
2044              (num_equal_edges != s2->transition_count) )
2045         {
2046           /* Make sure ALL edges of possible equal states are the same */
2047           table[idx / 32] |= (1 << (idx % 32));
2048           change = 1;  /* changed a marker, need to run again */
2049         }
2050       }
2051     }
2052   }
2053
2054   /* Merge states that are equal */
2055   for (s1 = a->states_head; NULL != s1; s1 = s1_next)
2056   {
2057     s1_next = s1->next;
2058     for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
2059     {
2060       s2_next = s2->next;
2061       idx = s1->marked * state_cnt + s2->marked;
2062       if (0 == (table[idx / 32] & (1 << (idx % 32))))
2063         automaton_merge_states (ctx, a, s1, s2);
2064     }
2065   }
2066
2067   GNUNET_free (table);
2068   return GNUNET_OK;
2069 }
2070
2071
2072 /**
2073  * Minimize the given DFA 'a' by removing all unreachable states, removing all
2074  * dead states and merging all non distinguishable states
2075  *
2076  * @param ctx context
2077  * @param a DFA automaton
2078  * @return GNUNET_OK on success
2079  */
2080 static int
2081 dfa_minimize (struct REGEX_INTERNAL_Context *ctx,
2082               struct REGEX_INTERNAL_Automaton *a)
2083 {
2084   if (NULL == a)
2085     return GNUNET_SYSERR;
2086
2087   GNUNET_assert (DFA == a->type);
2088
2089   /* 1. remove unreachable states */
2090   dfa_remove_unreachable_states (a);
2091
2092   /* 2. remove dead states */
2093   dfa_remove_dead_states (a);
2094
2095   /* 3. Merge nondistinguishable states */
2096   if (GNUNET_OK != dfa_merge_nondistinguishable_states (ctx, a))
2097     return GNUNET_SYSERR;
2098   return GNUNET_OK;
2099 }
2100
2101
2102 /**
2103  * Context for adding strided transitions to a DFA.
2104  */
2105 struct REGEX_INTERNAL_Strided_Context
2106 {
2107   /**
2108    * Length of the strides.
2109    */
2110   const unsigned int stride;
2111
2112   /**
2113    * Strided transitions DLL. New strided transitions will be stored in this DLL
2114    * and afterwards added to the DFA.
2115    */
2116   struct REGEX_INTERNAL_Transition *transitions_head;
2117
2118   /**
2119    * Strided transitions DLL.
2120    */
2121   struct REGEX_INTERNAL_Transition *transitions_tail;
2122 };
2123
2124
2125 /**
2126  * Recursive helper function to add strides to a DFA.
2127  *
2128  * @param cls context, contains stride length and strided transitions DLL.
2129  * @param depth current depth of the depth-first traversal of the graph.
2130  * @param label current label, string that contains all labels on the path from
2131  *        'start' to 's'.
2132  * @param start start state for the depth-first traversal of the graph.
2133  * @param s current state in the depth-first traversal
2134  */
2135 static void
2136 dfa_add_multi_strides_helper (void *cls, const unsigned int depth, char *label,
2137                               struct REGEX_INTERNAL_State *start,
2138                               struct REGEX_INTERNAL_State *s)
2139 {
2140   struct REGEX_INTERNAL_Strided_Context *ctx = cls;
2141   struct REGEX_INTERNAL_Transition *t;
2142   char *new_label;
2143
2144   if (depth == ctx->stride)
2145   {
2146     t = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Transition));
2147     t->label = GNUNET_strdup (label);
2148     t->to_state = s;
2149     t->from_state = start;
2150     GNUNET_CONTAINER_DLL_insert (ctx->transitions_head, ctx->transitions_tail,
2151                                  t);
2152   }
2153   else
2154   {
2155     for (t = s->transitions_head; NULL != t; t = t->next)
2156     {
2157       /* Do not consider self-loops, because it end's up in too many
2158        * transitions */
2159       if (t->to_state == t->from_state)
2160         continue;
2161
2162       if (NULL != label)
2163       {
2164         GNUNET_asprintf (&new_label, "%s%s", label, t->label);
2165       }
2166       else
2167         new_label = GNUNET_strdup (t->label);
2168
2169       dfa_add_multi_strides_helper (cls, (depth + 1), new_label, start,
2170                                     t->to_state);
2171     }
2172   }
2173   GNUNET_free_non_null (label);
2174 }
2175
2176
2177 /**
2178  * Function called for each state in the DFA. Starts a traversal of depth set in
2179  * context starting from state 's'.
2180  *
2181  * @param cls context.
2182  * @param count not used.
2183  * @param s current state.
2184  */
2185 static void
2186 dfa_add_multi_strides (void *cls, const unsigned int count,
2187                        struct REGEX_INTERNAL_State *s)
2188 {
2189   dfa_add_multi_strides_helper (cls, 0, NULL, s, s);
2190 }
2191
2192
2193 /**
2194  * Adds multi-strided transitions to the given 'dfa'.
2195  *
2196  * @param regex_ctx regex context needed to add transitions to the automaton.
2197  * @param dfa DFA to which the multi strided transitions should be added.
2198  * @param stride_len length of the strides.
2199  */
2200 void
2201 REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx,
2202                                     struct REGEX_INTERNAL_Automaton *dfa,
2203                                     const unsigned int stride_len)
2204 {
2205   struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
2206   struct REGEX_INTERNAL_Transition *t;
2207   struct REGEX_INTERNAL_Transition *t_next;
2208
2209   if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
2210     return;
2211
2212   /* Compute the new transitions of given stride_len */
2213   REGEX_INTERNAL_automaton_traverse (dfa, dfa->start, NULL, NULL,
2214                                    &dfa_add_multi_strides, &ctx);
2215
2216   /* Add all the new transitions to the automaton. */
2217   for (t = ctx.transitions_head; NULL != t; t = t_next)
2218   {
2219     t_next = t->next;
2220     state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
2221     GNUNET_CONTAINER_DLL_remove (ctx.transitions_head, ctx.transitions_tail, t);
2222     GNUNET_free_non_null (t->label);
2223     GNUNET_free (t);
2224   }
2225
2226   /* Mark this automaton as multistrided */
2227   dfa->is_multistrided = GNUNET_YES;
2228 }
2229
2230 /**
2231  * Recursive Helper function for DFA path compression. Does DFS on the DFA graph
2232  * and adds new transitions to the given transitions DLL and marks states that
2233  * should be removed by setting state->contained to GNUNET_YES.
2234  *
2235  * @param dfa DFA for which the paths should be compressed.
2236  * @param start starting state for linear path search.
2237  * @param cur current state in the recursive DFS.
2238  * @param label current label (string of traversed labels).
2239  * @param max_len maximal path compression length.
2240  * @param transitions_head transitions DLL.
2241  * @param transitions_tail transitions DLL.
2242  */
2243 void
2244 dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa,
2245                            struct REGEX_INTERNAL_State *start,
2246                            struct REGEX_INTERNAL_State *cur, char *label,
2247                            unsigned int max_len,
2248                            struct REGEX_INTERNAL_Transition **transitions_head,
2249                            struct REGEX_INTERNAL_Transition **transitions_tail)
2250 {
2251   struct REGEX_INTERNAL_Transition *t;
2252   char *new_label;
2253
2254
2255   if (NULL != label &&
2256       ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting ||
2257         GNUNET_YES == cur->marked) || (start != dfa->start && max_len > 0 &&
2258                                        max_len == strlen (label)) ||
2259        (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label))))
2260   {
2261     t = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Transition));
2262     t->label = GNUNET_strdup (label);
2263     t->to_state = cur;
2264     t->from_state = start;
2265     GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t);
2266
2267     if (GNUNET_NO == cur->marked)
2268     {
2269       dfa_compress_paths_helper (dfa, cur, cur, NULL, max_len, transitions_head,
2270                                  transitions_tail);
2271     }
2272     return;
2273   }
2274   else if (cur != start)
2275     cur->contained = GNUNET_YES;
2276
2277   if (GNUNET_YES == cur->marked && cur != start)
2278     return;
2279
2280   cur->marked = GNUNET_YES;
2281
2282
2283   for (t = cur->transitions_head; NULL != t; t = t->next)
2284   {
2285     if (NULL != label)
2286       GNUNET_asprintf (&new_label, "%s%s", label, t->label);
2287     else
2288       new_label = GNUNET_strdup (t->label);
2289
2290     if (t->to_state != cur)
2291     {
2292       dfa_compress_paths_helper (dfa, start, t->to_state, new_label, max_len,
2293                                  transitions_head, transitions_tail);
2294     }
2295     GNUNET_free (new_label);
2296   }
2297 }
2298
2299
2300 /**
2301  * Compress paths in the given 'dfa'. Linear paths like 0->1->2->3 will be
2302  * compressed to 0->3 by combining transitions.
2303  *
2304  * @param regex_ctx context for adding new transitions.
2305  * @param dfa DFA representation, will directly modify the given DFA.
2306  * @param max_len maximal length of the compressed paths.
2307  */
2308 static void
2309 dfa_compress_paths (struct REGEX_INTERNAL_Context *regex_ctx,
2310                     struct REGEX_INTERNAL_Automaton *dfa, unsigned int max_len)
2311 {
2312   struct REGEX_INTERNAL_State *s;
2313   struct REGEX_INTERNAL_State *s_next;
2314   struct REGEX_INTERNAL_Transition *t;
2315   struct REGEX_INTERNAL_Transition *t_next;
2316   struct REGEX_INTERNAL_Transition *transitions_head = NULL;
2317   struct REGEX_INTERNAL_Transition *transitions_tail = NULL;
2318
2319   if (NULL == dfa)
2320     return;
2321
2322   /* Count the incoming transitions on each state. */
2323   for (s = dfa->states_head; NULL != s; s = s->next)
2324   {
2325     for (t = s->transitions_head; NULL != t; t = t->next)
2326     {
2327       if (NULL != t->to_state)
2328         t->to_state->incoming_transition_count++;
2329     }
2330   }
2331
2332   /* Unmark all states. */
2333   for (s = dfa->states_head; NULL != s; s = s->next)
2334   {
2335     s->marked = GNUNET_NO;
2336     s->contained = GNUNET_NO;
2337   }
2338
2339   /* Add strides and mark states that can be deleted. */
2340   dfa_compress_paths_helper (dfa, dfa->start, dfa->start, NULL, max_len,
2341                              &transitions_head, &transitions_tail);
2342
2343   /* Add all the new transitions to the automaton. */
2344   for (t = transitions_head; NULL != t; t = t_next)
2345   {
2346     t_next = t->next;
2347     state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
2348     GNUNET_CONTAINER_DLL_remove (transitions_head, transitions_tail, t);
2349     GNUNET_free_non_null (t->label);
2350     GNUNET_free (t);
2351   }
2352
2353   /* Remove marked states (including their incoming and outgoing transitions). */
2354   for (s = dfa->states_head; NULL != s; s = s_next)
2355   {
2356     s_next = s->next;
2357     if (GNUNET_YES == s->contained)
2358       automaton_remove_state (dfa, s);
2359   }
2360 }
2361
2362
2363 /**
2364  * Creates a new NFA fragment. Needs to be cleared using
2365  * automaton_fragment_clear.
2366  *
2367  * @param start starting state
2368  * @param end end state
2369  *
2370  * @return new NFA fragment
2371  */
2372 static struct REGEX_INTERNAL_Automaton *
2373 nfa_fragment_create (struct REGEX_INTERNAL_State *start,
2374                      struct REGEX_INTERNAL_State *end)
2375 {
2376   struct REGEX_INTERNAL_Automaton *n;
2377
2378   n = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Automaton));
2379
2380   n->type = NFA;
2381   n->start = NULL;
2382   n->end = NULL;
2383   n->state_count = 0;
2384
2385   if (NULL == start || NULL == end)
2386     return n;
2387
2388   automaton_add_state (n, end);
2389   automaton_add_state (n, start);
2390
2391   n->state_count = 2;
2392
2393   n->start = start;
2394   n->end = end;
2395
2396   return n;
2397 }
2398
2399
2400 /**
2401  * Adds a list of states to the given automaton 'n'.
2402  *
2403  * @param n automaton to which the states should be added
2404  * @param states_head head of the DLL of states
2405  * @param states_tail tail of the DLL of states
2406  */
2407 static void
2408 nfa_add_states (struct REGEX_INTERNAL_Automaton *n,
2409                 struct REGEX_INTERNAL_State *states_head,
2410                 struct REGEX_INTERNAL_State *states_tail)
2411 {
2412   struct REGEX_INTERNAL_State *s;
2413
2414   if (NULL == n || NULL == states_head)
2415   {
2416     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
2417     return;
2418   }
2419
2420   if (NULL == n->states_head)
2421   {
2422     n->states_head = states_head;
2423     n->states_tail = states_tail;
2424     return;
2425   }
2426
2427   if (NULL != states_head)
2428   {
2429     n->states_tail->next = states_head;
2430     n->states_tail = states_tail;
2431   }
2432
2433   for (s = states_head; NULL != s; s = s->next)
2434     n->state_count++;
2435 }
2436
2437
2438 /**
2439  * Creates a new NFA state. Needs to be freed using automaton_destroy_state.
2440  *
2441  * @param ctx context
2442  * @param accepting is it an accepting state or not
2443  *
2444  * @return new NFA state
2445  */
2446 static struct REGEX_INTERNAL_State *
2447 nfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting)
2448 {
2449   struct REGEX_INTERNAL_State *s;
2450
2451   s = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_State));
2452   s->id = ctx->state_id++;
2453   s->accepting = accepting;
2454   s->marked = GNUNET_NO;
2455   s->contained = 0;
2456   s->index = -1;
2457   s->lowlink = -1;
2458   s->scc_id = 0;
2459   s->name = NULL;
2460   GNUNET_asprintf (&s->name, "s%i", s->id);
2461
2462   return s;
2463 }
2464
2465
2466 /**
2467  * Calculates the closure set for the given set of states.
2468  *
2469  * @param ret set to sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
2470  * @param nfa the NFA containing 's'
2471  * @param states list of states on which to base the closure on
2472  * @param label transitioning label for which to base the closure on,
2473  *                pass NULL for epsilon transition
2474  */
2475 static void
2476 nfa_closure_set_create (struct REGEX_INTERNAL_StateSet *ret,
2477                         struct REGEX_INTERNAL_Automaton *nfa,
2478                         struct REGEX_INTERNAL_StateSet *states, const char *label)
2479 {
2480   struct REGEX_INTERNAL_State *s;
2481   unsigned int i;
2482   struct REGEX_INTERNAL_StateSet_MDLL cls_stack;
2483   struct REGEX_INTERNAL_State *clsstate;
2484   struct REGEX_INTERNAL_State *currentstate;
2485   struct REGEX_INTERNAL_Transition *ctran;
2486
2487   memset (ret, 0, sizeof (struct REGEX_INTERNAL_StateSet));
2488   if (NULL == states)
2489     return;
2490
2491   for (i = 0; i < states->off; i++)
2492   {
2493     s = states->states[i];
2494
2495     /* Add start state to closure only for epsilon closure */
2496     if (NULL == label)
2497       state_set_append (ret, s);
2498
2499     /* initialize work stack */
2500     cls_stack.head = NULL;
2501     cls_stack.tail = NULL;
2502     GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s);
2503     cls_stack.len = 1;
2504
2505     while (NULL != (currentstate = cls_stack.tail))
2506     {
2507       GNUNET_CONTAINER_MDLL_remove (ST, cls_stack.head, cls_stack.tail,
2508                                     currentstate);
2509       cls_stack.len--;
2510       for (ctran = currentstate->transitions_head; NULL != ctran;
2511            ctran = ctran->next)
2512       {
2513         if (NULL == (clsstate = ctran->to_state))
2514           continue;
2515         if (0 != clsstate->contained)
2516           continue;
2517         if (0 != nullstrcmp (label, ctran->label))
2518           continue;
2519         state_set_append (ret, clsstate);
2520         GNUNET_CONTAINER_MDLL_insert_tail (ST, cls_stack.head, cls_stack.tail,
2521                                            clsstate);
2522         cls_stack.len++;
2523         clsstate->contained = 1;
2524       }
2525     }
2526   }
2527   for (i = 0; i < ret->off; i++)
2528     ret->states[i]->contained = 0;
2529
2530   if (ret->off > 1)
2531     qsort (ret->states, ret->off, sizeof (struct REGEX_INTERNAL_State *),
2532            &state_compare);
2533 }
2534
2535
2536 /**
2537  * Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
2538  *
2539  * @param ctx context
2540  */
2541 static void
2542 nfa_add_concatenation (struct REGEX_INTERNAL_Context *ctx)
2543 {
2544   struct REGEX_INTERNAL_Automaton *a;
2545   struct REGEX_INTERNAL_Automaton *b;
2546   struct REGEX_INTERNAL_Automaton *new_nfa;
2547
2548   b = ctx->stack_tail;
2549   GNUNET_assert (NULL != b);
2550   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
2551   a = ctx->stack_tail;
2552   GNUNET_assert (NULL != a);
2553   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2554
2555   state_add_transition (ctx, a->end, NULL, b->start);
2556   a->end->accepting = 0;
2557   b->end->accepting = 1;
2558
2559   new_nfa = nfa_fragment_create (NULL, NULL);
2560   nfa_add_states (new_nfa, a->states_head, a->states_tail);
2561   nfa_add_states (new_nfa, b->states_head, b->states_tail);
2562   new_nfa->start = a->start;
2563   new_nfa->end = b->end;
2564   new_nfa->state_count += a->state_count + b->state_count;
2565   automaton_fragment_clear (a);
2566   automaton_fragment_clear (b);
2567
2568   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
2569 }
2570
2571
2572 /**
2573  * Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
2574  *
2575  * @param ctx context
2576  */
2577 static void
2578 nfa_add_star_op (struct REGEX_INTERNAL_Context *ctx)
2579 {
2580   struct REGEX_INTERNAL_Automaton *a;
2581   struct REGEX_INTERNAL_Automaton *new_nfa;
2582   struct REGEX_INTERNAL_State *start;
2583   struct REGEX_INTERNAL_State *end;
2584
2585   a = ctx->stack_tail;
2586
2587   if (NULL == a)
2588   {
2589     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2590                 "nfa_add_star_op failed, because there was no element on the stack");
2591     return;
2592   }
2593
2594   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2595
2596   start = nfa_state_create (ctx, 0);
2597   end = nfa_state_create (ctx, 1);
2598
2599   state_add_transition (ctx, start, NULL, a->start);
2600   state_add_transition (ctx, start, NULL, end);
2601   state_add_transition (ctx, a->end, NULL, a->start);
2602   state_add_transition (ctx, a->end, NULL, end);
2603
2604   a->end->accepting = 0;
2605   end->accepting = 1;
2606
2607   new_nfa = nfa_fragment_create (start, end);
2608   nfa_add_states (new_nfa, a->states_head, a->states_tail);
2609   automaton_fragment_clear (a);
2610
2611   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
2612 }
2613
2614
2615 /**
2616  * Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
2617  *
2618  * @param ctx context
2619  */
2620 static void
2621 nfa_add_plus_op (struct REGEX_INTERNAL_Context *ctx)
2622 {
2623   struct REGEX_INTERNAL_Automaton *a;
2624
2625   a = ctx->stack_tail;
2626
2627   if (NULL == a)
2628   {
2629     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2630                 "nfa_add_plus_op failed, because there was no element on the stack");
2631     return;
2632   }
2633
2634   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2635
2636   state_add_transition (ctx, a->end, NULL, a->start);
2637
2638   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
2639 }
2640
2641
2642 /**
2643  * Pops an NFA fragment (a) from the stack and adds a new fragment (a?)
2644  *
2645  * @param ctx context
2646  */
2647 static void
2648 nfa_add_question_op (struct REGEX_INTERNAL_Context *ctx)
2649 {
2650   struct REGEX_INTERNAL_Automaton *a;
2651   struct REGEX_INTERNAL_Automaton *new_nfa;
2652   struct REGEX_INTERNAL_State *start;
2653   struct REGEX_INTERNAL_State *end;
2654
2655   a = ctx->stack_tail;
2656   if (NULL == a)
2657   {
2658     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2659                 "nfa_add_question_op failed, because there was no element on the stack");
2660     return;
2661   }
2662
2663   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2664
2665   start = nfa_state_create (ctx, 0);
2666   end = nfa_state_create (ctx, 1);
2667
2668   state_add_transition (ctx, start, NULL, a->start);
2669   state_add_transition (ctx, start, NULL, end);
2670   state_add_transition (ctx, a->end, NULL, end);
2671
2672   a->end->accepting = 0;
2673
2674   new_nfa = nfa_fragment_create (start, end);
2675   nfa_add_states (new_nfa, a->states_head, a->states_tail);
2676   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
2677   automaton_fragment_clear (a);
2678 }
2679
2680
2681 /**
2682  * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment that
2683  * alternates between a and b (a|b)
2684  *
2685  * @param ctx context
2686  */
2687 static void
2688 nfa_add_alternation (struct REGEX_INTERNAL_Context *ctx)
2689 {
2690   struct REGEX_INTERNAL_Automaton *a;
2691   struct REGEX_INTERNAL_Automaton *b;
2692   struct REGEX_INTERNAL_Automaton *new_nfa;
2693   struct REGEX_INTERNAL_State *start;
2694   struct REGEX_INTERNAL_State *end;
2695
2696   b = ctx->stack_tail;
2697   GNUNET_assert (NULL != b);
2698   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
2699   a = ctx->stack_tail;
2700   GNUNET_assert (NULL != a);
2701   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
2702
2703   start = nfa_state_create (ctx, 0);
2704   end = nfa_state_create (ctx, 1);
2705   state_add_transition (ctx, start, NULL, a->start);
2706   state_add_transition (ctx, start, NULL, b->start);
2707
2708   state_add_transition (ctx, a->end, NULL, end);
2709   state_add_transition (ctx, b->end, NULL, end);
2710
2711   a->end->accepting = 0;
2712   b->end->accepting = 0;
2713   end->accepting = 1;
2714
2715   new_nfa = nfa_fragment_create (start, end);
2716   nfa_add_states (new_nfa, a->states_head, a->states_tail);
2717   nfa_add_states (new_nfa, b->states_head, b->states_tail);
2718   automaton_fragment_clear (a);
2719   automaton_fragment_clear (b);
2720
2721   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
2722 }
2723
2724
2725 /**
2726  * Adds a new nfa fragment to the stack
2727  *
2728  * @param ctx context
2729  * @param label label for nfa transition
2730  */
2731 static void
2732 nfa_add_label (struct REGEX_INTERNAL_Context *ctx, const char *label)
2733 {
2734   struct REGEX_INTERNAL_Automaton *n;
2735   struct REGEX_INTERNAL_State *start;
2736   struct REGEX_INTERNAL_State *end;
2737
2738   GNUNET_assert (NULL != ctx);
2739
2740   start = nfa_state_create (ctx, 0);
2741   end = nfa_state_create (ctx, 1);
2742   state_add_transition (ctx, start, label, end);
2743   n = nfa_fragment_create (start, end);
2744   GNUNET_assert (NULL != n);
2745   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
2746 }
2747
2748
2749 /**
2750  * Initialize a new context
2751  *
2752  * @param ctx context
2753  */
2754 static void
2755 REGEX_INTERNAL_context_init (struct REGEX_INTERNAL_Context *ctx)
2756 {
2757   if (NULL == ctx)
2758   {
2759     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
2760     return;
2761   }
2762   ctx->state_id = 0;
2763   ctx->transition_id = 0;
2764   ctx->stack_head = NULL;
2765   ctx->stack_tail = NULL;
2766 }
2767
2768
2769 /**
2770  * Construct an NFA by parsing the regex string of length 'len'.
2771  *
2772  * @param regex regular expression string
2773  * @param len length of the string
2774  *
2775  * @return NFA, needs to be freed using REGEX_INTERNAL_destroy_automaton
2776  */
2777 struct REGEX_INTERNAL_Automaton *
2778 REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len)
2779 {
2780   struct REGEX_INTERNAL_Context ctx;
2781   struct REGEX_INTERNAL_Automaton *nfa;
2782   const char *regexp;
2783   char curlabel[2];
2784   char *error_msg;
2785   unsigned int count;
2786   unsigned int altcount;
2787   unsigned int atomcount;
2788   unsigned int poff;
2789   unsigned int psize;
2790   struct
2791   {
2792     int altcount;
2793     int atomcount;
2794   }     *p;
2795
2796   if (NULL == regex || 0 == strlen (regex) || 0 == len)
2797   {
2798     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2799                 "Could not parse regex. Empty regex string provided.\n");
2800
2801     return NULL;
2802   }
2803   REGEX_INTERNAL_context_init (&ctx);
2804
2805   regexp = regex;
2806   curlabel[1] = '\0';
2807   p = NULL;
2808   error_msg = NULL;
2809   altcount = 0;
2810   atomcount = 0;
2811   poff = 0;
2812   psize = 0;
2813
2814   for (count = 0; count < len && *regexp; count++, regexp++)
2815   {
2816     switch (*regexp)
2817     {
2818     case '(':
2819       if (atomcount > 1)
2820       {
2821         --atomcount;
2822         nfa_add_concatenation (&ctx);
2823       }
2824       if (poff == psize)
2825         GNUNET_array_grow (p, psize, psize * 2 + 4); /* FIXME why *2 +4? */
2826       p[poff].altcount = altcount;
2827       p[poff].atomcount = atomcount;
2828       poff++;
2829       altcount = 0;
2830       atomcount = 0;
2831       break;
2832     case '|':
2833       if (0 == atomcount)
2834       {
2835         error_msg = "Cannot append '|' to nothing";
2836         goto error;
2837       }
2838       while (--atomcount > 0)
2839         nfa_add_concatenation (&ctx);
2840       altcount++;
2841       break;
2842     case ')':
2843       if (0 == poff)
2844       {
2845         error_msg = "Missing opening '('";
2846         goto error;
2847       }
2848       if (0 == atomcount)
2849       {
2850         /* Ignore this: "()" */
2851         poff--;
2852         altcount = p[poff].altcount;
2853         atomcount = p[poff].atomcount;
2854         break;
2855       }
2856       while (--atomcount > 0)
2857         nfa_add_concatenation (&ctx);
2858       for (; altcount > 0; altcount--)
2859         nfa_add_alternation (&ctx);
2860       poff--;
2861       altcount = p[poff].altcount;
2862       atomcount = p[poff].atomcount;
2863       atomcount++;
2864       break;
2865     case '*':
2866       if (atomcount == 0)
2867       {
2868         error_msg = "Cannot append '*' to nothing";
2869         goto error;
2870       }
2871       nfa_add_star_op (&ctx);
2872       break;
2873     case '+':
2874       if (atomcount == 0)
2875       {
2876         error_msg = "Cannot append '+' to nothing";
2877         goto error;
2878       }
2879       nfa_add_plus_op (&ctx);
2880       break;
2881     case '?':
2882       if (atomcount == 0)
2883       {
2884         error_msg = "Cannot append '?' to nothing";
2885         goto error;
2886       }
2887       nfa_add_question_op (&ctx);
2888       break;
2889     default:
2890       if (atomcount > 1)
2891       {
2892         --atomcount;
2893         nfa_add_concatenation (&ctx);
2894       }
2895       curlabel[0] = *regexp;
2896       nfa_add_label (&ctx, curlabel);
2897       atomcount++;
2898       break;
2899     }
2900   }
2901   if (0 != poff)
2902   {
2903     error_msg = "Unbalanced parenthesis";
2904     goto error;
2905   }
2906   while (--atomcount > 0)
2907     nfa_add_concatenation (&ctx);
2908   for (; altcount > 0; altcount--)
2909     nfa_add_alternation (&ctx);
2910
2911   GNUNET_array_grow (p, psize, 0);
2912
2913   nfa = ctx.stack_tail;
2914   GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2915
2916   if (NULL != ctx.stack_head)
2917   {
2918     error_msg = "Creating the NFA failed. NFA stack was not empty!";
2919     goto error;
2920   }
2921
2922   /* Remember the regex that was used to generate this NFA */
2923   nfa->regex = GNUNET_strdup (regex);
2924
2925   /* create depth-first numbering of the states for pretty printing */
2926   REGEX_INTERNAL_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL);
2927
2928   /* No multistriding added so far */
2929   nfa->is_multistrided = GNUNET_NO;
2930
2931   return nfa;
2932
2933 error:
2934   GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex);
2935   if (NULL != error_msg)
2936     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
2937
2938   GNUNET_free_non_null (p);
2939
2940   while (NULL != (nfa = ctx.stack_head))
2941   {
2942     GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2943     REGEX_INTERNAL_automaton_destroy (nfa);
2944   }
2945
2946   return NULL;
2947 }
2948
2949
2950 /**
2951  * Create DFA states based on given 'nfa' and starting with 'dfa_state'.
2952  *
2953  * @param ctx context.
2954  * @param nfa NFA automaton.
2955  * @param dfa DFA automaton.
2956  * @param dfa_state current dfa state, pass epsilon closure of first nfa state
2957  *                  for starting.
2958  */
2959 static void
2960 construct_dfa_states (struct REGEX_INTERNAL_Context *ctx,
2961                       struct REGEX_INTERNAL_Automaton *nfa,
2962                       struct REGEX_INTERNAL_Automaton *dfa,
2963                       struct REGEX_INTERNAL_State *dfa_state)
2964 {
2965   struct REGEX_INTERNAL_Transition *ctran;
2966   struct REGEX_INTERNAL_State *new_dfa_state;
2967   struct REGEX_INTERNAL_State *state_contains;
2968   struct REGEX_INTERNAL_State *state_iter;
2969   struct REGEX_INTERNAL_StateSet tmp;
2970   struct REGEX_INTERNAL_StateSet nfa_set;
2971
2972   for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
2973   {
2974     if (NULL == ctran->label || NULL != ctran->to_state)
2975       continue;
2976
2977     nfa_closure_set_create (&tmp, nfa, &dfa_state->nfa_set, ctran->label);
2978     nfa_closure_set_create (&nfa_set, nfa, &tmp, NULL);
2979     state_set_clear (&tmp);
2980
2981     state_contains = NULL;
2982     for (state_iter = dfa->states_head; NULL != state_iter;
2983          state_iter = state_iter->next)
2984     {
2985       if (0 == state_set_compare (&state_iter->nfa_set, &nfa_set))
2986       {
2987         state_contains = state_iter;
2988         break;
2989       }
2990     }
2991     if (NULL == state_contains)
2992     {
2993       new_dfa_state = dfa_state_create (ctx, &nfa_set);
2994       automaton_add_state (dfa, new_dfa_state);
2995       ctran->to_state = new_dfa_state;
2996       construct_dfa_states (ctx, nfa, dfa, new_dfa_state);
2997     }
2998     else
2999     {
3000       ctran->to_state = state_contains;
3001       state_set_clear (&nfa_set);
3002     }
3003   }
3004 }
3005
3006
3007 /**
3008  * Construct DFA for the given 'regex' of length 'len'.
3009  *
3010  * Path compression means, that for example a DFA o -> a -> b -> c -> o will be
3011  * compressed to o -> abc -> o. Note that this parameter influences the
3012  * non-determinism of states of the resulting NFA in the DHT (number of outgoing
3013  * edges with the same label). For example for an application that stores IPv4
3014  * addresses as bitstrings it could make sense to limit the path compression to
3015  * 4 or 8.
3016  *
3017  * @param regex regular expression string.
3018  * @param len length of the regular expression.
3019  * @param max_path_len limit the path compression length to the
3020  *        given value. If set to 1, no path compression is applied. Set to 0 for
3021  *        maximal possible path compression (generally not desireable).
3022  * @return DFA, needs to be freed using REGEX_INTERNAL_automaton_destroy.
3023  */
3024 struct REGEX_INTERNAL_Automaton *
3025 REGEX_INTERNAL_construct_dfa (const char *regex, const size_t len,
3026                               unsigned int max_path_len)
3027 {
3028   struct REGEX_INTERNAL_Context ctx;
3029   struct REGEX_INTERNAL_Automaton *dfa;
3030   struct REGEX_INTERNAL_Automaton *nfa;
3031   struct REGEX_INTERNAL_StateSet nfa_start_eps_cls;
3032   struct REGEX_INTERNAL_StateSet singleton_set;
3033
3034   REGEX_INTERNAL_context_init (&ctx);
3035
3036   /* Create NFA */
3037   nfa = REGEX_INTERNAL_construct_nfa (regex, len);
3038
3039   if (NULL == nfa)
3040   {
3041     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
3042                 "Could not create DFA, because NFA creation failed\n");
3043     return NULL;
3044   }
3045
3046   dfa = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Automaton));
3047   dfa->type = DFA;
3048   dfa->regex = GNUNET_strdup (regex);
3049
3050   /* Create DFA start state from epsilon closure */
3051   memset (&singleton_set, 0, sizeof (struct REGEX_INTERNAL_StateSet));
3052   state_set_append (&singleton_set, nfa->start);
3053   nfa_closure_set_create (&nfa_start_eps_cls, nfa, &singleton_set, NULL);
3054   state_set_clear (&singleton_set);
3055   dfa->start = dfa_state_create (&ctx, &nfa_start_eps_cls);
3056   automaton_add_state (dfa, dfa->start);
3057
3058   construct_dfa_states (&ctx, nfa, dfa, dfa->start);
3059   REGEX_INTERNAL_automaton_destroy (nfa);
3060
3061   /* Minimize DFA */
3062   if (GNUNET_OK != dfa_minimize (&ctx, dfa))
3063   {
3064     REGEX_INTERNAL_automaton_destroy (dfa);
3065     return NULL;
3066   }
3067
3068   /* Create proofs and hashes for all states */
3069   if (GNUNET_OK != automaton_create_proofs (dfa))
3070   {
3071     REGEX_INTERNAL_automaton_destroy (dfa);
3072     return NULL;
3073   }
3074
3075   /* Compress linear DFA paths */
3076   if (1 != max_path_len)
3077     dfa_compress_paths (&ctx, dfa, max_path_len);
3078
3079   return dfa;
3080 }
3081
3082
3083 /**
3084  * Free the memory allocated by constructing the REGEX_INTERNAL_Automaton data
3085  * structure.
3086  *
3087  * @param a automaton to be destroyed
3088  */
3089 void
3090 REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a)
3091 {
3092   struct REGEX_INTERNAL_State *s;
3093   struct REGEX_INTERNAL_State *next_state;
3094
3095   if (NULL == a)
3096     return;
3097
3098   GNUNET_free_non_null (a->regex);
3099   GNUNET_free_non_null (a->canonical_regex);
3100
3101   for (s = a->states_head; NULL != s; s = next_state)
3102   {
3103     next_state = s->next;
3104     GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
3105     automaton_destroy_state (s);
3106   }
3107
3108   GNUNET_free (a);
3109 }
3110
3111
3112 /**
3113  * Evaluates the given string using the given DFA automaton
3114  *
3115  * @param a automaton, type must be DFA
3116  * @param string string that should be evaluated
3117  *
3118  * @return 0 if string matches, non 0 otherwise
3119  */
3120 static int
3121 evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
3122 {
3123   const char *strp;
3124   struct REGEX_INTERNAL_State *s;
3125   unsigned int step_len;
3126
3127   if (DFA != a->type)
3128   {
3129     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
3130                 "Tried to evaluate DFA, but NFA automaton given");
3131     return -1;
3132   }
3133
3134   s = a->start;
3135
3136   /* If the string is empty but the starting state is accepting, we accept. */
3137   if ((NULL == string || 0 == strlen (string)) && s->accepting)
3138     return 0;
3139
3140   for (strp = string; NULL != strp && *strp; strp += step_len)
3141   {
3142     step_len = dfa_move (&s, strp);
3143
3144     if (NULL == s)
3145       break;
3146   }
3147
3148   if (NULL != s && s->accepting)
3149     return 0;
3150
3151   return 1;
3152 }
3153
3154
3155 /**
3156  * Evaluates the given string using the given NFA automaton
3157  *
3158  * @param a automaton, type must be NFA
3159  * @param string string that should be evaluated
3160  *
3161  * @return 0 if string matches, non 0 otherwise
3162  */
3163 static int
3164 evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
3165 {
3166   const char *strp;
3167   char str[2];
3168   struct REGEX_INTERNAL_State *s;
3169   struct REGEX_INTERNAL_StateSet sset;
3170   struct REGEX_INTERNAL_StateSet new_sset;
3171   struct REGEX_INTERNAL_StateSet singleton_set;
3172   unsigned int i;
3173   int result;
3174
3175   if (NFA != a->type)
3176   {
3177     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
3178                 "Tried to evaluate NFA, but DFA automaton given");
3179     return -1;
3180   }
3181
3182   /* If the string is empty but the starting state is accepting, we accept. */
3183   if ((NULL == string || 0 == strlen (string)) && a->start->accepting)
3184     return 0;
3185
3186   result = 1;
3187   memset (&singleton_set, 0, sizeof (struct REGEX_INTERNAL_StateSet));
3188   state_set_append (&singleton_set, a->start);
3189   nfa_closure_set_create (&sset, a, &singleton_set, NULL);
3190   state_set_clear (&singleton_set);
3191
3192   str[1] = '\0';
3193   for (strp = string; NULL != strp && *strp; strp++)
3194   {
3195     str[0] = *strp;
3196     nfa_closure_set_create (&new_sset, a, &sset, str);
3197     state_set_clear (&sset);
3198     nfa_closure_set_create (&sset, a, &new_sset, 0);
3199     state_set_clear (&new_sset);
3200   }
3201
3202   for (i = 0; i < sset.off; i++)
3203   {
3204     s = sset.states[i];
3205     if ( (NULL != s) && (s->accepting) )
3206     {
3207       result = 0;
3208       break;
3209     }
3210   }
3211
3212   state_set_clear (&sset);
3213   return result;
3214 }
3215
3216
3217 /**
3218  * Evaluates the given 'string' against the given compiled regex
3219  *
3220  * @param a automaton
3221  * @param string string to check
3222  *
3223  * @return 0 if string matches, non 0 otherwise
3224  */
3225 int
3226 REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string)
3227 {
3228   int result;
3229
3230   switch (a->type)
3231   {
3232   case DFA:
3233     result = evaluate_dfa (a, string);
3234     break;
3235   case NFA:
3236     result = evaluate_nfa (a, string);
3237     break;
3238   default:
3239     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
3240                 "Evaluating regex failed, automaton has no type!\n");
3241     result = GNUNET_SYSERR;
3242     break;
3243   }
3244
3245   return result;
3246 }
3247
3248
3249 /**
3250  * Get the canonical regex of the given automaton.
3251  * When constructing the automaton a proof is computed for each state,
3252  * consisting of the regular expression leading to this state. A complete
3253  * regex for the automaton can be computed by combining these proofs.
3254  * As of now this function is only useful for testing.
3255  *
3256  * @param a automaton for which the canonical regex should be returned.
3257  *
3258  * @return
3259  */
3260 const char *
3261 REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a)
3262 {
3263   if (NULL == a)
3264     return NULL;
3265
3266   return a->canonical_regex;
3267 }
3268
3269
3270 /**
3271  * Get the number of transitions that are contained in the given automaton.
3272  *
3273  * @param a automaton for which the number of transitions should be returned.
3274  *
3275  * @return number of transitions in the given automaton.
3276  */
3277 unsigned int
3278 REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a)
3279 {
3280   unsigned int t_count;
3281   struct REGEX_INTERNAL_State *s;
3282
3283   if (NULL == a)
3284     return 0;
3285
3286   t_count = 0;
3287   for (s = a->states_head; NULL != s; s = s->next)
3288     t_count += s->transition_count;
3289
3290   return t_count;
3291 }
3292
3293
3294 /**
3295  * Get the first key for the given 'input_string'. This hashes the first x bits
3296  * of the 'input_string'.
3297  *
3298  * @param input_string string.
3299  * @param string_len length of the 'input_string'.
3300  * @param key pointer to where to write the hash code.
3301  *
3302  * @return number of bits of 'input_string' that have been consumed
3303  *         to construct the key
3304  */
3305 size_t
3306 REGEX_INTERNAL_get_first_key (const char *input_string, size_t string_len,
3307                             struct GNUNET_HashCode * key)
3308 {
3309   size_t size;
3310
3311   size = string_len < GNUNET_REGEX_INITIAL_BYTES ? string_len :
3312                                                    GNUNET_REGEX_INITIAL_BYTES;
3313   if (NULL == input_string)
3314   {
3315     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
3316                 "Given input string was NULL!\n");
3317     return 0;
3318   }
3319   GNUNET_CRYPTO_hash (input_string, size, key);
3320
3321   return size;
3322 }
3323
3324
3325 /**
3326  * Recursive function that calls the iterator for each synthetic start state.
3327  *
3328  * @param min_len minimum length of the path in the graph.
3329  * @param max_len maximum length of the path in the graph.
3330  * @param consumed_string string consumed by traversing the graph till this state.
3331  * @param state current state of the automaton.
3332  * @param iterator iterator function called for each edge.
3333  * @param iterator_cls closure for the iterator function.
3334  */
3335 static void
3336 iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
3337                       char *consumed_string, struct REGEX_INTERNAL_State *state,
3338                       REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
3339 {
3340   char *temp;
3341   struct REGEX_INTERNAL_Transition *t;
3342   unsigned int num_edges = state->transition_count;
3343   struct REGEX_BLOCK_Edge edges[num_edges];
3344   struct REGEX_BLOCK_Edge edge[1];
3345   struct GNUNET_HashCode hash;
3346   struct GNUNET_HashCode hash_new;
3347   unsigned int cur_len;
3348
3349   if (NULL != consumed_string)
3350     cur_len = strlen (consumed_string);
3351   else
3352     cur_len = 0;
3353
3354   if ((cur_len >= min_len || GNUNET_YES == state->accepting) && cur_len > 0 &&
3355       NULL != consumed_string)
3356   {
3357     if (cur_len <= max_len)
3358     {
3359       if (state->proof != NULL && 0 != strcmp (consumed_string, state->proof))
3360       {
3361         (void) state_get_edges (state, edges);
3362         GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash);
3363         iterator (iterator_cls, &hash, consumed_string, state->accepting,
3364                   num_edges, edges);
3365       }
3366
3367       if (GNUNET_YES == state->accepting && cur_len > 1 &&
3368           state->transition_count < 1 && cur_len < max_len)
3369       {
3370         /* Special case for regex consisting of just a string that is shorter than
3371          * max_len */
3372         edge[0].label = &consumed_string[cur_len - 1];
3373         edge[0].destination = state->hash;
3374         temp = GNUNET_strdup (consumed_string);
3375         temp[cur_len - 1] = '\0';
3376         GNUNET_CRYPTO_hash (temp, cur_len - 1, &hash_new);
3377         iterator (iterator_cls, &hash_new, temp, GNUNET_NO, 1, edge);
3378         GNUNET_free (temp);
3379       }
3380     }
3381     else /* cur_len > max_len */
3382     {
3383       /* Case where the concatenated labels are longer than max_len, then split. */
3384       edge[0].label = &consumed_string[max_len];
3385       edge[0].destination = state->hash;
3386       temp = GNUNET_strdup (consumed_string);
3387       temp[max_len] = '\0';
3388       GNUNET_CRYPTO_hash (temp, max_len, &hash);
3389       iterator (iterator_cls, &hash, temp, GNUNET_NO, 1, edge);
3390       GNUNET_free (temp);
3391     }
3392   }
3393
3394   if (cur_len < max_len)
3395   {
3396     for (t = state->transitions_head; NULL != t; t = t->next)
3397     {
3398       if (NULL != consumed_string)
3399         GNUNET_asprintf (&temp, "%s%s", consumed_string, t->label);
3400       else
3401         GNUNET_asprintf (&temp, "%s", t->label);
3402
3403       iterate_initial_edge (min_len, max_len, temp, t->to_state, iterator,
3404                             iterator_cls);
3405       GNUNET_free (temp);
3406     }
3407   }
3408 }
3409
3410
3411 /**
3412  * Iterate over all edges starting from start state of automaton 'a'. Calling
3413  * iterator for each edge.
3414  *
3415  * @param a automaton.
3416  * @param iterator iterator called for each edge.
3417  * @param iterator_cls closure.
3418  */
3419 void
3420 REGEX_INTERNAL_iterate_all_edges (struct REGEX_INTERNAL_Automaton *a,
3421                                   REGEX_INTERNAL_KeyIterator iterator,
3422                                   void *iterator_cls)
3423 {
3424   struct REGEX_INTERNAL_State *s;
3425
3426   for (s = a->states_head; NULL != s; s = s->next)
3427   {
3428     struct REGEX_BLOCK_Edge edges[s->transition_count];
3429     unsigned int num_edges;
3430
3431     num_edges = state_get_edges (s, edges);
3432     if ( ( (NULL != s->proof) &&
3433            (0 < strlen (s->proof)) ) || s->accepting)
3434       iterator (iterator_cls, &s->hash, s->proof,
3435                 s->accepting,
3436                 num_edges, edges);
3437     s->marked = GNUNET_NO;
3438   }
3439
3440   iterate_initial_edge (GNUNET_REGEX_INITIAL_BYTES,
3441                         GNUNET_REGEX_INITIAL_BYTES,
3442                         NULL, a->start,
3443                         iterator, iterator_cls);
3444 }
3445
3446 /**
3447  * Struct to hold all the relevant state information in the HashMap.
3448  *
3449  * Contains the same info as the Regex Iterator parametes except the key,
3450  * which comes directly from the HashMap iterator.
3451  */
3452 struct temporal_state_store {
3453   int reachable;
3454   char *proof;
3455   int accepting;
3456   int num_edges;
3457   struct REGEX_BLOCK_Edge *edges;
3458 };
3459
3460
3461 /**
3462  * Store regex iterator and cls in one place to pass to the hashmap iterator.
3463  */
3464 struct client_iterator {
3465   REGEX_INTERNAL_KeyIterator iterator;
3466   void *iterator_cls;
3467 };
3468
3469
3470 /**
3471  * Iterator over all edges of a dfa. Stores all of them in a HashMap
3472  * for later reachability marking.
3473  *
3474  * @param cls Closure (HashMap)
3475  * @param key hash for current state.
3476  * @param proof proof for current state
3477  * @param accepting GNUNET_YES if this is an accepting state, GNUNET_NO if not.
3478  * @param num_edges number of edges leaving current state.
3479  * @param edges edges leaving current state.
3480  */
3481 static void
3482 store_all_states (void *cls,
3483                   const struct GNUNET_HashCode *key,
3484                   const char *proof,
3485                   int accepting,
3486                   unsigned int num_edges,
3487                   const struct REGEX_BLOCK_Edge *edges)
3488 {
3489   struct GNUNET_CONTAINER_MultiHashMap *hm = cls;
3490   struct temporal_state_store *tmp;
3491   size_t edges_size;
3492
3493   tmp = GNUNET_new (struct temporal_state_store);
3494   tmp->reachable = GNUNET_NO;
3495   tmp->proof = GNUNET_strdup (proof);
3496   tmp->accepting = accepting;
3497   tmp->num_edges = num_edges;
3498   edges_size = sizeof (struct REGEX_BLOCK_Edge) * num_edges;
3499   tmp->edges = GNUNET_malloc (edges_size);
3500   memcpy(tmp->edges, edges, edges_size);
3501   GNUNET_CONTAINER_multihashmap_put (hm, key, tmp,
3502                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
3503 }
3504
3505
3506 /**
3507  * Mark state as reachable and call recursively on all its edges.
3508  *
3509  * If already marked as reachable, do nothing.
3510  *
3511  * @param state State to mark as reachable.
3512  * @param hm HashMap which stores all the states indexed by key.
3513  */
3514 static void
3515 mark_as_reachable (struct temporal_state_store *state,
3516                    struct GNUNET_CONTAINER_MultiHashMap *hm)
3517 {
3518   struct temporal_state_store *child;
3519   unsigned int i;
3520
3521   if (GNUNET_YES == state->reachable)
3522     /* visited */
3523     return;
3524
3525   state->reachable = GNUNET_YES;
3526   for (i = 0; i < state->num_edges; i++)
3527   {
3528     child = GNUNET_CONTAINER_multihashmap_get (hm,
3529                                                &state->edges[i].destination);
3530     if (NULL == child)
3531     {
3532       GNUNET_break (0);
3533       continue;
3534     }
3535     mark_as_reachable (child, hm);
3536   }
3537 }
3538
3539
3540 /**
3541  * Iterator over hash map entries to mark the ones that are reachable.
3542  *
3543  * @param cls closure
3544  * @param key current key code
3545  * @param value value in the hash map
3546  * @return #GNUNET_YES if we should continue to iterate,
3547  *         #GNUNET_NO if not.
3548  */
3549 static int
3550 reachability_iterator (void *cls,
3551                        const struct GNUNET_HashCode *key,
3552                        void *value)
3553 {
3554   struct GNUNET_CONTAINER_MultiHashMap *hm = cls;
3555   struct temporal_state_store *state = value;
3556
3557   if (GNUNET_YES == state->reachable)
3558     /* already visited and marked */
3559     return GNUNET_YES;
3560
3561   if (GNUNET_REGEX_INITIAL_BYTES > strlen (state->proof) &&
3562       GNUNET_NO == state->accepting)
3563     /* not directly reachable */
3564     return GNUNET_YES;
3565
3566   mark_as_reachable (state, hm);
3567   return GNUNET_YES;
3568 }
3569
3570
3571 /**
3572  * Iterator over hash map entries.
3573  * Calling the callback on the ones marked as reachables.
3574  *
3575  * @param cls closure
3576  * @param key current key code
3577  * @param value value in the hash map
3578  * @return #GNUNET_YES if we should continue to iterate,
3579  *         #GNUNET_NO if not.
3580  */
3581 static int
3582 iterate_reachables (void *cls,
3583                     const struct GNUNET_HashCode *key,
3584                     void *value)
3585 {
3586   struct client_iterator *ci = cls;
3587   struct temporal_state_store *state = value;
3588
3589   if (GNUNET_YES == state->reachable)
3590   {
3591     ci->iterator (ci->iterator_cls, key,
3592                   state->proof, state->accepting,
3593                   state->num_edges, state->edges);
3594   }
3595   GNUNET_free (state->edges);
3596   GNUNET_free (state->proof);
3597   GNUNET_free (state);
3598   return GNUNET_YES;
3599
3600 }
3601
3602 /**
3603  * Iterate over all edges of automaton 'a' that are reachable from a state with
3604  * a proof of at least GNUNET_REGEX_INITIAL_BYTES characters.
3605  *
3606  * Call the iterator for each such edge.
3607  *
3608  * @param a automaton.
3609  * @param iterator iterator called for each reachable edge.
3610  * @param iterator_cls closure.
3611  */
3612 void
3613 REGEX_INTERNAL_iterate_reachable_edges (struct REGEX_INTERNAL_Automaton *a,
3614                                         REGEX_INTERNAL_KeyIterator iterator,
3615                                         void *iterator_cls)
3616 {
3617   struct GNUNET_CONTAINER_MultiHashMap *hm;
3618   struct client_iterator ci;
3619
3620   hm = GNUNET_CONTAINER_multihashmap_create (a->state_count * 2, GNUNET_NO);
3621   ci.iterator = iterator;
3622   ci.iterator_cls = iterator_cls;
3623
3624   REGEX_INTERNAL_iterate_all_edges (a, &store_all_states, hm);
3625   GNUNET_CONTAINER_multihashmap_iterate (hm, &reachability_iterator, hm);
3626   GNUNET_CONTAINER_multihashmap_iterate (hm, &iterate_reachables, &ci);
3627
3628   GNUNET_CONTAINER_multihashmap_destroy (hm);
3629 }
3630
3631
3632 /* end of regex_internal.c */