[GNUnet-SVN] r22298 - in gnunet/src: include regex

[gnunet]

Author: szengel
Date: 2012-06-26 15:52:08 +0200 (Tue, 26 Jun 2012)
New Revision: 22298

Modified:
   gnunet/src/include/gnunet_regex_lib.h
   gnunet/src/regex/regex.c
   gnunet/src/regex/test_regex_eval_api.c
   gnunet/src/regex/test_regex_proofs.c
Log:
doxygen fixes

Modified: gnunet/src/include/gnunet_regex_lib.h
===================================================================
--- gnunet/src/include/gnunet_regex_lib.h       2012-06-26 13:17:53 UTC (rev 
22297)
+++ gnunet/src/include/gnunet_regex_lib.h       2012-06-26 13:52:08 UTC (rev 
22298)
@@ -111,15 +111,19 @@
 GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a,
                    const char *string);
 
-/**
- * Get the computed regex of the given automaton.
+/** 
+ * Get the canonical regex of the given automaton.
  * When constructing the automaton a proof is computed for each state,
  * consisting of the regular expression leading to this state. A complete
  * regex for the automaton can be computed by combining these proofs.
- * As of now this computed regex is only useful for testing.
+ * As of now this function is only useful for testing.
+ * 
+ * @param a automaton for which the canonical regex should be returned.
+ * 
+ * @return 
  */
 const char *
-GNUNET_REGEX_get_computed_regex (struct GNUNET_REGEX_Automaton *a);
+GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a);
 
 /**
  * Get the first key for the given 'input_string'. This hashes

Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c    2012-06-26 13:17:53 UTC (rev 22297)
+++ gnunet/src/regex/regex.c    2012-06-26 13:52:08 UTC (rev 22298)
@@ -28,6 +28,9 @@
 #include "gnunet_regex_lib.h"
 #include "regex.h"
 
+/**
+ * Constant for how many bits the initial string regex should have.
+ */
 #define INITIAL_BITS 10
 
 /**
@@ -118,9 +121,9 @@
   char *regex;
 
   /**
-   * Computed regex (result of RX->NFA->DFA->RX)
+   * Canonical regex (result of RX->NFA->DFA->RX)
    */
-  char *computed_regex;
+  char *canonical_regex;
 };
 
 /**
@@ -282,9 +285,20 @@
 /*
  * Debug helper functions
  */
+
+/**
+ * Print all the transitions of state 's'.
+ *
+ * @param s state for which to print it's transitions.
+ */
 void
-debug_print_transitions (struct GNUNET_REGEX_State *);
+debug_print_transitions (struct GNUNET_REGEX_State *s);
 
+/**
+ * Print information of the given state 's'.
+ *
+ * @param s state for which debug information should be printed.
+ */
 void
 debug_print_state (struct GNUNET_REGEX_State *s)
 {
@@ -304,6 +318,11 @@
   debug_print_transitions (s);
 }
 
+/**
+ * Print debug information for all states contained in the automaton 'a'.
+ *
+ * @param a automaton for which debug information of it's states should be 
printed.
+ */
 void
 debug_print_states (struct GNUNET_REGEX_Automaton *a)
 {
@@ -313,6 +332,11 @@
     debug_print_state (s);
 }
 
+/**
+ * Print debug information for given transition 't'.
+ *
+ * @param t transition for which to print debug info.
+ */
 void
 debug_print_transition (struct Transition *t)
 {
@@ -351,12 +375,13 @@
     debug_print_transition (t);
 }
 
+
 /**
  * Recursive function doing DFS with 'v' as a start, detecting all SCCs inside
  * the subgraph reachable from 'v'. Used with scc_tarjan function to detect all
  * SCCs inside an automaton.
  *
- * @param ctx context
+ * @param scc_counter counter for numbering the sccs
  * @param v start vertex
  * @param index current index
  * @param stack stack for saving all SCCs
@@ -408,12 +433,12 @@
   }
 }
 
+
 /**
  * Detect all SCCs (Strongly Connected Components) inside the given automaton.
  * SCCs will be marked using the scc_id on each state.
  *
- * @param ctx context
- * @param a automaton
+ * @param a the automaton for which SCCs should be computed and assigned.
  */
 static void
 scc_tarjan (struct GNUNET_REGEX_Automaton *a)
