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

[gnunet]

Author: szengel
Date: 2012-08-13 18:17:51 +0200 (Mon, 13 Aug 2012)
New Revision: 23212

Modified:
   gnunet/src/regex/regex.c
   gnunet/src/regex/regex_graph.c
   gnunet/src/regex/regex_internal.h
Log:
using strings as labels


Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c    2012-08-13 15:51:41 UTC (rev 23211)
+++ gnunet/src/regex/regex.c    2012-08-13 16:17:51 UTC (rev 23212)
@@ -143,13 +143,13 @@
 {
   char *to_state;
   char *from_state;
-  char label;
+  char *label;
 
   if (NULL == t)
     return;
 
   if (0 == t->label)
-    label = '0';
+    label = "0";
   else
     label = t->label;
 
@@ -163,7 +163,7 @@
   else
     from_state = t->from_state->name;
 
-  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %c to %s\n",
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: From %s on %s to %s\n",
               t->id, from_state, label, to_state);
 }
 
@@ -179,6 +179,26 @@
 
 
 /**
+ * Compare two strings for equality. If either is NULL they are not equal.
+ *
+ * @param str1 first string for comparison.
+ * @param str2 second string for comparison.
+ *
+ * @return 0 if the strings are the same or both NULL, 1 or -1 if not.
+ */
+static int
+nullstrcmp (const char *str1, const char *str2)
+{
+  if ((NULL == str1) != (NULL == str2))
+    return -1;
+  if ((NULL == str1) && (NULL == str2))
+    return 0;
+
+  return strcmp (str1, str2);
+}
+
+
+/**
  * Adds a transition from one state to another on 'label'. Does not add
  * duplicate states.
  *
@@ -189,7 +209,7 @@
  */
 static void
 state_add_transition (struct GNUNET_REGEX_Context *ctx,
-                      struct GNUNET_REGEX_State *from_state, const char label,
+                      struct GNUNET_REGEX_State *from_state, const char *label,
                       struct GNUNET_REGEX_State *to_state)
 {
   int is_dup;
@@ -206,7 +226,7 @@
   is_dup = GNUNET_NO;
   for (t = from_state->transitions_head; NULL != t; t = t->next)
   {
-    if (t->to_state == to_state && t->label == label &&
+    if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) &&
         t->from_state == from_state)
     {
       is_dup = GNUNET_YES;
@@ -220,13 +240,16 @@
   // sort transitions by label
   for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
   {
-    if (oth->label > label)
+    if (0 < nullstrcmp (oth->label, label))
       break;
   }
 
   t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition));
   t->id = ctx->transition_id++;
-  t->label = label;
+  if (NULL != label)
+    t->label = GNUNET_strdup (label);
+  else
+    t->label = NULL;
   t->to_state = to_state;
   t->from_state = from_state;
 
@@ -256,6 +279,7 @@
   state->transition_count--;
   GNUNET_CONTAINER_DLL_remove (state->transitions_head, 
state->transitions_tail,
                                transition);
+  GNUNET_free_non_null (transition->label);
   GNUNET_free (transition);
 }
 
@@ -307,7 +331,7 @@
   {
     if (NULL != t->to_state)
     {
-      edges[count].label = &t->label;
+      edges[count].label = t->label;
       edges[count].destination = t->to_state->hash;
       count++;
     }
@@ -408,6 +432,7 @@
   {
     next_t = t->next;
     GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t);
+    GNUNET_free_non_null (t->label);
     GNUNET_free (t);
   }
 
@@ -500,7 +525,7 @@
         is_dup = GNUNET_NO;
         for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
         {
-          if (t->to_state == s1 && t_check->label == t->label)
+          if (t->to_state == s1 && 0 == strcmp (t_check->label, t->label))
             is_dup = GNUNET_YES;
         }
         if (GNUNET_NO == is_dup)
