#define INITIAL_BITS 8
-/**
- * Context that contains an id counter for states and transitions as well as a
- * DLL of automatons used as a stack for NFA construction.
- */
-struct GNUNET_REGEX_Context
-{
- /**
- * Unique state id.
- */
- unsigned int state_id;
-
- /**
- * Unique transition id.
- */
- unsigned int transition_id;
-
- /**
- * DLL of GNUNET_REGEX_Automaton's used as a stack.
- */
- struct GNUNET_REGEX_Automaton *stack_head;
-
- /**
- * DLL of GNUNET_REGEX_Automaton's used as a stack.
- */
- struct GNUNET_REGEX_Automaton *stack_tail;
-};
-
-
/**
* Set of states.
*/
};
-/*
- * Debug helper functions
- */
-
-/**
- * Print all the transitions of state 's'.
- *
- * @param s state for which to print it's transitions.
- */
-void
-debug_print_transitions (struct GNUNET_REGEX_State *s);
-
-
-/**
- * Print information of the given state 's'.
- *
- * @param s state for which debug information should be printed.
- */
-void
-debug_print_state (struct GNUNET_REGEX_State *s)
-{
- char *proof;
-
- if (NULL == s->proof)
- proof = "NULL";
- else
- proof = s->proof;
-
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "State %i: %s marked: %i accepting: %i scc_id: %i transitions: %i proof: %s\n",
- s->id, s->name, s->marked, s->accepting, s->scc_id,
- s->transition_count, proof);
-
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transitions:\n");
- debug_print_transitions (s);
-}
-
-
-/**
- * Print debug information for all states contained in the automaton 'a'.
- *
- * @param a automaton for which debug information of it's states should be printed.
- */
-void
-debug_print_states (struct GNUNET_REGEX_Automaton *a)
-{
- struct GNUNET_REGEX_State *s;
-
- for (s = a->states_head; NULL != s; s = s->next)
- debug_print_state (s);
-}
-
-
-/**
- * Print debug information for given transition 't'.
- *
- * @param t transition for which to print debug info.
- */
-void
-debug_print_transition (struct GNUNET_REGEX_Transition *t)
-{
- char *to_state;
- char *from_state;
- char *label;
-
- if (NULL == t)
- return;
-
- if (0 == t->label)
- label = "0";
- else
- label = t->label;
-
- if (NULL == t->to_state)
- to_state = "NULL";
- else
- to_state = t->to_state->name;
-
- if (NULL == t->from_state)
- from_state = "NULL";
- else
- from_state = t->from_state->name;
-
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %s to %s\n",
- t->id, from_state, label, to_state);
-}
-
-
-void
-debug_print_transitions (struct GNUNET_REGEX_State *s)
-{
- struct GNUNET_REGEX_Transition *t;
-
- for (t = s->transitions_head; NULL != t; t = t->next)
- debug_print_transition (t);
-}
-
-
/**
* Compare two strings for equality. If either is NULL they are not equal.
*
* @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;
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);
+ }
}
}
*
* @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)
{
else
s = start;
- automaton_state_traverse (s, marks, &count, action, action_cls);
+ automaton_state_traverse (s, marks, &count, check, check_cls, action,
+ action_cls);
}
struct GNUNET_REGEX_Transition *t;
struct GNUNET_REGEX_Transition *t_next;
- GNUNET_REGEX_automaton_traverse (dfa, dfa->start, &add_multi_strides_to_dfa,
- &ctx);
+ if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
+ return;
+
+ // Compute the new transitions.
+ GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL,
+ &add_multi_strides_to_dfa, &ctx);
+ // Add all the new transitions to the automaton.
for (t = ctx.transitions_head; NULL != t; t = t_next)
{
t_next = t->next;
GNUNET_free_non_null (t->label);
GNUNET_free (t);
}
+
+ dfa->is_multistrided = GNUNET_YES;
}
}
/* 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]);
if (nfa_states->len < 1)
return s;
- // Create a name based on 'sset'
+ // Create a name based on 'nfa_states'
s->name = GNUNET_malloc (sizeof (char) * 2);
strcat (s->name, "{");
name = NULL;
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)
n->type = NFA;
n->start = NULL;
n->end = NULL;
+ n->state_count = 0;
if (NULL == start || NULL == end)
return n;
automaton_add_state (n, end);
automaton_add_state (n, start);
+ n->state_count = 2;
+
n->start = start;
n->end = end;
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);
}
nfa_add_question_op (&ctx);
break;
- case 92: /* escape: \ */
- regexp++;
- count++;
- /* fall through! */
default:
if (atomcount > 1)
{
goto error;
}
+ /* Remember the regex that was used to generate this NFA */
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);
+
+ /* No multistriding added so far */
+ nfa->is_multistrided = GNUNET_NO;
return nfa;
struct GNUNET_REGEX_Context ctx;
struct GNUNET_REGEX_Automaton *dfa;
struct GNUNET_REGEX_Automaton *nfa;
- struct GNUNET_REGEX_StateSet *nfa_set;
+ struct GNUNET_REGEX_StateSet *nfa_start_eps_cls;
GNUNET_REGEX_context_init (&ctx);
dfa->states_head = NULL;
dfa->states_tail = NULL;
dfa->regex = GNUNET_strdup (regex);
+ dfa->is_multistrided = GNUNET_NO;
// Create DFA start state from epsilon closure
- nfa_set = nfa_closure_create (nfa, nfa->start, 0);
- dfa->start = dfa_state_create (&ctx, nfa_set);
+ nfa_start_eps_cls = nfa_closure_create (nfa, nfa->start, 0);
+ dfa->start = dfa_state_create (&ctx, nfa_start_eps_cls);
automaton_add_state (dfa, dfa->start);
construct_dfa_states (&ctx, nfa, dfa, dfa->start);
}
+/**
+ * Get the number of transitions that are contained in the given automaton.
+ *
+ * @param a automaton for which the number of transitions should be returned.
+ *
+ * @return number of transitions in the given automaton.
+ */
+unsigned int
+GNUNET_REGEX_get_transition_count (struct GNUNET_REGEX_Automaton *a)
+{
+ unsigned int t_count;
+ struct GNUNET_REGEX_State *s;
+
+ if (NULL == a)
+ return 0;
+
+ for (t_count = 0, s = a->states_head; NULL != s; s = s->next)
+ {
+ t_count += s->transition_count;
+ }
+
+ return t_count;
+}
+
+
/**
* Get the first key for the given 'input_string'. This hashes the first x bits
* of the 'input_string'.
projects / oweals / gnunet.git / blobdiff