@@ -781,10 +806,8 @@
  * @param action_cls closure for action
  */
 static void
-automaton_state_traverse (struct GNUNET_REGEX_State *s,
-                          unsigned int *count,
-                          GNUNET_REGEX_traverse_action action,
-                         void *action_cls)
+automaton_state_traverse (struct GNUNET_REGEX_State *s, unsigned int *count,
+                          GNUNET_REGEX_traverse_action action, void 
*action_cls)
 {
   struct Transition *t;
 
@@ -795,7 +818,7 @@
     action (action_cls, *count, s);
   (*count)++;
   for (t = s->transitions_head; NULL != t; t = t->next)
-    automaton_state_traverse (t->to_state, count, action, action_cls);  
+    automaton_state_traverse (t->to_state, count, action, action_cls);
 }
 
 
@@ -809,8 +832,7 @@
  */
 static void
 automaton_traverse (struct GNUNET_REGEX_Automaton *a,
-                    GNUNET_REGEX_traverse_action action,
-                   void *action_cls)
+                    GNUNET_REGEX_traverse_action action, void *action_cls)
 {
   unsigned int count;
   struct GNUNET_REGEX_State *s;
@@ -827,7 +849,7 @@
  * using it to generate a regex.
  *
  * Currently only tests for first and last characters being '()' respectively.
- * FIXME: What about "(ab)|(cd)"?  
+ * FIXME: What about "(ab)|(cd)"?
  *
  * @param str string
  *
@@ -842,10 +864,9 @@
   const char *pos;
   unsigned int cnt;
 
-  if ( (NULL == str) ||
-       ((slen = strlen(str)) < 2) )
+  if ((NULL == str) || ((slen = strlen (str)) < 2))
     return GNUNET_NO;
-  
+
   if ('(' != str[0])
     return GNUNET_YES;
   cnt = 1;
@@ -859,7 +880,7 @@
       return GNUNET_YES;
     }
     op = strchr (pos, '(');
-    if ( (NULL != op) && (op < cl))
+    if ((NULL != op) && (op < cl))
     {
       cnt++;
       pos = op + 1;
@@ -879,7 +900,7 @@
  * You need to GNUNET_free the returned string.
  *
  * Currently only tests for first and last characters being '()' respectively.
- * FIXME: What about "(ab)|(cd)"?  
+ * FIXME: What about "(ab)|(cd)"?
  *
  * @param str string, free'd or re-used by this function, can be NULL
  *
@@ -891,7 +912,8 @@
 {
   size_t slen;
 
-  if ( (NULL == str) || ('(' != str[0]) || (str[(slen = strlen(str)) - 1] != 
')') )
+  if ((NULL == str) || ('(' != str[0]) ||
+      (str[(slen = strlen (str)) - 1] != ')'))
     return str;
   memmove (str, &str[1], slen - 2);
   str[slen - 2] = '\0';
@@ -910,7 +932,8 @@
 static int
 has_epsilon (const char *str)
 {
-  return  (NULL != str) && ('(' == str[0]) && ('|' == str[1]) && (')' == 
str[strlen(str) - 1]);
+  return (NULL != str) && ('(' == str[0]) && ('|' == str[1]) &&
+      (')' == str[strlen (str) - 1]);
 }
 
 
@@ -931,28 +954,28 @@
 
   if (NULL == str)
     return NULL;
-  if ( ('(' == str[0]) && ('|' == str[1]) )
+  if (('(' == str[0]) && ('|' == str[1]))
   {
     len = strlen (str);
-    if (')' == str[len-1])    
+    if (')' == str[len - 1])
       return GNUNET_strndup (&str[2], len - 3);
   }
   return GNUNET_strdup (str);
 }
 
-/** 
+/**
  * Compare 'str1', starting from position 'k',  with whole 'str2'
- * 
+ *
  * @param str1 first string to compare, starting from position 'k'
  * @param str2 second string for comparison
  * @param k starting position in 'str1'
- * 
+ *
  * @return -1 if any of the strings is NULL, 0 if equal, non 0 otherwise
  */
 static int
 strkcmp (const char *str1, const char *str2, size_t k)
 {
-  if ( (NULL == str1) || (NULL == str2) || (strlen(str1) < k) )
+  if ((NULL == str1) || (NULL == str2) || (strlen (str1) < k))
     return -1;
   return strcmp (&str1[k], str2);
 }
@@ -962,20 +985,23 @@
  * Compare two strings for equality. If either is NULL (or if both are
  * NULL), they are not equal.
  *
- * @return 0 if the strings are the same, 1 or -1 if not
+ * @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) )
+  if ((NULL == str1) || (NULL == str2))
     return -1;
   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.
