[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r25468 - gnunet/src/regex
From: |
gnunet |
Subject: |
[GNUnet-SVN] r25468 - gnunet/src/regex |
Date: |
Thu, 13 Dec 2012 21:10:13 +0100 |
Author: grothoff
Date: 2012-12-13 21:10:13 +0100 (Thu, 13 Dec 2012)
New Revision: 25468
Modified:
gnunet/src/regex/regex.c
Log:
-fix
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-12-13 20:07:15 UTC (rev 25467)
+++ gnunet/src/regex/regex.c 2012-12-13 20:10:13 UTC (rev 25468)
@@ -1934,6 +1934,75 @@
/**
+ * Calculates the NFA closure set for the given state.
+ *
+ * @param cls set to sorted nfa closure on 'label' (epsilon closure if 'label'
is NULL)
+ * @param nfa the NFA containing 's'
+ * @param s starting point state
+ * @param label transitioning label on which to base the closure on,
+ * pass NULL for epsilon transition
+ */
+static void
+nfa_closure_create (struct GNUNET_REGEX_StateSet *cls,
+ struct GNUNET_REGEX_Automaton *nfa,
+ struct GNUNET_REGEX_State *s, const char *label)
+{
+ unsigned int i;
+ struct GNUNET_REGEX_StateSet_MDLL cls_stack;
+ struct GNUNET_REGEX_State *clsstate;
+ struct GNUNET_REGEX_State *currentstate;
+ struct GNUNET_REGEX_Transition *ctran;
+
+ memset (cls, 0, sizeof (struct GNUNET_REGEX_StateSet));
+ if (NULL == s)
+ return;
+
+ cls_stack.head = NULL;
+ cls_stack.tail = NULL;
+
+ /* Add start state to closure only for epsilon closure */
+ if (NULL == label)
+ state_set_append (cls, s);
+
+ GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s);
+ cls_stack.len = 1;
+
+ while (cls_stack.len > 0)
+ {
+ currentstate = cls_stack.tail;
+ GNUNET_CONTAINER_MDLL_remove (ST, cls_stack.head, cls_stack.tail,
+ currentstate);
+ cls_stack.len--;
+
+ for (ctran = currentstate->transitions_head; NULL != ctran;
+ ctran = ctran->next)
+ {
+ if (NULL == (clsstate = ctran->to_state))
+ continue;
+ if (0 != nullstrcmp (label, ctran->label))
+ continue;
+ if (0 == clsstate->contained)
+ {
+ state_set_append (cls, clsstate);
+ GNUNET_CONTAINER_MDLL_insert_tail (ST, cls_stack.head, cls_stack.tail,
+ clsstate);
+ cls_stack.len++;
+ clsstate->contained = 1;
+ }
+ }
+ }
+
+ for (i = 0; i < cls->off; i++)
+ cls->states[i]->contained = 0;
+
+ /* sort the states */
+ if (cls->off > 1)
+ qsort (cls->states, cls->off, sizeof (struct GNUNET_REGEX_State *),
+ &state_compare);
+}
+
+
+/**
* Calculates the closure set for the given set of states.
*
* @param ret set to sorted nfa closure on 'label' (epsilon closure if 'label'
is NULL)
@@ -1948,11 +2017,11 @@
struct GNUNET_REGEX_StateSet *states, const char
*label)
{
struct GNUNET_REGEX_State *s;
+ struct GNUNET_REGEX_StateSet sset;
unsigned int i;
- struct GNUNET_REGEX_StateSet_MDLL cls_stack;
- struct GNUNET_REGEX_State *clsstate;
- struct GNUNET_REGEX_State *currentstate;
- struct GNUNET_REGEX_Transition *ctran;
+ unsigned int j;
+ unsigned int k;
+ unsigned int contains;
memset (ret, 0, sizeof (struct GNUNET_REGEX_StateSet));
if (NULL == states)
@@ -1961,41 +2030,23 @@
for (i = 0; i < states->off; i++)
{
s = states->states[i];
-
- /* 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_insert (ST, cls_stack.head, cls_stack.tail, s);
- cls_stack.len = 1;
-
- while (NULL != (currentstate = cls_stack.tail))
+ nfa_closure_create (&sset, nfa, s, label);
+ for (j = 0; j < sset.off; j++)
{
- GNUNET_CONTAINER_MDLL_remove (ST, cls_stack.head, cls_stack.tail,
- currentstate);
- cls_stack.len--;
- for (ctran = currentstate->transitions_head; NULL != ctran;
- ctran = ctran->next)
+ contains = 0;
+ for (k = 0; k < ret->off; k++)
{
- if (NULL == (clsstate = ctran->to_state))
- continue;
- if (0 != clsstate->contained)
- continue;
- if (0 != nullstrcmp (label, ctran->label))
- continue;
- state_set_append (ret, clsstate);
- GNUNET_CONTAINER_MDLL_insert_tail (ST, cls_stack.head, cls_stack.tail,
- clsstate);
- cls_stack.len++;
- clsstate->contained = 1;
- }
+ if (sset.states[j]->id == ret->states[k]->id)
+ {
+ contains = 1;
+ break;
+ }
+ }
+ if (!contains)
+ state_set_append (ret, sset.states[j]);
}
+ state_set_clear (&sset);
}
- for (i = 0; i < ret->off; i++)
- ret->states[i]->contained = 0;
if (ret->off > 1)
qsort (ret->states, ret->off, sizeof (struct GNUNET_REGEX_State *),
@@ -2418,20 +2469,7 @@
return NULL;
}
-static unsigned long long doopy,loopy;
-static const struct GNUNET_HashCode *
-get_state_key (struct GNUNET_REGEX_StateSet *nfa_set)
-{
- static struct GNUNET_HashCode key;
-
- GNUNET_CRYPTO_hash (nfa_set->states,
- sizeof (struct GNUNET_REGEX_State *) * nfa_set->off,
- &key);
- return &key;
-}
-
-
/**
* Create DFA states based on given 'nfa' and starting with 'dfa_state'.
*
@@ -2440,22 +2478,19 @@
* @param dfa DFA automaton.
* @param dfa_state current dfa state, pass epsilon closure of first nfa state
* for starting.
- * @param state_map map to find states under their proof quickly
*/
static void
construct_dfa_states (struct GNUNET_REGEX_Context *ctx,
struct GNUNET_REGEX_Automaton *nfa,
struct GNUNET_REGEX_Automaton *dfa,
- struct GNUNET_REGEX_State *dfa_state,
- struct GNUNET_CONTAINER_MultiHashMap *state_map)
+ struct GNUNET_REGEX_State *dfa_state)
{
struct GNUNET_REGEX_Transition *ctran;
- struct GNUNET_REGEX_State *state_iter;
struct GNUNET_REGEX_State *new_dfa_state;
struct GNUNET_REGEX_State *state_contains;
+ struct GNUNET_REGEX_State *state_iter;
struct GNUNET_REGEX_StateSet tmp;
struct GNUNET_REGEX_StateSet nfa_set;
- const struct GNUNET_HashCode *key;
for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
{
@@ -2466,19 +2501,22 @@
nfa_closure_set_create (&nfa_set, nfa, &tmp, NULL);
state_set_clear (&tmp);
- /* FIXME: this O(n) loop can be done in O(1) with a hash map */
- state_contains = GNUNET_CONTAINER_multihashmap_get (state_map,
- key = get_state_key
(&nfa_set));
+ state_contains = NULL;
+ for (state_iter = dfa->states_head; NULL != state_iter;
+ state_iter = state_iter->next)
+ {
+ if (0 == state_set_compare (&state_iter->nfa_set, &nfa_set))
+ {
+ state_contains = state_iter;
+ break;
+ }
+ }
if (NULL == state_contains)
{
new_dfa_state = dfa_state_create (ctx, &nfa_set);
automaton_add_state (dfa, new_dfa_state);
ctran->to_state = new_dfa_state;
- GNUNET_CONTAINER_multihashmap_put (state_map,
- key,
- new_dfa_state,
-
GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
- construct_dfa_states (ctx, nfa, dfa, new_dfa_state, state_map);
+ construct_dfa_states (ctx, nfa, dfa, new_dfa_state);
}
else
{
@@ -2513,8 +2551,6 @@
struct GNUNET_REGEX_Automaton *dfa;
struct GNUNET_REGEX_Automaton *nfa;
struct GNUNET_REGEX_StateSet nfa_start_eps_cls;
- struct GNUNET_REGEX_StateSet singleton_set;
- struct GNUNET_CONTAINER_MultiHashMap *state_map;
GNUNET_REGEX_context_init (&ctx);
@@ -2534,18 +2570,12 @@
dfa->regex = GNUNET_strdup (regex);
/* Create DFA start state from epsilon closure */
- memset (&singleton_set, 0, sizeof (struct GNUNET_REGEX_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);
+ nfa_closure_create (&nfa_start_eps_cls, nfa, nfa->start, NULL);
dfa->start = dfa_state_create (&ctx, &nfa_start_eps_cls);
automaton_add_state (dfa, dfa->start);
fprintf (stderr, "D");
- state_map = GNUNET_CONTAINER_multihashmap_create (1024 * 16, GNUNET_NO);
- construct_dfa_states (&ctx, nfa, dfa, dfa->start, state_map);
- GNUNET_CONTAINER_multihashmap_destroy (state_map);
- fprintf (stderr, "D-X: %llu/%llu\n", loopy, doopy);
+ construct_dfa_states (&ctx, nfa, dfa, dfa->start);
GNUNET_REGEX_automaton_destroy (nfa);
/* Minimize DFA */
@@ -2553,7 +2583,7 @@
dfa_minimize (&ctx, dfa);
/* Create proofs and hashes for all states */
- // automaton_create_proofs (dfa);
+ automaton_create_proofs (dfa);
/* Compress linear DFA paths */
if (1 != max_path_len)
@@ -2651,7 +2681,6 @@
struct GNUNET_REGEX_State *s;
struct GNUNET_REGEX_StateSet sset;
struct GNUNET_REGEX_StateSet new_sset;
- struct GNUNET_REGEX_StateSet singleton_set;
unsigned int i;
int result;
@@ -2667,10 +2696,7 @@
return 0;
result = 1;
- memset (&singleton_set, 0, sizeof (struct GNUNET_REGEX_StateSet));
- state_set_append (&singleton_set, a->start);
- nfa_closure_set_create (&sset, a, &singleton_set, NULL);
- state_set_clear (&singleton_set);
+ nfa_closure_create (&sset, a, a->start, NULL);
str[1] = '\0';
for (strp = string; NULL != strp && *strp; strp++)
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r25468 - gnunet/src/regex,
gnunet <=