[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r24997 - gnunet/src/regex
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r24997 - gnunet/src/regex |
|
Date: |
Fri, 16 Nov 2012 14:08:51 +0100 |
Author: szengel
Date: 2012-11-16 14:08:51 +0100 (Fri, 16 Nov 2012)
New Revision: 24997
Modified:
gnunet/src/regex/gnunet-regex-simulation-profiler.c
gnunet/src/regex/regex.c
gnunet/src/regex/regex_internal.h
gnunet/src/regex/regex_random.c
gnunet/src/regex/regex_simulation_profiler_test.conf
gnunet/src/regex/test_regex_eval_api.c
gnunet/src/regex/test_regex_graph_api.c
gnunet/src/regex/test_regex_iterate_api.c
Log:
Cleaup, indentation, comments etc.
Modified: gnunet/src/regex/gnunet-regex-simulation-profiler.c
===================================================================
--- gnunet/src/regex/gnunet-regex-simulation-profiler.c 2012-11-16 13:08:10 UTC
(rev 24996)
+++ gnunet/src/regex/gnunet-regex-simulation-profiler.c 2012-11-16 13:08:51 UTC
(rev 24997)
@@ -32,26 +32,53 @@
#include "gnunet_mysql_lib.h"
#include <mysql/mysql.h>
+/**
+ * MySQL statement to insert an edge.
+ */
#define INSERT_EDGE_STMT "INSERT IGNORE INTO `%s` "\
"(`key`, `label`, `to_key`, `accepting`) "\
"VALUES (?, ?, ?, ?);"
/**
+ * MySQL statement to select a key count.
+ */
+#define SELECT_KEY_STMT "SELECT COUNT(*) FROM `%s` "\
+ "WHERE `key` = ? AND `label` = ?;"
+
+/**
* Simple struct to keep track of progress, and print a
* nice little percentage meter for long running tasks.
*/
struct ProgressMeter
{
+ /**
+ * Total number of elements.
+ */
unsigned int total;
+ /**
+ * Intervall for printing percentage.
+ */
unsigned int modnum;
+ /**
+ * Number of dots to print.
+ */
unsigned int dotnum;
+ /**
+ * Completed number.
+ */
unsigned int completed;
+ /**
+ * Should the meter be printed?
+ */
int print;
+ /**
+ * String to print on startup.
+ */
char *startup_string;
};
@@ -67,6 +94,11 @@
static GNUNET_SCHEDULER_TaskIdentifier abort_task;
/**
+ * Shutdown task identifier.
+ */
+static GNUNET_SCHEDULER_TaskIdentifier shutdown_task;
+
+/**
* Scan task identifier;
*/
static GNUNET_SCHEDULER_TaskIdentifier scan_task;
@@ -87,6 +119,11 @@
static struct GNUNET_MYSQL_StatementHandle *stmt_handle;
/**
+ * MySQL prepared statement handle for `key` select.
+ */
+static struct GNUNET_MYSQL_StatementHandle *select_stmt_handle;
+
+/**
* MySQL table name.
*/
static char *table_name;
@@ -111,8 +148,23 @@
*/
static unsigned int max_path_compression;
+/**
+ * Number of merged transitions.
+ */
+static unsigned long long num_merged_transitions;
/**
+ * Number of merged states from different policies.
+ */
+static unsigned long long num_merged_states;
+
+/**
+ * Prefix to add before every regex we're announcing.
+ */
+static char *regex_prefix;
+
+
+/**
* Create a meter to keep track of the progress of some task.
*
* @param total the total number of items to complete
@@ -167,7 +219,7 @@
(int) (((float) meter->completed / meter->total) * 100));
}
else if (meter->completed % meter->dotnum == 0)
- FPRINTF (stdout, "%s", ".");
+ FPRINTF (stdout, "%s", ".");
if (meter->completed + 1 == meter->total)
FPRINTF (stdout, "%d%%]\n", 100);
@@ -224,12 +276,15 @@
static void
do_shutdown (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
{
+ shutdown_task = GNUNET_SCHEDULER_NO_TASK;
+ if (GNUNET_SCHEDULER_NO_TASK != abort_task)
+ GNUNET_SCHEDULER_cancel (abort_task);
if (NULL != mysql_ctx)
GNUNET_MYSQL_context_destroy (mysql_ctx);
if (NULL != meter)
free_meter (meter);
- GNUNET_SCHEDULER_shutdown (); /* Stop scheduler to shutdown testbed
run */
+ GNUNET_SCHEDULER_shutdown (); /* Stop scheduler to shutdown testbed run */
}
@@ -252,6 +307,22 @@
/**
+ * Dummy function for prepared select. Always return GNUNET_OK.
+ *
+ * @param cls closure
+ * @param num_values number of values.
+ * @param values returned values from select stmt.
+ *
+ * @return GNUNET_OK
+ */
+static int
+return_ok (void *cls, unsigned int num_values, MYSQL_BIND * values)
+{
+ return GNUNET_OK;
+}
+
+
+/**
* Iterator over all states that inserts each state into the MySQL db.
*
* @param cls closure.
@@ -262,11 +333,8 @@
* @param edges edges leaving current state.
*/
static void
-regex_iterator (void *cls,
- const struct GNUNET_HashCode *key,
- const char *proof,
- int accepting,
- unsigned int num_edges,
+regex_iterator (void *cls, const struct GNUNET_HashCode *key, const char
*proof,
+ int accepting, unsigned int num_edges,
const struct GNUNET_REGEX_Edge *edges)
{
unsigned int i;
@@ -274,6 +342,8 @@
unsigned long k_length;
unsigned long e_length;
unsigned long d_length;
+ MYSQL_BIND rbind[1];
+ unsigned long long total;
GNUNET_assert (NULL != mysql_ctx);
@@ -282,21 +352,71 @@
k_length = sizeof (struct GNUNET_HashCode);
e_length = strlen (edges[i].label);
d_length = sizeof (struct GNUNET_HashCode);
+ memset (rbind, 0, sizeof (rbind));
+ total = -1;
+ rbind[0].buffer_type = MYSQL_TYPE_LONGLONG;
+ rbind[0].buffer = &total;
+ rbind[0].is_unsigned = GNUNET_YES;
result =
- GNUNET_MYSQL_statement_run_prepared (
- mysql_ctx,
- stmt_handle,
- NULL,
- MYSQL_TYPE_BLOB, key, sizeof (struct GNUNET_HashCode), &k_length,
- MYSQL_TYPE_STRING, edges[i].label, strlen (edges[i].label), &e_length,
- MYSQL_TYPE_BLOB, &edges[i].destination, sizeof (struct
GNUNET_HashCode), &d_length,
- MYSQL_TYPE_LONG, &accepting, GNUNET_YES,
- -1);
+ GNUNET_MYSQL_statement_run_prepared_select (mysql_ctx,
+ select_stmt_handle, 1,
+ rbind, &return_ok, NULL,
+ MYSQL_TYPE_BLOB, key,
+ sizeof (struct
+ GNUNET_HashCode),
+ &k_length,
+ MYSQL_TYPE_STRING,
+ edges[i].label,
+ strlen (edges[i].label),
+ &e_length, -1);
- if (1 != result && 0 != result)
+ if (GNUNET_SYSERR == result)
{
GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Error executing prepared mysql select statement\n");
+ GNUNET_SCHEDULER_add_now (&do_abort, NULL);
+ return;
+ }
+
+ if (-1 != total && total > 0)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO, "Total: %llu (%s, %s)\n", total,
+ GNUNET_h2s (key), edges[i].label);
+ }
+
+ result =
+ GNUNET_MYSQL_statement_run_prepared (mysql_ctx, stmt_handle, NULL,
+ MYSQL_TYPE_BLOB, key,
+ sizeof (struct GNUNET_HashCode),
+ &k_length, MYSQL_TYPE_STRING,
+ edges[i].label,
+ strlen (edges[i].label),
&e_length,
+ MYSQL_TYPE_BLOB,
+ &edges[i].destination,
+ sizeof (struct GNUNET_HashCode),
+ &d_length, MYSQL_TYPE_LONG,
+ &accepting, GNUNET_YES, -1);
+
+ if (0 == result)
+ {
+ char *key_str = GNUNET_strdup (GNUNET_h2s (key));
+ char *to_key_str = GNUNET_strdup (GNUNET_h2s (&edges[i].destination));
+
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Merged (%s, %s, %s, %i)\n",
key_str,
+ edges[i].label, to_key_str, accepting);
+ GNUNET_free (key_str);
+ GNUNET_free (to_key_str);
+ num_merged_transitions++;
+ }
+ else if (-1 != total)
+ {
+ num_merged_states++;
+ }
+
+ if (GNUNET_SYSERR == result || (1 != result && 0 != result))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
"Error executing prepared mysql statement for edge: Affected
rows: %i, expected 0 or 1!\n",
result);
GNUNET_SCHEDULER_add_now (&do_abort, NULL);
@@ -310,15 +430,14 @@
d_length = 0;
result =
- GNUNET_MYSQL_statement_run_prepared (
- mysql_ctx,
- stmt_handle,
- NULL,
- MYSQL_TYPE_BLOB, key, sizeof (struct GNUNET_HashCode), &k_length,
- MYSQL_TYPE_STRING, NULL, 0, &e_length,
- MYSQL_TYPE_BLOB, NULL, 0, &d_length,
- MYSQL_TYPE_LONG, &accepting, GNUNET_YES,
- -1);
+ GNUNET_MYSQL_statement_run_prepared (mysql_ctx, stmt_handle, NULL,
+ MYSQL_TYPE_BLOB, key,
+ sizeof (struct GNUNET_HashCode),
+ &k_length, MYSQL_TYPE_STRING,
NULL,
+ 0, &e_length, MYSQL_TYPE_BLOB,
+ NULL, 0, &d_length,
+ MYSQL_TYPE_LONG, &accepting,
+ GNUNET_YES, -1);
if (1 != result && 0 != result)
{
@@ -343,12 +462,13 @@
{
struct GNUNET_REGEX_Automaton *dfa;
- dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex),
max_path_compression);
+ dfa =
+ GNUNET_REGEX_construct_dfa (regex, strlen (regex), max_path_compression);
if (NULL == dfa)
{
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "Failed to create DFA for regex %s\n", regex);
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Failed to create DFA for regex %s\n",
+ regex);
abort_task = GNUNET_SCHEDULER_add_now (&do_abort, NULL);
return GNUNET_SYSERR;
}
@@ -380,21 +500,22 @@
GNUNET_assert (NULL != filename);
- GNUNET_log (GNUNET_ERROR_TYPE_INFO,
- "Announcing regexes from file %s\n",
+ GNUNET_log (GNUNET_ERROR_TYPE_INFO, "Announcing regexes from file %s\n",
filename);
if (GNUNET_YES != GNUNET_DISK_file_test (filename))
{
- GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
- "Could not find policy file %s\n", filename);
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Could not find policy file %s\n",
+ filename);
return GNUNET_OK;
}
- if (GNUNET_OK != GNUNET_DISK_file_size (filename, &filesize, GNUNET_YES,
GNUNET_YES))
+ if (GNUNET_OK !=
+ GNUNET_DISK_file_size (filename, &filesize, GNUNET_YES, GNUNET_YES))
filesize = 0;
if (0 == filesize)
{
- GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Policy file %s is empty.\n",
filename);
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Policy file %s is empty.\n",
+ filename);
return GNUNET_OK;
}
data = GNUNET_malloc (filesize);
@@ -416,24 +537,24 @@
offset++;
if (((data[offset] == '\n')) && (buf != &data[offset]))
{
- data[offset] = '\0';
- regex = buf;
- GNUNET_assert (NULL != regex);
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Announcing regex: %s\n",
- regex);
+ data[offset] = '|';
num_policies++;
-
- if (GNUNET_OK != announce_regex (regex))
- {
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "Could not announce regex %s\n", regex);
- }
-
buf = &data[offset + 1];
}
else if ((data[offset] == '\n') || (data[offset] == '\0'))
buf = &data[offset + 1];
}
+ data[offset] = '\0';
+ GNUNET_asprintf (®ex, "%s(%s)", regex_prefix, data);
+ GNUNET_assert (NULL != regex);
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Announcing regex: %s\n", regex);
+
+ if (GNUNET_OK != announce_regex (regex))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not announce regex %s\n",
+ regex);
+ }
+ GNUNET_free (regex);
GNUNET_free (data);
return GNUNET_OK;
}
@@ -452,32 +573,34 @@
struct GNUNET_TIME_Relative duration;
char *stmt;
- if (GNUNET_SCHEDULER_NO_TASK != abort_task)
- GNUNET_SCHEDULER_cancel (abort_task);
-
/* Create an MySQL prepared statement for the inserts */
GNUNET_asprintf (&stmt, INSERT_EDGE_STMT, table_name);
stmt_handle = GNUNET_MYSQL_statement_prepare (mysql_ctx, stmt);
GNUNET_free (stmt);
+ GNUNET_asprintf (&stmt, SELECT_KEY_STMT, table_name);
+ select_stmt_handle = GNUNET_MYSQL_statement_prepare (mysql_ctx, stmt);
+ GNUNET_free (stmt);
+
GNUNET_assert (NULL != stmt_handle);
- meter = create_meter (num_policy_files, "Announcing policy files\n",
GNUNET_YES);
+ meter =
+ create_meter (num_policy_files, "Announcing policy files\n", GNUNET_YES);
start_time = GNUNET_TIME_absolute_get ();
- GNUNET_DISK_directory_scan (policy_dir,
- &policy_filename_cb,
- stmt_handle);
+ GNUNET_DISK_directory_scan (policy_dir, &policy_filename_cb, stmt_handle);
duration = GNUNET_TIME_absolute_get_duration (start_time);
reset_meter (meter);
free_meter (meter);
meter = NULL;
- printf ("Announced %u files containing %u policies in %s\n",
+ printf ("Announced %u files containing %u policies in %s\n"
+ "Duplicate transitions: %llu\nMerged states: %llu\n",
num_policy_files, num_policies,
- GNUNET_STRINGS_relative_time_to_string (duration, GNUNET_NO));
+ GNUNET_STRINGS_relative_time_to_string (duration, GNUNET_NO),
+ num_merged_transitions, num_merged_states);
result = GNUNET_OK;
- GNUNET_SCHEDULER_add_now (&do_shutdown, NULL);
+ shutdown_task = GNUNET_SCHEDULER_add_now (&do_shutdown, NULL);
}
@@ -495,26 +618,27 @@
{
if (NULL == args[0])
{
- fprintf (stderr, _("No policy directory specified on command line.
Exiting.\n"));
+ fprintf (stderr,
+ _("No policy directory specified on command line. Exiting.\n"));
result = GNUNET_SYSERR;
return;
}
if (GNUNET_YES != GNUNET_DISK_directory_test (args[0], GNUNET_YES))
{
- fprintf (stderr, _("Specified policies directory does not exist.
Exiting.\n"));
+ fprintf (stderr,
+ _("Specified policies directory does not exist. Exiting.\n"));
result = GNUNET_SYSERR;
return;
}
policy_dir = args[0];
- num_policy_files = GNUNET_DISK_directory_scan (policy_dir,
- NULL,
- NULL);
+ num_policy_files = GNUNET_DISK_directory_scan (policy_dir, NULL, NULL);
meter = NULL;
if (NULL == table_name)
{
- GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "No table name specified, using
default \"NFA\".\n");
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+ "No table name specified, using default \"NFA\".\n");
table_name = "NFA";
}
@@ -526,14 +650,27 @@
return;
}
+ if (GNUNET_OK !=
+ GNUNET_CONFIGURATION_get_value_string (config, "regex-mysql",
+ "REGEX_PREFIX", ®ex_prefix))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ _
+ ("%s service is lacking key configuration settings (%s).
Exiting.\n"),
+ "regexprofiler", "regex_prefix");
+ result = GNUNET_SYSERR;
+ return;
+ }
+
+
result = GNUNET_OK;
scan_task = GNUNET_SCHEDULER_add_now (&do_directory_scan, NULL);
- abort_task =
- GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply
- (GNUNET_TIME_UNIT_SECONDS, 10), &do_abort,
- NULL);
+ /* Scheduled the task to clean up when shutdown is called */
+ shutdown_task =
+ GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL, &do_shutdown,
+ NULL);
}
@@ -563,9 +700,9 @@
result = GNUNET_SYSERR;
ret =
- GNUNET_PROGRAM_run (argc, argv, "gnunet-regex-simulationprofiler
[OPTIONS] policy-dir",
- _("Profiler for regex library"),
- options, &run, NULL);
+ GNUNET_PROGRAM_run (argc, argv,
+ "gnunet-regex-simulationprofiler [OPTIONS]
policy-dir",
+ _("Profiler for regex library"), options, &run,
NULL);
if (GNUNET_OK != ret)
return ret;
if (GNUNET_OK != result)
Modified: gnunet/src/regex/regex.c
===================================================================
--- gnunet/src/regex/regex.c 2012-11-16 13:08:10 UTC (rev 24996)
+++ gnunet/src/regex/regex.c 2012-11-16 13:08:51 UTC (rev 24997)
@@ -19,7 +19,9 @@
*/
/**
* @file src/regex/regex.c
- * @brief library to create automatons from regular expressions
+ * @brief library to create Deterministic Finite Automatons (DFAs) from regular
+ * expressions (regexes). Used by mesh for announcing regexes in the network
and
+ * matching strings against published regexes.
* @author Maximilian Szengel
*/
#include "platform.h"
@@ -30,7 +32,7 @@
/**
* Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA
- * creation.
+ * creation. Disabled by default for better performance.
*/
#define REGEX_DEBUG_DFA GNUNET_NO
@@ -115,7 +117,7 @@
return;
}
- // Do not add duplicate state transitions
+ /* Do not add duplicate state transitions */
for (t = from_state->transitions_head; NULL != t; t = t->next)
{
if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) &&
@@ -123,7 +125,7 @@
return;
}
- // sort transitions by label
+ /* sort transitions by label */
for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
{
if (0 < nullstrcmp (oth->label, label))
@@ -140,7 +142,7 @@
t->to_state = to_state;
t->from_state = from_state;
- // Add outgoing transition to 'from_state'
+ /* Add outgoing transition to 'from_state' */
from_state->transition_count++;
GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head,
from_state->transitions_tail, oth, t);
@@ -348,7 +350,7 @@
if (NULL == a || NULL == s)
return;
- // remove all transitions leading to this state
+ /* remove all transitions leading to this state */
for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
{
for (t_check = s_check->transitions_head; NULL != t_check;
@@ -360,7 +362,7 @@
}
}
- // remove state
+ /* remove state */
GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
a->state_count--;
@@ -370,7 +372,7 @@
/**
* Merge two states into one. Will merge 's1' and 's2' into 's1' and destroy
- * 's2'.
+ * 's2'. 's1' will contain all (non-duplicate) outgoing transitions of 's2'.
*
* @param ctx context
* @param a automaton
@@ -395,7 +397,7 @@
return;
/* 1. Make all transitions pointing to s2 point to s1, unless this transition
- does not already exists, if it already exists remove transition. */
+ * does not already exists, if it already exists remove transition. */
for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
{
for (t_check = s_check->transitions_head; NULL != t_check; t_check =
t_next)
@@ -428,6 +430,7 @@
/* 3. Rename s1 to {s1,s2} */
#if REGEX_DEBUG_DFA
char *new_name;
+
new_name = s1->name;
GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name);
GNUNET_free (new_name);
@@ -747,13 +750,14 @@
size_t length_r;
GNUNET_assert (NULL == *R_cur_ij && NULL != R_cur_ij);
+ /*
+ * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^*
R^{(k-1)}_{kj}
+ * R_last == R^{(k-1)}, R_cur == R^{(k)}
+ * R_cur_ij = R_cur_l | R_cur_r
+ * R_cur_l == R^{(k-1)}_{ij}
+ * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
+ */
- // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^*
R^{(k-1)}_{kj}
- // R_last == R^{(k-1)}, R_cur == R^{(k)}
- // R_cur_ij = R_cur_l | R_cur_r
- // R_cur_l == R^{(k-1)}_{ij}
- // R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
-
if ((NULL == R_last_ij) && ((NULL == R_last_ik) || (NULL == R_last_kk) ||
/* technically cannot happen, but looks saner */
(NULL == R_last_kj)))
{
@@ -770,20 +774,20 @@
return;
}
- // $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
- // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^*
R^{(k-1)}_{kj}
+ /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
+ * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^*
R^{(k-1)}_{kj} */
R_cur_r = NULL;
R_cur_l = NULL;
- // cache results from strcmp, we might need these many times
+ /* cache results from strcmp, we might need these many times */
ij_kj_cmp = nullstrcmp (R_last_ij, R_last_kj);
ij_ik_cmp = nullstrcmp (R_last_ij, R_last_ik);
ik_kk_cmp = nullstrcmp (R_last_ik, R_last_kk);
kk_kj_cmp = nullstrcmp (R_last_kk, R_last_kj);
- // Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
- // as parentheses, so we can better compare the contents
+ /* 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_ik));
R_temp_kk = remove_parentheses (remove_epsilon (R_last_kk));
R_temp_kj = remove_parentheses (remove_epsilon (R_last_kj));
@@ -791,11 +795,11 @@
clean_ik_kk_cmp = nullstrcmp (R_last_ik, R_temp_kk);
clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last_kj);
- // construct R_cur_l (and, if necessary R_cur_r)
+ /* construct R_cur_l (and, if necessary R_cur_r) */
if (NULL != R_last_ij)
{
- // Assign R_temp_ij to R_last_ij and remove epsilon as well
- // as parentheses, so we can better compare the contents
+ /* Assign R_temp_ij to R_last_ij and remove epsilon as well
+ * as parentheses, so we can better compare the contents */
R_temp_ij = remove_parentheses (remove_epsilon (R_last_ij));
if (0 == strcmp (R_temp_ij, R_temp_ik) && 0 == strcmp (R_temp_ik,
R_temp_kk)
@@ -809,13 +813,15 @@
(0 == strncmp (R_last_ik, "(|", 2) &&
0 == strncmp (R_last_kj, "(|", 2)))
{
- // a|(e|a)a*(e|a) = a*
- // a|(e|a)(e|a)*(e|a) = a*
- // (e|a)|aa*a = a*
- // (e|a)|aa*(e|a) = a*
- // (e|a)|(e|a)a*a = a*
- // (e|a)|(e|a)a*(e|a) = a*
- // (e|a)|(e|a)(e|a)*(e|a) = a*
+ /*
+ * a|(e|a)a*(e|a) = a*
+ * a|(e|a)(e|a)*(e|a) = a*
+ * (e|a)|aa*a = a*
+ * (e|a)|aa*(e|a) = a*
+ * (e|a)|(e|a)a*a = a*
+ * (e|a)|(e|a)a*(e|a) = a*
+ * (e|a)|(e|a)(e|a)*(e|a) = a*
+ */
if (GNUNET_YES == needs_parentheses (R_temp_ij))
GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_ij);
else
@@ -823,11 +829,13 @@
}
else
{
- // a|aa*a = a+
- // a|(e|a)a*a = a+
- // a|aa*(e|a) = a+
- // a|(e|a)(e|a)*a = a+
- // a|a(e|a)*(e|a) = a+
+ /*
+ * a|aa*a = a+
+ * a|(e|a)a*a = a+
+ * a|aa*(e|a) = a+
+ * a|(e|a)(e|a)*a = a+
+ * a|a(e|a)*(e|a) = a+
+ */
if (GNUNET_YES == needs_parentheses (R_temp_ij))
GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_ij);
else
@@ -836,7 +844,7 @@
}
else if (0 == ij_ik_cmp && 0 == clean_kk_kj_cmp && 0 != clean_ik_kk_cmp)
{
- // a|ab*b = ab*
+ /* a|ab*b = ab* */
if (strlen (R_last_kk) < 1)
R_cur_r = GNUNET_strdup (R_last_ij);
else if (GNUNET_YES == needs_parentheses (R_temp_kk))
@@ -848,7 +856,7 @@
}
else if (0 == ij_kj_cmp && 0 == clean_ik_kk_cmp && 0 != clean_kk_kj_cmp)
{
- // a|bb*a = b*a
+ /* a|bb*a = b*a */
if (strlen (R_last_kk) < 1)
R_cur_r = GNUNET_strdup (R_last_kj);
else if (GNUNET_YES == needs_parentheses (R_temp_kk))
@@ -861,7 +869,7 @@
else if (0 == ij_ik_cmp && 0 == kk_kj_cmp && !has_epsilon (R_last_ij) &&
has_epsilon (R_last_kk))
{
- // a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab*
+ /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */
if (needs_parentheses (R_temp_kk))
GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last_ij, R_temp_kk);
else
@@ -872,7 +880,7 @@
else if (0 == ij_kj_cmp && 0 == ik_kk_cmp && !has_epsilon (R_last_ij) &&
has_epsilon (R_last_kk))
{
- // a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a
+ /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a */
if (needs_parentheses (R_temp_kk))
GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last_ij);
else
@@ -891,16 +899,16 @@
}
else
{
- // we have no left side
+ /* we have no left side */
R_cur_l = NULL;
}
- // construct R_cur_r, if not already constructed
+ /* construct R_cur_r, if not already constructed */
if (NULL == R_cur_r)
{
length = strlen (R_temp_kk) - strlen (R_last_ik);
- // a(ba)*bx = (ab)+x
+ /* a(ba)*bx = (ab)+x */
if (length > 0 && NULL != R_last_kk && 0 < strlen (R_last_kk) &&
NULL != R_last_kj && 0 < strlen (R_last_kj) && NULL != R_last_ik &&
0 < strlen (R_last_ik) && 0 == strkcmp (R_temp_kk, R_last_ik, length)
&&
@@ -928,7 +936,7 @@
temp_a[length_l] = '\0';
temp_b[length_r] = '\0';
- // e|(ab)+ = (ab)*
+ /* e|(ab)+ = (ab)* */
if (NULL != R_cur_l && 0 == strlen (R_cur_l) && 0 == strlen (temp_b))
{
GNUNET_asprintf (&R_cur_r, "(%s%s)*", R_last_ik, temp_a);
@@ -945,8 +953,10 @@
else if (0 == strcmp (R_temp_ik, R_temp_kk) &&
0 == strcmp (R_temp_kk, R_temp_kj))
{
- // (e|a)a*(e|a) = a*
- // (e|a)(e|a)*(e|a) = a*
+ /*
+ * (e|a)a*(e|a) = a*
+ * (e|a)(e|a)*(e|a) = a*
+ */
if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj))
{
if (needs_parentheses (R_temp_kk))
@@ -954,7 +964,7 @@
else
GNUNET_asprintf (&R_cur_r, "%s*", R_temp_kk);
}
- // aa*a = a+a
+ /* aa*a = a+a */
else if (0 == clean_ik_kk_cmp && 0 == clean_kk_kj_cmp &&
!has_epsilon (R_last_ik))
{
@@ -963,10 +973,12 @@
else
GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk);
}
- // (e|a)a*a = a+
- // aa*(e|a) = a+
- // a(e|a)*(e|a) = a+
- // (e|a)a*a = a+
+ /*
+ * (e|a)a*a = a+
+ * aa*(e|a) = a+
+ * a(e|a)*(e|a) = a+
+ * (e|a)a*a = a+
+ */
else
{
eps_check =
@@ -982,8 +994,10 @@
}
}
}
- // aa*b = a+b
- // (e|a)(e|a)*b = a*b
+ /*
+ * aa*b = a+b
+ * (e|a)(e|a)*b = a*b
+ */
else if (0 == strcmp (R_temp_ik, R_temp_kk))
{
if (has_epsilon (R_last_ik))
@@ -1001,8 +1015,10 @@
GNUNET_asprintf (&R_cur_r, "%s+%s", R_temp_kk, R_last_kj);
}
}
- // ba*a = ba+
- // b(e|a)*(e|a) = ba*
+ /*
+ * ba*a = ba+
+ * b(e|a)*(e|a) = ba*
+ */
else if (0 == strcmp (R_temp_kk, R_temp_kj))
{
if (has_epsilon (R_last_kj))
@@ -1079,11 +1095,15 @@
/**
- * create proofs for all states in the given automaton. Implementation of the
+ * Create proofs for all states in the given automaton. Implementation of the
* algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and
* Computation 3rd Edition" by Hopcroft, Motwani and Ullman.
*
- * @param a automaton.
+ * Each state in the automaton gets assigned 'proof' and 'hash' (hash of the
+ * proof) fields. The starting state will only have a valid proof/hash if it
has
+ * any incoming transitions.
+ *
+ * @param a automaton for which to assign proofs and hashes.
*/
static void
automaton_create_proofs (struct GNUNET_REGEX_Automaton *a)
@@ -1132,16 +1152,17 @@
else
{
temp = R_last[i * n + j];
- GNUNET_asprintf (&R_last[i * n + j], "%s|%s", R_last[i * n + j],
t->label);
+ GNUNET_asprintf (&R_last[i * n + j], "%s|%s", R_last[i * n + j],
+ t->label);
GNUNET_free (temp);
}
}
- if (NULL == R_last[i*n+i])
- GNUNET_asprintf (&R_last[i*n+i], "");
+ if (NULL == R_last[i * n + i])
+ GNUNET_asprintf (&R_last[i * n + i], "");
else
{
- temp = R_last[i*n+i];
- GNUNET_asprintf (&R_last[i*n+i], "(|%s)", R_last[i*n+i]);
+ temp = R_last[i * n + i];
+ GNUNET_asprintf (&R_last[i * n + i], "(|%s)", R_last[i * n + i]);
GNUNET_free (temp);
}
}
@@ -1162,18 +1183,19 @@
{
for (j = 0; j < n; j++)
{
- // Basis for the recursion:
- // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk}
)^* R^{(k-1)}_{kj}
- // R_last == R^{(k-1)}, R_cur == R^{(k)}
+ /* Basis for the recursion:
+ * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk}
)^* R^{(k-1)}_{kj}
+ * R_last == R^{(k-1)}, R_cur == R^{(k)}
+ */
- // Create R_cur[i][j] and simplify the expression
- automaton_create_proofs_simplify (R_last[i * n + j], R_last[i*n+k],
- R_last[k*n+k], R_last[k*n+j],
+ /* Create R_cur[i][j] and simplify the expression */
+ automaton_create_proofs_simplify (R_last[i * n + j], R_last[i * n + k],
+ R_last[k * n + k], R_last[k * n + j],
&R_cur[i * n + j]);
}
}
- // set R_last = R_cur
+ /* set R_last = R_cur */
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
@@ -1185,41 +1207,43 @@
}
}
- // assign proofs and hashes
+ /* assign proofs and hashes */
for (i = 0; i < n; i++)
{
- if (NULL != R_last[a->start->dfs_id*n+i])
+ if (NULL != R_last[a->start->dfs_id * n + i])
{
- states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id*n+i]);
+ states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id * n + i]);
GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof),
&states[i]->hash);
}
}
- // complete regex for whole DFA: union of all pairs (start state/accepting
- // state(s)).
+ /* complete regex for whole DFA: union of all pairs (start state/accepting
+ * state(s)). */
complete_regex = NULL;
for (i = 0; i < n; i++)
{
if (states[i]->accepting)
{
- if (NULL == complete_regex && 0 < strlen (R_last[a->start->dfs_id*n+i]))
+ if (NULL == complete_regex &&
+ 0 < strlen (R_last[a->start->dfs_id * n + i]))
{
- GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->dfs_id*n+i]);
+ GNUNET_asprintf (&complete_regex, "%s",
+ R_last[a->start->dfs_id * n + i]);
}
- else if (NULL != R_last[a->start->dfs_id*n+i] &&
- 0 < strlen (R_last[a->start->dfs_id*n+i]))
+ else if (NULL != R_last[a->start->dfs_id * n + i] &&
+ 0 < strlen (R_last[a->start->dfs_id * n + i]))
{
temp = complete_regex;
GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex,
- R_last[a->start->dfs_id*n+i]);
+ R_last[a->start->dfs_id * n + i]);
GNUNET_free (temp);
}
}
}
a->canonical_regex = complete_regex;
- // cleanup
+ /* cleanup */
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
@@ -1272,7 +1296,7 @@
if (nfa_states->len < 1)
return s;
- // Create a name based on 'nfa_states'
+ /* Create a name based on 'nfa_states' */
s->name = GNUNET_malloc (sizeof (char) * 2);
strcat (s->name, "{");
name = NULL;
@@ -1291,15 +1315,15 @@
name = NULL;
}
- // Add a transition for each distinct label to NULL state
+ /* Add a transition for each distinct label to NULL state */
for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
{
if (NULL != ctran->label)
state_add_transition (ctx, s, ctran->label, NULL);
}
- // If the nfa_states contain an accepting state, the new dfa state is also
- // accepting
+ /* If the nfa_states contain an accepting state, the new dfa state is also
+ * accepting. */
if (cstate->accepting)
s->accepting = 1;
}
@@ -1381,14 +1405,14 @@
struct GNUNET_REGEX_State *s;
struct GNUNET_REGEX_State *s_next;
- // 1. unmark all states
+ /* 1. unmark all states */
for (s = a->states_head; NULL != s; s = s->next)
s->marked = GNUNET_NO;
- // 2. traverse dfa from start state and mark all visited states
+ /* 2. traverse dfa from start state and mark all visited states */
GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &mark_states,
NULL);
- // 3. delete all states that were not visited
+ /* 3. delete all states that were not visited */
for (s = a->states_head; NULL != s; s = s_next)
{
s_next = s->next;
@@ -1434,7 +1458,7 @@
if (0 == dead)
continue;
- // state s is dead, remove it
+ /* state s is dead, remove it */
automaton_remove_state (a, s);
}
}
@@ -1470,7 +1494,8 @@
}
state_cnt = a->state_count;
- table = (int *)GNUNET_malloc_large (sizeof (int) * state_cnt *
a->state_count);
+ table =
+ (int *) GNUNET_malloc_large (sizeof (int) * state_cnt * a->state_count);
for (i = 0, s1 = a->states_head; i < state_cnt && NULL != s1;
i++, s1 = s1->next)
@@ -1513,8 +1538,12 @@
if (0 == strcmp (t1->label, t2->label))
{
num_equal_edges++;
- if (0 != table[((t1->to_state->marked * state_cnt) +
t2->to_state->marked)] ||
- 0 != table[((t2->to_state->marked * state_cnt) +
t1->to_state->marked)])
+ if (0 !=
+ table[((t1->to_state->marked * state_cnt) +
+ t2->to_state->marked)] ||
+ 0 !=
+ table[((t2->to_state->marked * state_cnt) +
+ t1->to_state->marked)])
{
table[((s1->marked * state_cnt) + s2->marked)] = 1;
change = 1;
@@ -1564,13 +1593,13 @@
GNUNET_assert (DFA == a->type);
- // 1. remove unreachable states
+ /* 1. remove unreachable states */
dfa_remove_unreachable_states (a);
- // 2. remove dead states
+ /* 2. remove dead states */
dfa_remove_dead_states (a);
- // 3. Merge nondistinguishable states
+ /* 3. Merge nondistinguishable states */
dfa_merge_nondistinguishable_states (ctx, a);
}
@@ -1685,11 +1714,11 @@
if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
return;
- // Compute the new transitions of given stride_len
+ /* Compute the new transitions of given stride_len */
GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL,
&dfa_add_multi_strides, &ctx);
- // Add all the new transitions to the automaton.
+ /* Add all the new transitions to the automaton. */
for (t = ctx.transitions_head; NULL != t; t = t_next)
{
t_next = t->next;
@@ -1699,7 +1728,7 @@
GNUNET_free (t);
}
- // Mark this automaton as multistrided
+ /* Mark this automaton as multistrided */
dfa->is_multistrided = GNUNET_YES;
}
@@ -1729,10 +1758,9 @@
if (NULL != label &&
- ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting
-// || cur->transition_count > 1
- || GNUNET_YES == cur->marked) || (start != dfa->start && max_len > 0 &&
- max_len == strlen (label)) ||
+ ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting ||
+ GNUNET_YES == cur->marked) || (start != dfa->start && max_len > 0 &&
+ max_len == strlen (label)) ||
(start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label))))
{
t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition));
@@ -1795,7 +1823,7 @@
if (NULL == dfa)
return;
- // Count the incoming transitions on each state.
+ /* Count the incoming transitions on each state. */
for (s = dfa->states_head; NULL != s; s = s->next)
{
for (t = s->transitions_head; NULL != t; t = t->next)
@@ -1805,18 +1833,18 @@
}
}
- // Unmark all states.
+ /* Unmark all states. */
for (s = dfa->states_head; NULL != s; s = s->next)
{
s->marked = GNUNET_NO;
s->contained = GNUNET_NO;
}
- // Add strides and mark states that can be deleted.
+ /* Add strides and mark states that can be deleted. */
dfa_compress_paths_helper (dfa, dfa->start, dfa->start, NULL, max_len,
&transitions_head, &transitions_tail);
- // Add all the new transitions to the automaton.
+ /* Add all the new transitions to the automaton. */
for (t = transitions_head; NULL != t; t = t_next)
{
t_next = t->next;
@@ -1826,7 +1854,7 @@
GNUNET_free (t);
}
- // Remove marked states (including their incoming and outgoing transitions).
+ /* Remove marked states (including their incoming and outgoing transitions).
*/
for (s = dfa->states_head; NULL != s; s = s_next)
{
s_next = s->next;
@@ -1955,7 +1983,7 @@
{
unsigned int i;
struct GNUNET_REGEX_StateSet *cls;
- struct GNUNET_REGEX_StateSet_MDLL cls_check;
+ struct GNUNET_REGEX_StateSet_MDLL cls_stack;
struct GNUNET_REGEX_State *clsstate;
struct GNUNET_REGEX_State *currentstate;
struct GNUNET_REGEX_Transition *ctran;
@@ -1964,21 +1992,22 @@
return NULL;
cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet));
- cls_check.head = NULL;
- cls_check.tail = NULL;
+ cls_stack.head = NULL;
+ cls_stack.tail = NULL;
- // Add start state to closure only for epsilon closure
+ /* Add start state to closure only for epsilon closure */
if (NULL == label)
GNUNET_array_append (cls->states, cls->len, s);
- GNUNET_CONTAINER_MDLL_insert (SS, cls_check.head, cls_check.tail, s);
- cls_check.len = 1;
+ GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s);
+ cls_stack.len = 1;
- while (cls_check.len > 0)
+ while (cls_stack.len > 0)
{
- currentstate = cls_check.tail;
- GNUNET_CONTAINER_MDLL_remove (SS, cls_check.head, cls_check.tail,
currentstate);
- cls_check.len--;
+ 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)
@@ -1990,8 +2019,9 @@
if (NULL != clsstate && 0 == clsstate->contained)
{
GNUNET_array_append (cls->states, cls->len, clsstate);
- GNUNET_CONTAINER_MDLL_insert_tail (SS, cls_check.head,
cls_check.tail, clsstate);
- cls_check.len++;
+ GNUNET_CONTAINER_MDLL_insert_tail (ST, cls_stack.head,
cls_stack.tail,
+ clsstate);
+ cls_stack.len++;
clsstate->contained = 1;
}
}
@@ -2001,7 +2031,7 @@
for (i = 0; i < cls->len; i++)
cls->states[i]->contained = 0;
- // sort the states
+ /* sort the states */
if (cls->len > 1)
qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *),
state_compare);
@@ -2379,7 +2409,7 @@
}
if (0 == atomcount)
{
- // Ignore this: "()"
+ /* Ignore this: "()" */
pcount--;
altcount = p[pcount].altcount;
atomcount = p[pcount].atomcount;
@@ -2560,7 +2590,7 @@
GNUNET_REGEX_context_init (&ctx);
- // Create NFA
+ /* Create NFA */
nfa = GNUNET_REGEX_construct_nfa (regex, len);
if (NULL == nfa)
@@ -2578,7 +2608,7 @@
dfa->regex = GNUNET_strdup (regex);
dfa->is_multistrided = GNUNET_NO;
- // Create DFA start state from epsilon closure
+ /* Create DFA start state from epsilon closure */
nfa_start_eps_cls = nfa_closure_create (nfa, nfa->start, 0);
dfa->start = dfa_state_create (&ctx, nfa_start_eps_cls);
automaton_add_state (dfa, dfa->start);
@@ -2587,19 +2617,16 @@
GNUNET_REGEX_automaton_destroy (nfa);
- // Minimize DFA
+ /* Minimize DFA */
dfa_minimize (&ctx, dfa);
- // Create proofs for all states
+ /* Create proofs and hashes for all states */
automaton_create_proofs (dfa);
- // Compress DFA paths
+ /* Compress linear DFA paths */
if (1 != max_path_len)
dfa_compress_paths (&ctx, dfa, max_path_len);
- // Add strides to DFA
- //GNUNET_REGEX_dfa_add_multi_strides (&ctx, dfa, 2);
-
return dfa;
}
@@ -2657,7 +2684,7 @@
s = a->start;
- // If the string is empty but the starting state is accepting, we accept.
+ /* If the string is empty but the starting state is accepting, we accept. */
if ((NULL == string || 0 == strlen (string)) && s->accepting)
return 0;
@@ -2702,7 +2729,7 @@
return -1;
}
- // If the string is empty but the starting state is accepting, we accept.
+ /* If the string is empty but the starting state is accepting, we accept. */
if ((NULL == string || 0 == strlen (string)) && a->start->accepting)
return 0;
@@ -2921,8 +2948,8 @@
if (GNUNET_YES == state->accepting && cur_len > 1 &&
state->transition_count < 1 && cur_len < max_len)
{
- // Special case for regex consisting of just a string that is shorter
than
- // max_len
+ /* Special case for regex consisting of just a string that is shorter
than
+ * max_len */
edge[0].label = &consumed_string[cur_len - 1];
edge[0].destination = state->hash;
temp = GNUNET_strdup (consumed_string);
@@ -2934,7 +2961,7 @@
}
else if (max_len < cur_len)
{
- // Case where the concatenated labels are longer than max_len, then
split.
+ /* Case where the concatenated labels are longer than max_len, then
split. */
edge[0].label = &consumed_string[max_len];
edge[0].destination = state->hash;
temp = GNUNET_strdup (consumed_string);
Modified: gnunet/src/regex/regex_internal.h
===================================================================
--- gnunet/src/regex/regex_internal.h 2012-11-16 13:08:10 UTC (rev 24996)
+++ gnunet/src/regex/regex_internal.h 2012-11-16 13:08:51 UTC (rev 24997)
@@ -19,7 +19,7 @@
*/
/**
* @file src/regex/regex_internal.h
- * @brief common internal definitions for regex library
+ * @brief common internal definitions for regex library.
* @author Maximilian Szengel
*/
#ifndef REGEX_INTERNAL_H
@@ -43,8 +43,9 @@
/**
- * Transition between two states. Each state can have 0-n transitions. If
label
- * is 0, this is considered to be an epsilon transition.
+ * Transition between two states. Transitions are stored at the states from
+ * which they origin ('from_state'). Each state can have 0-n transitions.
+ * If label is 0, this is considered to be an epsilon transition.
*/
struct GNUNET_REGEX_Transition
{
@@ -96,16 +97,26 @@
struct GNUNET_REGEX_State *next;
/**
- * This is a multi DLL for StateSet_p.
+ * This is a multi DLL for StateSet_MDLL.
*/
struct GNUNET_REGEX_State *prev_SS;
/**
- * This is a multi DLL for StateSet_p.
+ * This is a multi DLL for StateSet_MDLL.
*/
struct GNUNET_REGEX_State *next_SS;
/**
+ * This is a multi DLL for StateSet_MDLL Stack.
+ */
+ struct GNUNET_REGEX_State *prev_ST;
+
+ /**
+ * This is a multi DLL for StateSet_MDLL Stack.
+ */
+ struct GNUNET_REGEX_State *next_ST;
+
+ /**
* Unique state id.
*/
unsigned int id;
Modified: gnunet/src/regex/regex_random.c
===================================================================
--- gnunet/src/regex/regex_random.c 2012-11-16 13:08:10 UTC (rev 24996)
+++ gnunet/src/regex/regex_random.c 2012-11-16 13:08:51 UTC (rev 24997)
@@ -106,7 +106,7 @@
current_char = '?';
break;
case 3:
- if (i < rx_length - 1) // '|' cannot be at the end
+ if (i < rx_length - 1) /* '|' cannot be at the end */
current_char = '|';
else
current_char = get_random_literal ();
Modified: gnunet/src/regex/regex_simulation_profiler_test.conf
===================================================================
--- gnunet/src/regex/regex_simulation_profiler_test.conf 2012-11-16
13:08:10 UTC (rev 24996)
+++ gnunet/src/regex/regex_simulation_profiler_test.conf 2012-11-16
13:08:51 UTC (rev 24997)
@@ -4,3 +4,4 @@
PASSWORD =
HOST = localhost
PORT = 3306
+REGEX_PREFIX = GNVPN-0001-PAD
Modified: gnunet/src/regex/test_regex_eval_api.c
===================================================================
--- gnunet/src/regex/test_regex_eval_api.c 2012-11-16 13:08:10 UTC (rev
24996)
+++ gnunet/src/regex/test_regex_eval_api.c 2012-11-16 13:08:51 UTC (rev
24997)
@@ -123,7 +123,8 @@
/* Match canonical regex */
dfa =
- GNUNET_REGEX_construct_dfa (canonical_regex, strlen (canonical_regex),
0);
+ GNUNET_REGEX_construct_dfa (canonical_regex, strlen (canonical_regex),
+ 0);
if (NULL == dfa)
{
GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Constructing DFA failed\n");
@@ -251,7 +252,7 @@
int check_rand;
char *check_proof;
- struct Regex_String_Pair rxstr[18] = {
+ struct Regex_String_Pair rxstr[19] = {
{"ab?(abcd)?", 5,
{"ababcd", "abab", "aabcd", "a", "abb"},
{match, nomatch, match, match, nomatch}},
@@ -311,14 +312,19 @@
{nomatch}},
{"a()b", 1,
{"ab"},
- {match}}
+ {match}},
+
{"GNVPN-0001-PAD(001110101001001010(0|1)*|001110101001001010000(0|1)*|001110101001001010001(0|1)*|001110101001001010010(0|1)*|001110101001001010011(0|1)*|001110101001001010100(0|1)*|001110101001001010101(0|1)*|001110101001001010110(0|1)*|001110101001001010111(0|1)*|0011101010110110(0|1)*|001110101011011000000(0|1)*|001110101011011000001(0|1)*|001110101011011000010(0|1)*|001110101011011000011(0|1)*|001110101011011000100(0|1)*|001110101011011000101(0|1)*|001110101011011000110(0|1)*|001110101011011000111(0|1)*|001110101011011001000(0|1)*|001110101011011001001(0|1)*|001110101011011001010(0|1)*|001110101011011001011(0|1)*|001110101011011001100(0|1)*|001110101011011001101(0|1)*|001110101011011001110(0|1)*|001110101011011001111(0|1)*|001110101011011010000(0|1)*|001110101011011010001(0|1)*|001110101011011010010(0|1)*|001110101011011010011(0|1)*|001110101011011010100(0|1)*|001110101011011010101(0|1)*|001110101011011010110(0|1)*|001110101011011010111(0|1)*|001110101011011011000(0|
1)*|0011
10101011011011001(0|1)*|001110101011011011010(0|1)*|001110101011011011011(0|1)*|001110101011011011100(0|1)*|001110101011011011101(0|1)*|001110101011011011110(0|1)*|001110101011011011111(0|1)*|0011101110111101(0|1)*|001110111011110100000(0|1)*|001110111011110100001(0|1)*|001110111011110100010(0|1)*|001110111011110100011(0|1)*|001110111011110100100(0|1)*|001110111011110100101(0|1)*|001110111011110100110(0|1)*|001110111011110100111(0|1)*|001110111011110101000(0|1)*|001110111011110101001(0|1)*|001110111011110101010(0|1)*|001110111011110101011(0|1)*|001110111011110101100(0|1)*|001110111011110101101(0|1)*|001110111011110101110(0|1)*|001110111011110101111(0|1)*|001110111011110110000(0|1)*|001110111011110110001(0|1)*|001110111011110110010(0|1)*|001110111011110110011(0|1)*|001110111011110110100(0|1)*|001110111011110110101(0|1)*|001110111011110110110(0|1)*|001110111011110110111(0|1)*|001110111011110111000(0|1)*|001110111011110111001(0|1)*|001110111011110111010(0|1)*|001110111011110111
011(0|1)
*|001110111011110111100(0|1)*|001110111011110111101(0|1)*|001110111011110111110(0|1)*|0111010001010110(0|1)*|011101000101011000000(0|1)*|011101000101011000001(0|1)*|011101000101011000010(0|1)*|011101000101011000011(0|1)*|011101000101011000100(0|1)*|011101000101011000101(0|1)*|011101000101011000110(0|1)*|011101000101011000111(0|1)*|011101000101011001000(0|1)*|011101000101011001001(0|1)*|011101000101011001010(0|1)*|011101000101011001011(0|1)*|011101000101011001100(0|1)*|011101000101011001101(0|1)*|011101000101011001110(0|1)*|011101000101011001111(0|1)*|011101000101011010000(0|1)*|011101000101011010001(0|1)*|011101000101011010010(0|1)*|011101000101011010011(0|1)*|011101000101011010100(0|1)*|011101000101011010101(0|1)*|011101000101011010110(0|1)*|011101000101011010111(0|1)*|011101000101011011000(0|1)*|011101000101011011001(0|1)*|011101000101011011010(0|1)*|011101000101011011011(0|1)*|011101000101011011100(0|1)*|011101000101011011101(0|1)*|011101000101011011110(0|1)*|011101000101
01101111
1(0|1)*|0111010001010111(0|1)*|011101000101011100000(0|1)*|011101000101011100001(0|1)*|011101000101011100010(0|1)*|011101000101011100011(0|1)*|011101000101011100100(0|1)*|011101000101011100101(0|1)*|011101000101011100110(0|1)*|011101000101011100111(0|1)*|011101000101011101000(0|1)*|011101000101011101001(0|1)*|011101000101011101010(0|1)*|011101000101011101011(0|1)*|011101000101011101100(0|1)*|011101000101011101101(0|1)*|011101000101011101110(0|1)*|011101000101011101111(0|1)*|011101000101011110000(0|1)*|011101000101011110001(0|1)*|011101000101011110010(0|1)*|011101000101011110011(0|1)*|011101000101011110100(0|1)*|011101000101011110101(0|1)*|011101000101011110110(0|1)*|011101000101011110111(0|1)*|011101000101011111000(0|1)*|011101000101011111001(0|1)*|011101000101011111010(0|1)*|011101000101011111011(0|1)*|011101000101011111100(0|1)*|011101000101011111101(0|1)*|011101000101011111110(0|1)*|011101000101011111111(0|1)*|0111010001011000(0|1)*|011101000101100000000(0|1)*|01110100010
11000000
01(0|1)*|011101000101100000010(0|1)*|011101000101100000011(0|1)*|011101000101100000100(0|1)*|011101000101100000101(0|1)*|011101000101100000110(0|1)*|011101000101100000111(0|1)*|011101000101100001000(0|1)*|011101000101100001001(0|1)*|011101000101100001010(0|1)*|011101000101100001011(0|1)*|011101000101100001100(0|1)*|011101000101100001101(0|1)*|011101000101100001110(0|1)*|011101000101100001111(0|1)*|011101000101100010000(0|1)*|011101000101100010001(0|1)*|011101000101100010010(0|1)*|011101000101100010011(0|1)*|011101000101100010100(0|1)*|011101000101100010101(0|1)*|011101000101100010110(0|1)*|011101000101100010111(0|1)*|011101000101100011000(0|1)*|011101000101100011001(0|1)*|011101000101100011010(0|1)*|011101000101100011011(0|1)*|011101000101100011100(0|1)*|011101000101100011101(0|1)*|011101000101100011110(0|1)*|011101000101100011111(0|1)*|01110100010110010(0|1)*|011101000101100100000(0|1)*|011101000101100100001(0|1)*|011101000101100100010(0|1)*|011101000101100100011(0|1)*|0111
01000101
100100100(0|1)*|011101000101100100101(0|1)*|011101000101100100110(0|1)*|011101000101100100111(0|1)*|011101000101100101000(0|1)*|011101000101100101001(0|1)*|011101000101100101010(0|1)*|011101000101100101011(0|1)*|011101000101100101100(0|1)*|011101000101100101101(0|1)*|011101000101100101110(0|1)*|011101000101100101111(0|1)*|011101000101100101111000(0|1)*|1100101010011100(0|1)*|110010101001110000000(0|1)*|110010101001110000000001(0|1)*|110010101001110000000010(0|1)*|110010101001110000000110(0|1)*|110010101001110000001(0|1)*|110010101001110000001000(0|1)*|110010101001110000001001(0|1)*|110010101001110000001010(0|1)*|110010101001110000001011(0|1)*|110010101001110000001101(0|1)*|110010101001110000001110(0|1)*|110010101001110000010(0|1)*|110010101001110000011(0|1)*|110010101001110000100(0|1)*|110010101001110000101(0|1)*|110010101001110000110(0|1)*|110010101001110000111(0|1)*|110010101001110001000(0|1)*|110010101001110001001(0|1)*|110010101001110001010(0|1)*|110010101001110001011(0|
1)*|1100
10101001110001100(0|1)*|110010101001110001101(0|1)*|110010101001110001110(0|1)*|110010101001110001111(0|1)*|110010101001110010000(0|1)*|110010101001110010001(0|1)*|110010101001110010010(0|1)*|110010101001110010011(0|1)*|110010101001110010100(0|1)*|110010101001110010101(0|1)*|110010101001110010110(0|1)*|110010101001110010111(0|1)*|110010101001110011000(0|1)*|110010101001110011001(0|1)*|110010101001110011010(0|1)*|110010101001110011011(0|1)*|110010101001110011100(0|1)*|110010101001110011101(0|1)*|110010101001110011110(0|1)*|110010101001110011111(0|1)*|1101101010111010(0|1)*|110110101011101000000(0|1)*|110110101011101000000001(0|1)*|110110101011101000001000(0|1)*|110110101011101000001001(0|1)*|110110101011101000001010(0|1)*|110110101011101000001011(0|1)*|110110101011101000001100(0|1)*|110110101011101000001110(0|1)*|110110101011101000001111(0|1)*|110110101011101000010(0|1)*|110110101011101000010000(0|1)*|110110101011101000010001(0|1)*|110110101011101000010010(0|1)*|1101101010111
01000010
011(0|1)*|110110101011101000011(0|1)*|110110101011101000100(0|1)*|110110101011101000101(0|1)*|110110101011101000110(0|1)*|110110101011101000111(0|1)*|110110101011101001000(0|1)*|110110101011101001001(0|1)*|110110101011101001010(0|1)*|110110101011101001011(0|1)*|110110101011101001100(0|1)*|110110101011101001101(0|1)*|110110101011101001110(0|1)*|110110101011101001111(0|1)*|110110101011101010000(0|1)*|110110101011101010001(0|1)*|110110101011101010010(0|1)*|110110101011101010011(0|1)*|110110101011101010100(0|1)*|110110101011101010101(0|1)*|110110101011101010110(0|1)*|110110101011101010111(0|1)*|110110101011101011000(0|1)*|110110101011101011001(0|1)*|110110101011101011010(0|1)*|110110101011101011011(0|1)*|110110101011101011100(0|1)*|110110101011101011101(0|1)*|110110101011101011110(0|1)*|110110101011101011111(0|1)*|1101101011010100(0|1)*|110110101101010000000(0|1)*|110110101101010000001(0|1)*|110110101101010000010(0|1)*|110110101101010000011(0|1)*|110110101101010000100(0|1)*|1101
10101101
010000101(0|1)*|110110101101010000110(0|1)*|110110101101010000111(0|1)*|110110101101010001000(0|1)*|110110101101010001001(0|1)*|110110101101010001010(0|1)*|110110101101010001011(0|1)*|110110101101010001100(0|1)*|110110101101010001101(0|1)*|110110101101010001110(0|1)*|110110101101010001111(0|1)*|110110101101010010000(0|1)*|110110101101010010001(0|1)*|110110101101010010010(0|1)*|110110101101010010011(0|1)*|110110101101010010100(0|1)*|1101101011010100101000(0|1)*|110110101101010010101(0|1)*|110110101101010010110(0|1)*|110110101101010010111(0|1)*|110110101101010011000(0|1)*|110110101101010011010(0|1)*|110110101101010011011(0|1)*|110110101101010011100(0|1)*|110110101101010011101(0|1)*|110110101101010011110(0|1)*|110110101101010011111(0|1)*|1101111010100100(0|1)*|110111101010010000000(0|1)*|110111101010010000001(0|1)*|110111101010010000010(0|1)*|110111101010010000011(0|1)*|110111101010010000100(0|1)*|110111101010010000101(0|1)*|110111101010010000110(0|1)*|110111101010010000111(0|1
)*|11011
1101010010001000(0|1)*|110111101010010001001(0|1)*|110111101010010001010(0|1)*|110111101010010001011(0|1)*|110111101010010001100(0|1)*|110111101010010001101(0|1)*|110111101010010001110(0|1)*|110111101010010001111(0|1)*|110111101010010010000(0|1)*|110111101010010010001(0|1)*|110111101010010010010(0|1)*|110111101010010010011(0|1)*|110111101010010010100(0|1)*|110111101010010010101(0|1)*|110111101010010010110(0|1)*|110111101010010010111(0|1)*|110111101010010011000(0|1)*|110111101010010011001(0|1)*|110111101010010011010(0|1)*|110111101010010011011(0|1)*|110111101010010011100(0|1)*|110111101010010011101(0|1)*|110111101010010011110(0|1)*|110111101010010011111(0|1)*|11011110101001010(0|1)*|110111101010010100000(0|1)*|110111101010010100001(0|1)*|110111101010010100010(0|1)*|110111101010010100011(0|1)*|110111101010010100100(0|1)*|110111101010010100101(0|1)*|110111101010010100110(0|1)*|110111101010010100111(0|1)*|110111101010010101000(0|1)*|110111101010010101001(0|1)*|110111101010010101
010(0|1)
*|110111101010010101011(0|1)*|110111101010010101100(0|1)*|110111101010010101101(0|1)*|110111101010010101110(0|1)*|110111101010010101111(0|1)*)",
+ 2,
+ {"GNVPN-0001-PAD1101111010100101011101010101010101",
+ "GNVPN-0001-PAD11001010100111000101101010101"},
+ {match, match}}
};
check_nfa = 0;
check_dfa = 0;
check_rand = 0;
- for (i = 0; i < 18; i++)
+ for (i = 0; i < 19; i++)
{
if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED))
{
Modified: gnunet/src/regex/test_regex_graph_api.c
===================================================================
--- gnunet/src/regex/test_regex_graph_api.c 2012-11-16 13:08:10 UTC (rev
24996)
+++ gnunet/src/regex/test_regex_graph_api.c 2012-11-16 13:08:51 UTC (rev
24997)
@@ -28,7 +28,7 @@
#include "gnunet_regex_lib.h"
#include "regex_internal.h"
-#define KEEP_FILES 0
+#define KEEP_FILES 1
/**
* Check if 'filename' exists and is not empty.
@@ -43,7 +43,7 @@
int error = 0;
FILE *fp;
- // Check if file was created and delete it again
+ /* Check if file was created and delete it again */
if (NULL == (fp = fopen (filename, "r")))
{
GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not find graph %s\n",
filename);
@@ -54,18 +54,16 @@
if (1 > ftell (fp))
{
GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
- "Graph writing failed, got empty file (%s)!\n",
- filename);
+ "Graph writing failed, got empty file (%s)!\n", filename);
error = 2;
}
-
+
GNUNET_assert (0 == fclose (fp));
if (!KEEP_FILES)
{
if (0 != unlink (filename))
- GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR,
- "unlink", filename);
+ GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "unlink", filename);
}
return error;
}
@@ -78,6 +76,7 @@
struct GNUNET_REGEX_Automaton *a;
unsigned int i;
const char *filename = "test_graph.dot";
+
const char *regex[12] = {
"ab(c|d)+c*(a(b|c)+d)+(bla)+",
"(bla)*",
@@ -90,7 +89,6 @@
"a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*",
"a",
"a|b",
-// "abc(d+|e)fgh"
"PADPADPADPADPADPabcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd"
};
@@ -98,7 +96,7 @@
error = 0;
for (i = 0; i < 12; i++)
{
- // Check NFA graph creation
+ /* Check NFA graph creation */
a = GNUNET_REGEX_construct_nfa (regex[i], strlen (regex[i]));
GNUNET_REGEX_automaton_save_graph (a, filename,
GNUNET_REGEX_GRAPH_DEFAULT);
GNUNET_REGEX_automaton_destroy (a);
@@ -127,7 +125,7 @@
error += filecheck (filename);
- // Check DFA graph creation
+ /* Check DFA graph creation */
a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 0);
GNUNET_REGEX_automaton_save_graph (a, filename,
GNUNET_REGEX_GRAPH_DEFAULT);
GNUNET_REGEX_automaton_destroy (a);
@@ -148,10 +146,8 @@
error += filecheck (filename);
- a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 0);
- GNUNET_REGEX_automaton_save_graph (a, filename,
GNUNET_REGEX_GRAPH_DEFAULT); //|
- // GNUNET_REGEX_GRAPH_VERBOSE |
- //GNUNET_REGEX_GRAPH_COLORING);
+ a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 4);
+ GNUNET_REGEX_automaton_save_graph (a, filename,
GNUNET_REGEX_GRAPH_DEFAULT);
GNUNET_REGEX_automaton_destroy (a);
error += filecheck (filename);
Modified: gnunet/src/regex/test_regex_iterate_api.c
===================================================================
--- gnunet/src/regex/test_regex_iterate_api.c 2012-11-16 13:08:10 UTC (rev
24996)
+++ gnunet/src/regex/test_regex_iterate_api.c 2012-11-16 13:08:51 UTC (rev
24997)
@@ -158,7 +158,7 @@
rxstr[i].regex);
- // Create graph
+ /* Create graph */
if (GNUNET_YES == GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH)
{
GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i);
@@ -183,12 +183,13 @@
ctx.graph_filep = NULL;
}
- // Iterate over DFA edges
+ /* Iterate over DFA edges */
transition_counter = 0;
ctx.string_count = rxstr[i].string_count;
ctx.strings = rxstr[i].strings;
ctx.match_count = 0;
- dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex),
0);
+ dfa =
+ GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex),
0);
GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx);
num_transitions =
GNUNET_REGEX_get_transition_count (dfa) - dfa->start->transition_count;
@@ -217,7 +218,7 @@
GNUNET_REGEX_automaton_destroy (dfa);
- // Finish graph
+ /* Finish graph */
if (GNUNET_YES == ctx.should_save_graph)
{
fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep);
@@ -234,7 +235,8 @@
ctx.strings = rxstr[i].strings;
ctx.match_count = 0;
- dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex),
0);
+ dfa =
+ GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex),
0);
GNUNET_REGEX_dfa_add_multi_strides (NULL, dfa, 2);
GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx);
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r24997 - gnunet/src/regex,
gnunet <=