@@ -735,24 +760,6 @@
 
 
 /**
- * Compare two strings for equality. If either is NULL (or if both are
- * NULL), they are not equal.
- *
- * @param str1 first string for comparison.
- * @param str2 second string for comparison.
- *
- * @return  0 if the strings are the same, 1 or -1 if not
- */
-static int
-nullstrcmp (const char *str1, const char *str2)
-{
-  if ((NULL == str1) || (NULL == str2))
-    return -1;
-  return strcmp (str1, str2);
-}
-
-
-/**
  * Helper function used as 'action' in 'GNUNET_REGEX_automaton_traverse' 
function to create
  * the depth-first numbering of the states.
  *
@@ -1180,11 +1187,11 @@
     {
       j = t->to_state->proof_id;
       if (NULL == R_last[i][j])
-        GNUNET_asprintf (&R_last[i][j], "%c", t->label);
+        GNUNET_asprintf (&R_last[i][j], "%s", t->label);
       else
       {
         temp = R_last[i][j];
-        GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label);
+        GNUNET_asprintf (&R_last[i][j], "%s|%s", R_last[i][j], t->label);
         GNUNET_free (temp);
       }
     }
@@ -1342,7 +1349,7 @@
     // Add a transition for each distinct label to NULL state
     for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
     {
-      if (0 != ctran->label)
+      if (NULL != ctran->label)
         state_add_transition (ctx, s, ctran->label, NULL);
     }
 
@@ -1367,7 +1374,7 @@
  * @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 label)
+dfa_move (struct GNUNET_REGEX_State *s, const char *label)
 {
   struct GNUNET_REGEX_Transition *t;
   struct GNUNET_REGEX_State *new_s;
@@ -1379,7 +1386,9 @@
 
   for (t = s->transitions_head; NULL != t; t = t->next)
   {
-    if (label == t->label)
+    // TODO: Use strstr to match substring and return number of char's that 
have
+    // been consumed'
+    if (0 == strcmp (label, t->label))
     {
       new_s = t->to_state;
       break;
@@ -1517,13 +1526,13 @@
         {
           for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
           {
-            if (t1->label == t2->label)
+            if (0 == strcmp (t1->label, t2->label))
             {
               num_equal_edges++;
               if (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->label != 0 ? t1->label : 1;
+                table[s1->marked][s2->marked] = 1;
                 change = 1;
               }
             }
@@ -1686,13 +1695,13 @@
  * @param nfa the NFA containing 's'
  * @param s starting point state
  * @param label transitioning label on which to base the closure on,
- *                pass 0 for epsilon transition
+ *                pass NULL for epsilon transition
  *
- * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
  */
 static struct GNUNET_REGEX_StateSet *
 nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa,
-                    struct GNUNET_REGEX_State *s, const char label)
+                    struct GNUNET_REGEX_State *s, const char *label)
 {
   struct GNUNET_REGEX_StateSet *cls;
   struct GNUNET_REGEX_StateSet *cls_check;
@@ -1710,7 +1719,7 @@
     clsstate->contained = 0;
 
   // Add start state to closure only for epsilon closure
-  if (0 == label)
+  if (NULL == label)
     GNUNET_array_append (cls->states, cls->len, s);
 
   GNUNET_array_append (cls_check->states, cls_check->len, s);
@@ -1722,7 +1731,7 @@
     for (ctran = currentstate->transitions_head; NULL != ctran;
          ctran = ctran->next)
     {
-      if (NULL != ctran->to_state && label == ctran->label)
+      if (NULL != ctran->to_state && 0 == nullstrcmp (label, ctran->label))
       {
         clsstate = ctran->to_state;
 
@@ -1753,13 +1762,13 @@
  * @param nfa the NFA containing 's'
  * @param states list of states on which to base the closure on
  * @param label transitioning label for which to base the closure on,
- *                pass 0 for epsilon transition
+ *                pass NULL for epsilon transition
  *
- * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0)
+ * @return sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
  */
 static struct GNUNET_REGEX_StateSet *
 nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa,
-                        struct GNUNET_REGEX_StateSet *states, const char label)
+                        struct GNUNET_REGEX_StateSet *states, const char 
*label)
 {
   struct GNUNET_REGEX_State *s;
   struct GNUNET_REGEX_StateSet *sset;
@@ -1823,7 +1832,7 @@
   GNUNET_assert (NULL != a);
   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 
-  state_add_transition (ctx, a->end, 0, b->start);
+  state_add_transition (ctx, a->end, NULL, b->start);
   a->end->accepting = 0;
   b->end->accepting = 1;
 
@@ -1866,10 +1875,10 @@
   start = nfa_state_create (ctx, 0);
   end = nfa_state_create (ctx, 1);
 
-  state_add_transition (ctx, start, 0, a->start);
-  state_add_transition (ctx, start, 0, end);
-  state_add_transition (ctx, a->end, 0, a->start);
-  state_add_transition (ctx, a->end, 0, end);
+  state_add_transition (ctx, start, NULL, a->start);
+  state_add_transition (ctx, start, NULL, end);
+  state_add_transition (ctx, a->end, NULL, a->start);
+  state_add_transition (ctx, a->end, NULL, end);
 
   a->end->accepting = 0;
   end->accepting = 1;
@@ -1895,7 +1904,7 @@
   a = ctx->stack_tail;
   GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);
 
