[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r23386 - gnunet/src/regex
From: |
gnunet |
Subject: |
[GNUnet-SVN] r23386 - gnunet/src/regex |
Date: |
Thu, 23 Aug 2012 18:30:39 +0200 |
Author: szengel
Date: 2012-08-23 18:30:39 +0200 (Thu, 23 Aug 2012)
New Revision: 23386
Modified:
gnunet/src/regex/regex.c
gnunet/src/regex/regex_graph.c
gnunet/src/regex/regex_internal.h
gnunet/src/regex/test_regex_eval_api.c
Log:
- 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
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-08-23 14:54:27 UTC (rev 23385)
+++ gnunet/src/regex/regex.c 2012-08-23 16:30:39 UTC (rev 23386)
@@ -580,12 +580,16 @@
* @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 @@
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 @@
*
* @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 @@
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 @@
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 @@
}
/* 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 @@
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 @@
n->type = NFA;
n->start = NULL;
n->end = NULL;
+ n->state_count = 0;
if (NULL == start || NULL == end)
return n;
@@ -1791,6 +1808,8 @@
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_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 @@
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;
Modified: gnunet/src/regex/regex_graph.c
===================================================================
--- gnunet/src/regex/regex_graph.c 2012-08-23 14:54:27 UTC (rev 23385)
+++ gnunet/src/regex/regex_graph.c 2012-08-23 16:30:39 UTC (rev 23386)
@@ -315,12 +315,13 @@
}
/* 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);
Modified: gnunet/src/regex/regex_internal.h
===================================================================
--- gnunet/src/regex/regex_internal.h 2012-08-23 14:54:27 UTC (rev 23385)
+++ gnunet/src/regex/regex_internal.h 2012-08-23 16:30:39 UTC (rev 23386)
@@ -257,6 +257,23 @@
/**
+ * 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.
*
* @param cls closure.
@@ -275,16 +292,20 @@
*
* @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,
Modified: gnunet/src/regex/test_regex_eval_api.c
===================================================================
--- gnunet/src/regex/test_regex_eval_api.c 2012-08-23 14:54:27 UTC (rev
23385)
+++ gnunet/src/regex/test_regex_eval_api.c 2012-08-23 16:30:39 UTC (rev
23386)
@@ -348,8 +348,8 @@
/* 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;
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r23386 - gnunet/src/regex,
gnunet <=