#include "regex_internal.h"
-/**
- * Constant for how many bits the initial string regex should have.
- */
-#define INITIAL_BITS 10
-
-
-/**
- * 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'.
+ * Compare two strings for equality. If either is NULL they are not equal.
*
- * @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 str1 first string for comparison.
+ * @param str2 second string for comparison.
*
- * @param t transition for which to print debug info.
+ * @return 0 if the strings are the same or both NULL, 1 or -1 if not.
*/
-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 %c to %s\n",
- t->id, from_state, label, to_state);
-}
-
-
-void
-debug_print_transitions (struct GNUNET_REGEX_State *s)
+static int
+nullstrcmp (const char *str1, const char *str2)
{
- struct GNUNET_REGEX_Transition *t;
+ if ((NULL == str1) != (NULL == str2))
+ return -1;
+ if ((NULL == str1) && (NULL == str2))
+ return 0;
- for (t = s->transitions_head; NULL != t; t = t->next)
- debug_print_transition (t);
+ return strcmp (str1, str2);
}
*/
static void
state_add_transition (struct GNUNET_REGEX_Context *ctx,
- struct GNUNET_REGEX_State *from_state, const char label,
+ struct GNUNET_REGEX_State *from_state, const char *label,
struct GNUNET_REGEX_State *to_state)
{
- int is_dup;
struct GNUNET_REGEX_Transition *t;
struct GNUNET_REGEX_Transition *oth;
}
// Do not add duplicate state transitions
- is_dup = GNUNET_NO;
for (t = from_state->transitions_head; NULL != t; t = t->next)
{
- if (t->to_state == to_state && t->label == label &&
+ if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) &&
t->from_state == from_state)
- {
- is_dup = GNUNET_YES;
- break;
- }
+ return;
}
- if (GNUNET_YES == is_dup)
- return;
-
// sort transitions by label
for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
{
- if (oth->label > label)
+ if (0 < nullstrcmp (oth->label, label))
break;
}
t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition));
- t->id = ctx->transition_id++;
- t->label = label;
+ if (NULL != ctx)
+ t->id = ctx->transition_id++;
+ if (NULL != label)
+ t->label = GNUNET_strdup (label);
+ else
+ t->label = NULL;
t->to_state = to_state;
t->from_state = from_state;
if (transition->from_state != state)
return;
+ GNUNET_free_non_null (transition->label);
+
state->transition_count--;
GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail,
transition);
+
GNUNET_free (transition);
}
{
if (NULL != t->to_state)
{
- edges[count].label = &t->label;
+ edges[count].label = t->label;
edges[count].destination = t->to_state->hash;
count++;
}
static void
state_set_clear (struct GNUNET_REGEX_StateSet *set)
{
- if (NULL != set)
- {
- GNUNET_free_non_null (set->states);
- GNUNET_free (set);
- }
+ if (NULL == set)
+ return;
+
+ if (set->len > 0)
+ GNUNET_array_grow (set->states, set->len, 0);
+ GNUNET_free (set);
}
GNUNET_free_non_null (s->name);
GNUNET_free_non_null (s->proof);
+ state_set_clear (s->nfa_set);
for (t = s->transitions_head; NULL != t; t = next_t)
{
next_t = t->next;
- GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
- GNUNET_free (t);
+ state_remove_transition (s, t);
}
- state_set_clear (s->nfa_set);
-
GNUNET_free (s);
}
automaton_remove_state (struct GNUNET_REGEX_Automaton *a,
struct GNUNET_REGEX_State *s)
{
- struct GNUNET_REGEX_State *ss;
struct GNUNET_REGEX_State *s_check;
struct GNUNET_REGEX_Transition *t_check;
+ struct GNUNET_REGEX_Transition *t_check_next;
if (NULL == a || NULL == s)
return;
- // remove state
- ss = s;
- GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
- a->state_count--;
-
// remove all transitions leading to this state
for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
{
for (t_check = s_check->transitions_head; NULL != t_check;
- t_check = t_check->next)
+ t_check = t_check_next)
{
- if (t_check->to_state == ss)
- {
- GNUNET_CONTAINER_DLL_remove (s_check->transitions_head,
- s_check->transitions_tail, t_check);
- s_check->transition_count--;
- }
+ t_check_next = t_check->next;
+ if (t_check->to_state == s)
+ state_remove_transition (s_check, t_check);
}
}
- automaton_destroy_state (ss);
+ // remove state
+ GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
+ a->state_count--;
+
+ automaton_destroy_state (s);
}
is_dup = GNUNET_NO;
for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
{
- if (t->to_state == s1 && t_check->label == t->label)
+ if (t->to_state == s1 && 0 == strcmp (t_check->label, t->label))
is_dup = GNUNET_YES;
}
if (GNUNET_NO == is_dup)
/**
- * Depth-first traversal of all states that are reachable from state 's'. Expects the states to
- * be unmarked (s->marked == GNUNET_NO). Performs 'action' on each visited
- * state.
+ * Depth-first traversal (DFS) of all states that are reachable from state
+ * 's'. Performs 'action' on each visited state.
*
* @param s start state.
+ * @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
+ * @param action_cls closure for action.
*/
static void
-automaton_state_traverse (struct GNUNET_REGEX_State *s, unsigned int *count,
+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;
- if (GNUNET_NO != s->marked)
+ if (GNUNET_YES == marks[s->traversal_id])
return;
- s->marked = GNUNET_YES;
+
+ marks[s->traversal_id] = GNUNET_YES;
+
if (NULL != action)
action (action_cls, *count, s);
+
(*count)++;
+
for (t = s->transitions_head; NULL != t; t = t->next)
- automaton_state_traverse (t->to_state, 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);
+ }
+ }
}
/**
- * Traverses the given automaton from it's start state, visiting all reachable
- * states and calling 'action' on each one of them.
- *
- * @param a automaton.
+ * Traverses the given automaton using depth-first-search (DFS) from it's start
+ * state, visiting all reachable states and calling 'action' on each one of
+ * them.
+ *
+ * @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 (struct GNUNET_REGEX_Automaton *a,
+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)
{
unsigned int count;
struct GNUNET_REGEX_State *s;
- for (s = a->states_head; NULL != s; s = s->next)
- s->marked = GNUNET_NO;
+ if (NULL == a || 0 == a->state_count)
+ return;
+
+ int marks[a->state_count];
+
+ for (count = 0, s = a->states_head; NULL != s && count < a->state_count;
+ s = s->next, count++)
+ {
+ s->traversal_id = count;
+ marks[s->traversal_id] = GNUNET_NO;
+ }
+
count = 0;
- automaton_state_traverse (a->start, &count, action, action_cls);
+
+ if (NULL == start)
+ s = a->start;
+ else
+ s = start;
+
+ automaton_state_traverse (s, marks, &count, check, check_cls, action,
+ action_cls);
}
*
* @param str string
*
- * @return string without preceding epsilon, string 'str' if no preceding epsilon
- * could be found, NULL if 'str' was NULL
+ * @return string without preceding epsilon, string 'str' if no preceding
+ * epsilon could be found, NULL if 'str' was NULL
*/
static char *
remove_epsilon (const char *str)
/**
- * Compare two strings for equality. If either is NULL (or if both are
- * NULL), they are not equal.
- *
- * @param str1 first string for comparison.
- * @param str2 second string for comparison.
- *
- * @return 0 if the strings are the same, 1 or -1 if not
- */
-static int
-nullstrcmp (const char *str1, const char *str2)
-{
- if ((NULL == str1) || (NULL == str2))
- return -1;
- return strcmp (str1, str2);
-}
-
-
-/**
- * Helper function used as 'action' in 'GNUNET_REGEX_automaton_traverse' function to create
- * the depth-first numbering of the states.
+ * Helper function used as 'action' in 'GNUNET_REGEX_automaton_traverse'
+ * function to create the depth-first numbering of the states.
*
* @param cls states array.
* @param count current state counter.
* @param s current state.
*/
-static void
-number_states (void *cls, unsigned int count, struct GNUNET_REGEX_State *s)
+void
+number_states (void *cls, const unsigned int count,
+ struct GNUNET_REGEX_State *s)
{
struct GNUNET_REGEX_State **states = cls;
- s->proof_id = count;
- states[count] = s;
+ s->dfs_id = count;
+ if (NULL != states)
+ states[count] = s;
}
static void
automaton_create_proofs (struct GNUNET_REGEX_Automaton *a)
{
+ if (NULL == a)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Could not create proofs, automaton was NULL\n");
+ return;
+ }
+
unsigned int n = a->state_count;
struct GNUNET_REGEX_State *states[n];
char *R_last[n][n];
unsigned int j;
unsigned int k;
-
/* create depth-first numbering of the states, initializes 'state' */
- GNUNET_REGEX_automaton_traverse (a, &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]);
/* Compute regular expressions of length "1" between each pair of states */
for (i = 0; i < n; i++)
}
for (t = states[i]->transitions_head; NULL != t; t = t->next)
{
- j = t->to_state->proof_id;
+ j = t->to_state->dfs_id;
if (NULL == R_last[i][j])
- GNUNET_asprintf (&R_last[i][j], "%c", t->label);
+ GNUNET_asprintf (&R_last[i][j], "%s", t->label);
else
{
temp = R_last[i][j];
- GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label);
+ GNUNET_asprintf (&R_last[i][j], "%s|%s", R_last[i][j], t->label);
GNUNET_free (temp);
}
}
GNUNET_free (temp);
}
- /* Compute regular expressions of length "k" between each pair of states per induction */
+ /* Compute regular expressions of length "k" between each pair of states per
+ * induction */
for (k = 0; k < n; k++)
{
for (i = 0; i < n; i++)
// assign proofs and hashes
for (i = 0; i < n; i++)
{
- if (NULL != R_last[a->start->proof_id][i])
+ if (NULL != R_last[a->start->dfs_id][i])
{
- states[i]->proof = GNUNET_strdup (R_last[a->start->proof_id][i]);
+ states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id][i]);
GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof),
&states[i]->hash);
}
}
- // complete regex for whole DFA: union of all pairs (start state/accepting state(s)).
+ // complete regex for whole DFA: union of all pairs (start state/accepting
+ // state(s)).
complete_regex = NULL;
for (i = 0; i < n; i++)
{
if (states[i]->accepting)
{
- if (NULL == complete_regex && 0 < strlen (R_last[a->start->proof_id][i]))
+ if (NULL == complete_regex && 0 < strlen (R_last[a->start->dfs_id][i]))
{
- GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->proof_id][i]);
+ GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->dfs_id][i]);
}
- else if (NULL != R_last[a->start->proof_id][i] &&
- 0 < strlen (R_last[a->start->proof_id][i]))
+ else if (NULL != R_last[a->start->dfs_id][i] &&
+ 0 < strlen (R_last[a->start->dfs_id][i]))
{
temp = complete_regex;
GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex,
- R_last[a->start->proof_id][i]);
+ R_last[a->start->dfs_id][i]);
GNUNET_free (temp);
}
}
s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State));
s->id = ctx->state_id++;
s->accepting = 0;
- s->marked = 0;
+ s->marked = GNUNET_NO;
s->name = NULL;
s->scc_id = 0;
s->index = -1;
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;
// Add a transition for each distinct label to NULL state
for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
{
- if (0 != ctran->label)
+ if (NULL != ctran->label)
state_add_transition (ctx, s, ctran->label, NULL);
}
/**
- * Move from the given state 's' to the next state on transition 'label'
+ * Move from the given state 's' to the next state on transition 'str'. Consumes
+ * as much of the given 'str' as possible (usefull for strided DFAs). On return
+ * 's' will point to the next state, and the length of the substring used for
+ * this transition will be returned. If no transition possible 0 is returned and
+ * 's' points to NULL.
*
- * @param s starting state
- * @param label edge label to follow
+ * @param s starting state, will point to the next state or NULL (if no
+ * transition possible)
+ * @param str edge label to follow (will match longest common prefix)
*
- * @return new state or NULL, if transition on label not possible
+ * @return length of the substring comsumed from 'str'
*/
-static struct GNUNET_REGEX_State *
-dfa_move (struct GNUNET_REGEX_State *s, const char label)
+static unsigned int
+dfa_move (struct GNUNET_REGEX_State **s, const char *str)
{
struct GNUNET_REGEX_Transition *t;
struct GNUNET_REGEX_State *new_s;
+ unsigned int len;
+ unsigned int max_len;
if (NULL == s)
- return NULL;
+ return 0;
new_s = NULL;
-
- for (t = s->transitions_head; NULL != t; t = t->next)
+ max_len = 0;
+ for (t = (*s)->transitions_head; NULL != t; t = t->next)
{
- if (label == t->label)
+ len = strlen (t->label);
+
+ if (0 == strncmp (t->label, str, len))
{
- new_s = t->to_state;
- break;
+ if (len >= max_len)
+ {
+ max_len = len;
+ new_s = t->to_state;
+ }
}
}
- return new_s;
+ *s = new_s;
+ return max_len;
}
+/**
+ * Set the given state 'marked' to GNUNET_YES. Used by the
+ * 'dfa_remove_unreachable_states' function to detect unreachable states in the
+ * automaton.
+ *
+ * @param cls closure, not used.
+ * @param count count, not used.
+ * @param s state where the marked attribute will be set to GNUNET_YES.
+ */
+void
+mark_states (void *cls, const unsigned int count, struct GNUNET_REGEX_State *s)
+{
+ s->marked = GNUNET_YES;
+}
/**
* Remove all unreachable states from DFA 'a'. Unreachable states are those
s->marked = GNUNET_NO;
// 2. traverse dfa from start state and mark all visited states
- GNUNET_REGEX_automaton_traverse (a, NULL, 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)
/**
* Remove all dead states from the DFA 'a'. Dead states are those states that do
- * not transition to any other state but themselfes.
+ * not transition to any other state but themselves.
*
* @param a DFA automaton
*/
dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx,
struct GNUNET_REGEX_Automaton *a)
{
- unsigned int i;
int table[a->state_count][a->state_count];
struct GNUNET_REGEX_State *s1;
struct GNUNET_REGEX_State *s2;
struct GNUNET_REGEX_State *s2_next;
int change;
unsigned int num_equal_edges;
+ unsigned int i;
for (i = 0, s1 = a->states_head; i < a->state_count && NULL != s1;
i++, s1 = s1->next)
{
for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
{
- if (t1->label == t2->label)
+ if (0 == strcmp (t1->label, t2->label))
{
num_equal_edges++;
if (0 != table[t1->to_state->marked][t2->to_state->marked] ||
0 != table[t2->to_state->marked][t1->to_state->marked])
{
- table[s1->marked][s2->marked] = t1->label != 0 ? t1->label : 1;
+ table[s1->marked][s2->marked] = 1;
change = 1;
}
}
}
+/**
+ * Context for adding strided transitions to a DFA.
+ */
+struct GNUNET_REGEX_Strided_Context
+{
+ /**
+ * Length of the strides.
+ */
+ const unsigned int stride;
+
+ /**
+ * Strided transitions DLL. New strided transitions will be stored in this DLL
+ * and afterwards added to the DFA.
+ */
+ struct GNUNET_REGEX_Transition *transitions_head;
+
+ /**
+ * Strided transitions DLL.
+ */
+ struct GNUNET_REGEX_Transition *transitions_tail;
+};
+
+
+/**
+ * Recursive helper function to add strides to a DFA.
+ *
+ * @param cls context, contains stride length and strided transitions DLL.
+ * @param depth current depth of the depth-first traversal of the graph.
+ * @param label current label, string that contains all labels on the path from
+ * 'start' to 's'.
+ * @param start start state for the depth-first traversal of the graph.
+ * @param s current state in the depth-first traversal
+ */
+void
+dfa_add_multi_strides_helper (void *cls, const unsigned int depth, char *label,
+ struct GNUNET_REGEX_State *start,
+ struct GNUNET_REGEX_State *s)
+{
+ struct GNUNET_REGEX_Strided_Context *ctx = cls;
+ struct GNUNET_REGEX_Transition *t;
+ char *new_label;
+
+ if (depth == ctx->stride)
+ {
+ t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition));
+ t->label = GNUNET_strdup (label);
+ t->to_state = s;
+ t->from_state = start;
+ GNUNET_CONTAINER_DLL_insert (ctx->transitions_head, ctx->transitions_tail,
+ t);
+ }
+ else
+ {
+ for (t = s->transitions_head; NULL != t; t = t->next)
+ {
+ /* Do not consider self-loops, because it end's up in too many
+ * transitions */
+ if (t->to_state == t->from_state)
+ continue;
+
+ if (NULL != label)
+ {
+ GNUNET_asprintf (&new_label, "%s%s", label, t->label);
+ }
+ else
+ new_label = GNUNET_strdup (t->label);
+
+ dfa_add_multi_strides_helper (cls, (depth + 1), new_label, start,
+ t->to_state);
+ }
+ }
+ GNUNET_free_non_null (label);
+}
+
+
+/**
+ * Function called for each state in the DFA. Starts a traversal of depth set in
+ * context starting from state 's'.
+ *
+ * @param cls context.
+ * @param count not used.
+ * @param s current state.
+ */
+void
+dfa_add_multi_strides (void *cls, const unsigned int count,
+ struct GNUNET_REGEX_State *s)
+{
+ dfa_add_multi_strides_helper (cls, 0, NULL, s, s);
+}
+
+
+/**
+ * Adds multi-strided transitions to the given 'dfa'.
+ *
+ * @param regex_ctx regex context needed to add transitions to the automaton.
+ * @param dfa DFA to which the multi strided transitions should be added.
+ * @param stride_len length of the strides.
+ */
+void
+GNUNET_REGEX_dfa_add_multi_strides (struct GNUNET_REGEX_Context *regex_ctx,
+ struct GNUNET_REGEX_Automaton *dfa,
+ const unsigned int stride_len)
+{
+ struct GNUNET_REGEX_Strided_Context ctx = { stride_len, NULL, NULL };
+ struct GNUNET_REGEX_Transition *t;
+ struct GNUNET_REGEX_Transition *t_next;
+
+ if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
+ return;
+
+ // Compute the new transitions of given stride_len
+ GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL,
+ &dfa_add_multi_strides, &ctx);
+
+ // Add all the new transitions to the automaton.
+ for (t = ctx.transitions_head; NULL != t; t = t_next)
+ {
+ t_next = t->next;
+ state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
+ GNUNET_CONTAINER_DLL_remove (ctx.transitions_head, ctx.transitions_tail, t);
+ GNUNET_free_non_null (t->label);
+ GNUNET_free (t);
+ }
+
+ // Mark this automaton as multistrided
+ dfa->is_multistrided = GNUNET_YES;
+}
+
+/**
+ * Recursive Helper function for DFA path compression. Does DFS on the DFA graph
+ * and adds new transitions to the given transitions DLL and marks states that
+ * should be removed by setting state->contained to GNUNET_YES.
+ *
+ * @param dfa DFA for which the paths should be compressed.
+ * @param start starting state for linear path search.
+ * @param cur current state in the recursive DFS.
+ * @param label current label (string of traversed labels).
+ * @param max_len maximal path compression length.
+ * @param transitions_head transitions DLL.
+ * @param transitions_tail transitions DLL.
+ */
+void
+dfa_compress_paths_helper (struct GNUNET_REGEX_Automaton *dfa,
+ struct GNUNET_REGEX_State *start,
+ struct GNUNET_REGEX_State *cur, char *label,
+ unsigned int max_len,
+ struct GNUNET_REGEX_Transition **transitions_head,
+ struct GNUNET_REGEX_Transition **transitions_tail)
+{
+ struct GNUNET_REGEX_Transition *t;
+ char *new_label;
+
+
+ if (NULL != label &&
+ ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting
+// || cur->transition_count > 1
+ || GNUNET_YES == cur->marked) || (start != dfa->start && max_len > 0 &&
+ max_len == strlen (label)) ||
+ (start == dfa->start && GNUNET_REGEX_INITIAL_BITS == strlen (label))))
+ {
+ t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition));
+ t->label = GNUNET_strdup (label);
+ t->to_state = cur;
+ t->from_state = start;
+ GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t);
+
+ if (GNUNET_NO == cur->marked)
+ {
+ dfa_compress_paths_helper (dfa, cur, cur, NULL, max_len, transitions_head,
+ transitions_tail);
+ }
+ return;
+ }
+ else if (cur != start)
+ cur->contained = GNUNET_YES;
+
+ if (GNUNET_YES == cur->marked && cur != start)
+ return;
+
+ cur->marked = GNUNET_YES;
+
+
+ for (t = cur->transitions_head; NULL != t; t = t->next)
+ {
+ if (NULL != label)
+ GNUNET_asprintf (&new_label, "%s%s", label, t->label);
+ else
+ new_label = GNUNET_strdup (t->label);
+
+ if (t->to_state != cur)
+ {
+ dfa_compress_paths_helper (dfa, start, t->to_state, new_label, max_len,
+ transitions_head, transitions_tail);
+ }
+ GNUNET_free (new_label);
+ }
+}
+
+/**
+ * Compress paths in the given 'dfa'. Linear paths like 0->1->2->3 will be
+ * compressed to 0->3 by combining transitions.
+ *
+ * @param regex_ctx context for adding new transitions.
+ * @param dfa DFA representation, will directly modify the given DFA.
+ * @param max_len maximal length of the compressed paths.
+ */
+static void
+dfa_compress_paths (struct GNUNET_REGEX_Context *regex_ctx,
+ struct GNUNET_REGEX_Automaton *dfa, unsigned int max_len)
+{
+ struct GNUNET_REGEX_State *s;
+ struct GNUNET_REGEX_State *s_next;
+ struct GNUNET_REGEX_Transition *t;
+ struct GNUNET_REGEX_Transition *t_next;
+ struct GNUNET_REGEX_Transition *transitions_head = NULL;
+ struct GNUNET_REGEX_Transition *transitions_tail = NULL;
+
+ if (NULL == dfa)
+ return;
+
+ // Count the incoming transitions on each state.
+ for (s = dfa->states_head; NULL != s; s = s->next)
+ {
+ for (t = s->transitions_head; NULL != t; t = t->next)
+ {
+ if (NULL != t->to_state)
+ t->to_state->incoming_transition_count++;
+ }
+ }
+
+ // Unmark all states.
+ for (s = dfa->states_head; NULL != s; s = s->next)
+ {
+ s->marked = GNUNET_NO;
+ s->contained = GNUNET_NO;
+ }
+
+ // Add strides and mark states that can be deleted.
+ dfa_compress_paths_helper (dfa, dfa->start, dfa->start, NULL, max_len,
+ &transitions_head, &transitions_tail);
+
+ // Add all the new transitions to the automaton.
+ for (t = transitions_head; NULL != t; t = t_next)
+ {
+ t_next = t->next;
+ state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
+ GNUNET_CONTAINER_DLL_remove (transitions_head, transitions_tail, t);
+ GNUNET_free_non_null (t->label);
+ GNUNET_free (t);
+ }
+
+ // Remove marked states (including their incoming and outgoing transitions).
+ for (s = dfa->states_head; NULL != s; s = s_next)
+ {
+ s_next = s->next;
+ if (GNUNET_YES == s->contained)
+ automaton_remove_state (dfa, s);
+ }
+}
+
+
/**
* Creates a new NFA fragment. Needs to be cleared using
* automaton_fragment_clear.
n->type = NFA;
n->start = NULL;
n->end = NULL;
+ n->state_count = 0;
- if (NULL == start && NULL == end)
+ 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;
s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State));
s->id = ctx->state_id++;
s->accepting = accepting;
- s->marked = 0;
+ s->marked = GNUNET_NO;
s->contained = 0;
s->index = -1;
s->lowlink = -1;
* @param nfa the NFA containing 's'
* @param s starting point state
* @param label transitioning label on which to base the closure on,
- * pass 0 for epsilon transition
+ * pass NULL for epsilon transition
*
- * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
*/
static struct GNUNET_REGEX_StateSet *
nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa,
- struct GNUNET_REGEX_State *s, const char label)
+ struct GNUNET_REGEX_State *s, const char *label)
{
struct GNUNET_REGEX_StateSet *cls;
struct GNUNET_REGEX_StateSet *cls_check;
clsstate->contained = 0;
// Add start state to closure only for epsilon closure
- if (0 == label)
+ if (NULL == label)
GNUNET_array_append (cls->states, cls->len, s);
GNUNET_array_append (cls_check->states, cls_check->len, s);
for (ctran = currentstate->transitions_head; NULL != ctran;
ctran = ctran->next)
{
- if (NULL != ctran->to_state && label == ctran->label)
+ if (NULL != ctran->to_state && 0 == nullstrcmp (label, ctran->label))
{
clsstate = ctran->to_state;
* @param nfa the NFA containing 's'
* @param states list of states on which to base the closure on
* @param label transitioning label for which to base the closure on,
- * pass 0 for epsilon transition
+ * pass NULL for epsilon transition
*
- * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
*/
static struct GNUNET_REGEX_StateSet *
nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa,
- struct GNUNET_REGEX_StateSet *states, const char label)
+ struct GNUNET_REGEX_StateSet *states, const char *label)
{
struct GNUNET_REGEX_State *s;
struct GNUNET_REGEX_StateSet *sset;
{
struct GNUNET_REGEX_Automaton *a;
struct GNUNET_REGEX_Automaton *b;
- struct GNUNET_REGEX_Automaton *new;
+ struct GNUNET_REGEX_Automaton *new_nfa;
b = ctx->stack_tail;
+ GNUNET_assert (NULL != b);
GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
a = ctx->stack_tail;
+ GNUNET_assert (NULL != a);
GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
- state_add_transition (ctx, a->end, 0, b->start);
+ state_add_transition (ctx, a->end, NULL, b->start);
a->end->accepting = 0;
b->end->accepting = 1;
- new = nfa_fragment_create (NULL, NULL);
- nfa_add_states (new, a->states_head, a->states_tail);
- nfa_add_states (new, b->states_head, b->states_tail);
- new->start = a->start;
- new->end = b->end;
+ new_nfa = nfa_fragment_create (NULL, NULL);
+ nfa_add_states (new_nfa, a->states_head, a->states_tail);
+ 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);
- GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
+ GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}
nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
{
struct GNUNET_REGEX_Automaton *a;
- struct GNUNET_REGEX_Automaton *new;
+ struct GNUNET_REGEX_Automaton *new_nfa;
struct GNUNET_REGEX_State *start;
struct GNUNET_REGEX_State *end;
a = ctx->stack_tail;
- GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
if (NULL == a)
{
return;
}
+ GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
+
start = nfa_state_create (ctx, 0);
end = nfa_state_create (ctx, 1);
- state_add_transition (ctx, start, 0, a->start);
- state_add_transition (ctx, start, 0, end);
- state_add_transition (ctx, a->end, 0, a->start);
- state_add_transition (ctx, a->end, 0, end);
+ state_add_transition (ctx, start, NULL, a->start);
+ state_add_transition (ctx, start, NULL, end);
+ state_add_transition (ctx, a->end, NULL, a->start);
+ state_add_transition (ctx, a->end, NULL, end);
a->end->accepting = 0;
end->accepting = 1;
- new = nfa_fragment_create (start, end);
- nfa_add_states (new, a->states_head, a->states_tail);
+ new_nfa = nfa_fragment_create (start, end);
+ nfa_add_states (new_nfa, a->states_head, a->states_tail);
automaton_fragment_clear (a);
- GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
+ GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}
struct GNUNET_REGEX_Automaton *a;
a = ctx->stack_tail;
+
+ if (NULL == a)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "nfa_add_plus_op failed, because there was no element on the stack");
+ return;
+ }
+
GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
- state_add_transition (ctx, a->end, 0, a->start);
+ state_add_transition (ctx, a->end, NULL, a->start);
GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
}
nfa_add_question_op (struct GNUNET_REGEX_Context *ctx)
{
struct GNUNET_REGEX_Automaton *a;
- struct GNUNET_REGEX_Automaton *new;
+ struct GNUNET_REGEX_Automaton *new_nfa;
struct GNUNET_REGEX_State *start;
struct GNUNET_REGEX_State *end;
a = ctx->stack_tail;
- GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
if (NULL == a)
{
return;
}
+ GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
+
start = nfa_state_create (ctx, 0);
end = nfa_state_create (ctx, 1);
- state_add_transition (ctx, start, 0, a->start);
- state_add_transition (ctx, start, 0, end);
- state_add_transition (ctx, a->end, 0, end);
+ state_add_transition (ctx, start, NULL, a->start);
+ state_add_transition (ctx, start, NULL, end);
+ state_add_transition (ctx, a->end, NULL, end);
a->end->accepting = 0;
- new = nfa_fragment_create (start, end);
- nfa_add_states (new, a->states_head, a->states_tail);
+ new_nfa = nfa_fragment_create (start, end);
+ nfa_add_states (new_nfa, a->states_head, a->states_tail);
automaton_fragment_clear (a);
- GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
+ GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}
{
struct GNUNET_REGEX_Automaton *a;
struct GNUNET_REGEX_Automaton *b;
- struct GNUNET_REGEX_Automaton *new;
+ struct GNUNET_REGEX_Automaton *new_nfa;
struct GNUNET_REGEX_State *start;
struct GNUNET_REGEX_State *end;
b = ctx->stack_tail;
+ GNUNET_assert (NULL != b);
GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
a = ctx->stack_tail;
+ GNUNET_assert (NULL != a);
GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
start = nfa_state_create (ctx, 0);
end = nfa_state_create (ctx, 1);
- state_add_transition (ctx, start, 0, a->start);
- state_add_transition (ctx, start, 0, b->start);
+ state_add_transition (ctx, start, NULL, a->start);
+ state_add_transition (ctx, start, NULL, b->start);
- state_add_transition (ctx, a->end, 0, end);
- state_add_transition (ctx, b->end, 0, end);
+ state_add_transition (ctx, a->end, NULL, end);
+ state_add_transition (ctx, b->end, NULL, end);
a->end->accepting = 0;
b->end->accepting = 0;
end->accepting = 1;
- new = nfa_fragment_create (start, end);
- nfa_add_states (new, a->states_head, a->states_tail);
- nfa_add_states (new, b->states_head, b->states_tail);
+ new_nfa = nfa_fragment_create (start, end);
+ nfa_add_states (new_nfa, a->states_head, a->states_tail);
+ nfa_add_states (new_nfa, b->states_head, b->states_tail);
automaton_fragment_clear (a);
automaton_fragment_clear (b);
- GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new);
+ GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}
* Adds a new nfa fragment to the stack
*
* @param ctx context
- * @param lit label for nfa transition
+ * @param label label for nfa transition
*/
static void
-nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit)
+nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char *label)
{
struct GNUNET_REGEX_Automaton *n;
struct GNUNET_REGEX_State *start;
start = nfa_state_create (ctx, 0);
end = nfa_state_create (ctx, 1);
- state_add_transition (ctx, start, lit, end);
+ state_add_transition (ctx, start, label, end);
n = nfa_fragment_create (start, end);
GNUNET_assert (NULL != n);
GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
struct GNUNET_REGEX_Context ctx;
struct GNUNET_REGEX_Automaton *nfa;
const char *regexp;
+ char curlabel[2];
char *error_msg;
unsigned int count;
unsigned int altcount;
int atomcount;
} *p;
+ if (NULL == regex || 0 == strlen (regex) || 0 == len)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Could not parse regex. Empty regex string provided.\n");
+
+ return NULL;
+ }
+
GNUNET_REGEX_context_init (&ctx);
regexp = regex;
+ curlabel[1] = '\0';
p = NULL;
error_msg = NULL;
altcount = 0;
}
nfa_add_question_op (&ctx);
break;
- case 92: /* escape: \ */
- regexp++;
- count++;
default:
if (atomcount > 1)
{
--atomcount;
nfa_add_concatenation (&ctx);
}
- nfa_add_label (&ctx, *regexp);
+ curlabel[0] = *regexp;
+ nfa_add_label (&ctx, curlabel);
atomcount++;
break;
}
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, NULL, NULL, &number_states, NULL);
+
+ /* No multistriding added so far */
+ nfa->is_multistrided = GNUNET_NO;
+
return nfa;
error:
for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
{
- if (0 == ctran->label || NULL != ctran->to_state)
+ if (NULL == ctran->label || NULL != ctran->to_state)
continue;
tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label);
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 = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton));
dfa->type = DFA;
+ dfa->state_count = 0;
+ 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);
// Create proofs for all states
automaton_create_proofs (dfa);
+ // Compress DFA paths
+ dfa_compress_paths (&ctx, dfa, 8);
+
+ // Add strides to DFA
+ //GNUNET_REGEX_dfa_add_multi_strides (&ctx, dfa, 2);
+
return dfa;
}
GNUNET_free_non_null (a->regex);
GNUNET_free_non_null (a->canonical_regex);
- for (s = a->states_head; NULL != s;)
+ for (s = a->states_head; NULL != s; s = next_state)
{
next_state = s->next;
+ GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
automaton_destroy_state (s);
- s = next_state;
}
GNUNET_free (a);
{
const char *strp;
struct GNUNET_REGEX_State *s;
+ unsigned int step_len;
if (DFA != a->type)
{
if ((NULL == string || 0 == strlen (string)) && s->accepting)
return 0;
- for (strp = string; NULL != strp && *strp; strp++)
+ for (strp = string; NULL != strp && *strp; strp += step_len)
{
- s = dfa_move (s, *strp);
+ step_len = dfa_move (&s, strp);
+
if (NULL == s)
break;
}
evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
{
const char *strp;
+ char str[2];
struct GNUNET_REGEX_State *s;
struct GNUNET_REGEX_StateSet *sset;
struct GNUNET_REGEX_StateSet *new_sset;
return 0;
result = 1;
- strp = string;
sset = nfa_closure_create (a, a->start, 0);
+ str[1] = '\0';
for (strp = string; NULL != strp && *strp; strp++)
{
- new_sset = nfa_closure_set_create (a, sset, *strp);
+ str[0] = *strp;
+ new_sset = nfa_closure_set_create (a, sset, str);
state_set_clear (sset);
sset = nfa_closure_set_create (a, new_sset, 0);
state_set_clear (new_sset);
}
+/**
+ * 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;
+
+ t_count = 0;
+ for (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'.
{
unsigned int size;
- size = string_len < INITIAL_BITS ? string_len : INITIAL_BITS;
+ size =
+ string_len <
+ GNUNET_REGEX_INITIAL_BITS ? string_len : GNUNET_REGEX_INITIAL_BITS;
if (NULL == input_string)
{
GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key)
{
struct GNUNET_HashCode key_check;
+
+ if (NULL == proof || NULL == key)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
+ return GNUNET_NO;
+ }
+
GNUNET_CRYPTO_hash (proof, strlen (proof), &key_check);
- return (0 == GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
+ return (0 ==
+ GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
}
/**
- * Iterate over all edges helper function starting from state 's', calling
- * iterator on for each edge.
+ * Recursive function that calls the iterator for each synthetic start state.
*
- * @param s state.
+ * @param min_len minimum length of the path in the graph.
+ * @param max_len maximum length of the path in the graph.
+ * @param consumed_string string consumed by traversing the graph till this state.
+ * @param state current state of the automaton.
* @param iterator iterator function called for each edge.
- * @param iterator_cls closure.
+ * @param iterator_cls closure for the iterator function.
*/
static void
-iterate_edge (struct GNUNET_REGEX_State *s, GNUNET_REGEX_KeyIterator iterator,
- void *iterator_cls)
+iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
+ char *consumed_string, struct GNUNET_REGEX_State *state,
+ GNUNET_REGEX_KeyIterator iterator, void *iterator_cls)
{
+ unsigned int i;
+ char *temp;
struct GNUNET_REGEX_Transition *t;
- struct GNUNET_REGEX_Edge edges[s->transition_count];
- unsigned int num_edges;
+ unsigned int num_edges = state->transition_count;
+ struct GNUNET_REGEX_Edge edges[num_edges];
+ struct GNUNET_REGEX_Edge edge[1];
+ struct GNUNET_HashCode hash;
+ struct GNUNET_HashCode hash_new;
+
+ unsigned int cur_len;
- if (GNUNET_YES != s->marked)
+ if (NULL != consumed_string)
+ cur_len = strlen (consumed_string);
+ else
+ cur_len = 0;
+
+ if ((cur_len >= min_len || GNUNET_YES == state->accepting) && cur_len > 0 &&
+ NULL != consumed_string)
{
- s->marked = GNUNET_YES;
+ if (cur_len <= max_len)
+ {
+ if (state->proof != NULL && 0 != strcmp (consumed_string, state->proof))
+ {
+ for (i = 0, t = state->transitions_head; NULL != t && i < num_edges;
+ t = t->next, i++)
+ {
+ edges[i].label = t->label;
+ edges[i].destination = t->to_state->hash;
+ }
+ GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash);
+ iterator (iterator_cls, &hash, consumed_string, state->accepting,
+ num_edges, edges);
+ }
- num_edges = state_get_edges (s, edges);
+ if (GNUNET_YES == state->accepting && cur_len > 1 &&
+ state->transition_count < 1 && cur_len < max_len)
+ {
+ // Special case for regex consisting of just a string that is shorter than
+ // max_len
+ edge[0].label = &consumed_string[cur_len - 1];
+ edge[0].destination = state->hash;
+ temp = GNUNET_strdup (consumed_string);
+ temp[cur_len - 1] = '\0';
+ GNUNET_CRYPTO_hash (temp, cur_len - 1, &hash_new);
+ iterator (iterator_cls, &hash_new, temp, GNUNET_NO, 1, edge);
+ GNUNET_free (temp);
+ }
+ }
+ else if (max_len < cur_len)
+ {
+ // Case where the concatenated labels are longer than max_len, then split.
+ edge[0].label = &consumed_string[max_len];
+ edge[0].destination = state->hash;
+ temp = GNUNET_strdup (consumed_string);
+ temp[max_len] = '\0';
+ GNUNET_CRYPTO_hash (temp, max_len, &hash);
+ iterator (iterator_cls, &hash, temp, GNUNET_NO, 1, edge);
+ GNUNET_free (temp);
+ }
+ }
- iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges, edges);
+ if (cur_len < max_len)
+ {
+ for (t = state->transitions_head; NULL != t; t = t->next)
+ {
+ if (NULL != consumed_string)
+ GNUNET_asprintf (&temp, "%s%s", consumed_string, t->label);
+ else
+ GNUNET_asprintf (&temp, "%s", t->label);
- for (t = s->transitions_head; NULL != t; t = t->next)
- iterate_edge (t->to_state, iterator, iterator_cls);
+ iterate_initial_edge (min_len, max_len, temp, t->to_state, iterator,
+ iterator_cls);
+ GNUNET_free (temp);
+ }
}
}
struct GNUNET_REGEX_State *s;
for (s = a->states_head; NULL != s; s = s->next)
+ {
+ struct GNUNET_REGEX_Edge edges[s->transition_count];
+ unsigned int num_edges;
+
+ num_edges = state_get_edges (s, edges);
+
+ if ((NULL != s->proof && 0 < strlen (s->proof)) || s->accepting)
+ iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges,
+ edges);
+
s->marked = GNUNET_NO;
+ }
+
+ iterate_initial_edge (GNUNET_REGEX_INITIAL_BITS, GNUNET_REGEX_INITIAL_BITS,
+ NULL, a->start, iterator, iterator_cls);
+}
+
+
+/**
+ * Create a string with binary IP notation for the given 'addr' in 'str'.
+ *
+ * @param af address family of the given 'addr'.
+ * @param addr address that should be converted to a string.
+ * struct in_addr * for IPv4 and struct in6_addr * for IPv6.
+ * @param str string that will contain binary notation of 'addr'. Expected
+ * to be at least 33 bytes long for IPv4 and 129 bytes long for IPv6.
+ */
+static void
+iptobinstr (const int af, const void *addr, char *str)
+{
+ int i;
+
+ switch (af)
+ {
+ case AF_INET:
+ {
+ uint32_t b = htonl (((struct in_addr *) addr)->s_addr);
+
+ str[32] = '\0';
+ str += 31;
+ for (i = 31; i >= 0; i--)
+ {
+ *str = (b & 1) + '0';
+ str--;
+ b >>= 1;
+ }
+ break;
+ }
+ case AF_INET6:
+ {
+ struct in6_addr b = *(const struct in6_addr *) addr;
+
+ str[128] = '\0';
+ str += 127;
+ for (i = 127; i >= 0; i--)
+ {
+ *str = (b.s6_addr[i / 8] & 1) + '0';
+ str--;
+ b.s6_addr[i / 8] >>= 1;
+ }
+ break;
+ }
+ }
+}
+
- iterate_edge (a->start, iterator, iterator_cls);
+/**
+ * Get the ipv4 network prefix from the given 'netmask'.
+ *
+ * @param netmask netmask for which to get the prefix len.
+ *
+ * @return length of ipv4 prefix for 'netmask'.
+ */
+static unsigned int
+ipv4netmasktoprefixlen (const char *netmask)
+{
+ struct in_addr a;
+ unsigned int len;
+ uint32_t t;
+
+ if (1 != inet_pton (AF_INET, netmask, &a))
+ return 0;
+ len = 32;
+ for (t = htonl (~a.s_addr); 0 != t; t >>= 1)
+ len--;
+ return len;
+}
+
+
+/**
+ * Create a regex in 'rxstr' from the given 'ip' and 'netmask'.
+ *
+ * @param ip IPv4 representation.
+ * @param netmask netmask for the ip.
+ * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV4_REGEXLEN
+ * bytes long.
+ */
+void
+GNUNET_REGEX_ipv4toregex (const struct in_addr *ip, const char *netmask,
+ char *rxstr)
+{
+ unsigned int pfxlen;
+
+ pfxlen = ipv4netmasktoprefixlen (netmask);
+ iptobinstr (AF_INET, ip, rxstr);
+ rxstr[pfxlen] = '\0';
+ if (pfxlen < 32)
+ strcat (rxstr, "(0|1)+");
+}
+
+
+/**
+ * Create a regex in 'rxstr' from the given 'ipv6' and 'prefixlen'.
+ *
+ * @param ipv6 IPv6 representation.
+ * @param prefixlen length of the ipv6 prefix.
+ * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV6_REGEXLEN
+ * bytes long.
+ */
+void
+GNUNET_REGEX_ipv6toregex (const struct in6_addr *ipv6, unsigned int prefixlen,
+ char *rxstr)
+{
+ iptobinstr (AF_INET6, ipv6, rxstr);
+ rxstr[prefixlen] = '\0';
+ if (prefixlen < 128)
+ strcat (rxstr, "(0|1)+");
}