[GNUnet-SVN] r22275 - gnunet/src/regex

[gnunet]

Author: szengel
Date: 2012-06-25 18:16:08 +0200 (Mon, 25 Jun 2012)
New Revision: 22275

Modified:
   gnunet/src/regex/regex.c
   gnunet/src/regex/test_regex_iterate_api.c
Log:
regex bugfixes and optimizations

Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c    2012-06-25 12:55:31 UTC (rev 22274)
+++ gnunet/src/regex/regex.c    2012-06-25 16:16:08 UTC (rev 22275)
@@ -47,11 +47,6 @@
   unsigned int transition_id;
 
   /**
-   * Unique SCC (Strongly Connected Component) id.
-   */
-  unsigned int scc_id;
-
-  /**
    * DLL of GNUNET_REGEX_Automaton's used as a stack.
    */
   struct GNUNET_REGEX_Automaton *stack_head;
@@ -77,12 +72,12 @@
 struct GNUNET_REGEX_Automaton
 {
   /**
-   * This is a linked list.
+   * Linked list of NFAs used for partial NFA creation.
    */
   struct GNUNET_REGEX_Automaton *prev;
 
   /**
-   * This is a linked list.
+   * Linked list of NFAs used for partial NFA creation.
    */
   struct GNUNET_REGEX_Automaton *next;
 
@@ -93,7 +88,7 @@
   struct GNUNET_REGEX_State *start;
 
   /**
-   * End state of the automaton.
+   * End state of the partial NFA. This is undefined for DFAs
    */
   struct GNUNET_REGEX_State *end;
 
@@ -368,8 +363,8 @@
  * @param stack_size current size of the stack
  */
 static void
-scc_tarjan_strongconnect (struct GNUNET_REGEX_Context *ctx,
-                          struct GNUNET_REGEX_State *v, int *index,
+scc_tarjan_strongconnect (unsigned int *scc_counter,
+                          struct GNUNET_REGEX_State *v, unsigned int *index,
                           struct GNUNET_REGEX_State **stack,
                           unsigned int *stack_size)
 {
@@ -387,7 +382,7 @@
     w = t->to_state;
     if (NULL != w && w->index < 0)
     {
-      scc_tarjan_strongconnect (ctx, w, index, stack, stack_size);
+      scc_tarjan_strongconnect (scc_counter, w, index, stack, stack_size);
       v->lowlink = (v->lowlink > w->lowlink) ? w->lowlink : v->lowlink;
     }
     else if (0 != w->contained)
@@ -401,14 +396,14 @@
 
     if (v != w)
     {
-      ctx->scc_id++;
+      (*scc_counter)++;
       while (v != w)
       {
-        w->scc_id = ctx->scc_id;
+        w->scc_id = *scc_counter;
         w = stack[--(*stack_size)];
         w->contained = 0;
       }
-      w->scc_id = ctx->scc_id;
+      w->scc_id = *scc_counter;
     }
   }
 }
@@ -421,9 +416,10 @@
  * @param a automaton
  */
 static void
-scc_tarjan (struct GNUNET_REGEX_Context *ctx, struct GNUNET_REGEX_Automaton *a)
+scc_tarjan (struct GNUNET_REGEX_Automaton *a)
 {
-  int index;
+  unsigned int index;
+  unsigned int scc_counter;
   struct GNUNET_REGEX_State *v;
   struct GNUNET_REGEX_State *stack[a->state_count];
   unsigned int stack_size;
@@ -437,11 +433,12 @@
 
   stack_size = 0;
   index = 0;
+  scc_counter = 0;
 
   for (v = a->states_head; NULL != v; v = v->next)
   {
     if (v->index < 0)
-      scc_tarjan_strongconnect (ctx, v, &index, stack, &stack_size);
+      scc_tarjan_strongconnect (&scc_counter, v, &index, stack, &stack_size);
   }
 }
 
@@ -840,12 +837,39 @@
 needs_parentheses (const char *str)
 {
   size_t slen;
+  const char *op;
+  const char *cl;
+  const char *pos;
+  unsigned int cnt;
 
   if ( (NULL == str) ||
-       ((slen = strlen(str)) < 2) ||
-       ( ('(' == str[0]) && (')' == str[slen-1]) ) )
+       ((slen = strlen(str)) < 2) )
     return GNUNET_NO;
-  return GNUNET_YES;
+  
+  if ('(' != str[0])
+    return GNUNET_YES;
+  cnt = 1;
+  pos = &str[1];
+  while (cnt > 0)
+  {
+    cl = strchr (pos, ')');
+    if (NULL == cl)
+    {
+      GNUNET_break (0);
+      return GNUNET_YES;
+    }
+    op = strchr (pos, '(');
+    if ( (NULL != op) && (op < cl))
+    {
+      cnt++;
+      pos = op + 1;
+      continue;
+    }
+    /* got ')' first */
+    cnt--;
+    pos = cl + 1;
+  }
+  return (*pos == '\0') ? GNUNET_NO : GNUNET_YES;
 }
 
 
@@ -948,7 +972,14 @@
   return strcmp (str1, str2);
 }
 
-
+/** 
+ * Helper function used as 'action' in '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)
 {
@@ -2192,7 +2223,6 @@
   }
   ctx->state_id = 0;
   ctx->transition_id = 0;
-  ctx->scc_id = 0;
   ctx->stack_head = NULL;
   ctx->stack_tail = NULL;
 }
@@ -2456,9 +2486,6 @@
   // Minimize DFA
   dfa_minimize (&ctx, dfa);
 
-  // Calculate SCCs
-  scc_tarjan (&ctx, dfa);
-
   // Create proofs for all states
   automaton_create_proofs (dfa);
 
@@ -2607,6 +2634,9 @@
     return;
   }
 
+  /* First add the SCCs to the automaton, so we can color them nicely */
+  scc_tarjan (a);
+
   start = "digraph G {\nrankdir=LR\n";
   fwrite (start, strlen (start), 1, p);
 

Modified: gnunet/src/regex/test_regex_iterate_api.c
===================================================================
--- gnunet/src/regex/test_regex_iterate_api.c   2012-06-25 12:55:31 UTC (rev 
22274)
+++ gnunet/src/regex/test_regex_iterate_api.c   2012-06-25 16:16:08 UTC (rev 
22275)
@@ -65,7 +65,7 @@
   /* regex = "(bla)*"; */
   /*regex = "b(lab)*la"; */
   /* regex = "(ab)*"; */
-  /*regex = "ab(c|d)+c*(a(b|c)+d)+(bla)(bla)*"; */
+  regex = "ab(c|d)+c*(a(b|c)+d)+(bla)(bla)*";
   /*regex = "z(abc|def)?xyz"; */
   /* regex = "1*0(0|1)*"; */
   /* regex = "a*b*"; */
@@ -83,8 +83,7 @@
   /* regex = "(ab)+"; */
   /* regex = "(ab|cs|df|sdf)*"; */
   /* regex = "(ab|cd)*"; */
-  regex = "(cd|ab)*";
-  regex = "(cd|ab)*";
+  /* regex = "(cd|ab)*"; */
   /* regex = "(ab|c)+"; */
   /* regex = "(a|bc)+"; */
   /* regex = "(ab|c)(ab|c)*"; */