-  state_add_transition (ctx, a->end, 0, a->start);
+  state_add_transition (ctx, a->end, NULL, a->start);
 
   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
 }
@@ -1928,9 +1937,9 @@
   start = nfa_state_create (ctx, 0);
   end = nfa_state_create (ctx, 1);
 
-  state_add_transition (ctx, start, 0, a->start);
-  state_add_transition (ctx, start, 0, end);
-  state_add_transition (ctx, a->end, 0, end);
+  state_add_transition (ctx, start, NULL, a->start);
+  state_add_transition (ctx, start, NULL, end);
+  state_add_transition (ctx, a->end, NULL, end);
 
   a->end->accepting = 0;
 
@@ -1966,11 +1975,11 @@
 
   start = nfa_state_create (ctx, 0);
   end = nfa_state_create (ctx, 1);
-  state_add_transition (ctx, start, 0, a->start);
-  state_add_transition (ctx, start, 0, b->start);
+  state_add_transition (ctx, start, NULL, a->start);
+  state_add_transition (ctx, start, NULL, b->start);
 
-  state_add_transition (ctx, a->end, 0, end);
-  state_add_transition (ctx, b->end, 0, end);
+  state_add_transition (ctx, a->end, NULL, end);
+  state_add_transition (ctx, b->end, NULL, end);
 
   a->end->accepting = 0;
   b->end->accepting = 0;
@@ -1990,10 +1999,10 @@
  * Adds a new nfa fragment to the stack
  *
  * @param ctx context
- * @param lit label for nfa transition
+ * @param label label for nfa transition
  */
 static void
-nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit)
+nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char *label)
 {
   struct GNUNET_REGEX_Automaton *n;
   struct GNUNET_REGEX_State *start;
@@ -2003,7 +2012,7 @@
 
   start = nfa_state_create (ctx, 0);
   end = nfa_state_create (ctx, 1);
-  state_add_transition (ctx, start, lit, end);
+  state_add_transition (ctx, start, label, end);
   n = nfa_fragment_create (start, end);
   GNUNET_assert (NULL != n);
   GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
@@ -2044,6 +2053,7 @@
   struct GNUNET_REGEX_Context ctx;
   struct GNUNET_REGEX_Automaton *nfa;
   const char *regexp;
+  char curlabel[2];
   char *error_msg;
   unsigned int count;
   unsigned int altcount;
@@ -2058,6 +2068,7 @@
   GNUNET_REGEX_context_init (&ctx);
 
   regexp = regex;
+  curlabel[1] = '\0';
   p = NULL;
   error_msg = NULL;
   altcount = 0;
@@ -2147,7 +2158,8 @@
         --atomcount;
         nfa_add_concatenation (&ctx);
       }
-      nfa_add_label (&ctx, *regexp);
+      curlabel[0] = *regexp;
+      nfa_add_label (&ctx, curlabel);
       atomcount++;
       break;
     }
@@ -2221,7 +2233,7 @@
 
   for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
   {
-    if (0 == ctran->label || NULL != ctran->to_state)
+    if (NULL == ctran->label || NULL != ctran->to_state)
       continue;
 
     tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label);
