[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r21001 - in gnunet/src: include regex
From: |
gnunet |
Subject: |
[GNUnet-SVN] r21001 - in gnunet/src: include regex |
Date: |
Tue, 17 Apr 2012 22:43:56 +0200 |
Author: szengel
Date: 2012-04-17 22:43:56 +0200 (Tue, 17 Apr 2012)
New Revision: 21001
Modified:
gnunet/src/include/gnunet_regex_lib.h
gnunet/src/regex/regex.c
Log:
api changes
Modified: gnunet/src/include/gnunet_regex_lib.h
===================================================================
--- gnunet/src/include/gnunet_regex_lib.h 2012-04-17 20:25:50 UTC (rev
21000)
+++ gnunet/src/include/gnunet_regex_lib.h 2012-04-17 20:43:56 UTC (rev
21001)
@@ -43,10 +43,21 @@
struct GNUNET_REGEX_Automaton;
/**
- * State representation.
+ * Edge representation.
*/
-struct GNUNET_REGEX_State;
+struct GNUNET_REGEX_Edge
+{
+ /**
+ * Label of the edge.
+ */
+ const char *label;
+ /**
+ * Destionation of the edge.
+ */
+ GNUNET_HashCode destination;
+};
+
/**
* Construct an NFA by parsing the regex string of length 'len'.
*
@@ -100,89 +111,59 @@
GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a,
const char *string);
-
-
/**
- * Get the starting state of the given automaton 'a'.
- *
- * @param a automaton.
- *
- * @return starting state.
- */
-struct GNUNET_REGEX_State *
-GNUNET_REGEX_automaton_get_start (struct GNUNET_REGEX_Automaton *a);
-
-
-/**
* @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,
- GNUNET_HashCode *key);
+ unsigned int string_len,
+ GNUNET_HashCode *key);
-
/**
+ * Check if the given 'proof' matches the given 'key'.
+ *
+ * @param proof partial regex
+ * @param key hash
+ *
* @return GNUNET_OK if the proof is valid for the given key
*/
int
GNUNET_REGEX_check_proof (const char *proof,
- const GNUNET_HashCode *key);
+ const GNUNET_HashCode *key);
-struct GNUNET_REGEX_Edge
-{
- const char *label;
- GNUNET_HashCode destination;
-};
-
-
-typedef void (*GNUNET_REGEX_KeyIterator)(void *cls,
- const GNUNET_HashCode *key,
- const char *proof,
- unsigned int num_edges,
- const struct GNUNET_REGEX_Edge *edges);
-
-
-int
-GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a,
- GNUNET_REGEX_KeyIterator iterator,
- void *iterator_cls);
-
-
/**
- * Get the next states, starting from states 's'.
+ * Iterator callback function.
*
- * @param a automaton.
- * @param s states.
- * @param count number of states given in 's'. Will contain number of
- * states that were returned upon return.
- *
- * @return next states, 'count' will contain the number of states.
+ * @param cls closure.
+ * @param key hash for current state.
+ * @param proof proof for current state.
+ * @param num_edges number of edges leaving current state.
+ * @param edges edges leaving current state.
*/
-struct GNUNET_REGEX_State **
-GNUNET_REGEX_automaton_states_get_next (struct GNUNET_REGEX_Automaton *a,
- struct GNUNET_REGEX_State **s,
- unsigned int *count);
+typedef void (*GNUNET_REGEX_KeyIterator)(void *cls,
+ const GNUNET_HashCode *key,
+ const char *proof,
+ unsigned int num_edges,
+ const struct GNUNET_REGEX_Edge
*edges);
+
/**
- * Hash a set of states.
+ * Iterate over all edges starting from start state of automaton 'a'. Calling
+ * iterator for each edge.
*
* @param a automaton.
- * @param s states.
- * @param count number of states.
- *
- * @return hash.
+ * @param iterator iterator called for each edge.
+ * @param iterator_cls closure.
*/
-struct GNUNET_HashCode
-GNUNET_REGEX_automaton_states_hash (struct GNUNET_REGEX_Automaton *a,
- struct GNUNET_REGEX_State **s,
- unsigned int count);
+void
+GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a,
+ GNUNET_REGEX_KeyIterator iterator,
+ void *iterator_cls);
-
-
#if 0 /* keep Emacsens' auto-indent happy */
{
#endif
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-04-17 20:25:50 UTC (rev 21000)
+++ gnunet/src/regex/regex.c 2012-04-17 20:43:56 UTC (rev 21001)
@@ -24,9 +24,12 @@
*/
#include "platform.h"
#include "gnunet_container_lib.h"
+#include "gnunet_crypto_lib.h"
#include "gnunet_regex_lib.h"
#include "regex.h"
+#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.
@@ -177,6 +180,8 @@
*/
char *name;
+ GNUNET_HashCode hash;
+
/**
* Number of transitions from this state to other states.
*/
@@ -201,7 +206,7 @@
/**
* Transition between two states. Each state can have 0-n transitions.
- * If literal is 0, this is considered to be an epsilon transition.
+ * If label is 0, this is considered to be an epsilon transition.
*/
struct Transition
{
@@ -221,10 +226,10 @@
unsigned int id;
/**
- * Literal for this transition. This is basically the edge label for
+ * label for this transition. This is basically the edge label for
* the graph.
*/
- char literal;
+ char label;
/**
* State to which this transition leads.
@@ -279,14 +284,14 @@
{
struct Transition *t;
char *state;
- char literal;
+ char label;
for (t = s->transitions_head; NULL != t; t = t->next)
{
- if (0 == t->literal)
- literal = '0';
+ if (0 == t->label)
+ label = '0';
else
- literal = t->literal;
+ label = t->label;
if (NULL == t->to_state)
state = "NULL";
@@ -294,7 +299,7 @@
state = t->to_state->name;
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id,
- literal, state);
+ label, state);
}
}
@@ -460,16 +465,16 @@
}
/**
- * Adds a transition from one state to another on 'literal'
+ * Adds a transition from one state to another on 'label'
*
* @param ctx context
* @param from_state starting state for the transition
- * @param literal transition label
+ * @param label transition label
* @param to_state state to where the transition should point to
*/
static void
state_add_transition (struct GNUNET_REGEX_Context *ctx,
- struct GNUNET_REGEX_State *from_state, const char
literal,
+ struct GNUNET_REGEX_State *from_state, const char label,
struct GNUNET_REGEX_State *to_state)
{
struct Transition *t;
@@ -483,7 +488,7 @@
t = GNUNET_malloc (sizeof (struct Transition));
t->id = ctx->transition_id++;
- t->literal = literal;
+ t->label = label;
t->to_state = to_state;
t->from_state = from_state;
@@ -620,10 +625,10 @@
{
for (t = s1->transitions_head; NULL != t; t = t->next)
{
- if (t_check->literal != t->literal && NULL != t_check->to_state &&
+ if (t_check->label != t->label && NULL != t_check->to_state &&
t_check->to_state != t->to_state && t_check->to_state != s2)
{
- state_add_transition (ctx, s1, t_check->literal, t_check->to_state);
+ state_add_transition (ctx, s1, t_check->label, t_check->to_state);
}
}
}
@@ -658,7 +663,55 @@
a->state_count++;
}
+typedef void (*GNUNET_REGEX_traverse_action)(void *cls, struct
+ GNUNET_REGEX_State *s);
+
/**
+ * Traverses all states that are reachable from state 's'. Expects
+ * the states to be unmarked (s->marked == GNUNET_NO). Performs
+ * 'action' on each visited state.
+ *
+ * @param s start state.
+ * @param action action to be performed on each state.
+ */
+static void
+automaton_state_traverse (void *cls, struct GNUNET_REGEX_State *s,
+ GNUNET_REGEX_traverse_action action)
+{
+ struct Transition *t;
+
+ if (GNUNET_NO == s->marked)
+ {
+ s->marked = GNUNET_YES;
+
+ if (NULL != action)
+ action (cls, s);
+
+ for (t = s->transitions_head; NULL != t; t = t->next)
+ automaton_state_traverse (cls, t->to_state, action);
+ }
+}
+
+/**
+ * Traverses the given automaton from it's start state, visiting all
+ * reachable states and calling 'action' on each one of them.
+ *
+ * @param a automaton.
+ * @param action action to be performed on each state.
+ */
+static void
+automaton_traverse (void *cls, struct GNUNET_REGEX_Automaton *a,
+ GNUNET_REGEX_traverse_action action)
+{
+ struct GNUNET_REGEX_State *s;
+
+ for (s = a->start; NULL != s; s = s->next)
+ s->marked = GNUNET_NO;
+
+ automaton_state_traverse (cls, a->start, action);
+}
+
+/**
* Creates a new DFA state based on a set of NFA states. Needs to be freed
* using automaton_destroy_state.
*
@@ -720,16 +773,16 @@
name = NULL;
}
- // Add a transition for each distinct literal to NULL state
+ // Add a transition for each distinct label to NULL state
for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
{
- if (0 != ctran->literal)
+ if (0 != ctran->label)
{
insert = 1;
for (t = s->transitions_head; NULL != t; t = t->next)
{
- if (t->literal == ctran->literal)
+ if (t->label == ctran->label)
{
insert = 0;
break;
@@ -737,7 +790,7 @@
}
if (insert)
- state_add_transition (ctx, s, ctran->literal, NULL);
+ state_add_transition (ctx, s, ctran->label, NULL);
}
}
@@ -753,15 +806,15 @@
/**
* Move from the given state 's' to the next state on
- * transition 'literal'
+ * transition 'label'
*
* @param s starting state
- * @param literal edge label to follow
+ * @param label edge label to follow
*
- * @return new state or NULL, if transition on literal not possible
+ * @return new state or NULL, if transition on label not possible
*/
static struct GNUNET_REGEX_State *
-dfa_move (struct GNUNET_REGEX_State *s, const char literal)
+dfa_move (struct GNUNET_REGEX_State *s, const char label)
{
struct Transition *t;
struct GNUNET_REGEX_State *new_s;
@@ -773,7 +826,7 @@
for (t = s->transitions_head; NULL != t; t = t->next)
{
- if (literal == t->literal)
+ if (label == t->label)
{
new_s = t->to_state;
break;
@@ -783,6 +836,7 @@
return new_s;
}
+
/**
* Remove all unreachable states from DFA 'a'. Unreachable states
* are those states that are not reachable from the starting state.
@@ -792,37 +846,21 @@
static void
dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
{
- struct GNUNET_REGEX_State *stack[a->state_count * a->state_count];
- int stack_len;
struct GNUNET_REGEX_State *s;
struct GNUNET_REGEX_State *s_next;
- struct Transition *t;
- stack_len = 0;
-
// 1. unmark all states
for (s = a->states_head; NULL != s; s = s->next)
- s->marked = 0;
+ s->marked = GNUNET_NO;
// 2. traverse dfa from start state and mark all visited states
- stack[stack_len++] = a->start;
- while (stack_len > 0)
- {
- s = stack[--stack_len];
- s->marked = 1; // mark s as visited
- for (t = s->transitions_head; NULL != t; t = t->next)
- {
- // add next states to stack
- if (NULL != t->to_state && 0 == t->to_state->marked)
- stack[stack_len++] = t->to_state;
- }
- }
+ automaton_traverse (NULL, a, NULL);
// 3. delete all states that were not visited
for (s = a->states_head; NULL != s; s = s_next)
{
s_next = s->next;
- if (0 == s->marked)
+ if (GNUNET_NO == s->marked)
{
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Removed state %s\n", s->name);
automaton_remove_state (a, s);
@@ -920,14 +958,14 @@
{
for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
{
- if (t1->literal == t2->literal && t1->to_state == t2->to_state &&
+ if (t1->label == t2->label && t1->to_state == t2->to_state &&
(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->literal;
+ table[s1->marked][s2->marked] = t1->label;
change = 1;
}
- else if (t1->literal != t2->literal && t1->to_state !=
t2->to_state)
+ else if (t1->label != t2->label && t1->to_state != t2->to_state)
{
table[s1->marked][s2->marked] = -1;
change = 1;
@@ -1078,14 +1116,14 @@
*
* @param nfa the NFA containing 's'
* @param s starting point state
- * @param literal transitioning literal on which to base the closure on,
+ * @param label transitioning label on which to base the closure on,
* pass 0 for epsilon transition
*
- * @return sorted nfa closure on 'literal' (epsilon closure if 'literal' is 0)
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
*/
static struct GNUNET_REGEX_StateSet *
nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa,
- struct GNUNET_REGEX_State *s, const char literal)
+ struct GNUNET_REGEX_State *s, const char label)
{
struct GNUNET_REGEX_StateSet *cls;
struct GNUNET_REGEX_StateSet *cls_check;
@@ -1103,7 +1141,7 @@
clsstate->contained = 0;
// Add start state to closure only for epsilon closure
- if (0 == literal)
+ if (0 == label)
GNUNET_array_append (cls->states, cls->len, s);
GNUNET_array_append (cls_check->states, cls_check->len, s);
@@ -1115,7 +1153,7 @@
for (ctran = currentstate->transitions_head; NULL != ctran;
ctran = ctran->next)
{
- if (NULL != ctran->to_state && literal == ctran->literal)
+ if (NULL != ctran->to_state && label == ctran->label)
{
clsstate = ctran->to_state;
@@ -1143,15 +1181,15 @@
*
* @param nfa the NFA containing 's'
* @param states list of states on which to base the closure on
- * @param literal transitioning literal for which to base the closure on,
+ * @param label transitioning label for which to base the closure on,
* pass 0 for epsilon transition
*
- * @return sorted nfa closure on 'literal' (epsilon closure if 'literal' is 0)
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
*/
static struct GNUNET_REGEX_StateSet *
nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa,
struct GNUNET_REGEX_StateSet *states,
- const char literal)
+ const char label)
{
struct GNUNET_REGEX_State *s;
struct GNUNET_REGEX_StateSet *sset;
@@ -1169,7 +1207,7 @@
for (i = 0; i < states->len; i++)
{
s = states->states[i];
- sset = nfa_closure_create (nfa, s, literal);
+ sset = nfa_closure_create (nfa, s, label);
for (j = 0; j < sset->len; j++)
{
@@ -1370,10 +1408,10 @@
* Adds a new nfa fragment to the stack
*
* @param ctx context
- * @param lit literal for nfa transition
+ * @param lit label for nfa transition
*/
static void
-nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit)
+nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit)
{
struct GNUNET_REGEX_Automaton *n;
struct GNUNET_REGEX_State *start;
@@ -1525,7 +1563,7 @@
--atomcount;
nfa_add_concatenation (&ctx);
}
- nfa_add_literal (&ctx, *regexp);
+ nfa_add_label (&ctx, *regexp);
atomcount++;
break;
}
@@ -1624,9 +1662,9 @@
for (ctran = dfa_state->transitions_head; NULL != ctran;
ctran = ctran->next)
{
- if (0 != ctran->literal && NULL == ctran->to_state)
+ if (0 != ctran->label && NULL == ctran->to_state)
{
- tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->literal);
+ tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label);
nfa_set = nfa_closure_set_create (nfa, tmp, 0);
state_set_clear (tmp);
new_dfa_state = dfa_state_create (&ctx, nfa_set);
@@ -1761,7 +1799,7 @@
continue;
}
- if (ctran->literal == 0)
+ if (ctran->label == 0)
{
GNUNET_asprintf (&s_tran,
"\"%s\" -> \"%s\" [label = \"epsilon\", color=\"0.%i
0.8 0.95\"];\n",
@@ -1771,7 +1809,7 @@
{
GNUNET_asprintf (&s_tran,
"\"%s\" -> \"%s\" [label = \"%c\", color=\"0.%i 0.8
0.95\"];\n",
- s->name, ctran->to_state->name, ctran->literal,
+ s->name, ctran->to_state->name, ctran->label,
s->scc_id);
}
@@ -1904,72 +1942,130 @@
}
/**
- * Get the starting state of the given automaton 'a'.
+ * Get the first key for the given 'input_string'. This hashes
+ * the first x bits of the 'input_strings'.
*
- * @param a automaton.
+ * @param input_string string.
+ * @param string_len length of the 'input_string'.
+ * @param key pointer to where to write the hash code.
*
- * @return starting state.
+ * @return number of bits of 'input_string' that have been consumed
+ * to construct the key
*/
-struct GNUNET_REGEX_State *
-GNUNET_REGEX_automaton_get_start (struct GNUNET_REGEX_Automaton *a)
+unsigned int
+GNUNET_REGEX_get_first_key (const char *input_string,
+ unsigned int string_len,
+ GNUNET_HashCode *key)
{
- return a->start;
+ unsigned int size;
+
+ size = string_len < initial_bits ? string_len : initial_bits;
+
+ if (NULL == input_string)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n");
+ return 0;
+ }
+
+ GNUNET_CRYPTO_hash (input_string, size, key);
+
+ return size;
}
/**
- * Get the next states, starting from states 's'.
+ * Check if the given 'proof' matches the given 'key'.
*
- * @param a automaton.
- * @param s states.
- * @param count number of states given in 's'. Will contain number of
- * states that were returned upon return.
+ * @param proof partial regex
+ * @param key hash
*
- * @return next states, 'count' will contain the number of states.
+ * @return GNUNET_OK if the proof is valid for the given key
*/
-struct GNUNET_REGEX_State **
-GNUNET_REGEX_automaton_states_get_next (struct GNUNET_REGEX_Automaton *a,
- struct GNUNET_REGEX_State **s,
- unsigned int *count)
+int
+GNUNET_REGEX_check_proof (const char *proof,
+ const GNUNET_HashCode *key)
{
- struct GNUNET_REGEX_State *states[a->state_count];
- struct GNUNET_REGEX_State *state;
+ return GNUNET_OK;
+}
+
+/**
+ * Get all edges leaving state 's'.
+ *
+ * @param s state.
+ * @param edges all edges leaving 's'.
+ *
+ * @return number of edges.
+ */
+static unsigned int
+state_get_edges (struct GNUNET_REGEX_State *s, struct GNUNET_REGEX_Edge *edges)
+{
struct Transition *t;
- unsigned int cnt;
- int i;
+ unsigned int count;
+ if (NULL == s)
+ return 0;
- for (cnt = 0, i = 0; i < *count; i++)
+ count = 0;
+
+ for (t = s->transitions_head; NULL != t; t = t->next)
{
- state = s[i];
- for (t = state->transitions_head; NULL != t; t = t->next)
+ if (NULL != t->to_state)
{
- if (NULL != t && NULL != t->to_state)
- {
- states[cnt++] = t->to_state;
- }
+ edges[count].label = &t->label;
+ edges[count].destination = t->to_state->hash;
+ count++;
}
}
+ return count;
+}
- *count = cnt;
+/**
+ * Iterate over all edges helper function starting from state 's', calling
+ * iterator on for each edge.
+ *
+ * @param s state.
+ * @param iterator iterator function called for each edge.
+ * @param iterator_cls closure.
+ */
+static void
+iterate_edge (struct GNUNET_REGEX_State *s,
+ GNUNET_REGEX_KeyIterator iterator,
+ void *iterator_cls)
+{
+ struct Transition *t;
+ struct GNUNET_REGEX_Edge edges[s->transition_count];
+ unsigned int num_edges;
- return NULL;
+ if (GNUNET_NO == s->marked)
+ {
+ s->marked = GNUNET_YES;
+
+ num_edges = state_get_edges (s, edges);
+
+ iterator (iterator_cls,
+ &s->hash,
+ NULL,
+
+ num_edges,
+ edges);
+
+
+ for (t = s->transitions_head; NULL != t; t = t->next)
+ iterate_edge (t->to_state, iterator, iterator_cls);
+ }
}
/**
- * Hash a set of states.
+ * Iterate over all edges starting from start state of automaton 'a'. Calling
+ * iterator for each edge.
*
* @param a automaton.
- * @param s states.
- * @param count number of states.
- *
- * @return hash.
+ * @param iterator iterator called for each edge.
+ * @param iterator_cls closure.
*/
-struct GNUNET_HashCode
-GNUNET_REGEX_automaton_states_hash (struct GNUNET_REGEX_Automaton *a,
- struct GNUNET_REGEX_State **s,
- unsigned int count)
+void
+GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a,
+ GNUNET_REGEX_KeyIterator iterator,
+ void *iterator_cls)
{
- struct GNUNET_HashCode hash;
-
- return hash;
+ iterate_edge (a->start, iterator, iterator_cls);
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r21001 - in gnunet/src: include regex,
gnunet <=