@@ -1036,37 +1062,37 @@
   /* Compute regular expressions of length "1" between each pair of states */
   for (i = 0; i < n; i++)
   {
-    for (j=0;j<n;j++)
+    for (j = 0; j < n; j++)
     {
       R_cur[i][j] = NULL;
       R_last[i][j] = NULL;
     }
     for (t = states[i]->transitions_head; NULL != t; t = t->next)
     {
-      j = t->to_state->proof_id;      
+      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], "%c", t->label);
       else
-       {
-         temp_a = R_last[i][j];
-         GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label);
-         GNUNET_free (temp_a);
-       }
+      {
+        temp_a = R_last[i][j];
+        GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label);
+        GNUNET_free (temp_a);
+      }
       if (GNUNET_YES == needs_parentheses (R_last[i][j]))
-        {
-         temp_a = R_last[i][j];
-         GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
-         GNUNET_free (temp_a);
-       }
+      {
+        temp_a = R_last[i][j];
+        GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]);
+        GNUNET_free (temp_a);
+      }
     }
     if (NULL == R_last[i][i])
       GNUNET_asprintf (&R_last[i][i], "");
     else
-      {
-       temp_a = R_last[i][i];
-       GNUNET_asprintf (&R_last[i][i], "(|%s)", R_last[i][i]);
-       GNUNET_free (temp_a);
-      }  
+    {
+      temp_a = R_last[i][i];
+      GNUNET_asprintf (&R_last[i][i], "(|%s)", R_last[i][i]);
+      GNUNET_free (temp_a);
+    }
   }
 
 
@@ -1086,12 +1112,12 @@
         R_cur_r = NULL;
         R_cur_l = NULL;
 
-       // cache results from strcmp, we might need these many times
-       ij_kj_cmp = nullstrcmp (R_last[i][j], R_last[k][j]);
-       ij_ik_cmp = nullstrcmp (R_last[i][j], R_last[i][k]);
-       ik_kk_cmp = nullstrcmp (R_last[i][k], R_last[k][k]);
-       ik_kj_cmp = nullstrcmp (R_last[i][k], R_last[k][j]);
-       kk_kj_cmp = nullstrcmp (R_last[k][k], R_last[k][j]);
+        // cache results from strcmp, we might need these many times
+        ij_kj_cmp = nullstrcmp (R_last[i][j], R_last[k][j]);
+        ij_ik_cmp = nullstrcmp (R_last[i][j], R_last[i][k]);
+        ik_kk_cmp = nullstrcmp (R_last[i][k], R_last[k][k]);
+        ik_kj_cmp = nullstrcmp (R_last[i][k], R_last[k][j]);
+        kk_kj_cmp = nullstrcmp (R_last[k][k], R_last[k][j]);
 
         // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk})^* 
R^{(k-1)}_{kj}
         // With: R_cur[i][j] = R_cur_l | R_cur_r
@@ -1116,19 +1142,19 @@
 
           // Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
           // as parentheses, so we can better compare the contents
