/**
* Set of states using MDLL API.
*/
-struct REGEX_ITERNAL_StateSet_MDLL
+struct REGEX_INTERNAL_StateSet_MDLL
{
/**
* MDLL of states.
*/
- struct REGEX_ITERNAL_State *head;
+ struct REGEX_INTERNAL_State *head;
/**
* MDLL of states.
*/
- struct REGEX_ITERNAL_State *tail;
+ struct REGEX_INTERNAL_State *tail;
/**
* Length of the MDLL.
* @param state state to be appended
*/
static void
-state_set_append (struct REGEX_ITERNAL_StateSet *set,
- struct REGEX_ITERNAL_State *state)
+state_set_append (struct REGEX_INTERNAL_StateSet *set,
+ struct REGEX_INTERNAL_State *state)
{
if (set->off == set->size)
GNUNET_array_grow (set->states, set->size, set->size * 2 + 4);
* @param to_state state to where the transition should point to
*/
static void
-state_add_transition (struct REGEX_ITERNAL_Context *ctx,
- struct REGEX_ITERNAL_State *from_state, const char *label,
- struct REGEX_ITERNAL_State *to_state)
+state_add_transition (struct REGEX_INTERNAL_Context *ctx,
+ struct REGEX_INTERNAL_State *from_state, const char *label,
+ struct REGEX_INTERNAL_State *to_state)
{
- struct REGEX_ITERNAL_Transition *t;
- struct REGEX_ITERNAL_Transition *oth;
+ struct REGEX_INTERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *oth;
if (NULL == from_state)
{
break;
}
- t = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Transition));
+ t = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Transition));
if (NULL != ctx)
t->id = ctx->transition_id++;
if (NULL != label)
* @param transition transition that should be removed from state 'state'.
*/
static void
-state_remove_transition (struct REGEX_ITERNAL_State *state,
- struct REGEX_ITERNAL_Transition *transition)
+state_remove_transition (struct REGEX_INTERNAL_State *state,
+ struct REGEX_INTERNAL_Transition *transition)
{
if (NULL == state || NULL == transition)
return;
static int
state_compare (const void *a, const void *b)
{
- struct REGEX_ITERNAL_State **s1 = (struct REGEX_ITERNAL_State **) a;
- struct REGEX_ITERNAL_State **s2 = (struct REGEX_ITERNAL_State **) b;
+ struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **) a;
+ struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **) b;
return (*s1)->id - (*s2)->id;
}
* @return number of edges.
*/
static unsigned int
-state_get_edges (struct REGEX_ITERNAL_State *s, struct REGEX_ITERNAL_Edge *edges)
+state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges)
{
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t;
unsigned int count;
if (NULL == s)
* @return 0 if the sets are equal, otherwise non-zero
*/
static int
-state_set_compare (struct REGEX_ITERNAL_StateSet *sset1,
- struct REGEX_ITERNAL_StateSet *sset2)
+state_set_compare (struct REGEX_INTERNAL_StateSet *sset1,
+ struct REGEX_INTERNAL_StateSet *sset2)
{
int result;
unsigned int i;
* @param set set to be cleared
*/
static void
-state_set_clear (struct REGEX_ITERNAL_StateSet *set)
+state_set_clear (struct REGEX_INTERNAL_StateSet *set)
{
GNUNET_array_grow (set->states, set->size, 0);
set->off = 0;
* @param a automaton to be cleared
*/
static void
-automaton_fragment_clear (struct REGEX_ITERNAL_Automaton *a)
+automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a)
{
if (NULL == a)
return;
* @param s state that should be destroyed
*/
static void
-automaton_destroy_state (struct REGEX_ITERNAL_State *s)
+automaton_destroy_state (struct REGEX_INTERNAL_State *s)
{
- struct REGEX_ITERNAL_Transition *t;
- struct REGEX_ITERNAL_Transition *next_t;
+ struct REGEX_INTERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *next_t;
if (NULL == s)
return;
* @param s state to remove
*/
static void
-automaton_remove_state (struct REGEX_ITERNAL_Automaton *a,
- struct REGEX_ITERNAL_State *s)
+automaton_remove_state (struct REGEX_INTERNAL_Automaton *a,
+ struct REGEX_INTERNAL_State *s)
{
- struct REGEX_ITERNAL_State *s_check;
- struct REGEX_ITERNAL_Transition *t_check;
- struct REGEX_ITERNAL_Transition *t_check_next;
+ struct REGEX_INTERNAL_State *s_check;
+ struct REGEX_INTERNAL_Transition *t_check;
+ struct REGEX_INTERNAL_Transition *t_check_next;
if (NULL == a || NULL == s)
return;
* @param s2 second state, will be destroyed
*/
static void
-automaton_merge_states (struct REGEX_ITERNAL_Context *ctx,
- struct REGEX_ITERNAL_Automaton *a,
- struct REGEX_ITERNAL_State *s1,
- struct REGEX_ITERNAL_State *s2)
-{
- struct REGEX_ITERNAL_State *s_check;
- struct REGEX_ITERNAL_Transition *t_check;
- struct REGEX_ITERNAL_Transition *t;
- struct REGEX_ITERNAL_Transition *t_next;
+automaton_merge_states (struct REGEX_INTERNAL_Context *ctx,
+ struct REGEX_INTERNAL_Automaton *a,
+ struct REGEX_INTERNAL_State *s1,
+ struct REGEX_INTERNAL_State *s2)
+{
+ struct REGEX_INTERNAL_State *s_check;
+ struct REGEX_INTERNAL_Transition *t_check;
+ struct REGEX_INTERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t_next;
int is_dup;
if (s1 == s2)
* @param s state that should be added
*/
static void
-automaton_add_state (struct REGEX_ITERNAL_Automaton *a,
- struct REGEX_ITERNAL_State *s)
+automaton_add_state (struct REGEX_INTERNAL_Automaton *a,
+ struct REGEX_INTERNAL_State *s)
{
GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
a->state_count++;
* @param action_cls closure for action.
*/
static void
-automaton_state_traverse (struct REGEX_ITERNAL_State *s, int *marks,
+automaton_state_traverse (struct REGEX_INTERNAL_State *s, int *marks,
unsigned int *count,
- REGEX_ITERNAL_traverse_check check, void *check_cls,
- REGEX_ITERNAL_traverse_action action, void *action_cls)
+ REGEX_INTERNAL_traverse_check check, void *check_cls,
+ REGEX_INTERNAL_traverse_action action, void *action_cls)
{
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t;
if (GNUNET_YES == marks[s->traversal_id])
return;
* @param action_cls closure for action
*/
void
-REGEX_ITERNAL_automaton_traverse (const struct REGEX_ITERNAL_Automaton *a,
- struct REGEX_ITERNAL_State *start,
- REGEX_ITERNAL_traverse_check check,
+REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a,
+ struct REGEX_INTERNAL_State *start,
+ REGEX_INTERNAL_traverse_check check,
void *check_cls,
- REGEX_ITERNAL_traverse_action action,
+ REGEX_INTERNAL_traverse_action action,
void *action_cls)
{
unsigned int count;
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
if (NULL == a || 0 == a->state_count)
return;
* Allocated buffer.
*/
char *abuf;
-
+
/**
* Length of the string in the buffer.
*/
* change). This is used in an optimization that improves
* performance by about 1% --- if we use int16_t here. With just
* "int" for both flags, performance drops (on my system) significantly,
- * most likely due to increased cache misses.
+ * most likely due to increased cache misses.
*/
int16_t synced;
-
+
};
return -1;
return memcmp (s1->sbuf, s2->sbuf, s1->slen);
}
-
+
/**
- * Compare two strings for equality.
+ * Compare two strings for equality.
*
* @param s1 first string for comparison.
* @param s2 second string for comparison.
return -1;
return memcmp (s1->sbuf, s2->sbuf, s1->slen);
}
-
+
/**
* Reallocate the buffer of 'ret' to fit 'nlen' characters;
ret->sbuf = ret->abuf;
GNUNET_free_non_null (old);
}
-
+
/**
* Append a string.
sarg->slen);
ret->slen += sarg->slen;
}
-
+
/**
* Append a C string.
cstr_len);
ret->slen += cstr_len;
}
-
+
/**
* Wrap a string buffer, that is, set ret to the format string
static void
sb_strdup (struct StringBuffer *out,
const struct StringBuffer *in)
-
+
{
out->null_flag = in->null_flag;
if (GNUNET_YES == out->null_flag)
}
/* while '(' before ')', count opening parens */
while ( (NULL != (op = memchr (pos, '(', end - pos))) &&
- (op < cl) )
+ (op < cl) )
{
cnt++;
pos = op + 1;
if (0)
return;
sbuf = str->sbuf;
- if ( (GNUNET_YES == str->null_flag) ||
+ if ( (GNUNET_YES == str->null_flag) ||
(1 >= (slen = str->slen)) ||
('(' != str->sbuf[0]) ||
(')' != str->sbuf[slen - 1]) )
end = &sbuf[slen - 1];
op = memchr (pos, '(', end - pos);
cp = memchr (pos, ')', end - pos);
- while (NULL != cp)
+ while (NULL != cp)
{
while ( (NULL != op) &&
(op < cp) )
return;
}
str->sbuf++;
- str->slen -= 2;
+ str->slen -= 2;
}
static int
has_epsilon (const struct StringBuffer *str)
{
- return
- (GNUNET_YES != str->null_flag) &&
+ return
+ (GNUNET_YES != str->null_flag) &&
(0 < str->slen) &&
- ('(' == str->sbuf[0]) &&
+ ('(' == str->sbuf[0]) &&
('|' == str->sbuf[1]) &&
(')' == str->sbuf[str->slen - 1]);
}
{
ret->null_flag = GNUNET_YES;
return;
- }
- if ( (str->slen > 1) &&
+ }
+ if ( (str->slen > 1) &&
('(' == str->sbuf[0]) &&
('|' == str->sbuf[1]) &&
(')' == str->sbuf[str->slen - 1]) )
* @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
*/
static int
-sb_strncmp (const struct StringBuffer *str1,
+sb_strncmp (const struct StringBuffer *str1,
const struct StringBuffer *str2, size_t n)
{
size_t max;
-
+
if ( (str1->slen != str2->slen) &&
( (str1->slen < n) ||
(str2->slen < n) ) )
* @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
*/
static int
-sb_strncmp_cstr (const struct StringBuffer *str1,
+sb_strncmp_cstr (const struct StringBuffer *str1,
const char *str2, size_t n)
{
- if (str1->slen < n)
+ if (str1->slen < n)
return -1;
return memcmp (str1->sbuf, str2, n);
}
/**
- * Initialize string buffer for storing strings of up to n
+ * Initialize string buffer for storing strings of up to n
* characters.
*
* @param sb buffer to initialize
* @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
*/
static int
-sb_strkcmp (const struct StringBuffer *str1,
+sb_strkcmp (const struct StringBuffer *str1,
const struct StringBuffer *str2, size_t k)
{
if ( (GNUNET_YES == str1->null_flag) ||
/**
- * Helper function used as 'action' in 'REGEX_ITERNAL_automaton_traverse'
+ * Helper function used as 'action' in 'REGEX_INTERNAL_automaton_traverse'
* function to create the depth-first numbering of the states.
*
* @param cls states array.
*/
static void
number_states (void *cls, const unsigned int count,
- struct REGEX_ITERNAL_State *s)
+ struct REGEX_INTERNAL_State *s)
{
- struct REGEX_ITERNAL_State **states = cls;
+ struct REGEX_INTERNAL_State **states = cls;
s->dfs_id = count;
if (NULL != states)
* @param R_cur_r optimization -- kept between iterations to avoid realloc
*/
static void
-automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
+automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
const struct StringBuffer *R_last_ik,
const struct StringBuffer *R_last_kk,
const struct StringBuffer *R_last_kj,
* R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
*/
- if ( (GNUNET_YES == R_last_ij->null_flag) &&
- ( (GNUNET_YES == R_last_ik->null_flag) ||
+ if ( (GNUNET_YES == R_last_ij->null_flag) &&
+ ( (GNUNET_YES == R_last_ik->null_flag) ||
(GNUNET_YES == R_last_kj->null_flag)))
{
/* R^{(k)}_{ij} = N | N */
return;
}
- if ( (GNUNET_YES == R_last_ik->null_flag) ||
+ if ( (GNUNET_YES == R_last_ik->null_flag) ||
(GNUNET_YES == R_last_kj->null_flag) )
{
/* R^{(k)}_{ij} = R^{(k-1)}_{ij} | N */
if (GNUNET_YES == R_last_ij->synced)
{
- R_cur_ij->synced = GNUNET_YES;
+ R_cur_ij->synced = GNUNET_YES;
R_cur_ij->null_flag = GNUNET_NO;
return;
}
/* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
* $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} */
- R_cur_r->null_flag = GNUNET_YES;
- R_cur_r->slen = 0;
- R_cur_l->null_flag = GNUNET_YES;
- R_cur_l->slen = 0;
+ R_cur_r->null_flag = GNUNET_YES;
+ R_cur_r->slen = 0;
+ R_cur_l->null_flag = GNUNET_YES;
+ R_cur_l->slen = 0;
/* cache results from strcmp, we might need these many times */
ij_kj_cmp = sb_nullstrcmp (R_last_ij, R_last_kj);
remove_epsilon (R_last_ij, &R_temp_ij);
remove_parentheses (&R_temp_ij);
- if ( (0 == sb_strcmp (&R_temp_ij, &R_temp_ik)) &&
- (0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
+ if ( (0 == sb_strcmp (&R_temp_ij, &R_temp_ik)) &&
+ (0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
(0 == sb_strcmp (&R_temp_kk, &R_temp_kj)) )
{
if (0 == R_temp_ij.slen)
length = R_temp_kk.slen - R_last_ik->slen;
/* a(ba)*bx = (ab)+x */
- if ( (length > 0) &&
+ if ( (length > 0) &&
(GNUNET_YES != R_last_kk->null_flag) &&
(0 < R_last_kk->slen) &&
- (GNUNET_YES != R_last_kj->null_flag) &&
+ (GNUNET_YES != R_last_kj->null_flag) &&
(0 < R_last_kj->slen) &&
(GNUNET_YES != R_last_ik->null_flag) &&
(0 < R_last_ik->slen) &&
(0 == sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
(0 == sb_strncmp (&R_temp_kk, R_last_kj, length)) )
- {
+ {
struct StringBuffer temp_a;
struct StringBuffer temp_b;
sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_kk);
}
/* aa*a = a+a */
- else if ( (0 == clean_ik_kk_cmp) &&
+ else if ( (0 == clean_ik_kk_cmp) &&
(0 == clean_kk_kj_cmp) &&
(! has_epsilon (R_last_ik)) )
{
sb_free (&R_temp_kk);
sb_free (&R_temp_kj);
- if ( (GNUNET_YES == R_cur_l->null_flag) &&
+ if ( (GNUNET_YES == R_cur_l->null_flag) &&
(GNUNET_YES == R_cur_r->null_flag) )
{
R_cur_ij->null_flag = GNUNET_YES;
* @param a automaton for which to assign proofs and hashes, must not be NULL
*/
static int
-automaton_create_proofs (struct REGEX_ITERNAL_Automaton *a)
+automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a)
{
unsigned int n = a->state_count;
- struct REGEX_ITERNAL_State *states[n];
+ struct REGEX_INTERNAL_State *states[n];
struct StringBuffer *R_last;
struct StringBuffer *R_cur;
struct StringBuffer R_cur_r;
struct StringBuffer R_cur_l;
struct StringBuffer *R_swap;
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t;
struct StringBuffer complete_regex;
unsigned int i;
unsigned int j;
}
/* create depth-first numbering of the states, initializes 'state' */
- REGEX_ITERNAL_automaton_traverse (a, a->start, NULL, NULL, &number_states,
+ REGEX_INTERNAL_automaton_traverse (a, a->start, NULL, NULL, &number_states,
states);
for (i = 0; i < n; i++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (needs_parentheses (&R_last[i * n + j]))
- sb_wrap (&R_last[i * n + j], "(%.*s)", 2);
+ sb_wrap (&R_last[i * n + j], "(%.*s)", 2);
/* Compute regular expressions of length "k" between each pair of states per
* induction */
memset (&R_cur_l, 0, sizeof (struct StringBuffer));
if ( (0 == complete_regex.slen) &&
(0 < R_last[a->start->dfs_id * n + i].slen) )
{
- sb_append (&complete_regex,
+ sb_append (&complete_regex,
&R_last[a->start->dfs_id * n + i]);
}
else if ( (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) &&
(0 < R_last[a->start->dfs_id * n + i].slen) )
{
sb_append_cstr (&complete_regex, "|");
- sb_append (&complete_regex,
+ sb_append (&complete_regex,
&R_last[a->start->dfs_id * n + i]);
}
}
/* cleanup */
sb_free (&complete_regex);
- for (i = 0; i < n; i++)
+ for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
- sb_free (&R_cur[i * n + j]);
- sb_free (&R_last[i * n + j]);
+ sb_free (&R_cur[i * n + j]);
+ sb_free (&R_last[i * n + j]);
}
GNUNET_free (R_cur);
GNUNET_free (R_last);
*
* @return new DFA state
*/
-static struct REGEX_ITERNAL_State *
-dfa_state_create (struct REGEX_ITERNAL_Context *ctx,
- struct REGEX_ITERNAL_StateSet *nfa_states)
+static struct REGEX_INTERNAL_State *
+dfa_state_create (struct REGEX_INTERNAL_Context *ctx,
+ struct REGEX_INTERNAL_StateSet *nfa_states)
{
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
char *pos;
size_t len;
- struct REGEX_ITERNAL_State *cstate;
- struct REGEX_ITERNAL_Transition *ctran;
+ struct REGEX_INTERNAL_State *cstate;
+ struct REGEX_INTERNAL_Transition *ctran;
unsigned int i;
- s = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_State));
+ s = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_State));
s->id = ctx->state_id++;
s->index = -1;
s->lowlink = -1;
pos += strlen (pos);
/* Add a transition for each distinct label to NULL state */
- for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
+ for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
if (NULL != ctran->label)
- state_add_transition (ctx, s, ctran->label, NULL);
+ state_add_transition (ctx, s, ctran->label, NULL);
/* If the nfa_states contain an accepting state, the new dfa state is also
* accepting. */
if (cstate->accepting)
s->accepting = 1;
- }
+ }
pos[-1] = '}';
s->name = GNUNET_realloc (s->name, strlen (s->name) + 1);
- memset (nfa_states, 0, sizeof (struct REGEX_ITERNAL_StateSet));
+ memset (nfa_states, 0, sizeof (struct REGEX_INTERNAL_StateSet));
return s;
}
* @return length of the substring comsumed from 'str'
*/
static unsigned int
-dfa_move (struct REGEX_ITERNAL_State **s, const char *str)
+dfa_move (struct REGEX_INTERNAL_State **s, const char *str)
{
- struct REGEX_ITERNAL_Transition *t;
- struct REGEX_ITERNAL_State *new_s;
+ struct REGEX_INTERNAL_Transition *t;
+ struct REGEX_INTERNAL_State *new_s;
unsigned int len;
unsigned int max_len;
* @param s state where the marked attribute will be set to GNUNET_YES.
*/
static void
-mark_states (void *cls, const unsigned int count, struct REGEX_ITERNAL_State *s)
+mark_states (void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
{
s->marked = GNUNET_YES;
}
* @param a DFA automaton
*/
static void
-dfa_remove_unreachable_states (struct REGEX_ITERNAL_Automaton *a)
+dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a)
{
- struct REGEX_ITERNAL_State *s;
- struct REGEX_ITERNAL_State *s_next;
+ struct REGEX_INTERNAL_State *s;
+ struct REGEX_INTERNAL_State *s_next;
/* 1. unmark all states */
for (s = a->states_head; NULL != s; s = s->next)
s->marked = GNUNET_NO;
/* 2. traverse dfa from start state and mark all visited states */
- REGEX_ITERNAL_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL);
+ REGEX_INTERNAL_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)
* @param a DFA automaton
*/
static void
-dfa_remove_dead_states (struct REGEX_ITERNAL_Automaton *a)
+dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a)
{
- struct REGEX_ITERNAL_State *s;
- struct REGEX_ITERNAL_State *s_next;
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_State *s;
+ struct REGEX_INTERNAL_State *s_next;
+ struct REGEX_INTERNAL_Transition *t;
int dead;
GNUNET_assert (DFA == a->type);
* @return GNUNET_OK on success
*/
static int
-dfa_merge_nondistinguishable_states (struct REGEX_ITERNAL_Context *ctx,
- struct REGEX_ITERNAL_Automaton *a)
+dfa_merge_nondistinguishable_states (struct REGEX_INTERNAL_Context *ctx,
+ struct REGEX_INTERNAL_Automaton *a)
{
uint32_t *table;
- struct REGEX_ITERNAL_State *s1;
- struct REGEX_ITERNAL_State *s2;
- struct REGEX_ITERNAL_Transition *t1;
- struct REGEX_ITERNAL_Transition *t2;
- struct REGEX_ITERNAL_State *s1_next;
- struct REGEX_ITERNAL_State *s2_next;
+ struct REGEX_INTERNAL_State *s1;
+ struct REGEX_INTERNAL_State *s2;
+ struct REGEX_INTERNAL_Transition *t1;
+ struct REGEX_INTERNAL_Transition *t2;
+ struct REGEX_INTERNAL_State *s1_next;
+ struct REGEX_INTERNAL_State *s2_next;
int change;
unsigned int num_equal_edges;
unsigned int i;
* @return GNUNET_OK on success
*/
static int
-dfa_minimize (struct REGEX_ITERNAL_Context *ctx,
- struct REGEX_ITERNAL_Automaton *a)
+dfa_minimize (struct REGEX_INTERNAL_Context *ctx,
+ struct REGEX_INTERNAL_Automaton *a)
{
if (NULL == a)
return GNUNET_SYSERR;
/**
* Context for adding strided transitions to a DFA.
*/
-struct REGEX_ITERNAL_Strided_Context
+struct REGEX_INTERNAL_Strided_Context
{
/**
* Length of the strides.
* Strided transitions DLL. New strided transitions will be stored in this DLL
* and afterwards added to the DFA.
*/
- struct REGEX_ITERNAL_Transition *transitions_head;
+ struct REGEX_INTERNAL_Transition *transitions_head;
/**
* Strided transitions DLL.
*/
- struct REGEX_ITERNAL_Transition *transitions_tail;
+ struct REGEX_INTERNAL_Transition *transitions_tail;
};
* @param start start state for the depth-first traversal of the graph.
* @param s current state in the depth-first traversal
*/
-void
+static void
dfa_add_multi_strides_helper (void *cls, const unsigned int depth, char *label,
- struct REGEX_ITERNAL_State *start,
- struct REGEX_ITERNAL_State *s)
+ struct REGEX_INTERNAL_State *start,
+ struct REGEX_INTERNAL_State *s)
{
- struct REGEX_ITERNAL_Strided_Context *ctx = cls;
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_Strided_Context *ctx = cls;
+ struct REGEX_INTERNAL_Transition *t;
char *new_label;
if (depth == ctx->stride)
{
- t = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Transition));
+ t = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Transition));
t->label = GNUNET_strdup (label);
t->to_state = s;
t->from_state = start;
* @param count not used.
* @param s current state.
*/
-void
+static void
dfa_add_multi_strides (void *cls, const unsigned int count,
- struct REGEX_ITERNAL_State *s)
+ struct REGEX_INTERNAL_State *s)
{
dfa_add_multi_strides_helper (cls, 0, NULL, s, s);
}
* @param stride_len length of the strides.
*/
void
-REGEX_ITERNAL_dfa_add_multi_strides (struct REGEX_ITERNAL_Context *regex_ctx,
- struct REGEX_ITERNAL_Automaton *dfa,
+REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx,
+ struct REGEX_INTERNAL_Automaton *dfa,
const unsigned int stride_len)
{
- struct REGEX_ITERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
- struct REGEX_ITERNAL_Transition *t;
- struct REGEX_ITERNAL_Transition *t_next;
+ struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
+ struct REGEX_INTERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t_next;
if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
return;
/* Compute the new transitions of given stride_len */
- REGEX_ITERNAL_automaton_traverse (dfa, dfa->start, NULL, NULL,
+ REGEX_INTERNAL_automaton_traverse (dfa, dfa->start, NULL, NULL,
&dfa_add_multi_strides, &ctx);
/* Add all the new transitions to the automaton. */
* @param transitions_tail transitions DLL.
*/
void
-dfa_compress_paths_helper (struct REGEX_ITERNAL_Automaton *dfa,
- struct REGEX_ITERNAL_State *start,
- struct REGEX_ITERNAL_State *cur, char *label,
+dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa,
+ struct REGEX_INTERNAL_State *start,
+ struct REGEX_INTERNAL_State *cur, char *label,
unsigned int max_len,
- struct REGEX_ITERNAL_Transition **transitions_head,
- struct REGEX_ITERNAL_Transition **transitions_tail)
+ struct REGEX_INTERNAL_Transition **transitions_head,
+ struct REGEX_INTERNAL_Transition **transitions_tail)
{
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t;
char *new_label;
max_len == strlen (label)) ||
(start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label))))
{
- t = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Transition));
+ t = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Transition));
t->label = GNUNET_strdup (label);
t->to_state = cur;
t->from_state = start;
* @param max_len maximal length of the compressed paths.
*/
static void
-dfa_compress_paths (struct REGEX_ITERNAL_Context *regex_ctx,
- struct REGEX_ITERNAL_Automaton *dfa, unsigned int max_len)
+dfa_compress_paths (struct REGEX_INTERNAL_Context *regex_ctx,
+ struct REGEX_INTERNAL_Automaton *dfa, unsigned int max_len)
{
- struct REGEX_ITERNAL_State *s;
- struct REGEX_ITERNAL_State *s_next;
- struct REGEX_ITERNAL_Transition *t;
- struct REGEX_ITERNAL_Transition *t_next;
- struct REGEX_ITERNAL_Transition *transitions_head = NULL;
- struct REGEX_ITERNAL_Transition *transitions_tail = NULL;
+ struct REGEX_INTERNAL_State *s;
+ struct REGEX_INTERNAL_State *s_next;
+ struct REGEX_INTERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t_next;
+ struct REGEX_INTERNAL_Transition *transitions_head = NULL;
+ struct REGEX_INTERNAL_Transition *transitions_tail = NULL;
if (NULL == dfa)
return;
*
* @return new NFA fragment
*/
-static struct REGEX_ITERNAL_Automaton *
-nfa_fragment_create (struct REGEX_ITERNAL_State *start,
- struct REGEX_ITERNAL_State *end)
+static struct REGEX_INTERNAL_Automaton *
+nfa_fragment_create (struct REGEX_INTERNAL_State *start,
+ struct REGEX_INTERNAL_State *end)
{
- struct REGEX_ITERNAL_Automaton *n;
+ struct REGEX_INTERNAL_Automaton *n;
- n = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Automaton));
+ n = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Automaton));
n->type = NFA;
n->start = NULL;
* @param states_tail tail of the DLL of states
*/
static void
-nfa_add_states (struct REGEX_ITERNAL_Automaton *n,
- struct REGEX_ITERNAL_State *states_head,
- struct REGEX_ITERNAL_State *states_tail)
+nfa_add_states (struct REGEX_INTERNAL_Automaton *n,
+ struct REGEX_INTERNAL_State *states_head,
+ struct REGEX_INTERNAL_State *states_tail)
{
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
if (NULL == n || NULL == states_head)
{
*
* @return new NFA state
*/
-static struct REGEX_ITERNAL_State *
-nfa_state_create (struct REGEX_ITERNAL_Context *ctx, int accepting)
+static struct REGEX_INTERNAL_State *
+nfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting)
{
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
- s = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_State));
+ s = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_State));
s->id = ctx->state_id++;
s->accepting = accepting;
s->marked = GNUNET_NO;
* pass NULL for epsilon transition
*/
static void
-nfa_closure_set_create (struct REGEX_ITERNAL_StateSet *ret,
- struct REGEX_ITERNAL_Automaton *nfa,
- struct REGEX_ITERNAL_StateSet *states, const char *label)
+nfa_closure_set_create (struct REGEX_INTERNAL_StateSet *ret,
+ struct REGEX_INTERNAL_Automaton *nfa,
+ struct REGEX_INTERNAL_StateSet *states, const char *label)
{
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
unsigned int i;
- struct REGEX_ITERNAL_StateSet_MDLL cls_stack;
- struct REGEX_ITERNAL_State *clsstate;
- struct REGEX_ITERNAL_State *currentstate;
- struct REGEX_ITERNAL_Transition *ctran;
+ struct REGEX_INTERNAL_StateSet_MDLL cls_stack;
+ struct REGEX_INTERNAL_State *clsstate;
+ struct REGEX_INTERNAL_State *currentstate;
+ struct REGEX_INTERNAL_Transition *ctran;
- memset (ret, 0, sizeof (struct REGEX_ITERNAL_StateSet));
+ memset (ret, 0, sizeof (struct REGEX_INTERNAL_StateSet));
if (NULL == states)
return;
/* Add start state to closure only for epsilon closure */
if (NULL == label)
state_set_append (ret, s);
-
+
/* initialize work stack */
cls_stack.head = NULL;
cls_stack.tail = NULL;
{
GNUNET_CONTAINER_MDLL_remove (ST, cls_stack.head, cls_stack.tail,
currentstate);
- cls_stack.len--;
+ cls_stack.len--;
for (ctran = currentstate->transitions_head; NULL != ctran;
ctran = ctran->next)
{
clsstate);
cls_stack.len++;
clsstate->contained = 1;
- }
+ }
}
}
for (i = 0; i < ret->off; i++)
ret->states[i]->contained = 0;
if (ret->off > 1)
- qsort (ret->states, ret->off, sizeof (struct REGEX_ITERNAL_State *),
+ qsort (ret->states, ret->off, sizeof (struct REGEX_INTERNAL_State *),
&state_compare);
}
* @param ctx context
*/
static void
-nfa_add_concatenation (struct REGEX_ITERNAL_Context *ctx)
+nfa_add_concatenation (struct REGEX_INTERNAL_Context *ctx)
{
- struct REGEX_ITERNAL_Automaton *a;
- struct REGEX_ITERNAL_Automaton *b;
- struct REGEX_ITERNAL_Automaton *new_nfa;
+ struct REGEX_INTERNAL_Automaton *a;
+ struct REGEX_INTERNAL_Automaton *b;
+ struct REGEX_INTERNAL_Automaton *new_nfa;
b = ctx->stack_tail;
GNUNET_assert (NULL != b);
* @param ctx context
*/
static void
-nfa_add_star_op (struct REGEX_ITERNAL_Context *ctx)
+nfa_add_star_op (struct REGEX_INTERNAL_Context *ctx)
{
- struct REGEX_ITERNAL_Automaton *a;
- struct REGEX_ITERNAL_Automaton *new_nfa;
- struct REGEX_ITERNAL_State *start;
- struct REGEX_ITERNAL_State *end;
+ struct REGEX_INTERNAL_Automaton *a;
+ struct REGEX_INTERNAL_Automaton *new_nfa;
+ struct REGEX_INTERNAL_State *start;
+ struct REGEX_INTERNAL_State *end;
a = ctx->stack_tail;
* @param ctx context
*/
static void
-nfa_add_plus_op (struct REGEX_ITERNAL_Context *ctx)
+nfa_add_plus_op (struct REGEX_INTERNAL_Context *ctx)
{
- struct REGEX_ITERNAL_Automaton *a;
+ struct REGEX_INTERNAL_Automaton *a;
a = ctx->stack_tail;
* @param ctx context
*/
static void
-nfa_add_question_op (struct REGEX_ITERNAL_Context *ctx)
+nfa_add_question_op (struct REGEX_INTERNAL_Context *ctx)
{
- struct REGEX_ITERNAL_Automaton *a;
- struct REGEX_ITERNAL_Automaton *new_nfa;
- struct REGEX_ITERNAL_State *start;
- struct REGEX_ITERNAL_State *end;
+ struct REGEX_INTERNAL_Automaton *a;
+ struct REGEX_INTERNAL_Automaton *new_nfa;
+ struct REGEX_INTERNAL_State *start;
+ struct REGEX_INTERNAL_State *end;
a = ctx->stack_tail;
-
if (NULL == a)
{
GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
* @param ctx context
*/
static void
-nfa_add_alternation (struct REGEX_ITERNAL_Context *ctx)
+nfa_add_alternation (struct REGEX_INTERNAL_Context *ctx)
{
- struct REGEX_ITERNAL_Automaton *a;
- struct REGEX_ITERNAL_Automaton *b;
- struct REGEX_ITERNAL_Automaton *new_nfa;
- struct REGEX_ITERNAL_State *start;
- struct REGEX_ITERNAL_State *end;
+ struct REGEX_INTERNAL_Automaton *a;
+ struct REGEX_INTERNAL_Automaton *b;
+ struct REGEX_INTERNAL_Automaton *new_nfa;
+ struct REGEX_INTERNAL_State *start;
+ struct REGEX_INTERNAL_State *end;
b = ctx->stack_tail;
GNUNET_assert (NULL != b);
* @param label label for nfa transition
*/
static void
-nfa_add_label (struct REGEX_ITERNAL_Context *ctx, const char *label)
+nfa_add_label (struct REGEX_INTERNAL_Context *ctx, const char *label)
{
- struct REGEX_ITERNAL_Automaton *n;
- struct REGEX_ITERNAL_State *start;
- struct REGEX_ITERNAL_State *end;
+ struct REGEX_INTERNAL_Automaton *n;
+ struct REGEX_INTERNAL_State *start;
+ struct REGEX_INTERNAL_State *end;
GNUNET_assert (NULL != ctx);
* @param ctx context
*/
static void
-REGEX_ITERNAL_context_init (struct REGEX_ITERNAL_Context *ctx)
+REGEX_INTERNAL_context_init (struct REGEX_INTERNAL_Context *ctx)
{
if (NULL == ctx)
{
* @param regex regular expression string
* @param len length of the string
*
- * @return NFA, needs to be freed using REGEX_ITERNAL_destroy_automaton
+ * @return NFA, needs to be freed using REGEX_INTERNAL_destroy_automaton
*/
-struct REGEX_ITERNAL_Automaton *
-REGEX_ITERNAL_construct_nfa (const char *regex, const size_t len)
+struct REGEX_INTERNAL_Automaton *
+REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len)
{
- struct REGEX_ITERNAL_Context ctx;
- struct REGEX_ITERNAL_Automaton *nfa;
+ struct REGEX_INTERNAL_Context ctx;
+ struct REGEX_INTERNAL_Automaton *nfa;
const char *regexp;
char curlabel[2];
char *error_msg;
return NULL;
}
- REGEX_ITERNAL_context_init (&ctx);
+ REGEX_INTERNAL_context_init (&ctx);
regexp = regex;
curlabel[1] = '\0';
nfa_add_concatenation (&ctx);
}
if (poff == psize)
- GNUNET_array_grow (p, psize, psize * 2 + 4);
+ GNUNET_array_grow (p, psize, psize * 2 + 4); /* FIXME why *2 +4? */
p[poff].altcount = altcount;
p[poff].atomcount = atomcount;
poff++;
nfa->regex = GNUNET_strdup (regex);
/* create depth-first numbering of the states for pretty printing */
- REGEX_ITERNAL_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL);
+ REGEX_INTERNAL_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL);
/* No multistriding added so far */
nfa->is_multistrided = GNUNET_NO;
while (NULL != (nfa = ctx.stack_head))
{
GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
- REGEX_ITERNAL_automaton_destroy (nfa);
+ REGEX_INTERNAL_automaton_destroy (nfa);
}
return NULL;
* for starting.
*/
static void
-construct_dfa_states (struct REGEX_ITERNAL_Context *ctx,
- struct REGEX_ITERNAL_Automaton *nfa,
- struct REGEX_ITERNAL_Automaton *dfa,
- struct REGEX_ITERNAL_State *dfa_state)
-{
- struct REGEX_ITERNAL_Transition *ctran;
- struct REGEX_ITERNAL_State *new_dfa_state;
- struct REGEX_ITERNAL_State *state_contains;
- struct REGEX_ITERNAL_State *state_iter;
- struct REGEX_ITERNAL_StateSet tmp;
- struct REGEX_ITERNAL_StateSet nfa_set;
+construct_dfa_states (struct REGEX_INTERNAL_Context *ctx,
+ struct REGEX_INTERNAL_Automaton *nfa,
+ struct REGEX_INTERNAL_Automaton *dfa,
+ struct REGEX_INTERNAL_State *dfa_state)
+{
+ struct REGEX_INTERNAL_Transition *ctran;
+ struct REGEX_INTERNAL_State *new_dfa_state;
+ struct REGEX_INTERNAL_State *state_contains;
+ struct REGEX_INTERNAL_State *state_iter;
+ struct REGEX_INTERNAL_StateSet tmp;
+ struct REGEX_INTERNAL_StateSet nfa_set;
for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
{
* @param max_path_len limit the path compression length to the
* given value. If set to 1, no path compression is applied. Set to 0 for
* maximal possible path compression (generally not desireable).
- * @return DFA, needs to be freed using REGEX_ITERNAL_automaton_destroy.
+ * @return DFA, needs to be freed using REGEX_INTERNAL_automaton_destroy.
*/
-struct REGEX_ITERNAL_Automaton *
-REGEX_ITERNAL_construct_dfa (const char *regex, const size_t len,
- unsigned int max_path_len)
+struct REGEX_INTERNAL_Automaton *
+REGEX_INTERNAL_construct_dfa (const char *regex, const size_t len,
+ unsigned int max_path_len)
{
- struct REGEX_ITERNAL_Context ctx;
- struct REGEX_ITERNAL_Automaton *dfa;
- struct REGEX_ITERNAL_Automaton *nfa;
- struct REGEX_ITERNAL_StateSet nfa_start_eps_cls;
- struct REGEX_ITERNAL_StateSet singleton_set;
+ struct REGEX_INTERNAL_Context ctx;
+ struct REGEX_INTERNAL_Automaton *dfa;
+ struct REGEX_INTERNAL_Automaton *nfa;
+ struct REGEX_INTERNAL_StateSet nfa_start_eps_cls;
+ struct REGEX_INTERNAL_StateSet singleton_set;
- REGEX_ITERNAL_context_init (&ctx);
+ REGEX_INTERNAL_context_init (&ctx);
/* Create NFA */
- // fprintf (stderr, "N");
- nfa = REGEX_ITERNAL_construct_nfa (regex, len);
+ nfa = REGEX_INTERNAL_construct_nfa (regex, len);
if (NULL == nfa)
{
return NULL;
}
- dfa = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Automaton));
+ dfa = GNUNET_malloc (sizeof (struct REGEX_INTERNAL_Automaton));
dfa->type = DFA;
dfa->regex = GNUNET_strdup (regex);
/* Create DFA start state from epsilon closure */
- memset (&singleton_set, 0, sizeof (struct REGEX_ITERNAL_StateSet));
+ memset (&singleton_set, 0, sizeof (struct REGEX_INTERNAL_StateSet));
state_set_append (&singleton_set, nfa->start);
nfa_closure_set_create (&nfa_start_eps_cls, nfa, &singleton_set, NULL);
state_set_clear (&singleton_set);
dfa->start = dfa_state_create (&ctx, &nfa_start_eps_cls);
automaton_add_state (dfa, dfa->start);
- // fprintf (stderr, "D");
construct_dfa_states (&ctx, nfa, dfa, dfa->start);
- REGEX_ITERNAL_automaton_destroy (nfa);
+ REGEX_INTERNAL_automaton_destroy (nfa);
/* Minimize DFA */
- // fprintf (stderr, "M");
if (GNUNET_OK != dfa_minimize (&ctx, dfa))
{
- REGEX_ITERNAL_automaton_destroy (dfa);
+ REGEX_INTERNAL_automaton_destroy (dfa);
return NULL;
}
/* Create proofs and hashes for all states */
if (GNUNET_OK != automaton_create_proofs (dfa))
{
- REGEX_ITERNAL_automaton_destroy (dfa);
+ REGEX_INTERNAL_automaton_destroy (dfa);
return NULL;
}
/**
- * Free the memory allocated by constructing the REGEX_ITERNAL_Automaton data
+ * Free the memory allocated by constructing the REGEX_INTERNAL_Automaton data
* structure.
*
* @param a automaton to be destroyed
*/
void
-REGEX_ITERNAL_automaton_destroy (struct REGEX_ITERNAL_Automaton *a)
+REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a)
{
- struct REGEX_ITERNAL_State *s;
- struct REGEX_ITERNAL_State *next_state;
+ struct REGEX_INTERNAL_State *s;
+ struct REGEX_INTERNAL_State *next_state;
if (NULL == a)
return;
* @return 0 if string matches, non 0 otherwise
*/
static int
-evaluate_dfa (struct REGEX_ITERNAL_Automaton *a, const char *string)
+evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
{
const char *strp;
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
unsigned int step_len;
if (DFA != a->type)
* @return 0 if string matches, non 0 otherwise
*/
static int
-evaluate_nfa (struct REGEX_ITERNAL_Automaton *a, const char *string)
+evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
{
const char *strp;
char str[2];
- struct REGEX_ITERNAL_State *s;
- struct REGEX_ITERNAL_StateSet sset;
- struct REGEX_ITERNAL_StateSet new_sset;
- struct REGEX_ITERNAL_StateSet singleton_set;
+ struct REGEX_INTERNAL_State *s;
+ struct REGEX_INTERNAL_StateSet sset;
+ struct REGEX_INTERNAL_StateSet new_sset;
+ struct REGEX_INTERNAL_StateSet singleton_set;
unsigned int i;
int result;
return 0;
result = 1;
- memset (&singleton_set, 0, sizeof (struct REGEX_ITERNAL_StateSet));
+ memset (&singleton_set, 0, sizeof (struct REGEX_INTERNAL_StateSet));
state_set_append (&singleton_set, a->start);
nfa_closure_set_create (&sset, a, &singleton_set, NULL);
state_set_clear (&singleton_set);
* @return 0 if string matches, non 0 otherwise
*/
int
-REGEX_ITERNAL_eval (struct REGEX_ITERNAL_Automaton *a, const char *string)
+REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string)
{
int result;
* @return
*/
const char *
-REGEX_ITERNAL_get_canonical_regex (struct REGEX_ITERNAL_Automaton *a)
+REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a)
{
if (NULL == a)
return NULL;
* @return number of transitions in the given automaton.
*/
unsigned int
-REGEX_ITERNAL_get_transition_count (struct REGEX_ITERNAL_Automaton *a)
+REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a)
{
unsigned int t_count;
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
if (NULL == a)
return 0;
* to construct the key
*/
size_t
-REGEX_ITERNAL_get_first_key (const char *input_string, size_t string_len,
+REGEX_INTERNAL_get_first_key (const char *input_string, size_t string_len,
struct GNUNET_HashCode * key)
{
- unsigned int size;
-
- size =
- string_len <
- GNUNET_REGEX_INITIAL_BYTES ? string_len : GNUNET_REGEX_INITIAL_BYTES;
+ size_t size;
+ size = string_len < GNUNET_REGEX_INITIAL_BYTES ? string_len :
+ GNUNET_REGEX_INITIAL_BYTES;
if (NULL == input_string)
{
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n");
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Given input string was NULL!\n");
return 0;
}
-
GNUNET_CRYPTO_hash (input_string, size, key);
return size;
}
-/**
- * Check if the given 'proof' matches the given 'key'.
- *
- * @param proof partial regex of a state.
- * @param key hash of a state.
- *
- * @return GNUNET_OK if the proof is valid for the given key.
- */
-int
-REGEX_ITERNAL_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;
-}
-
-
/**
* Recursive function that calls the iterator for each synthetic start state.
*
*/
static void
iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
- char *consumed_string, struct REGEX_ITERNAL_State *state,
- REGEX_ITERNAL_KeyIterator iterator, void *iterator_cls)
+ char *consumed_string, struct REGEX_INTERNAL_State *state,
+ REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
{
- unsigned int i;
char *temp;
- struct REGEX_ITERNAL_Transition *t;
+ struct REGEX_INTERNAL_Transition *t;
unsigned int num_edges = state->transition_count;
- struct REGEX_ITERNAL_Edge edges[num_edges];
- struct REGEX_ITERNAL_Edge edge[1];
+ struct REGEX_BLOCK_Edge edges[num_edges];
+ struct REGEX_BLOCK_Edge edge[1];
struct GNUNET_HashCode hash;
struct GNUNET_HashCode hash_new;
-
unsigned int cur_len;
if (NULL != consumed_string)
{
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;
- }
+ (void) state_get_edges (state, edges);
GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash);
iterator (iterator_cls, &hash, consumed_string, state->accepting,
num_edges, edges);
GNUNET_free (temp);
}
}
- else if (max_len < cur_len)
+ else /* cur_len > max_len */
{
/* Case where the concatenated labels are longer than max_len, then split. */
edge[0].label = &consumed_string[max_len];
* @param iterator_cls closure.
*/
void
-REGEX_ITERNAL_iterate_all_edges (struct REGEX_ITERNAL_Automaton *a,
- REGEX_ITERNAL_KeyIterator iterator,
- void *iterator_cls)
+REGEX_INTERNAL_iterate_all_edges (struct REGEX_INTERNAL_Automaton *a,
+ REGEX_INTERNAL_KeyIterator iterator,
+ void *iterator_cls)
{
- struct REGEX_ITERNAL_State *s;
+ struct REGEX_INTERNAL_State *s;
for (s = a->states_head; NULL != s; s = s->next)
{
- struct REGEX_ITERNAL_Edge edges[s->transition_count];
+ struct REGEX_BLOCK_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;
+ }
- if ((NULL != s->proof && 0 < strlen (s->proof)) || s->accepting)
- iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges,
- edges);
+ iterate_initial_edge (GNUNET_REGEX_INITIAL_BYTES,
+ GNUNET_REGEX_INITIAL_BYTES,
+ NULL, a->start,
+ iterator, iterator_cls);
+}
- s->marked = GNUNET_NO;
+/**
+ * Struct to hold all the relevant state information in the HashMap.
+ *
+ * Contains the same info as the Regex Iterator parametes except the key,
+ * which comes directly from the HashMap iterator.
+ */
+struct temporal_state_store {
+ int reachable;
+ char *proof;
+ int accepting;
+ int num_edges;
+ struct REGEX_BLOCK_Edge *edges;
+};
+
+
+/**
+ * Store regex iterator and cls in one place to pass to the hashmap iterator.
+ */
+struct client_iterator {
+ REGEX_INTERNAL_KeyIterator iterator;
+ void *iterator_cls;
+};
+
+
+/**
+ * Iterator over all edges of a dfa. Stores all of them in a HashMap
+ * for later reachability marking.
+ *
+ * @param cls Closure (HashMap)
+ * @param key hash for current state.
+ * @param proof proof for current state
+ * @param accepting GNUNET_YES if this is an accepting state, GNUNET_NO if not.
+ * @param num_edges number of edges leaving current state.
+ * @param edges edges leaving current state.
+ */
+static void
+store_all_states (void *cls,
+ const struct GNUNET_HashCode *key,
+ const char *proof,
+ int accepting,
+ unsigned int num_edges,
+ const struct REGEX_BLOCK_Edge *edges)
+{
+ struct GNUNET_CONTAINER_MultiHashMap *hm = cls;
+ struct temporal_state_store *tmp;
+ size_t edges_size;
+
+ tmp = GNUNET_new (struct temporal_state_store);
+ tmp->reachable = GNUNET_NO;
+ tmp->proof = GNUNET_strdup (proof);
+ tmp->accepting = accepting;
+ tmp->num_edges = num_edges;
+ edges_size = sizeof (struct REGEX_BLOCK_Edge) * num_edges;
+ tmp->edges = GNUNET_malloc (edges_size);
+ memcpy(tmp->edges, edges, edges_size);
+ GNUNET_CONTAINER_multihashmap_put (hm, key, tmp,
+ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
+}
+
+
+/**
+ * Mark state as reachable and call recursively on all its edges.
+ *
+ * If already marked as reachable, do nothing.
+ *
+ * @param state State to mark as reachable.
+ * @param hm HashMap which stores all the states indexed by key.
+ */
+static void
+mark_as_reachable (struct temporal_state_store *state,
+ struct GNUNET_CONTAINER_MultiHashMap *hm)
+{
+ struct temporal_state_store *child;
+ unsigned int i;
+
+ if (GNUNET_YES == state->reachable)
+ /* visited */
+ return;
+
+ state->reachable = GNUNET_YES;
+ for (i = 0; i < state->num_edges; i++)
+ {
+ child = GNUNET_CONTAINER_multihashmap_get (hm,
+ &state->edges[i].destination);
+ if (NULL == child)
+ {
+ GNUNET_break (0);
+ continue;
+ }
+ mark_as_reachable (child, hm);
}
+}
+
+
+/**
+ * Iterator over hash map entries to mark the ones that are reachable.
+ *
+ * @param cls closure
+ * @param key current key code
+ * @param value value in the hash map
+ * @return #GNUNET_YES if we should continue to iterate,
+ * #GNUNET_NO if not.
+ */
+static int
+reachability_iterator (void *cls,
+ const struct GNUNET_HashCode *key,
+ void *value)
+{
+ struct GNUNET_CONTAINER_MultiHashMap *hm = cls;
+ struct temporal_state_store *state = value;
- iterate_initial_edge (GNUNET_REGEX_INITIAL_BYTES, GNUNET_REGEX_INITIAL_BYTES,
- NULL, a->start, iterator, iterator_cls);
+ if (GNUNET_YES == state->reachable)
+ /* already visited and marked */
+ return GNUNET_YES;
+
+ if (GNUNET_REGEX_INITIAL_BYTES > strlen (state->proof) &&
+ GNUNET_NO == state->accepting)
+ /* not directly reachable */
+ return GNUNET_YES;
+
+ mark_as_reachable (state, hm);
+ return GNUNET_YES;
}
+/**
+ * Iterator over hash map entries.
+ * Calling the callback on the ones marked as reachables.
+ *
+ * @param cls closure
+ * @param key current key code
+ * @param value value in the hash map
+ * @return #GNUNET_YES if we should continue to iterate,
+ * #GNUNET_NO if not.
+ */
+static int
+iterate_reachables (void *cls,
+ const struct GNUNET_HashCode *key,
+ void *value)
+{
+ struct client_iterator *ci = cls;
+ struct temporal_state_store *state = value;
+
+ if (GNUNET_YES == state->reachable)
+ {
+ ci->iterator (ci->iterator_cls, key,
+ state->proof, state->accepting,
+ state->num_edges, state->edges);
+ }
+ GNUNET_free (state->edges);
+ GNUNET_free (state->proof);
+ GNUNET_free (state);
+ return GNUNET_YES;
+
+}
+
+/**
+ * Iterate over all edges of automaton 'a' that are reachable from a state with
+ * a proof of at least GNUNET_REGEX_INITIAL_BYTES characters.
+ *
+ * Call the iterator for each such edge.
+ *
+ * @param a automaton.
+ * @param iterator iterator called for each reachable edge.
+ * @param iterator_cls closure.
+ */
+void
+REGEX_INTERNAL_iterate_reachable_edges (struct REGEX_INTERNAL_Automaton *a,
+ REGEX_INTERNAL_KeyIterator iterator,
+ void *iterator_cls)
+{
+ struct GNUNET_CONTAINER_MultiHashMap *hm;
+ struct client_iterator ci;
+
+ hm = GNUNET_CONTAINER_multihashmap_create (a->state_count * 2, GNUNET_NO);
+ ci.iterator = iterator;
+ ci.iterator_cls = iterator_cls;
+
+ REGEX_INTERNAL_iterate_all_edges (a, &store_all_states, hm);
+ GNUNET_CONTAINER_multihashmap_iterate (hm, &reachability_iterator, hm);
+ GNUNET_CONTAINER_multihashmap_iterate (hm, &iterate_reachables, &ci);
+
+ GNUNET_CONTAINER_multihashmap_destroy (hm);
+}
-/* end of regex.c */
+/* end of regex_internal.c */
projects / oweals / gnunet.git / blobdiff