/**
* Constant for how many bits the initial string regex should have.
*/
-#define INITIAL_BITS 10
+#define INITIAL_BITS 8
/**
* Get all edges leaving state 's'.
*
* @param s state.
- * @param edges all edges leaving 's'.
+ * @param edges all edges leaving 's', expected to be allocated and have enough
+ * space for s->transitions_count elements.
*
* @return number of edges.
*/
struct GNUNET_REGEX_State **states = cls;
s->proof_id = count;
- states[count] = s;
+ if (NULL != states)
+ states[count] = s;
}
/**
* 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
*/
n->start = NULL;
n->end = NULL;
- if (NULL == start && NULL == end)
+ if (NULL == start || NULL == end)
return n;
automaton_add_state (n, end);
{
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);
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;
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);
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);
}
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);
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);
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);
}
case 92: /* escape: \ */
regexp++;
count++;
+ /* fall through! */
default:
if (atomcount > 1)
{
nfa->regex = GNUNET_strdup (regex);
+ /* create depth-first numbering of the states for pretty printing */
+ GNUNET_REGEX_automaton_traverse (nfa, &number_states, NULL);
+
return nfa;
error:
return 0;
result = 1;
- strp = string;
sset = nfa_closure_create (a, a->start, 0);
for (strp = string; NULL != strp && *strp; strp++)
/**
* Get the first key for the given 'input_string'. This hashes the first x bits
- * of the 'input_strings'.
+ * of the 'input_string'.
*
* @param input_string string.
* @param string_len length of the 'input_string'.
* @return number of bits of 'input_string' that have been consumed
* to construct the key
*/
-unsigned int
-GNUNET_REGEX_get_first_key (const char *input_string, unsigned int string_len,
- struct GNUNET_HashCode *key)
+size_t
+GNUNET_REGEX_get_first_key (const char *input_string, size_t string_len,
+ struct GNUNET_HashCode * key)
{
unsigned int size;
/**
* Check if the given 'proof' matches the given 'key'.
*
- * @param proof partial regex
- * @param key hash
+ * @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
+ * @return GNUNET_OK if the proof is valid for the given key.
*/
int
GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key)
{
- return GNUNET_OK;
+ struct GNUNET_HashCode key_check;
+
+ GNUNET_CRYPTO_hash (proof, strlen (proof), &key_check);
+ return (0 ==
+ GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
+}
+
+
+/**
+ * Recursive helper function for iterate_initial_edges. Will call iterator
+ * function for each initial state.
+ *
+ * @param min_len minimum length of the path in the graph.
+ * @param max_len maximum length of the path in the graph.
+ * @param cur_len current length of the path already traversed.
+ * @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 for the iterator function.
+ */
+static void
+iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
+ unsigned int cur_len, char *consumed_string,
+ struct GNUNET_REGEX_State *state,
+ GNUNET_REGEX_KeyIterator iterator, void *iterator_cls)
+{
+ unsigned int i;
+ char label[state->transition_count][2];
+ char *temp;
+ struct GNUNET_REGEX_Transition *t;
+ unsigned int num_edges = state->transition_count;
+ struct GNUNET_REGEX_Edge edges[num_edges];
+ struct GNUNET_HashCode hash;
+
+ if (cur_len > min_len && NULL != consumed_string && cur_len <= max_len)
+ {
+ for (i = 0, t = state->transitions_head; NULL != t; t = t->next, i++)
+ {
+ label[i][0] = t->label;
+ label[i][1] = '\0';
+ edges[i].label = label[i];
+ 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);
+ }
+
+ if (cur_len < max_len)
+ {
+ cur_len++;
+ for (t = state->transitions_head; NULL != t; t = t->next)
+ {
+ if (NULL != consumed_string)
+ GNUNET_asprintf (&temp, "%s%c", consumed_string, t->label);
+ else
+ GNUNET_asprintf (&temp, "%c", t->label);
+
+ iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state,
+ iterator, iterator_cls);
+ GNUNET_free (temp);
+ }
+ }
+}
+
+
+/**
+ * Iterate over all initial edges that aren't actually part of the automaton.
+ * This is needed to find the initial states returned by
+ * GNUNET_REGEX_get_first_key. Iteration will start at the first branch state (a
+ * state that has more than one outgoing edge, can be the first state), because
+ * all previous states will have the same proof and be iterated over in
+ * iterate_all_edges.
+ *
+ * @param a the automaton for which the initial states should be computed.
+ * @param initial_len length of the initial state string.
+ * @param iterator iterator function called for each edge.
+ * @param iterator_cls closure for the iterator function.
+ */
+void
+iterate_initial_edges (struct GNUNET_REGEX_Automaton *a,
+ const unsigned int initial_len,
+ GNUNET_REGEX_KeyIterator iterator, void *iterator_cls)
+{
+ char *consumed_string;
+ char *temp;
+ struct GNUNET_REGEX_State *s;
+ unsigned int cur_len;
+
+ if (1 > initial_len)
+ return;
+
+ consumed_string = NULL;
+ s = a->start;
+ cur_len = 0;
+
+ if (1 == s->transition_count)
+ {
+ do
+ {
+ if (NULL != consumed_string)
+ {
+ temp = consumed_string;
+ GNUNET_asprintf (&consumed_string, "%s%c", consumed_string,
+ s->transitions_head->label);
+ GNUNET_free (temp);
+ }
+ else
+ GNUNET_asprintf (&consumed_string, "%c", s->transitions_head->label);
+
+ s = s->transitions_head->to_state;
+ cur_len++;
+ }
+ while (cur_len < initial_len && 1 == s->transition_count);
+ }
+
+ iterate_initial_edge (cur_len, initial_len, cur_len, consumed_string, s,
+ iterator, iterator_cls);
+
+ GNUNET_free_non_null (consumed_string);
}
num_edges = state_get_edges (s, edges);
- iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges, edges);
+ if (0 < strlen (s->proof) || s->accepting)
+ iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges,
+ edges);
for (t = s->transitions_head; NULL != t; t = t->next)
iterate_edge (t->to_state, iterator, iterator_cls);
for (s = a->states_head; NULL != s; s = s->next)
s->marked = GNUNET_NO;
+ iterate_initial_edges (a, INITIAL_BITS, iterator, iterator_cls);
iterate_edge (a->start, iterator, iterator_cls);
}
projects / oweals / gnunet.git / blobdiff