-         R_temp_ik = remove_parentheses (remove_epsilon (R_last[i][k]));
+          R_temp_ik = remove_parentheses (remove_epsilon (R_last[i][k]));
           R_temp_kk = remove_parentheses (remove_epsilon (R_last[k][k]));
           R_temp_kj = remove_parentheses (remove_epsilon (R_last[k][j]));
 
           clean_ik_kk_cmp = nullstrcmp (R_last[i][k], R_temp_kk);
           clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last[k][j]);
-          
+
           // construct R_cur_l (and, if necessary R_cur_r)
           if (NULL != R_last[i][j])
           {
             // Assign R_temp_ij to R_last[i][j] and remove epsilon as well
             // as parentheses, so we can better compare the contents
-           R_temp_ij = remove_parentheses (remove_epsilon (R_last[i][j]));
+            R_temp_ij = remove_parentheses (remove_epsilon (R_last[i][j]));
 
             if (0 == strcmp (R_temp_ij, R_temp_ik) &&
                 0 == strcmp (R_temp_ik, R_temp_kk) &&
@@ -1218,7 +1244,8 @@
             else
             {
               /* GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "NO SIMPLIFICATION\n"); 
*/
-             temp_a = (NULL == R_last[i][j]) ? NULL : GNUNET_strdup 
(R_last[i][j]);
+              temp_a =
+                  (NULL == R_last[i][j]) ? NULL : GNUNET_strdup (R_last[i][j]);
               temp_a = remove_parentheses (temp_a);
               R_cur_l = temp_a;
             }
@@ -1431,8 +1458,8 @@
       for (j = 0; j < n; j++)
       {
         GNUNET_free_non_null (R_last[i][j]);
-       R_last[i][j] = R_cur[i][j];
-       R_cur[i][j] = NULL;       
+        R_last[i][j] = R_cur[i][j];
+        R_cur[i][j] = NULL;
       }
     }
   }
@@ -1466,7 +1493,7 @@
       }
     }
   }
-  a->computed_regex = complete_regex;
+  a->canonical_regex = complete_regex;
 
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "---------------------------------------------\n");
@@ -2508,7 +2535,7 @@
     return;
 
   GNUNET_free_non_null (a->regex);
-  GNUNET_free_non_null (a->computed_regex);
+  GNUNET_free_non_null (a->canonical_regex);
 
   for (s = a->states_head; NULL != s;)
   {
@@ -2773,20 +2800,25 @@
   return result;
 }
 
+
 /**
- * Get the computed regex of the given automaton.
+ * Get the canonical regex of the given automaton.
  * When constructing the automaton a proof is computed for each state,
  * consisting of the regular expression leading to this state. A complete
  * regex for the automaton can be computed by combining these proofs.
- * As of now this computed regex is only useful for testing.
+ * As of now this function is only useful for testing.
+ *
+ * @param a automaton for which the canonical regex should be returned.
+ *
+ * @return
  */
 const char *