@@ -2343,6 +2355,7 @@
 evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
 {
   const char *strp;
+  char str[2];
   struct GNUNET_REGEX_State *s;
 
   if (DFA != a->type)
@@ -2358,9 +2371,11 @@
   if ((NULL == string || 0 == strlen (string)) && s->accepting)
     return 0;
 
+  str[1] = '\0';
   for (strp = string; NULL != strp && *strp; strp++)
   {
-    s = dfa_move (s, *strp);
+    str[0] = *strp;
+    s = dfa_move (s, str);
     if (NULL == s)
       break;
   }
@@ -2384,6 +2399,7 @@
 evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
 {
   const char *strp;
+  char str[2];
   struct GNUNET_REGEX_State *s;
   struct GNUNET_REGEX_StateSet *sset;
   struct GNUNET_REGEX_StateSet *new_sset;
@@ -2404,9 +2420,11 @@
   result = 1;
   sset = nfa_closure_create (a, a->start, 0);
 
+  str[1] = '\0';
   for (strp = string; NULL != strp && *strp; strp++)
   {
-    new_sset = nfa_closure_set_create (a, sset, *strp);
+    str[0] = *strp;
+    new_sset = nfa_closure_set_create (a, sset, str);
     state_set_clear (sset);
     sset = nfa_closure_set_create (a, new_sset, 0);
     state_set_clear (new_sset);
@@ -2549,7 +2567,6 @@
                       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;
@@ -2560,9 +2577,7 @@
   {
     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].label = t->label;
       edges[i].destination = t->to_state->hash;
     }
 
@@ -2577,9 +2592,9 @@
     for (t = state->transitions_head; NULL != t; t = t->next)
     {
       if (NULL != consumed_string)
-        GNUNET_asprintf (&temp, "%s%c", consumed_string, t->label);
+        GNUNET_asprintf (&temp, "%s%s", consumed_string, t->label);
       else
-        GNUNET_asprintf (&temp, "%c", t->label);
+        GNUNET_asprintf (&temp, "%s", t->label);
 
       iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state,
                             iterator, iterator_cls);
@@ -2626,12 +2641,12 @@
       if (NULL != consumed_string)
       {
         temp = consumed_string;
-        GNUNET_asprintf (&consumed_string, "%s%c", consumed_string,
+        GNUNET_asprintf (&consumed_string, "%s%s", consumed_string,
                          s->transitions_head->label);
         GNUNET_free (temp);
       }
       else
-        GNUNET_asprintf (&consumed_string, "%c", s->transitions_head->label);
+        GNUNET_asprintf (&consumed_string, "%s", s->transitions_head->label);
 
       s = s->transitions_head->to_state;
       cur_len++;

Modified: gnunet/src/regex/regex_graph.c
===================================================================
--- gnunet/src/regex/regex_graph.c      2012-08-13 15:51:41 UTC (rev 23211)
+++ gnunet/src/regex/regex_graph.c      2012-08-13 16:17:51 UTC (rev 23212)
@@ -188,7 +188,8 @@
   }
   else if (GNUNET_YES == ctx->coloring)
   {
-    GNUNET_asprintf (&s_acc, "\"%s\" [shape=circle, color=\"0.%i 0.8 
0.95\"];\n", name,
+    GNUNET_asprintf (&s_acc,
+                     "\"%s\" [shape=circle, color=\"0.%i 0.8 0.95\"];\n", name,
                      s->scc_id);
   }
   else
@@ -224,7 +225,7 @@
     else
       GNUNET_asprintf (&to_name, "%i", ctran->to_state->proof_id);
 
-    if (ctran->label == 0)
+    if (NULL == ctran->label)
     {
       if (GNUNET_YES == ctx->coloring)
       {
@@ -234,8 +235,8 @@
       }
       else
       {
-        GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n",
-                         name, to_name, s->scc_id);
+        GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"ε\"];\n", name,
+                         to_name, s->scc_id);
       }
     }
     else
@@ -243,12 +244,12 @@
       if (GNUNET_YES == ctx->coloring)
       {
         GNUNET_asprintf (&s_tran,
-                         "\"%s\" -> \"%s\" [label = \"%c\", color=\"0.%i 0.8 
0.95\"];\n",
+                         "\"%s\" -> \"%s\" [label = \"%s\", color=\"0.%i 0.8 
0.95\"];\n",
                          name, to_name, ctran->label, s->scc_id);
       }
       else
       {
-        GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%c\"];\n", name,
+        GNUNET_asprintf (&s_tran, "\"%s\" -> \"%s\" [label = \"%s\"];\n", name,
                          to_name, ctran->label, s->scc_id);
       }
     }

Modified: gnunet/src/regex/regex_internal.h
===================================================================
--- gnunet/src/regex/regex_internal.h   2012-08-13 15:51:41 UTC (rev 23211)
+++ gnunet/src/regex/regex_internal.h   2012-08-13 16:17:51 UTC (rev 23212)
@@ -66,7 +66,7 @@
   /**
    * Label for this transition. This is basically the edge label for the graph.
    */
-  char label;
+  char *label;
 
   /**
    * State to which this transition leads.