diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-05 11:46:24 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-05 11:46:24 +0000 |
commit | 4bddef66e721cf68b17effea2c23aebd89ca1b8b (patch) | |
tree | 151e1e4ccdee93d60d5fbc99108a7e4eb88fe0d2 /src/regex/regex.c | |
parent | ff1407f3502c2294dbf9f2c6a753b9e3fa04973a (diff) | |
download | gnunet-4bddef66e721cf68b17effea2c23aebd89ca1b8b.tar.gz gnunet-4bddef66e721cf68b17effea2c23aebd89ca1b8b.zip |
Automatic regex generation for testing
Diffstat (limited to 'src/regex/regex.c')
-rw-r--r-- | src/regex/regex.c | 39 |
1 files changed, 32 insertions, 7 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 6432075a5..fc9de529c 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -416,6 +416,15 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, struct StateSet *nfa_states) | |||
416 | return s; | 416 | return s; |
417 | } | 417 | } |
418 | 418 | ||
419 | /** | ||
420 | * Move from the given state 's' to the next state on | ||
421 | * transition 'literal' | ||
422 | * | ||
423 | * @param s starting state | ||
424 | * @param literal edge label to follow | ||
425 | * | ||
426 | * @return new state or NULL, if transition on literal not possible | ||
427 | */ | ||
419 | static struct State * | 428 | static struct State * |
420 | dfa_move (struct State *s, const char literal) | 429 | dfa_move (struct State *s, const char literal) |
421 | { | 430 | { |
@@ -439,6 +448,12 @@ dfa_move (struct State *s, const char literal) | |||
439 | return new_s; | 448 | return new_s; |
440 | } | 449 | } |
441 | 450 | ||
451 | /** | ||
452 | * Remove all unreachable states from DFA 'a'. Unreachable states | ||
453 | * are those states that are not reachable from the starting state. | ||
454 | * | ||
455 | * @param a DFA automaton | ||
456 | */ | ||
442 | static void | 457 | static void |
443 | dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | 458 | dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) |
444 | { | 459 | { |
@@ -472,6 +487,12 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | |||
472 | */ | 487 | */ |
473 | } | 488 | } |
474 | 489 | ||
490 | /** | ||
491 | * Remove all dead states from the DFA 'a'. Dead states are those | ||
492 | * states that do not transition to any other state but themselfes. | ||
493 | * | ||
494 | * @param a DFA automaton | ||
495 | */ | ||
475 | static void | 496 | static void |
476 | dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a) | 497 | dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a) |
477 | { | 498 | { |
@@ -520,12 +541,23 @@ dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a) | |||
520 | } | 541 | } |
521 | } | 542 | } |
522 | 543 | ||
544 | /** | ||
545 | * Merge all non distinguishable states in the DFA 'a' | ||
546 | * | ||
547 | * @param a DFA automaton | ||
548 | */ | ||
523 | static void | 549 | static void |
524 | dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Automaton *a) | 550 | dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Automaton *a) |
525 | { | 551 | { |
526 | 552 | ||
527 | } | 553 | } |
528 | 554 | ||
555 | /** | ||
556 | * Minimize the given DFA 'a' by removing all unreachable states, | ||
557 | * removing all dead states and merging all non distinguishable states | ||
558 | * | ||
559 | * @param a DFA automaton | ||
560 | */ | ||
529 | static void | 561 | static void |
530 | dfa_minimize (struct GNUNET_REGEX_Automaton *a) | 562 | dfa_minimize (struct GNUNET_REGEX_Automaton *a) |
531 | { | 563 | { |
@@ -1029,10 +1061,6 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
1029 | goto error; | 1061 | goto error; |
1030 | } | 1062 | } |
1031 | 1063 | ||
1032 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1033 | "Created NFA with %i States and a total of %i Transitions\n", | ||
1034 | ctx.state_id, ctx.transition_id); | ||
1035 | |||
1036 | return nfa; | 1064 | return nfa; |
1037 | 1065 | ||
1038 | error: | 1066 | error: |
@@ -1156,9 +1184,6 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len) | |||
1156 | 1184 | ||
1157 | dfa_minimize (dfa); | 1185 | dfa_minimize (dfa); |
1158 | 1186 | ||
1159 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Created DFA with %i States\n", | ||
1160 | ctx.state_id); | ||
1161 | |||
1162 | return dfa; | 1187 | return dfa; |
1163 | } | 1188 | } |
1164 | 1189 | ||