-GNUNET_REGEX_get_computed_regex (struct GNUNET_REGEX_Automaton *a)
+GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a)
 {
   if (NULL == a)
     return NULL;
 
-  return a->computed_regex;
+  return a->canonical_regex;
 }
 
 /**

Modified: gnunet/src/regex/test_regex_eval_api.c
===================================================================
--- gnunet/src/regex/test_regex_eval_api.c      2012-06-26 13:17:53 UTC (rev 
22297)
+++ gnunet/src/regex/test_regex_eval_api.c      2012-06-26 13:52:08 UTC (rev 
22298)
@@ -71,14 +71,14 @@
   char current_char;
   int eval;
   int eval_check;
-  int eval_computed;
+  int eval_canonical;
   struct GNUNET_REGEX_Automaton *dfa;
   regex_t rx;
   regmatch_t matchptr[1];
   char error[200];
   int result;
   unsigned int str_len;
-  char *computed_regex;
+  char *canonical_regex;
 
   // At least one string is needed for matching
   GNUNET_assert (str_count > 0);
@@ -164,7 +164,7 @@
     }
 
     eval = GNUNET_REGEX_eval (dfa, matching_str[i]);
-    computed_regex = GNUNET_strdup (GNUNET_REGEX_get_computed_regex (dfa));
+    canonical_regex = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (dfa));
     GNUNET_REGEX_automaton_destroy (dfa);
 
     // Match string using glibc regex
@@ -178,18 +178,18 @@
     eval_check = regexec (&rx, matching_str[i], 1, matchptr, 0);
     regfree (&rx);
 
-    // Match computed regex
-    if (0 != regcomp (&rx, computed_regex, REG_EXTENDED))
+    // Match canonical regex
+    if (0 != regcomp (&rx, canonical_regex, REG_EXTENDED))
     {
       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                   "Could not compile regex using regcomp: %s\n",
-                  computed_regex);
+                  canonical_regex);
       return -1;
     }
 
-    eval_computed = regexec (&rx, matching_str[i], 1, matchptr, 0);
+    eval_canonical = regexec (&rx, matching_str[i], 1, matchptr, 0);
     regfree (&rx);
-    GNUNET_free (computed_regex);
+    GNUNET_free (canonical_regex);
 
     // We only want to match the whole string, because that's what our DFA 
does, too.
     if (eval_check == 0 &&
@@ -356,7 +356,7 @@
     // DFA test
     a = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex));
     check_dfa += test_automaton (a, &rx, &rxstr[i]);
-    check_proof = GNUNET_strdup (GNUNET_REGEX_get_computed_regex (a));
+    check_proof = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (a));
     GNUNET_REGEX_automaton_destroy (a);
     a = GNUNET_REGEX_construct_dfa (check_proof, strlen (check_proof));
     check_dfa += test_automaton (a, &rx, &rxstr[i]);
@@ -369,8 +369,8 @@
   }
 
   srand (time (NULL));
-  for (i = 0; i < 50; i++) 
-    check_rand += test_random (100, 120, 20); 
+  for (i = 0; i < 50; i++)
+    check_rand += test_random (100, 120, 20);
 
   return check_nfa + check_dfa + check_rand;
 }

Modified: gnunet/src/regex/test_regex_proofs.c
===================================================================
--- gnunet/src/regex/test_regex_proofs.c        2012-06-26 13:17:53 UTC (rev 
22297)
+++ gnunet/src/regex/test_regex_proofs.c        2012-06-26 13:52:08 UTC (rev 
22298)
@@ -40,6 +40,7 @@
 
   int error;
   int i;
+
   const char *regex[21] = {
     "ab(c|d)+c*(a(b|c)+d)+(bla)+",
     "(bla)*",
@@ -63,7 +64,7 @@
     "(ab|cs|df|sdf)*",
     "a|aa*a"
   };
-  char *computed_regex;
+  char *canonical_regex;
   struct GNUNET_REGEX_Automaton *dfa;
 
   error = 0;
@@ -71,14 +72,18 @@
   for (i = 0; i < 21; i++)
   {
     dfa = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]));
-    computed_regex = GNUNET_strdup (GNUNET_REGEX_get_computed_regex (dfa));
+    canonical_regex = GNUNET_strdup (GNUNET_REGEX_get_canonical_regex (dfa));
     GNUNET_REGEX_automaton_destroy (dfa);
 
-    dfa = GNUNET_REGEX_construct_dfa (computed_regex, strlen (computed_regex));
-    error += (0 == strcmp (computed_regex, GNUNET_REGEX_get_computed_regex 
(dfa))) ? 0 : 1;
-    GNUNET_free (computed_regex);
+    dfa =
+        GNUNET_REGEX_construct_dfa (canonical_regex, strlen (canonical_regex));
+    error +=
+        (0 ==
+         strcmp (canonical_regex,
+                 GNUNET_REGEX_get_canonical_regex (dfa))) ? 0 : 1;
+    GNUNET_free (canonical_regex);
     GNUNET_REGEX_automaton_destroy (dfa);
   }
-  
+
   return error;
 }