From 09f394f4f8fc77de47857adf9b8630136d930005 Mon Sep 17 00:00:00 2001 From: Maximilian Szengel Date: Thu, 23 Aug 2012 16:30:39 +0000 Subject: - added check for automaton traversal - fixed a bug that caused nfa's state_count to be incorrect for certain regexes - only compute scc's when coloring option is set --- src/regex/regex.c | 34 +++++++++++++++++++++++++++------- src/regex/regex_graph.c | 5 +++-- src/regex/regex_internal.h | 23 ++++++++++++++++++++++- src/regex/test_regex_eval_api.c | 4 ++-- 4 files changed, 54 insertions(+), 12 deletions(-) (limited to 'src/regex') diff --git a/src/regex/regex.c b/src/regex/regex.c index 79d94ea03..f8177305e 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c @@ -580,12 +580,16 @@ automaton_add_state (struct GNUNET_REGEX_Automaton *a, * @param marks an array of size a->state_count to remember which state was * already visited. * @param count current count of the state. + * @param check function that is checked before advancing on each transition + * in the DFS. + * @param check_cls closure for check. * @param action action to be performed on each state. * @param action_cls closure for action. */ static void automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, unsigned int *count, + GNUNET_REGEX_traverse_check check, void *check_cls, GNUNET_REGEX_traverse_action action, void *action_cls) { struct GNUNET_REGEX_Transition *t; @@ -602,7 +606,12 @@ automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, for (t = s->transitions_head; NULL != t; t = t->next) { - automaton_state_traverse (t->to_state, marks, count, action, action_cls); + if (NULL == check || + (NULL != check && GNUNET_YES == check (check_cls, s, t))) + { + automaton_state_traverse (t->to_state, marks, count, check, check_cls, + action, action_cls); + } } } @@ -614,12 +623,17 @@ automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, * * @param a automaton to be traversed. * @param start start state, pass a->start or NULL to traverse the whole automaton. + * @param check function that is checked before advancing on each transition + * in the DFS. + * @param check_cls closure for check. * @param action action to be performed on each state. * @param action_cls closure for action */ void GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, struct GNUNET_REGEX_State *start, + GNUNET_REGEX_traverse_check check, + void *check_cls, GNUNET_REGEX_traverse_action action, void *action_cls) { @@ -644,7 +658,8 @@ GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, else s = start; - automaton_state_traverse (s, marks, &count, action, action_cls); + automaton_state_traverse (s, marks, &count, check, check_cls, action, + action_cls); } @@ -755,8 +770,8 @@ GNUNET_REGEX_add_multi_strides_to_dfa (struct GNUNET_REGEX_Context *regex_ctx, struct GNUNET_REGEX_Transition *t; struct GNUNET_REGEX_Transition *t_next; - GNUNET_REGEX_automaton_traverse (dfa, dfa->start, &add_multi_strides_to_dfa, - &ctx); + GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, + &add_multi_strides_to_dfa, &ctx); for (t = ctx.transitions_head; NULL != t; t = t_next) { @@ -1329,7 +1344,8 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) } /* create depth-first numbering of the states, initializes 'state' */ - GNUNET_REGEX_automaton_traverse (a, a->start, &number_states, states); + GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &number_states, + states); for (i = 0; i < n; i++) GNUNET_assert (NULL != states[i]); @@ -1591,7 +1607,7 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) s->marked = GNUNET_NO; // 2. traverse dfa from start state and mark all visited states - GNUNET_REGEX_automaton_traverse (a, a->start, &mark_states, NULL); + GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL); // 3. delete all states that were not visited for (s = a->states_head; NULL != s; s = s_next) @@ -1784,6 +1800,7 @@ nfa_fragment_create (struct GNUNET_REGEX_State *start, n->type = NFA; n->start = NULL; n->end = NULL; + n->state_count = 0; if (NULL == start || NULL == end) return n; @@ -1791,6 +1808,8 @@ nfa_fragment_create (struct GNUNET_REGEX_State *start, automaton_add_state (n, end); automaton_add_state (n, start); + n->state_count = 2; + n->start = start; n->end = end; @@ -2016,6 +2035,7 @@ nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx) nfa_add_states (new_nfa, b->states_head, b->states_tail); new_nfa->start = a->start; new_nfa->end = b->end; + new_nfa->state_count += a->state_count + b->state_count; automaton_fragment_clear (a); automaton_fragment_clear (b); @@ -2363,7 +2383,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) nfa->regex = GNUNET_strdup (regex); /* create depth-first numbering of the states for pretty printing */ - GNUNET_REGEX_automaton_traverse (nfa, NULL, &number_states, NULL); + GNUNET_REGEX_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL); return nfa; diff --git a/src/regex/regex_graph.c b/src/regex/regex_graph.c index 9223200c8..5db3780d0 100644 --- a/src/regex/regex_graph.c +++ b/src/regex/regex_graph.c @@ -315,12 +315,13 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, } /* First add the SCCs to the automaton, so we can color them nicely */ - scc_tarjan (a); + if (GNUNET_YES == ctx.coloring) + scc_tarjan (a); start = "digraph G {\nrankdir=LR\n"; fwrite (start, strlen (start), 1, ctx.filep); - GNUNET_REGEX_automaton_traverse (a, a->start, + GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &GNUNET_REGEX_automaton_save_graph_step, &ctx); diff --git a/src/regex/regex_internal.h b/src/regex/regex_internal.h index f96d51fb0..20e81d93c 100644 --- a/src/regex/regex_internal.h +++ b/src/regex/regex_internal.h @@ -256,6 +256,23 @@ struct GNUNET_REGEX_Automaton }; +/** + * Function that get's passed to automaton traversal and is called before each + * next traversal from state 's' using transition 't' to check if traversal + * should proceed. Return GNUNET_NO to stop traversal or GNUNET_YES to continue. + * + * @param cls closure for the check. + * @param s current state in the traversal. + * @param t current transition from state 's' that will be used for the next + * step. + * + * @return GNUNET_YES to proceed traversal, GNUNET_NO to stop. + */ +typedef int (*GNUNET_REGEX_traverse_check) (void *cls, + struct GNUNET_REGEX_State * s, + struct GNUNET_REGEX_Transition * t); + + /** * Function that is called with each state, when traversing an automaton. * @@ -275,16 +292,20 @@ typedef void (*GNUNET_REGEX_traverse_action) (void *cls, * * @param a automaton to be traversed. * @param start start state, pass a->start or NULL to traverse the whole automaton. + * @param check function that is checked before advancing on each transition + * in the DFS. + * @param check_cls closure for check. * @param action action to be performed on each state. * @param action_cls closure for action */ void GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, struct GNUNET_REGEX_State *start, + GNUNET_REGEX_traverse_check check, + void *check_cls, GNUNET_REGEX_traverse_action action, void *action_cls); - /** * Get the canonical regex of the given automaton. * When constructing the automaton a proof is computed for each state, diff --git a/src/regex/test_regex_eval_api.c b/src/regex/test_regex_eval_api.c index 2de7d40b2..a4b183127 100644 --- a/src/regex/test_regex_eval_api.c +++ b/src/regex/test_regex_eval_api.c @@ -348,8 +348,8 @@ main (int argc, char *argv[]) /* Random tests */ srand (time (NULL)); - for (i = 0; i < 50; i++) - check_rand += test_random (50, 60, 30); + for (i = 0; i < 20; i++) + check_rand += test_random (50, 60, 10); return check_nfa + check_dfa + check_rand; } -- cgit v1.2.3