diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-11-16 13:08:51 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-11-16 13:08:51 +0000 |
commit | b6908a90bf1a1f8008bffa8bfb0416da3c7bc1d5 (patch) | |
tree | b0768f32b98c4e04588577508b4316a41ac4156b | |
parent | 58857960c4d0329b1e19636b07672db320b24ec0 (diff) | |
download | gnunet-b6908a90bf1a1f8008bffa8bfb0416da3c7bc1d5.tar.gz gnunet-b6908a90bf1a1f8008bffa8bfb0416da3c7bc1d5.zip |
Cleaup, indentation, comments etc.
-rw-r--r-- | src/regex/gnunet-regex-simulation-profiler.c | 277 | ||||
-rw-r--r-- | src/regex/regex.c | 293 | ||||
-rw-r--r-- | src/regex/regex_internal.h | 21 | ||||
-rw-r--r-- | src/regex/regex_random.c | 2 | ||||
-rw-r--r-- | src/regex/regex_simulation_profiler_test.conf | 1 | ||||
-rw-r--r-- | src/regex/test_regex_eval_api.c | 14 | ||||
-rw-r--r-- | src/regex/test_regex_graph_api.c | 24 | ||||
-rw-r--r-- | src/regex/test_regex_iterate_api.c | 12 |
8 files changed, 412 insertions, 232 deletions
diff --git a/src/regex/gnunet-regex-simulation-profiler.c b/src/regex/gnunet-regex-simulation-profiler.c index 4bb033ea6..32b09eaee 100644 --- a/src/regex/gnunet-regex-simulation-profiler.c +++ b/src/regex/gnunet-regex-simulation-profiler.c | |||
@@ -32,26 +32,53 @@ | |||
32 | #include "gnunet_mysql_lib.h" | 32 | #include "gnunet_mysql_lib.h" |
33 | #include <mysql/mysql.h> | 33 | #include <mysql/mysql.h> |
34 | 34 | ||
35 | /** | ||
36 | * MySQL statement to insert an edge. | ||
37 | */ | ||
35 | #define INSERT_EDGE_STMT "INSERT IGNORE INTO `%s` "\ | 38 | #define INSERT_EDGE_STMT "INSERT IGNORE INTO `%s` "\ |
36 | "(`key`, `label`, `to_key`, `accepting`) "\ | 39 | "(`key`, `label`, `to_key`, `accepting`) "\ |
37 | "VALUES (?, ?, ?, ?);" | 40 | "VALUES (?, ?, ?, ?);" |
38 | 41 | ||
39 | /** | 42 | /** |
43 | * MySQL statement to select a key count. | ||
44 | */ | ||
45 | #define SELECT_KEY_STMT "SELECT COUNT(*) FROM `%s` "\ | ||
46 | "WHERE `key` = ? AND `label` = ?;" | ||
47 | |||
48 | /** | ||
40 | * Simple struct to keep track of progress, and print a | 49 | * Simple struct to keep track of progress, and print a |
41 | * nice little percentage meter for long running tasks. | 50 | * nice little percentage meter for long running tasks. |
42 | */ | 51 | */ |
43 | struct ProgressMeter | 52 | struct ProgressMeter |
44 | { | 53 | { |
54 | /** | ||
55 | * Total number of elements. | ||
56 | */ | ||
45 | unsigned int total; | 57 | unsigned int total; |
46 | 58 | ||
59 | /** | ||
60 | * Intervall for printing percentage. | ||
61 | */ | ||
47 | unsigned int modnum; | 62 | unsigned int modnum; |
48 | 63 | ||
64 | /** | ||
65 | * Number of dots to print. | ||
66 | */ | ||
49 | unsigned int dotnum; | 67 | unsigned int dotnum; |
50 | 68 | ||
69 | /** | ||
70 | * Completed number. | ||
71 | */ | ||
51 | unsigned int completed; | 72 | unsigned int completed; |
52 | 73 | ||
74 | /** | ||
75 | * Should the meter be printed? | ||
76 | */ | ||
53 | int print; | 77 | int print; |
54 | 78 | ||
79 | /** | ||
80 | * String to print on startup. | ||
81 | */ | ||
55 | char *startup_string; | 82 | char *startup_string; |
56 | }; | 83 | }; |
57 | 84 | ||
@@ -67,6 +94,11 @@ static struct ProgressMeter *meter; | |||
67 | static GNUNET_SCHEDULER_TaskIdentifier abort_task; | 94 | static GNUNET_SCHEDULER_TaskIdentifier abort_task; |
68 | 95 | ||
69 | /** | 96 | /** |
97 | * Shutdown task identifier. | ||
98 | */ | ||
99 | static GNUNET_SCHEDULER_TaskIdentifier shutdown_task; | ||
100 | |||
101 | /** | ||
70 | * Scan task identifier; | 102 | * Scan task identifier; |
71 | */ | 103 | */ |
72 | static GNUNET_SCHEDULER_TaskIdentifier scan_task; | 104 | static GNUNET_SCHEDULER_TaskIdentifier scan_task; |
@@ -87,6 +119,11 @@ static struct GNUNET_MYSQL_Context *mysql_ctx; | |||
87 | static struct GNUNET_MYSQL_StatementHandle *stmt_handle; | 119 | static struct GNUNET_MYSQL_StatementHandle *stmt_handle; |
88 | 120 | ||
89 | /** | 121 | /** |
122 | * MySQL prepared statement handle for `key` select. | ||
123 | */ | ||
124 | static struct GNUNET_MYSQL_StatementHandle *select_stmt_handle; | ||
125 | |||
126 | /** | ||
90 | * MySQL table name. | 127 | * MySQL table name. |
91 | */ | 128 | */ |
92 | static char *table_name; | 129 | static char *table_name; |
@@ -111,6 +148,21 @@ static unsigned int num_policies; | |||
111 | */ | 148 | */ |
112 | static unsigned int max_path_compression; | 149 | static unsigned int max_path_compression; |
113 | 150 | ||
151 | /** | ||
152 | * Number of merged transitions. | ||
153 | */ | ||
154 | static unsigned long long num_merged_transitions; | ||
155 | |||
156 | /** | ||
157 | * Number of merged states from different policies. | ||
158 | */ | ||
159 | static unsigned long long num_merged_states; | ||
160 | |||
161 | /** | ||
162 | * Prefix to add before every regex we're announcing. | ||
163 | */ | ||
164 | static char *regex_prefix; | ||
165 | |||
114 | 166 | ||
115 | /** | 167 | /** |
116 | * Create a meter to keep track of the progress of some task. | 168 | * Create a meter to keep track of the progress of some task. |
@@ -167,7 +219,7 @@ update_meter (struct ProgressMeter *meter) | |||
167 | (int) (((float) meter->completed / meter->total) * 100)); | 219 | (int) (((float) meter->completed / meter->total) * 100)); |
168 | } | 220 | } |
169 | else if (meter->completed % meter->dotnum == 0) | 221 | else if (meter->completed % meter->dotnum == 0) |
170 | FPRINTF (stdout, "%s", "."); | 222 | FPRINTF (stdout, "%s", "."); |
171 | 223 | ||
172 | if (meter->completed + 1 == meter->total) | 224 | if (meter->completed + 1 == meter->total) |
173 | FPRINTF (stdout, "%d%%]\n", 100); | 225 | FPRINTF (stdout, "%d%%]\n", 100); |
@@ -224,12 +276,15 @@ free_meter (struct ProgressMeter *meter) | |||
224 | static void | 276 | static void |
225 | do_shutdown (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | 277 | do_shutdown (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) |
226 | { | 278 | { |
279 | shutdown_task = GNUNET_SCHEDULER_NO_TASK; | ||
280 | if (GNUNET_SCHEDULER_NO_TASK != abort_task) | ||
281 | GNUNET_SCHEDULER_cancel (abort_task); | ||
227 | if (NULL != mysql_ctx) | 282 | if (NULL != mysql_ctx) |
228 | GNUNET_MYSQL_context_destroy (mysql_ctx); | 283 | GNUNET_MYSQL_context_destroy (mysql_ctx); |
229 | if (NULL != meter) | 284 | if (NULL != meter) |
230 | free_meter (meter); | 285 | free_meter (meter); |
231 | 286 | ||
232 | GNUNET_SCHEDULER_shutdown (); /* Stop scheduler to shutdown testbed run */ | 287 | GNUNET_SCHEDULER_shutdown (); /* Stop scheduler to shutdown testbed run */ |
233 | } | 288 | } |
234 | 289 | ||
235 | 290 | ||
@@ -252,6 +307,22 @@ do_abort (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | |||
252 | 307 | ||
253 | 308 | ||
254 | /** | 309 | /** |
310 | * Dummy function for prepared select. Always return GNUNET_OK. | ||
311 | * | ||
312 | * @param cls closure | ||
313 | * @param num_values number of values. | ||
314 | * @param values returned values from select stmt. | ||
315 | * | ||
316 | * @return GNUNET_OK | ||
317 | */ | ||
318 | static int | ||
319 | return_ok (void *cls, unsigned int num_values, MYSQL_BIND * values) | ||
320 | { | ||
321 | return GNUNET_OK; | ||
322 | } | ||
323 | |||
324 | |||
325 | /** | ||
255 | * Iterator over all states that inserts each state into the MySQL db. | 326 | * Iterator over all states that inserts each state into the MySQL db. |
256 | * | 327 | * |
257 | * @param cls closure. | 328 | * @param cls closure. |
@@ -262,11 +333,8 @@ do_abort (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | |||
262 | * @param edges edges leaving current state. | 333 | * @param edges edges leaving current state. |
263 | */ | 334 | */ |
264 | static void | 335 | static void |
265 | regex_iterator (void *cls, | 336 | regex_iterator (void *cls, const struct GNUNET_HashCode *key, const char *proof, |
266 | const struct GNUNET_HashCode *key, | 337 | int accepting, unsigned int num_edges, |
267 | const char *proof, | ||
268 | int accepting, | ||
269 | unsigned int num_edges, | ||
270 | const struct GNUNET_REGEX_Edge *edges) | 338 | const struct GNUNET_REGEX_Edge *edges) |
271 | { | 339 | { |
272 | unsigned int i; | 340 | unsigned int i; |
@@ -274,6 +342,8 @@ regex_iterator (void *cls, | |||
274 | unsigned long k_length; | 342 | unsigned long k_length; |
275 | unsigned long e_length; | 343 | unsigned long e_length; |
276 | unsigned long d_length; | 344 | unsigned long d_length; |
345 | MYSQL_BIND rbind[1]; | ||
346 | unsigned long long total; | ||
277 | 347 | ||
278 | GNUNET_assert (NULL != mysql_ctx); | 348 | GNUNET_assert (NULL != mysql_ctx); |
279 | 349 | ||
@@ -282,19 +352,69 @@ regex_iterator (void *cls, | |||
282 | k_length = sizeof (struct GNUNET_HashCode); | 352 | k_length = sizeof (struct GNUNET_HashCode); |
283 | e_length = strlen (edges[i].label); | 353 | e_length = strlen (edges[i].label); |
284 | d_length = sizeof (struct GNUNET_HashCode); | 354 | d_length = sizeof (struct GNUNET_HashCode); |
355 | memset (rbind, 0, sizeof (rbind)); | ||
356 | total = -1; | ||
357 | rbind[0].buffer_type = MYSQL_TYPE_LONGLONG; | ||
358 | rbind[0].buffer = &total; | ||
359 | rbind[0].is_unsigned = GNUNET_YES; | ||
360 | |||
361 | result = | ||
362 | GNUNET_MYSQL_statement_run_prepared_select (mysql_ctx, | ||
363 | select_stmt_handle, 1, | ||
364 | rbind, &return_ok, NULL, | ||
365 | MYSQL_TYPE_BLOB, key, | ||
366 | sizeof (struct | ||
367 | GNUNET_HashCode), | ||
368 | &k_length, | ||
369 | MYSQL_TYPE_STRING, | ||
370 | edges[i].label, | ||
371 | strlen (edges[i].label), | ||
372 | &e_length, -1); | ||
373 | |||
374 | if (GNUNET_SYSERR == result) | ||
375 | { | ||
376 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
377 | "Error executing prepared mysql select statement\n"); | ||
378 | GNUNET_SCHEDULER_add_now (&do_abort, NULL); | ||
379 | return; | ||
380 | } | ||
381 | |||
382 | if (-1 != total && total > 0) | ||
383 | { | ||
384 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, "Total: %llu (%s, %s)\n", total, | ||
385 | GNUNET_h2s (key), edges[i].label); | ||
386 | } | ||
285 | 387 | ||
286 | result = | 388 | result = |
287 | GNUNET_MYSQL_statement_run_prepared ( | 389 | GNUNET_MYSQL_statement_run_prepared (mysql_ctx, stmt_handle, NULL, |
288 | mysql_ctx, | 390 | MYSQL_TYPE_BLOB, key, |
289 | stmt_handle, | 391 | sizeof (struct GNUNET_HashCode), |
290 | NULL, | 392 | &k_length, MYSQL_TYPE_STRING, |
291 | MYSQL_TYPE_BLOB, key, sizeof (struct GNUNET_HashCode), &k_length, | 393 | edges[i].label, |
292 | MYSQL_TYPE_STRING, edges[i].label, strlen (edges[i].label), &e_length, | 394 | strlen (edges[i].label), &e_length, |
293 | MYSQL_TYPE_BLOB, &edges[i].destination, sizeof (struct GNUNET_HashCode), &d_length, | 395 | MYSQL_TYPE_BLOB, |
294 | MYSQL_TYPE_LONG, &accepting, GNUNET_YES, | 396 | &edges[i].destination, |
295 | -1); | 397 | sizeof (struct GNUNET_HashCode), |
398 | &d_length, MYSQL_TYPE_LONG, | ||
399 | &accepting, GNUNET_YES, -1); | ||
400 | |||
401 | if (0 == result) | ||
402 | { | ||
403 | char *key_str = GNUNET_strdup (GNUNET_h2s (key)); | ||
404 | char *to_key_str = GNUNET_strdup (GNUNET_h2s (&edges[i].destination)); | ||
405 | |||
406 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Merged (%s, %s, %s, %i)\n", key_str, | ||
407 | edges[i].label, to_key_str, accepting); | ||
408 | GNUNET_free (key_str); | ||
409 | GNUNET_free (to_key_str); | ||
410 | num_merged_transitions++; | ||
411 | } | ||
412 | else if (-1 != total) | ||
413 | { | ||
414 | num_merged_states++; | ||
415 | } | ||
296 | 416 | ||
297 | if (1 != result && 0 != result) | 417 | if (GNUNET_SYSERR == result || (1 != result && 0 != result)) |
298 | { | 418 | { |
299 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 419 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
300 | "Error executing prepared mysql statement for edge: Affected rows: %i, expected 0 or 1!\n", | 420 | "Error executing prepared mysql statement for edge: Affected rows: %i, expected 0 or 1!\n", |
@@ -310,15 +430,14 @@ regex_iterator (void *cls, | |||
310 | d_length = 0; | 430 | d_length = 0; |
311 | 431 | ||
312 | result = | 432 | result = |
313 | GNUNET_MYSQL_statement_run_prepared ( | 433 | GNUNET_MYSQL_statement_run_prepared (mysql_ctx, stmt_handle, NULL, |
314 | mysql_ctx, | 434 | MYSQL_TYPE_BLOB, key, |
315 | stmt_handle, | 435 | sizeof (struct GNUNET_HashCode), |
316 | NULL, | 436 | &k_length, MYSQL_TYPE_STRING, NULL, |
317 | MYSQL_TYPE_BLOB, key, sizeof (struct GNUNET_HashCode), &k_length, | 437 | 0, &e_length, MYSQL_TYPE_BLOB, |
318 | MYSQL_TYPE_STRING, NULL, 0, &e_length, | 438 | NULL, 0, &d_length, |
319 | MYSQL_TYPE_BLOB, NULL, 0, &d_length, | 439 | MYSQL_TYPE_LONG, &accepting, |
320 | MYSQL_TYPE_LONG, &accepting, GNUNET_YES, | 440 | GNUNET_YES, -1); |
321 | -1); | ||
322 | 441 | ||
323 | if (1 != result && 0 != result) | 442 | if (1 != result && 0 != result) |
324 | { | 443 | { |
@@ -343,12 +462,13 @@ announce_regex (const char *regex) | |||
343 | { | 462 | { |
344 | struct GNUNET_REGEX_Automaton *dfa; | 463 | struct GNUNET_REGEX_Automaton *dfa; |
345 | 464 | ||
346 | dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex), max_path_compression); | 465 | dfa = |
466 | GNUNET_REGEX_construct_dfa (regex, strlen (regex), max_path_compression); | ||
347 | 467 | ||
348 | if (NULL == dfa) | 468 | if (NULL == dfa) |
349 | { | 469 | { |
350 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 470 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Failed to create DFA for regex %s\n", |
351 | "Failed to create DFA for regex %s\n", regex); | 471 | regex); |
352 | abort_task = GNUNET_SCHEDULER_add_now (&do_abort, NULL); | 472 | abort_task = GNUNET_SCHEDULER_add_now (&do_abort, NULL); |
353 | return GNUNET_SYSERR; | 473 | return GNUNET_SYSERR; |
354 | } | 474 | } |
@@ -380,21 +500,22 @@ policy_filename_cb (void *cls, const char *filename) | |||
380 | 500 | ||
381 | GNUNET_assert (NULL != filename); | 501 | GNUNET_assert (NULL != filename); |
382 | 502 | ||
383 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, | 503 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, "Announcing regexes from file %s\n", |
384 | "Announcing regexes from file %s\n", | ||
385 | filename); | 504 | filename); |
386 | 505 | ||
387 | if (GNUNET_YES != GNUNET_DISK_file_test (filename)) | 506 | if (GNUNET_YES != GNUNET_DISK_file_test (filename)) |
388 | { | 507 | { |
389 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | 508 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Could not find policy file %s\n", |
390 | "Could not find policy file %s\n", filename); | 509 | filename); |
391 | return GNUNET_OK; | 510 | return GNUNET_OK; |
392 | } | 511 | } |
393 | if (GNUNET_OK != GNUNET_DISK_file_size (filename, &filesize, GNUNET_YES, GNUNET_YES)) | 512 | if (GNUNET_OK != |
513 | GNUNET_DISK_file_size (filename, &filesize, GNUNET_YES, GNUNET_YES)) | ||
394 | filesize = 0; | 514 | filesize = 0; |
395 | if (0 == filesize) | 515 | if (0 == filesize) |
396 | { | 516 | { |
397 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Policy file %s is empty.\n", filename); | 517 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "Policy file %s is empty.\n", |
518 | filename); | ||
398 | return GNUNET_OK; | 519 | return GNUNET_OK; |
399 | } | 520 | } |
400 | data = GNUNET_malloc (filesize); | 521 | data = GNUNET_malloc (filesize); |
@@ -416,24 +537,24 @@ policy_filename_cb (void *cls, const char *filename) | |||
416 | offset++; | 537 | offset++; |
417 | if (((data[offset] == '\n')) && (buf != &data[offset])) | 538 | if (((data[offset] == '\n')) && (buf != &data[offset])) |
418 | { | 539 | { |
419 | data[offset] = '\0'; | 540 | data[offset] = '|'; |
420 | regex = buf; | ||
421 | GNUNET_assert (NULL != regex); | ||
422 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Announcing regex: %s\n", | ||
423 | regex); | ||
424 | num_policies++; | 541 | num_policies++; |
425 | |||
426 | if (GNUNET_OK != announce_regex (regex)) | ||
427 | { | ||
428 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
429 | "Could not announce regex %s\n", regex); | ||
430 | } | ||
431 | |||
432 | buf = &data[offset + 1]; | 542 | buf = &data[offset + 1]; |
433 | } | 543 | } |
434 | else if ((data[offset] == '\n') || (data[offset] == '\0')) | 544 | else if ((data[offset] == '\n') || (data[offset] == '\0')) |
435 | buf = &data[offset + 1]; | 545 | buf = &data[offset + 1]; |
436 | } | 546 | } |
547 | data[offset] = '\0'; | ||
548 | GNUNET_asprintf (®ex, "%s(%s)", regex_prefix, data); | ||
549 | GNUNET_assert (NULL != regex); | ||
550 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Announcing regex: %s\n", regex); | ||
551 | |||
552 | if (GNUNET_OK != announce_regex (regex)) | ||
553 | { | ||
554 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not announce regex %s\n", | ||
555 | regex); | ||
556 | } | ||
557 | GNUNET_free (regex); | ||
437 | GNUNET_free (data); | 558 | GNUNET_free (data); |
438 | return GNUNET_OK; | 559 | return GNUNET_OK; |
439 | } | 560 | } |
@@ -452,32 +573,34 @@ do_directory_scan (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | |||
452 | struct GNUNET_TIME_Relative duration; | 573 | struct GNUNET_TIME_Relative duration; |
453 | char *stmt; | 574 | char *stmt; |
454 | 575 | ||
455 | if (GNUNET_SCHEDULER_NO_TASK != abort_task) | ||
456 | GNUNET_SCHEDULER_cancel (abort_task); | ||
457 | |||
458 | /* Create an MySQL prepared statement for the inserts */ | 576 | /* Create an MySQL prepared statement for the inserts */ |
459 | GNUNET_asprintf (&stmt, INSERT_EDGE_STMT, table_name); | 577 | GNUNET_asprintf (&stmt, INSERT_EDGE_STMT, table_name); |
460 | stmt_handle = GNUNET_MYSQL_statement_prepare (mysql_ctx, stmt); | 578 | stmt_handle = GNUNET_MYSQL_statement_prepare (mysql_ctx, stmt); |
461 | GNUNET_free (stmt); | 579 | GNUNET_free (stmt); |
462 | 580 | ||
581 | GNUNET_asprintf (&stmt, SELECT_KEY_STMT, table_name); | ||
582 | select_stmt_handle = GNUNET_MYSQL_statement_prepare (mysql_ctx, stmt); | ||
583 | GNUNET_free (stmt); | ||
584 | |||
463 | GNUNET_assert (NULL != stmt_handle); | 585 | GNUNET_assert (NULL != stmt_handle); |
464 | 586 | ||
465 | meter = create_meter (num_policy_files, "Announcing policy files\n", GNUNET_YES); | 587 | meter = |
588 | create_meter (num_policy_files, "Announcing policy files\n", GNUNET_YES); | ||
466 | start_time = GNUNET_TIME_absolute_get (); | 589 | start_time = GNUNET_TIME_absolute_get (); |
467 | GNUNET_DISK_directory_scan (policy_dir, | 590 | GNUNET_DISK_directory_scan (policy_dir, &policy_filename_cb, stmt_handle); |
468 | &policy_filename_cb, | ||
469 | stmt_handle); | ||
470 | duration = GNUNET_TIME_absolute_get_duration (start_time); | 591 | duration = GNUNET_TIME_absolute_get_duration (start_time); |
471 | reset_meter (meter); | 592 | reset_meter (meter); |
472 | free_meter (meter); | 593 | free_meter (meter); |
473 | meter = NULL; | 594 | meter = NULL; |
474 | 595 | ||
475 | printf ("Announced %u files containing %u policies in %s\n", | 596 | printf ("Announced %u files containing %u policies in %s\n" |
597 | "Duplicate transitions: %llu\nMerged states: %llu\n", | ||
476 | num_policy_files, num_policies, | 598 | num_policy_files, num_policies, |
477 | GNUNET_STRINGS_relative_time_to_string (duration, GNUNET_NO)); | 599 | GNUNET_STRINGS_relative_time_to_string (duration, GNUNET_NO), |
600 | num_merged_transitions, num_merged_states); | ||
478 | 601 | ||
479 | result = GNUNET_OK; | 602 | result = GNUNET_OK; |
480 | GNUNET_SCHEDULER_add_now (&do_shutdown, NULL); | 603 | shutdown_task = GNUNET_SCHEDULER_add_now (&do_shutdown, NULL); |
481 | } | 604 | } |
482 | 605 | ||
483 | 606 | ||
@@ -495,26 +618,27 @@ run (void *cls, char *const *args, const char *cfgfile, | |||
495 | { | 618 | { |
496 | if (NULL == args[0]) | 619 | if (NULL == args[0]) |
497 | { | 620 | { |
498 | fprintf (stderr, _("No policy directory specified on command line. Exiting.\n")); | 621 | fprintf (stderr, |
622 | _("No policy directory specified on command line. Exiting.\n")); | ||
499 | result = GNUNET_SYSERR; | 623 | result = GNUNET_SYSERR; |
500 | return; | 624 | return; |
501 | } | 625 | } |
502 | if (GNUNET_YES != GNUNET_DISK_directory_test (args[0], GNUNET_YES)) | 626 | if (GNUNET_YES != GNUNET_DISK_directory_test (args[0], GNUNET_YES)) |
503 | { | 627 | { |
504 | fprintf (stderr, _("Specified policies directory does not exist. Exiting.\n")); | 628 | fprintf (stderr, |
629 | _("Specified policies directory does not exist. Exiting.\n")); | ||
505 | result = GNUNET_SYSERR; | 630 | result = GNUNET_SYSERR; |
506 | return; | 631 | return; |
507 | } | 632 | } |
508 | policy_dir = args[0]; | 633 | policy_dir = args[0]; |
509 | 634 | ||
510 | num_policy_files = GNUNET_DISK_directory_scan (policy_dir, | 635 | num_policy_files = GNUNET_DISK_directory_scan (policy_dir, NULL, NULL); |
511 | NULL, | ||
512 | NULL); | ||
513 | meter = NULL; | 636 | meter = NULL; |
514 | 637 | ||
515 | if (NULL == table_name) | 638 | if (NULL == table_name) |
516 | { | 639 | { |
517 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "No table name specified, using default \"NFA\".\n"); | 640 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, |
641 | "No table name specified, using default \"NFA\".\n"); | ||
518 | table_name = "NFA"; | 642 | table_name = "NFA"; |
519 | } | 643 | } |
520 | 644 | ||
@@ -526,14 +650,27 @@ run (void *cls, char *const *args, const char *cfgfile, | |||
526 | return; | 650 | return; |
527 | } | 651 | } |
528 | 652 | ||
653 | if (GNUNET_OK != | ||
654 | GNUNET_CONFIGURATION_get_value_string (config, "regex-mysql", | ||
655 | "REGEX_PREFIX", ®ex_prefix)) | ||
656 | { | ||
657 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
658 | _ | ||
659 | ("%s service is lacking key configuration settings (%s). Exiting.\n"), | ||
660 | "regexprofiler", "regex_prefix"); | ||
661 | result = GNUNET_SYSERR; | ||
662 | return; | ||
663 | } | ||
664 | |||
665 | |||
529 | result = GNUNET_OK; | 666 | result = GNUNET_OK; |
530 | 667 | ||
531 | scan_task = GNUNET_SCHEDULER_add_now (&do_directory_scan, NULL); | 668 | scan_task = GNUNET_SCHEDULER_add_now (&do_directory_scan, NULL); |
532 | 669 | ||
533 | abort_task = | 670 | /* Scheduled the task to clean up when shutdown is called */ |
534 | GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_relative_multiply | 671 | shutdown_task = |
535 | (GNUNET_TIME_UNIT_SECONDS, 10), &do_abort, | 672 | GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL, &do_shutdown, |
536 | NULL); | 673 | NULL); |
537 | } | 674 | } |
538 | 675 | ||
539 | 676 | ||
@@ -563,9 +700,9 @@ main (int argc, char *const *argv) | |||
563 | 700 | ||
564 | result = GNUNET_SYSERR; | 701 | result = GNUNET_SYSERR; |
565 | ret = | 702 | ret = |
566 | GNUNET_PROGRAM_run (argc, argv, "gnunet-regex-simulationprofiler [OPTIONS] policy-dir", | 703 | GNUNET_PROGRAM_run (argc, argv, |
567 | _("Profiler for regex library"), | 704 | "gnunet-regex-simulationprofiler [OPTIONS] policy-dir", |
568 | options, &run, NULL); | 705 | _("Profiler for regex library"), options, &run, NULL); |
569 | if (GNUNET_OK != ret) | 706 | if (GNUNET_OK != ret) |
570 | return ret; | 707 | return ret; |
571 | if (GNUNET_OK != result) | 708 | if (GNUNET_OK != result) |
diff --git a/src/regex/regex.c b/src/regex/regex.c index 96d8747b7..03cdf9d72 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -19,7 +19,9 @@ | |||
19 | */ | 19 | */ |
20 | /** | 20 | /** |
21 | * @file src/regex/regex.c | 21 | * @file src/regex/regex.c |
22 | * @brief library to create automatons from regular expressions | 22 | * @brief library to create Deterministic Finite Automatons (DFAs) from regular |
23 | * expressions (regexes). Used by mesh for announcing regexes in the network and | ||
24 | * matching strings against published regexes. | ||
23 | * @author Maximilian Szengel | 25 | * @author Maximilian Szengel |
24 | */ | 26 | */ |
25 | #include "platform.h" | 27 | #include "platform.h" |
@@ -30,7 +32,7 @@ | |||
30 | 32 | ||
31 | /** | 33 | /** |
32 | * Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA | 34 | * Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA |
33 | * creation. | 35 | * creation. Disabled by default for better performance. |
34 | */ | 36 | */ |
35 | #define REGEX_DEBUG_DFA GNUNET_NO | 37 | #define REGEX_DEBUG_DFA GNUNET_NO |
36 | 38 | ||
@@ -115,7 +117,7 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
115 | return; | 117 | return; |
116 | } | 118 | } |
117 | 119 | ||
118 | // Do not add duplicate state transitions | 120 | /* Do not add duplicate state transitions */ |
119 | for (t = from_state->transitions_head; NULL != t; t = t->next) | 121 | for (t = from_state->transitions_head; NULL != t; t = t->next) |
120 | { | 122 | { |
121 | if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) && | 123 | if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) && |
@@ -123,7 +125,7 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
123 | return; | 125 | return; |
124 | } | 126 | } |
125 | 127 | ||
126 | // sort transitions by label | 128 | /* sort transitions by label */ |
127 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) | 129 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) |
128 | { | 130 | { |
129 | if (0 < nullstrcmp (oth->label, label)) | 131 | if (0 < nullstrcmp (oth->label, label)) |
@@ -140,7 +142,7 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
140 | t->to_state = to_state; | 142 | t->to_state = to_state; |
141 | t->from_state = from_state; | 143 | t->from_state = from_state; |
142 | 144 | ||
143 | // Add outgoing transition to 'from_state' | 145 | /* Add outgoing transition to 'from_state' */ |
144 | from_state->transition_count++; | 146 | from_state->transition_count++; |
145 | GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head, | 147 | GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head, |
146 | from_state->transitions_tail, oth, t); | 148 | from_state->transitions_tail, oth, t); |
@@ -348,7 +350,7 @@ automaton_remove_state (struct GNUNET_REGEX_Automaton *a, | |||
348 | if (NULL == a || NULL == s) | 350 | if (NULL == a || NULL == s) |
349 | return; | 351 | return; |
350 | 352 | ||
351 | // remove all transitions leading to this state | 353 | /* remove all transitions leading to this state */ |
352 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 354 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
353 | { | 355 | { |
354 | for (t_check = s_check->transitions_head; NULL != t_check; | 356 | for (t_check = s_check->transitions_head; NULL != t_check; |
@@ -360,7 +362,7 @@ automaton_remove_state (struct GNUNET_REGEX_Automaton *a, | |||
360 | } | 362 | } |
361 | } | 363 | } |
362 | 364 | ||
363 | // remove state | 365 | /* remove state */ |
364 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | 366 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); |
365 | a->state_count--; | 367 | a->state_count--; |
366 | 368 | ||
@@ -370,7 +372,7 @@ automaton_remove_state (struct GNUNET_REGEX_Automaton *a, | |||
370 | 372 | ||
371 | /** | 373 | /** |
372 | * Merge two states into one. Will merge 's1' and 's2' into 's1' and destroy | 374 | * Merge two states into one. Will merge 's1' and 's2' into 's1' and destroy |
373 | * 's2'. | 375 | * 's2'. 's1' will contain all (non-duplicate) outgoing transitions of 's2'. |
374 | * | 376 | * |
375 | * @param ctx context | 377 | * @param ctx context |
376 | * @param a automaton | 378 | * @param a automaton |
@@ -395,7 +397,7 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
395 | return; | 397 | return; |
396 | 398 | ||
397 | /* 1. Make all transitions pointing to s2 point to s1, unless this transition | 399 | /* 1. Make all transitions pointing to s2 point to s1, unless this transition |
398 | does not already exists, if it already exists remove transition. */ | 400 | * does not already exists, if it already exists remove transition. */ |
399 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 401 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
400 | { | 402 | { |
401 | for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next) | 403 | for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next) |
@@ -428,6 +430,7 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
428 | /* 3. Rename s1 to {s1,s2} */ | 430 | /* 3. Rename s1 to {s1,s2} */ |
429 | #if REGEX_DEBUG_DFA | 431 | #if REGEX_DEBUG_DFA |
430 | char *new_name; | 432 | char *new_name; |
433 | |||
431 | new_name = s1->name; | 434 | new_name = s1->name; |
432 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); | 435 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); |
433 | GNUNET_free (new_name); | 436 | GNUNET_free (new_name); |
@@ -747,12 +750,13 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
747 | size_t length_r; | 750 | size_t length_r; |
748 | 751 | ||
749 | GNUNET_assert (NULL == *R_cur_ij && NULL != R_cur_ij); | 752 | GNUNET_assert (NULL == *R_cur_ij && NULL != R_cur_ij); |
750 | 753 | /* | |
751 | // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} | 754 | * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} |
752 | // R_last == R^{(k-1)}, R_cur == R^{(k)} | 755 | * R_last == R^{(k-1)}, R_cur == R^{(k)} |
753 | // R_cur_ij = R_cur_l | R_cur_r | 756 | * R_cur_ij = R_cur_l | R_cur_r |
754 | // R_cur_l == R^{(k-1)}_{ij} | 757 | * R_cur_l == R^{(k-1)}_{ij} |
755 | // R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} | 758 | * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} |
759 | */ | ||
756 | 760 | ||
757 | if ((NULL == R_last_ij) && ((NULL == R_last_ik) || (NULL == R_last_kk) || /* technically cannot happen, but looks saner */ | 761 | if ((NULL == R_last_ij) && ((NULL == R_last_ik) || (NULL == R_last_kk) || /* technically cannot happen, but looks saner */ |
758 | (NULL == R_last_kj))) | 762 | (NULL == R_last_kj))) |
@@ -770,20 +774,20 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
770 | return; | 774 | return; |
771 | } | 775 | } |
772 | 776 | ||
773 | // $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR | 777 | /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR |
774 | // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} | 778 | * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} */ |
775 | 779 | ||
776 | R_cur_r = NULL; | 780 | R_cur_r = NULL; |
777 | R_cur_l = NULL; | 781 | R_cur_l = NULL; |
778 | 782 | ||
779 | // cache results from strcmp, we might need these many times | 783 | /* cache results from strcmp, we might need these many times */ |
780 | ij_kj_cmp = nullstrcmp (R_last_ij, R_last_kj); | 784 | ij_kj_cmp = nullstrcmp (R_last_ij, R_last_kj); |
781 | ij_ik_cmp = nullstrcmp (R_last_ij, R_last_ik); | 785 | ij_ik_cmp = nullstrcmp (R_last_ij, R_last_ik); |
782 | ik_kk_cmp = nullstrcmp (R_last_ik, R_last_kk); | 786 | ik_kk_cmp = nullstrcmp (R_last_ik, R_last_kk); |
783 | kk_kj_cmp = nullstrcmp (R_last_kk, R_last_kj); | 787 | kk_kj_cmp = nullstrcmp (R_last_kk, R_last_kj); |
784 | 788 | ||
785 | // Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well | 789 | /* Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well |
786 | // as parentheses, so we can better compare the contents | 790 | * as parentheses, so we can better compare the contents */ |
787 | R_temp_ik = remove_parentheses (remove_epsilon (R_last_ik)); | 791 | R_temp_ik = remove_parentheses (remove_epsilon (R_last_ik)); |
788 | R_temp_kk = remove_parentheses (remove_epsilon (R_last_kk)); | 792 | R_temp_kk = remove_parentheses (remove_epsilon (R_last_kk)); |
789 | R_temp_kj = remove_parentheses (remove_epsilon (R_last_kj)); | 793 | R_temp_kj = remove_parentheses (remove_epsilon (R_last_kj)); |
@@ -791,11 +795,11 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
791 | clean_ik_kk_cmp = nullstrcmp (R_last_ik, R_temp_kk); | 795 | clean_ik_kk_cmp = nullstrcmp (R_last_ik, R_temp_kk); |
792 | clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last_kj); | 796 | clean_kk_kj_cmp = nullstrcmp (R_temp_kk, R_last_kj); |
793 | 797 | ||
794 | // construct R_cur_l (and, if necessary R_cur_r) | 798 | /* construct R_cur_l (and, if necessary R_cur_r) */ |
795 | if (NULL != R_last_ij) | 799 | if (NULL != R_last_ij) |
796 | { | 800 | { |
797 | // Assign R_temp_ij to R_last_ij and remove epsilon as well | 801 | /* Assign R_temp_ij to R_last_ij and remove epsilon as well |
798 | // as parentheses, so we can better compare the contents | 802 | * as parentheses, so we can better compare the contents */ |
799 | R_temp_ij = remove_parentheses (remove_epsilon (R_last_ij)); | 803 | R_temp_ij = remove_parentheses (remove_epsilon (R_last_ij)); |
800 | 804 | ||
801 | if (0 == strcmp (R_temp_ij, R_temp_ik) && 0 == strcmp (R_temp_ik, R_temp_kk) | 805 | if (0 == strcmp (R_temp_ij, R_temp_ik) && 0 == strcmp (R_temp_ik, R_temp_kk) |
@@ -809,13 +813,15 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
809 | (0 == strncmp (R_last_ik, "(|", 2) && | 813 | (0 == strncmp (R_last_ik, "(|", 2) && |
810 | 0 == strncmp (R_last_kj, "(|", 2))) | 814 | 0 == strncmp (R_last_kj, "(|", 2))) |
811 | { | 815 | { |
812 | // a|(e|a)a*(e|a) = a* | 816 | /* |
813 | // a|(e|a)(e|a)*(e|a) = a* | 817 | * a|(e|a)a*(e|a) = a* |
814 | // (e|a)|aa*a = a* | 818 | * a|(e|a)(e|a)*(e|a) = a* |
815 | // (e|a)|aa*(e|a) = a* | 819 | * (e|a)|aa*a = a* |
816 | // (e|a)|(e|a)a*a = a* | 820 | * (e|a)|aa*(e|a) = a* |
817 | // (e|a)|(e|a)a*(e|a) = a* | 821 | * (e|a)|(e|a)a*a = a* |
818 | // (e|a)|(e|a)(e|a)*(e|a) = a* | 822 | * (e|a)|(e|a)a*(e|a) = a* |
823 | * (e|a)|(e|a)(e|a)*(e|a) = a* | ||
824 | */ | ||
819 | if (GNUNET_YES == needs_parentheses (R_temp_ij)) | 825 | if (GNUNET_YES == needs_parentheses (R_temp_ij)) |
820 | GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_ij); | 826 | GNUNET_asprintf (&R_cur_r, "(%s)*", R_temp_ij); |
821 | else | 827 | else |
@@ -823,11 +829,13 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
823 | } | 829 | } |
824 | else | 830 | else |
825 | { | 831 | { |
826 | // a|aa*a = a+ | 832 | /* |
827 | // a|(e|a)a*a = a+ | 833 | * a|aa*a = a+ |
828 | // a|aa*(e|a) = a+ | 834 | * a|(e|a)a*a = a+ |
829 | // a|(e|a)(e|a)*a = a+ | 835 | * a|aa*(e|a) = a+ |
830 | // a|a(e|a)*(e|a) = a+ | 836 | * a|(e|a)(e|a)*a = a+ |
837 | * a|a(e|a)*(e|a) = a+ | ||
838 | */ | ||
831 | if (GNUNET_YES == needs_parentheses (R_temp_ij)) | 839 | if (GNUNET_YES == needs_parentheses (R_temp_ij)) |
832 | GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_ij); | 840 | GNUNET_asprintf (&R_cur_r, "(%s)+", R_temp_ij); |
833 | else | 841 | else |
@@ -836,7 +844,7 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
836 | } | 844 | } |
837 | else if (0 == ij_ik_cmp && 0 == clean_kk_kj_cmp && 0 != clean_ik_kk_cmp) | 845 | else if (0 == ij_ik_cmp && 0 == clean_kk_kj_cmp && 0 != clean_ik_kk_cmp) |
838 | { | 846 | { |
839 | // a|ab*b = ab* | 847 | /* a|ab*b = ab* */ |
840 | if (strlen (R_last_kk) < 1) | 848 | if (strlen (R_last_kk) < 1) |
841 | R_cur_r = GNUNET_strdup (R_last_ij); | 849 | R_cur_r = GNUNET_strdup (R_last_ij); |
842 | else if (GNUNET_YES == needs_parentheses (R_temp_kk)) | 850 | else if (GNUNET_YES == needs_parentheses (R_temp_kk)) |
@@ -848,7 +856,7 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
848 | } | 856 | } |
849 | else if (0 == ij_kj_cmp && 0 == clean_ik_kk_cmp && 0 != clean_kk_kj_cmp) | 857 | else if (0 == ij_kj_cmp && 0 == clean_ik_kk_cmp && 0 != clean_kk_kj_cmp) |
850 | { | 858 | { |
851 | // a|bb*a = b*a | 859 | /* a|bb*a = b*a */ |
852 | if (strlen (R_last_kk) < 1) | 860 | if (strlen (R_last_kk) < 1) |
853 | R_cur_r = GNUNET_strdup (R_last_kj); | 861 | R_cur_r = GNUNET_strdup (R_last_kj); |
854 | else if (GNUNET_YES == needs_parentheses (R_temp_kk)) | 862 | else if (GNUNET_YES == needs_parentheses (R_temp_kk)) |
@@ -861,7 +869,7 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
861 | else if (0 == ij_ik_cmp && 0 == kk_kj_cmp && !has_epsilon (R_last_ij) && | 869 | else if (0 == ij_ik_cmp && 0 == kk_kj_cmp && !has_epsilon (R_last_ij) && |
862 | has_epsilon (R_last_kk)) | 870 | has_epsilon (R_last_kk)) |
863 | { | 871 | { |
864 | // a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* | 872 | /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */ |
865 | if (needs_parentheses (R_temp_kk)) | 873 | if (needs_parentheses (R_temp_kk)) |
866 | GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last_ij, R_temp_kk); | 874 | GNUNET_asprintf (&R_cur_r, "%s(%s)*", R_last_ij, R_temp_kk); |
867 | else | 875 | else |
@@ -872,7 +880,7 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
872 | else if (0 == ij_kj_cmp && 0 == ik_kk_cmp && !has_epsilon (R_last_ij) && | 880 | else if (0 == ij_kj_cmp && 0 == ik_kk_cmp && !has_epsilon (R_last_ij) && |
873 | has_epsilon (R_last_kk)) | 881 | has_epsilon (R_last_kk)) |
874 | { | 882 | { |
875 | // a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a | 883 | /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a */ |
876 | if (needs_parentheses (R_temp_kk)) | 884 | if (needs_parentheses (R_temp_kk)) |
877 | GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last_ij); | 885 | GNUNET_asprintf (&R_cur_r, "(%s)*%s", R_temp_kk, R_last_ij); |
878 | else | 886 | else |
@@ -891,16 +899,16 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
891 | } | 899 | } |
892 | else | 900 | else |
893 | { | 901 | { |
894 | // we have no left side | 902 | /* we have no left side */ |
895 | R_cur_l = NULL; | 903 | R_cur_l = NULL; |
896 | } | 904 | } |
897 | 905 | ||
898 | // construct R_cur_r, if not already constructed | 906 | /* construct R_cur_r, if not already constructed */ |
899 | if (NULL == R_cur_r) | 907 | if (NULL == R_cur_r) |
900 | { | 908 | { |
901 | length = strlen (R_temp_kk) - strlen (R_last_ik); | 909 | length = strlen (R_temp_kk) - strlen (R_last_ik); |
902 | 910 | ||
903 | // a(ba)*bx = (ab)+x | 911 | /* a(ba)*bx = (ab)+x */ |
904 | if (length > 0 && NULL != R_last_kk && 0 < strlen (R_last_kk) && | 912 | if (length > 0 && NULL != R_last_kk && 0 < strlen (R_last_kk) && |
905 | NULL != R_last_kj && 0 < strlen (R_last_kj) && NULL != R_last_ik && | 913 | NULL != R_last_kj && 0 < strlen (R_last_kj) && NULL != R_last_ik && |
906 | 0 < strlen (R_last_ik) && 0 == strkcmp (R_temp_kk, R_last_ik, length) && | 914 | 0 < strlen (R_last_ik) && 0 == strkcmp (R_temp_kk, R_last_ik, length) && |
@@ -928,7 +936,7 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
928 | temp_a[length_l] = '\0'; | 936 | temp_a[length_l] = '\0'; |
929 | temp_b[length_r] = '\0'; | 937 | temp_b[length_r] = '\0'; |
930 | 938 | ||
931 | // e|(ab)+ = (ab)* | 939 | /* e|(ab)+ = (ab)* */ |
932 | if (NULL != R_cur_l && 0 == strlen (R_cur_l) && 0 == strlen (temp_b)) | 940 | if (NULL != R_cur_l && 0 == strlen (R_cur_l) && 0 == strlen (temp_b)) |
933 | { | 941 | { |
934 | GNUNET_asprintf (&R_cur_r, "(%s%s)*", R_last_ik, temp_a); | 942 | GNUNET_asprintf (&R_cur_r, "(%s%s)*", R_last_ik, temp_a); |
@@ -945,8 +953,10 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
945 | else if (0 == strcmp (R_temp_ik, R_temp_kk) && | 953 | else if (0 == strcmp (R_temp_ik, R_temp_kk) && |
946 | 0 == strcmp (R_temp_kk, R_temp_kj)) | 954 | 0 == strcmp (R_temp_kk, R_temp_kj)) |
947 | { | 955 | { |
948 | // (e|a)a*(e|a) = a* | 956 | /* |
949 | // (e|a)(e|a)*(e|a) = a* | 957 | * (e|a)a*(e|a) = a* |
958 | * (e|a)(e|a)*(e|a) = a* | ||
959 | */ | ||
950 | if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj)) | 960 | if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj)) |
951 | { | 961 | { |
952 | if (needs_parentheses (R_temp_kk)) | 962 | if (needs_parentheses (R_temp_kk)) |
@@ -954,7 +964,7 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
954 | else | 964 | else |
955 | GNUNET_asprintf (&R_cur_r, "%s*", R_temp_kk); | 965 | GNUNET_asprintf (&R_cur_r, "%s*", R_temp_kk); |
956 | } | 966 | } |
957 | // aa*a = a+a | 967 | /* aa*a = a+a */ |
958 | else if (0 == clean_ik_kk_cmp && 0 == clean_kk_kj_cmp && | 968 | else if (0 == clean_ik_kk_cmp && 0 == clean_kk_kj_cmp && |
959 | !has_epsilon (R_last_ik)) | 969 | !has_epsilon (R_last_ik)) |
960 | { | 970 | { |
@@ -963,10 +973,12 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
963 | else | 973 | else |
964 | GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk); | 974 | GNUNET_asprintf (&R_cur_r, "(%s)+%s", R_temp_kk, R_temp_kk); |
965 | } | 975 | } |
966 | // (e|a)a*a = a+ | 976 | /* |
967 | // aa*(e|a) = a+ | 977 | * (e|a)a*a = a+ |
968 | // a(e|a)*(e|a) = a+ | 978 | * aa*(e|a) = a+ |
969 | // (e|a)a*a = a+ | 979 | * a(e|a)*(e|a) = a+ |
980 | * (e|a)a*a = a+ | ||
981 | */ | ||
970 | else | 982 | else |
971 | { | 983 | { |
972 | eps_check = | 984 | eps_check = |
@@ -982,8 +994,10 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
982 | } | 994 | } |
983 | } | 995 | } |
984 | } | 996 | } |
985 | // aa*b = a+b | 997 | /* |
986 | // (e|a)(e|a)*b = a*b | 998 | * aa*b = a+b |
999 | * (e|a)(e|a)*b = a*b | ||
1000 | */ | ||
987 | else if (0 == strcmp (R_temp_ik, R_temp_kk)) | 1001 | else if (0 == strcmp (R_temp_ik, R_temp_kk)) |
988 | { | 1002 | { |
989 | if (has_epsilon (R_last_ik)) | 1003 | if (has_epsilon (R_last_ik)) |
@@ -1001,8 +1015,10 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
1001 | GNUNET_asprintf (&R_cur_r, "%s+%s", R_temp_kk, R_last_kj); | 1015 | GNUNET_asprintf (&R_cur_r, "%s+%s", R_temp_kk, R_last_kj); |
1002 | } | 1016 | } |
1003 | } | 1017 | } |
1004 | // ba*a = ba+ | 1018 | /* |
1005 | // b(e|a)*(e|a) = ba* | 1019 | * ba*a = ba+ |
1020 | * b(e|a)*(e|a) = ba* | ||
1021 | */ | ||
1006 | else if (0 == strcmp (R_temp_kk, R_temp_kj)) | 1022 | else if (0 == strcmp (R_temp_kk, R_temp_kj)) |
1007 | { | 1023 | { |
1008 | if (has_epsilon (R_last_kj)) | 1024 | if (has_epsilon (R_last_kj)) |
@@ -1079,11 +1095,15 @@ automaton_create_proofs_simplify (char *R_last_ij, char *R_last_ik, | |||
1079 | 1095 | ||
1080 | 1096 | ||
1081 | /** | 1097 | /** |
1082 | * create proofs for all states in the given automaton. Implementation of the | 1098 | * Create proofs for all states in the given automaton. Implementation of the |
1083 | * algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and | 1099 | * algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and |
1084 | * Computation 3rd Edition" by Hopcroft, Motwani and Ullman. | 1100 | * Computation 3rd Edition" by Hopcroft, Motwani and Ullman. |
1085 | * | 1101 | * |
1086 | * @param a automaton. | 1102 | * Each state in the automaton gets assigned 'proof' and 'hash' (hash of the |
1103 | * proof) fields. The starting state will only have a valid proof/hash if it has | ||
1104 | * any incoming transitions. | ||
1105 | * | ||
1106 | * @param a automaton for which to assign proofs and hashes. | ||
1087 | */ | 1107 | */ |
1088 | static void | 1108 | static void |
1089 | automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | 1109 | automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) |
@@ -1132,16 +1152,17 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1132 | else | 1152 | else |
1133 | { | 1153 | { |
1134 | temp = R_last[i * n + j]; | 1154 | temp = R_last[i * n + j]; |
1135 | GNUNET_asprintf (&R_last[i * n + j], "%s|%s", R_last[i * n + j], t->label); | 1155 | GNUNET_asprintf (&R_last[i * n + j], "%s|%s", R_last[i * n + j], |
1156 | t->label); | ||
1136 | GNUNET_free (temp); | 1157 | GNUNET_free (temp); |
1137 | } | 1158 | } |
1138 | } | 1159 | } |
1139 | if (NULL == R_last[i*n+i]) | 1160 | if (NULL == R_last[i * n + i]) |
1140 | GNUNET_asprintf (&R_last[i*n+i], ""); | 1161 | GNUNET_asprintf (&R_last[i * n + i], ""); |
1141 | else | 1162 | else |
1142 | { | 1163 | { |
1143 | temp = R_last[i*n+i]; | 1164 | temp = R_last[i * n + i]; |
1144 | GNUNET_asprintf (&R_last[i*n+i], "(|%s)", R_last[i*n+i]); | 1165 | GNUNET_asprintf (&R_last[i * n + i], "(|%s)", R_last[i * n + i]); |
1145 | GNUNET_free (temp); | 1166 | GNUNET_free (temp); |
1146 | } | 1167 | } |
1147 | } | 1168 | } |
@@ -1162,18 +1183,19 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1162 | { | 1183 | { |
1163 | for (j = 0; j < n; j++) | 1184 | for (j = 0; j < n; j++) |
1164 | { | 1185 | { |
1165 | // Basis for the recursion: | 1186 | /* Basis for the recursion: |
1166 | // $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} | 1187 | * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} |
1167 | // R_last == R^{(k-1)}, R_cur == R^{(k)} | 1188 | * R_last == R^{(k-1)}, R_cur == R^{(k)} |
1168 | 1189 | */ | |
1169 | // Create R_cur[i][j] and simplify the expression | 1190 | |
1170 | automaton_create_proofs_simplify (R_last[i * n + j], R_last[i*n+k], | 1191 | /* Create R_cur[i][j] and simplify the expression */ |
1171 | R_last[k*n+k], R_last[k*n+j], | 1192 | automaton_create_proofs_simplify (R_last[i * n + j], R_last[i * n + k], |
1193 | R_last[k * n + k], R_last[k * n + j], | ||
1172 | &R_cur[i * n + j]); | 1194 | &R_cur[i * n + j]); |
1173 | } | 1195 | } |
1174 | } | 1196 | } |
1175 | 1197 | ||
1176 | // set R_last = R_cur | 1198 | /* set R_last = R_cur */ |
1177 | for (i = 0; i < n; i++) | 1199 | for (i = 0; i < n; i++) |
1178 | { | 1200 | { |
1179 | for (j = 0; j < n; j++) | 1201 | for (j = 0; j < n; j++) |
@@ -1185,41 +1207,43 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1185 | } | 1207 | } |
1186 | } | 1208 | } |
1187 | 1209 | ||
1188 | // assign proofs and hashes | 1210 | /* assign proofs and hashes */ |
1189 | for (i = 0; i < n; i++) | 1211 | for (i = 0; i < n; i++) |
1190 | { | 1212 | { |
1191 | if (NULL != R_last[a->start->dfs_id*n+i]) | 1213 | if (NULL != R_last[a->start->dfs_id * n + i]) |
1192 | { | 1214 | { |
1193 | states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id*n+i]); | 1215 | states[i]->proof = GNUNET_strdup (R_last[a->start->dfs_id * n + i]); |
1194 | GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof), | 1216 | GNUNET_CRYPTO_hash (states[i]->proof, strlen (states[i]->proof), |
1195 | &states[i]->hash); | 1217 | &states[i]->hash); |
1196 | } | 1218 | } |
1197 | } | 1219 | } |
1198 | 1220 | ||
1199 | // complete regex for whole DFA: union of all pairs (start state/accepting | 1221 | /* complete regex for whole DFA: union of all pairs (start state/accepting |
1200 | // state(s)). | 1222 | * state(s)). */ |
1201 | complete_regex = NULL; | 1223 | complete_regex = NULL; |
1202 | for (i = 0; i < n; i++) | 1224 | for (i = 0; i < n; i++) |
1203 | { | 1225 | { |
1204 | if (states[i]->accepting) | 1226 | if (states[i]->accepting) |
1205 | { | 1227 | { |
1206 | if (NULL == complete_regex && 0 < strlen (R_last[a->start->dfs_id*n+i])) | 1228 | if (NULL == complete_regex && |
1229 | 0 < strlen (R_last[a->start->dfs_id * n + i])) | ||
1207 | { | 1230 | { |
1208 | GNUNET_asprintf (&complete_regex, "%s", R_last[a->start->dfs_id*n+i]); | 1231 | GNUNET_asprintf (&complete_regex, "%s", |
1232 | R_last[a->start->dfs_id * n + i]); | ||
1209 | } | 1233 | } |
1210 | else if (NULL != R_last[a->start->dfs_id*n+i] && | 1234 | else if (NULL != R_last[a->start->dfs_id * n + i] && |
1211 | 0 < strlen (R_last[a->start->dfs_id*n+i])) | 1235 | 0 < strlen (R_last[a->start->dfs_id * n + i])) |
1212 | { | 1236 | { |
1213 | temp = complete_regex; | 1237 | temp = complete_regex; |
1214 | GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex, | 1238 | GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex, |
1215 | R_last[a->start->dfs_id*n+i]); | 1239 | R_last[a->start->dfs_id * n + i]); |
1216 | GNUNET_free (temp); | 1240 | GNUNET_free (temp); |
1217 | } | 1241 | } |
1218 | } | 1242 | } |
1219 | } | 1243 | } |
1220 | a->canonical_regex = complete_regex; | 1244 | a->canonical_regex = complete_regex; |
1221 | 1245 | ||
1222 | // cleanup | 1246 | /* cleanup */ |
1223 | for (i = 0; i < n; i++) | 1247 | for (i = 0; i < n; i++) |
1224 | { | 1248 | { |
1225 | for (j = 0; j < n; j++) | 1249 | for (j = 0; j < n; j++) |
@@ -1272,7 +1296,7 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
1272 | if (nfa_states->len < 1) | 1296 | if (nfa_states->len < 1) |
1273 | return s; | 1297 | return s; |
1274 | 1298 | ||
1275 | // Create a name based on 'nfa_states' | 1299 | /* Create a name based on 'nfa_states' */ |
1276 | s->name = GNUNET_malloc (sizeof (char) * 2); | 1300 | s->name = GNUNET_malloc (sizeof (char) * 2); |
1277 | strcat (s->name, "{"); | 1301 | strcat (s->name, "{"); |
1278 | name = NULL; | 1302 | name = NULL; |
@@ -1291,15 +1315,15 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
1291 | name = NULL; | 1315 | name = NULL; |
1292 | } | 1316 | } |
1293 | 1317 | ||
1294 | // Add a transition for each distinct label to NULL state | 1318 | /* Add a transition for each distinct label to NULL state */ |
1295 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) | 1319 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) |
1296 | { | 1320 | { |
1297 | if (NULL != ctran->label) | 1321 | if (NULL != ctran->label) |
1298 | state_add_transition (ctx, s, ctran->label, NULL); | 1322 | state_add_transition (ctx, s, ctran->label, NULL); |
1299 | } | 1323 | } |
1300 | 1324 | ||
1301 | // If the nfa_states contain an accepting state, the new dfa state is also | 1325 | /* If the nfa_states contain an accepting state, the new dfa state is also |
1302 | // accepting | 1326 | * accepting. */ |
1303 | if (cstate->accepting) | 1327 | if (cstate->accepting) |
1304 | s->accepting = 1; | 1328 | s->accepting = 1; |
1305 | } | 1329 | } |
@@ -1381,14 +1405,14 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | |||
1381 | struct GNUNET_REGEX_State *s; | 1405 | struct GNUNET_REGEX_State *s; |
1382 | struct GNUNET_REGEX_State *s_next; | 1406 | struct GNUNET_REGEX_State *s_next; |
1383 | 1407 | ||
1384 | // 1. unmark all states | 1408 | /* 1. unmark all states */ |
1385 | for (s = a->states_head; NULL != s; s = s->next) | 1409 | for (s = a->states_head; NULL != s; s = s->next) |
1386 | s->marked = GNUNET_NO; | 1410 | s->marked = GNUNET_NO; |
1387 | 1411 | ||
1388 | // 2. traverse dfa from start state and mark all visited states | 1412 | /* 2. traverse dfa from start state and mark all visited states */ |
1389 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL); | 1413 | GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL); |
1390 | 1414 | ||
1391 | // 3. delete all states that were not visited | 1415 | /* 3. delete all states that were not visited */ |
1392 | for (s = a->states_head; NULL != s; s = s_next) | 1416 | for (s = a->states_head; NULL != s; s = s_next) |
1393 | { | 1417 | { |
1394 | s_next = s->next; | 1418 | s_next = s->next; |
@@ -1434,7 +1458,7 @@ dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a) | |||
1434 | if (0 == dead) | 1458 | if (0 == dead) |
1435 | continue; | 1459 | continue; |
1436 | 1460 | ||
1437 | // state s is dead, remove it | 1461 | /* state s is dead, remove it */ |
1438 | automaton_remove_state (a, s); | 1462 | automaton_remove_state (a, s); |
1439 | } | 1463 | } |
1440 | } | 1464 | } |
@@ -1470,7 +1494,8 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1470 | } | 1494 | } |
1471 | 1495 | ||
1472 | state_cnt = a->state_count; | 1496 | state_cnt = a->state_count; |
1473 | table = (int *)GNUNET_malloc_large (sizeof (int) * state_cnt * a->state_count); | 1497 | table = |
1498 | (int *) GNUNET_malloc_large (sizeof (int) * state_cnt * a->state_count); | ||
1474 | 1499 | ||
1475 | for (i = 0, s1 = a->states_head; i < state_cnt && NULL != s1; | 1500 | for (i = 0, s1 = a->states_head; i < state_cnt && NULL != s1; |
1476 | i++, s1 = s1->next) | 1501 | i++, s1 = s1->next) |
@@ -1513,8 +1538,12 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
1513 | if (0 == strcmp (t1->label, t2->label)) | 1538 | if (0 == strcmp (t1->label, t2->label)) |
1514 | { | 1539 | { |
1515 | num_equal_edges++; | 1540 | num_equal_edges++; |
1516 | if (0 != table[((t1->to_state->marked * state_cnt) + t2->to_state->marked)] || | 1541 | if (0 != |
1517 | 0 != table[((t2->to_state->marked * state_cnt) + t1->to_state->marked)]) | 1542 | table[((t1->to_state->marked * state_cnt) + |
1543 | t2->to_state->marked)] || | ||
1544 | 0 != | ||
1545 | table[((t2->to_state->marked * state_cnt) + | ||
1546 | t1->to_state->marked)]) | ||
1518 | { | 1547 | { |
1519 | table[((s1->marked * state_cnt) + s2->marked)] = 1; | 1548 | table[((s1->marked * state_cnt) + s2->marked)] = 1; |
1520 | change = 1; | 1549 | change = 1; |
@@ -1564,13 +1593,13 @@ dfa_minimize (struct GNUNET_REGEX_Context *ctx, | |||
1564 | 1593 | ||
1565 | GNUNET_assert (DFA == a->type); | 1594 | GNUNET_assert (DFA == a->type); |
1566 | 1595 | ||
1567 | // 1. remove unreachable states | 1596 | /* 1. remove unreachable states */ |
1568 | dfa_remove_unreachable_states (a); | 1597 | dfa_remove_unreachable_states (a); |
1569 | 1598 | ||
1570 | // 2. remove dead states | 1599 | /* 2. remove dead states */ |
1571 | dfa_remove_dead_states (a); | 1600 | dfa_remove_dead_states (a); |
1572 | 1601 | ||
1573 | // 3. Merge nondistinguishable states | 1602 | /* 3. Merge nondistinguishable states */ |
1574 | dfa_merge_nondistinguishable_states (ctx, a); | 1603 | dfa_merge_nondistinguishable_states (ctx, a); |
1575 | } | 1604 | } |
1576 | 1605 | ||
@@ -1685,11 +1714,11 @@ GNUNET_REGEX_dfa_add_multi_strides (struct GNUNET_REGEX_Context *regex_ctx, | |||
1685 | if (1 > stride_len || GNUNET_YES == dfa->is_multistrided) | 1714 | if (1 > stride_len || GNUNET_YES == dfa->is_multistrided) |
1686 | return; | 1715 | return; |
1687 | 1716 | ||
1688 | // Compute the new transitions of given stride_len | 1717 | /* Compute the new transitions of given stride_len */ |
1689 | GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, | 1718 | GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, |
1690 | &dfa_add_multi_strides, &ctx); | 1719 | &dfa_add_multi_strides, &ctx); |
1691 | 1720 | ||
1692 | // Add all the new transitions to the automaton. | 1721 | /* Add all the new transitions to the automaton. */ |
1693 | for (t = ctx.transitions_head; NULL != t; t = t_next) | 1722 | for (t = ctx.transitions_head; NULL != t; t = t_next) |
1694 | { | 1723 | { |
1695 | t_next = t->next; | 1724 | t_next = t->next; |
@@ -1699,7 +1728,7 @@ GNUNET_REGEX_dfa_add_multi_strides (struct GNUNET_REGEX_Context *regex_ctx, | |||
1699 | GNUNET_free (t); | 1728 | GNUNET_free (t); |
1700 | } | 1729 | } |
1701 | 1730 | ||
1702 | // Mark this automaton as multistrided | 1731 | /* Mark this automaton as multistrided */ |
1703 | dfa->is_multistrided = GNUNET_YES; | 1732 | dfa->is_multistrided = GNUNET_YES; |
1704 | } | 1733 | } |
1705 | 1734 | ||
@@ -1729,10 +1758,9 @@ dfa_compress_paths_helper (struct GNUNET_REGEX_Automaton *dfa, | |||
1729 | 1758 | ||
1730 | 1759 | ||
1731 | if (NULL != label && | 1760 | if (NULL != label && |
1732 | ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting | 1761 | ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting || |
1733 | // || cur->transition_count > 1 | 1762 | GNUNET_YES == cur->marked) || (start != dfa->start && max_len > 0 && |
1734 | || GNUNET_YES == cur->marked) || (start != dfa->start && max_len > 0 && | 1763 | max_len == strlen (label)) || |
1735 | max_len == strlen (label)) || | ||
1736 | (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label)))) | 1764 | (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label)))) |
1737 | { | 1765 | { |
1738 | t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); | 1766 | t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); |
@@ -1795,7 +1823,7 @@ dfa_compress_paths (struct GNUNET_REGEX_Context *regex_ctx, | |||
1795 | if (NULL == dfa) | 1823 | if (NULL == dfa) |
1796 | return; | 1824 | return; |
1797 | 1825 | ||
1798 | // Count the incoming transitions on each state. | 1826 | /* Count the incoming transitions on each state. */ |
1799 | for (s = dfa->states_head; NULL != s; s = s->next) | 1827 | for (s = dfa->states_head; NULL != s; s = s->next) |
1800 | { | 1828 | { |
1801 | for (t = s->transitions_head; NULL != t; t = t->next) | 1829 | for (t = s->transitions_head; NULL != t; t = t->next) |
@@ -1805,18 +1833,18 @@ dfa_compress_paths (struct GNUNET_REGEX_Context *regex_ctx, | |||
1805 | } | 1833 | } |
1806 | } | 1834 | } |
1807 | 1835 | ||
1808 | // Unmark all states. | 1836 | /* Unmark all states. */ |
1809 | for (s = dfa->states_head; NULL != s; s = s->next) | 1837 | for (s = dfa->states_head; NULL != s; s = s->next) |
1810 | { | 1838 | { |
1811 | s->marked = GNUNET_NO; | 1839 | s->marked = GNUNET_NO; |
1812 | s->contained = GNUNET_NO; | 1840 | s->contained = GNUNET_NO; |
1813 | } | 1841 | } |
1814 | 1842 | ||
1815 | // Add strides and mark states that can be deleted. | 1843 | /* Add strides and mark states that can be deleted. */ |
1816 | dfa_compress_paths_helper (dfa, dfa->start, dfa->start, NULL, max_len, | 1844 | dfa_compress_paths_helper (dfa, dfa->start, dfa->start, NULL, max_len, |
1817 | &transitions_head, &transitions_tail); | 1845 | &transitions_head, &transitions_tail); |
1818 | 1846 | ||
1819 | // Add all the new transitions to the automaton. | 1847 | /* Add all the new transitions to the automaton. */ |
1820 | for (t = transitions_head; NULL != t; t = t_next) | 1848 | for (t = transitions_head; NULL != t; t = t_next) |
1821 | { | 1849 | { |
1822 | t_next = t->next; | 1850 | t_next = t->next; |
@@ -1826,7 +1854,7 @@ dfa_compress_paths (struct GNUNET_REGEX_Context *regex_ctx, | |||
1826 | GNUNET_free (t); | 1854 | GNUNET_free (t); |
1827 | } | 1855 | } |
1828 | 1856 | ||
1829 | // Remove marked states (including their incoming and outgoing transitions). | 1857 | /* Remove marked states (including their incoming and outgoing transitions). */ |
1830 | for (s = dfa->states_head; NULL != s; s = s_next) | 1858 | for (s = dfa->states_head; NULL != s; s = s_next) |
1831 | { | 1859 | { |
1832 | s_next = s->next; | 1860 | s_next = s->next; |
@@ -1955,7 +1983,7 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1955 | { | 1983 | { |
1956 | unsigned int i; | 1984 | unsigned int i; |
1957 | struct GNUNET_REGEX_StateSet *cls; | 1985 | struct GNUNET_REGEX_StateSet *cls; |
1958 | struct GNUNET_REGEX_StateSet_MDLL cls_check; | 1986 | struct GNUNET_REGEX_StateSet_MDLL cls_stack; |
1959 | struct GNUNET_REGEX_State *clsstate; | 1987 | struct GNUNET_REGEX_State *clsstate; |
1960 | struct GNUNET_REGEX_State *currentstate; | 1988 | struct GNUNET_REGEX_State *currentstate; |
1961 | struct GNUNET_REGEX_Transition *ctran; | 1989 | struct GNUNET_REGEX_Transition *ctran; |
@@ -1964,21 +1992,22 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1964 | return NULL; | 1992 | return NULL; |
1965 | 1993 | ||
1966 | cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet)); | 1994 | cls = GNUNET_malloc (sizeof (struct GNUNET_REGEX_StateSet)); |
1967 | cls_check.head = NULL; | 1995 | cls_stack.head = NULL; |
1968 | cls_check.tail = NULL; | 1996 | cls_stack.tail = NULL; |
1969 | 1997 | ||
1970 | // Add start state to closure only for epsilon closure | 1998 | /* Add start state to closure only for epsilon closure */ |
1971 | if (NULL == label) | 1999 | if (NULL == label) |
1972 | GNUNET_array_append (cls->states, cls->len, s); | 2000 | GNUNET_array_append (cls->states, cls->len, s); |
1973 | 2001 | ||
1974 | GNUNET_CONTAINER_MDLL_insert (SS, cls_check.head, cls_check.tail, s); | 2002 | GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s); |
1975 | cls_check.len = 1; | 2003 | cls_stack.len = 1; |
1976 | 2004 | ||
1977 | while (cls_check.len > 0) | 2005 | while (cls_stack.len > 0) |
1978 | { | 2006 | { |
1979 | currentstate = cls_check.tail; | 2007 | currentstate = cls_stack.tail; |
1980 | GNUNET_CONTAINER_MDLL_remove (SS, cls_check.head, cls_check.tail, currentstate); | 2008 | GNUNET_CONTAINER_MDLL_remove (ST, cls_stack.head, cls_stack.tail, |
1981 | cls_check.len--; | 2009 | currentstate); |
2010 | cls_stack.len--; | ||
1982 | 2011 | ||
1983 | for (ctran = currentstate->transitions_head; NULL != ctran; | 2012 | for (ctran = currentstate->transitions_head; NULL != ctran; |
1984 | ctran = ctran->next) | 2013 | ctran = ctran->next) |
@@ -1990,8 +2019,9 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1990 | if (NULL != clsstate && 0 == clsstate->contained) | 2019 | if (NULL != clsstate && 0 == clsstate->contained) |
1991 | { | 2020 | { |
1992 | GNUNET_array_append (cls->states, cls->len, clsstate); | 2021 | GNUNET_array_append (cls->states, cls->len, clsstate); |
1993 | GNUNET_CONTAINER_MDLL_insert_tail (SS, cls_check.head, cls_check.tail, clsstate); | 2022 | GNUNET_CONTAINER_MDLL_insert_tail (ST, cls_stack.head, cls_stack.tail, |
1994 | cls_check.len++; | 2023 | clsstate); |
2024 | cls_stack.len++; | ||
1995 | clsstate->contained = 1; | 2025 | clsstate->contained = 1; |
1996 | } | 2026 | } |
1997 | } | 2027 | } |
@@ -2001,7 +2031,7 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
2001 | for (i = 0; i < cls->len; i++) | 2031 | for (i = 0; i < cls->len; i++) |
2002 | cls->states[i]->contained = 0; | 2032 | cls->states[i]->contained = 0; |
2003 | 2033 | ||
2004 | // sort the states | 2034 | /* sort the states */ |
2005 | if (cls->len > 1) | 2035 | if (cls->len > 1) |
2006 | qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *), | 2036 | qsort (cls->states, cls->len, sizeof (struct GNUNET_REGEX_State *), |
2007 | state_compare); | 2037 | state_compare); |
@@ -2379,7 +2409,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
2379 | } | 2409 | } |
2380 | if (0 == atomcount) | 2410 | if (0 == atomcount) |
2381 | { | 2411 | { |
2382 | // Ignore this: "()" | 2412 | /* Ignore this: "()" */ |
2383 | pcount--; | 2413 | pcount--; |
2384 | altcount = p[pcount].altcount; | 2414 | altcount = p[pcount].altcount; |
2385 | atomcount = p[pcount].atomcount; | 2415 | atomcount = p[pcount].atomcount; |
@@ -2560,7 +2590,7 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len, | |||
2560 | 2590 | ||
2561 | GNUNET_REGEX_context_init (&ctx); | 2591 | GNUNET_REGEX_context_init (&ctx); |
2562 | 2592 | ||
2563 | // Create NFA | 2593 | /* Create NFA */ |
2564 | nfa = GNUNET_REGEX_construct_nfa (regex, len); | 2594 | nfa = GNUNET_REGEX_construct_nfa (regex, len); |
2565 | 2595 | ||
2566 | if (NULL == nfa) | 2596 | if (NULL == nfa) |
@@ -2578,7 +2608,7 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len, | |||
2578 | dfa->regex = GNUNET_strdup (regex); | 2608 | dfa->regex = GNUNET_strdup (regex); |
2579 | dfa->is_multistrided = GNUNET_NO; | 2609 | dfa->is_multistrided = GNUNET_NO; |
2580 | 2610 | ||
2581 | // Create DFA start state from epsilon closure | 2611 | /* Create DFA start state from epsilon closure */ |
2582 | nfa_start_eps_cls = nfa_closure_create (nfa, nfa->start, 0); | 2612 | nfa_start_eps_cls = nfa_closure_create (nfa, nfa->start, 0); |
2583 | dfa->start = dfa_state_create (&ctx, nfa_start_eps_cls); | 2613 | dfa->start = dfa_state_create (&ctx, nfa_start_eps_cls); |
2584 | automaton_add_state (dfa, dfa->start); | 2614 | automaton_add_state (dfa, dfa->start); |
@@ -2587,19 +2617,16 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len, | |||
2587 | 2617 | ||
2588 | GNUNET_REGEX_automaton_destroy (nfa); | 2618 | GNUNET_REGEX_automaton_destroy (nfa); |
2589 | 2619 | ||
2590 | // Minimize DFA | 2620 | /* Minimize DFA */ |
2591 | dfa_minimize (&ctx, dfa); | 2621 | dfa_minimize (&ctx, dfa); |
2592 | 2622 | ||
2593 | // Create proofs for all states | 2623 | /* Create proofs and hashes for all states */ |
2594 | automaton_create_proofs (dfa); | 2624 | automaton_create_proofs (dfa); |
2595 | 2625 | ||
2596 | // Compress DFA paths | 2626 | /* Compress linear DFA paths */ |
2597 | if (1 != max_path_len) | 2627 | if (1 != max_path_len) |
2598 | dfa_compress_paths (&ctx, dfa, max_path_len); | 2628 | dfa_compress_paths (&ctx, dfa, max_path_len); |
2599 | 2629 | ||
2600 | // Add strides to DFA | ||
2601 | //GNUNET_REGEX_dfa_add_multi_strides (&ctx, dfa, 2); | ||
2602 | |||
2603 | return dfa; | 2630 | return dfa; |
2604 | } | 2631 | } |
2605 | 2632 | ||
@@ -2657,7 +2684,7 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
2657 | 2684 | ||
2658 | s = a->start; | 2685 | s = a->start; |
2659 | 2686 | ||
2660 | // If the string is empty but the starting state is accepting, we accept. | 2687 | /* If the string is empty but the starting state is accepting, we accept. */ |
2661 | if ((NULL == string || 0 == strlen (string)) && s->accepting) | 2688 | if ((NULL == string || 0 == strlen (string)) && s->accepting) |
2662 | return 0; | 2689 | return 0; |
2663 | 2690 | ||
@@ -2702,7 +2729,7 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
2702 | return -1; | 2729 | return -1; |
2703 | } | 2730 | } |
2704 | 2731 | ||
2705 | // If the string is empty but the starting state is accepting, we accept. | 2732 | /* If the string is empty but the starting state is accepting, we accept. */ |
2706 | if ((NULL == string || 0 == strlen (string)) && a->start->accepting) | 2733 | if ((NULL == string || 0 == strlen (string)) && a->start->accepting) |
2707 | return 0; | 2734 | return 0; |
2708 | 2735 | ||
@@ -2921,8 +2948,8 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2921 | if (GNUNET_YES == state->accepting && cur_len > 1 && | 2948 | if (GNUNET_YES == state->accepting && cur_len > 1 && |
2922 | state->transition_count < 1 && cur_len < max_len) | 2949 | state->transition_count < 1 && cur_len < max_len) |
2923 | { | 2950 | { |
2924 | // Special case for regex consisting of just a string that is shorter than | 2951 | /* Special case for regex consisting of just a string that is shorter than |
2925 | // max_len | 2952 | * max_len */ |
2926 | edge[0].label = &consumed_string[cur_len - 1]; | 2953 | edge[0].label = &consumed_string[cur_len - 1]; |
2927 | edge[0].destination = state->hash; | 2954 | edge[0].destination = state->hash; |
2928 | temp = GNUNET_strdup (consumed_string); | 2955 | temp = GNUNET_strdup (consumed_string); |
@@ -2934,7 +2961,7 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2934 | } | 2961 | } |
2935 | else if (max_len < cur_len) | 2962 | else if (max_len < cur_len) |
2936 | { | 2963 | { |
2937 | // Case where the concatenated labels are longer than max_len, then split. | 2964 | /* Case where the concatenated labels are longer than max_len, then split. */ |
2938 | edge[0].label = &consumed_string[max_len]; | 2965 | edge[0].label = &consumed_string[max_len]; |
2939 | edge[0].destination = state->hash; | 2966 | edge[0].destination = state->hash; |
2940 | temp = GNUNET_strdup (consumed_string); | 2967 | temp = GNUNET_strdup (consumed_string); |
diff --git a/src/regex/regex_internal.h b/src/regex/regex_internal.h index 479de7024..493f01729 100644 --- a/src/regex/regex_internal.h +++ b/src/regex/regex_internal.h | |||
@@ -19,7 +19,7 @@ | |||
19 | */ | 19 | */ |
20 | /** | 20 | /** |
21 | * @file src/regex/regex_internal.h | 21 | * @file src/regex/regex_internal.h |
22 | * @brief common internal definitions for regex library | 22 | * @brief common internal definitions for regex library. |
23 | * @author Maximilian Szengel | 23 | * @author Maximilian Szengel |
24 | */ | 24 | */ |
25 | #ifndef REGEX_INTERNAL_H | 25 | #ifndef REGEX_INTERNAL_H |
@@ -43,8 +43,9 @@ extern "C" | |||
43 | 43 | ||
44 | 44 | ||
45 | /** | 45 | /** |
46 | * Transition between two states. Each state can have 0-n transitions. If label | 46 | * Transition between two states. Transitions are stored at the states from |
47 | * is 0, this is considered to be an epsilon transition. | 47 | * which they origin ('from_state'). Each state can have 0-n transitions. |
48 | * If label is 0, this is considered to be an epsilon transition. | ||
48 | */ | 49 | */ |
49 | struct GNUNET_REGEX_Transition | 50 | struct GNUNET_REGEX_Transition |
50 | { | 51 | { |
@@ -96,16 +97,26 @@ struct GNUNET_REGEX_State | |||
96 | struct GNUNET_REGEX_State *next; | 97 | struct GNUNET_REGEX_State *next; |
97 | 98 | ||
98 | /** | 99 | /** |
99 | * This is a multi DLL for StateSet_p. | 100 | * This is a multi DLL for StateSet_MDLL. |
100 | */ | 101 | */ |
101 | struct GNUNET_REGEX_State *prev_SS; | 102 | struct GNUNET_REGEX_State *prev_SS; |
102 | 103 | ||
103 | /** | 104 | /** |
104 | * This is a multi DLL for StateSet_p. | 105 | * This is a multi DLL for StateSet_MDLL. |
105 | */ | 106 | */ |
106 | struct GNUNET_REGEX_State *next_SS; | 107 | struct GNUNET_REGEX_State *next_SS; |
107 | 108 | ||
108 | /** | 109 | /** |
110 | * This is a multi DLL for StateSet_MDLL Stack. | ||
111 | */ | ||
112 | struct GNUNET_REGEX_State *prev_ST; | ||
113 | |||
114 | /** | ||
115 | * This is a multi DLL for StateSet_MDLL Stack. | ||
116 | */ | ||
117 | struct GNUNET_REGEX_State *next_ST; | ||
118 | |||
119 | /** | ||
109 | * Unique state id. | 120 | * Unique state id. |
110 | */ | 121 | */ |
111 | unsigned int id; | 122 | unsigned int id; |
diff --git a/src/regex/regex_random.c b/src/regex/regex_random.c index 3af9b7c5a..eee0c7334 100644 --- a/src/regex/regex_random.c +++ b/src/regex/regex_random.c | |||
@@ -106,7 +106,7 @@ GNUNET_REGEX_generate_random_regex (size_t rx_length, char *matching_str) | |||
106 | current_char = '?'; | 106 | current_char = '?'; |
107 | break; | 107 | break; |
108 | case 3: | 108 | case 3: |
109 | if (i < rx_length - 1) // '|' cannot be at the end | 109 | if (i < rx_length - 1) /* '|' cannot be at the end */ |
110 | current_char = '|'; | 110 | current_char = '|'; |
111 | else | 111 | else |
112 | current_char = get_random_literal (); | 112 | current_char = get_random_literal (); |
diff --git a/src/regex/regex_simulation_profiler_test.conf b/src/regex/regex_simulation_profiler_test.conf index 738fe7a81..9384aa249 100644 --- a/src/regex/regex_simulation_profiler_test.conf +++ b/src/regex/regex_simulation_profiler_test.conf | |||
@@ -4,3 +4,4 @@ USER = gnunet | |||
4 | PASSWORD = | 4 | PASSWORD = |
5 | HOST = localhost | 5 | HOST = localhost |
6 | PORT = 3306 | 6 | PORT = 3306 |
7 | REGEX_PREFIX = GNVPN-0001-PAD | ||
diff --git a/src/regex/test_regex_eval_api.c b/src/regex/test_regex_eval_api.c index 02aa1d01c..d87089868 100644 --- a/src/regex/test_regex_eval_api.c +++ b/src/regex/test_regex_eval_api.c | |||
@@ -123,7 +123,8 @@ test_random (unsigned int rx_length, unsigned int max_str_len, | |||
123 | 123 | ||
124 | /* Match canonical regex */ | 124 | /* Match canonical regex */ |
125 | dfa = | 125 | dfa = |
126 | GNUNET_REGEX_construct_dfa (canonical_regex, strlen (canonical_regex), 0); | 126 | GNUNET_REGEX_construct_dfa (canonical_regex, strlen (canonical_regex), |
127 | 0); | ||
127 | if (NULL == dfa) | 128 | if (NULL == dfa) |
128 | { | 129 | { |
129 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Constructing DFA failed\n"); | 130 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Constructing DFA failed\n"); |
@@ -251,7 +252,7 @@ main (int argc, char *argv[]) | |||
251 | int check_rand; | 252 | int check_rand; |
252 | char *check_proof; | 253 | char *check_proof; |
253 | 254 | ||
254 | struct Regex_String_Pair rxstr[18] = { | 255 | struct Regex_String_Pair rxstr[19] = { |
255 | {"ab?(abcd)?", 5, | 256 | {"ab?(abcd)?", 5, |
256 | {"ababcd", "abab", "aabcd", "a", "abb"}, | 257 | {"ababcd", "abab", "aabcd", "a", "abb"}, |
257 | {match, nomatch, match, match, nomatch}}, | 258 | {match, nomatch, match, match, nomatch}}, |
@@ -311,14 +312,19 @@ main (int argc, char *argv[]) | |||
311 | {nomatch}}, | 312 | {nomatch}}, |
312 | {"a()b", 1, | 313 | {"a()b", 1, |
313 | {"ab"}, | 314 | {"ab"}, |
314 | {match}} | 315 | {match}}, |
316 | {"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)*|001110101011011011001(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)*|001110111011110111011(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)*|011101000101011011111(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)*|011101000101100000001(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)*|011101000101100100100(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)*|110010101001110001100(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)*|110110101011101000010011(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)*|110110101101010000101(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)*|110111101010010001000(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)*|110111101010010101010(0|1)*|110111101010010101011(0|1)*|110111101010010101100(0|1)*|110111101010010101101(0|1)*|110111101010010101110(0|1)*|110111101010010101111(0|1)*)", | ||
317 | 2, | ||
318 | {"GNVPN-0001-PAD1101111010100101011101010101010101", | ||
319 | "GNVPN-0001-PAD11001010100111000101101010101"}, | ||
320 | {match, match}} | ||
315 | }; | 321 | }; |
316 | 322 | ||
317 | check_nfa = 0; | 323 | check_nfa = 0; |
318 | check_dfa = 0; | 324 | check_dfa = 0; |
319 | check_rand = 0; | 325 | check_rand = 0; |
320 | 326 | ||
321 | for (i = 0; i < 18; i++) | 327 | for (i = 0; i < 19; i++) |
322 | { | 328 | { |
323 | if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED)) | 329 | if (0 != regcomp (&rx, rxstr[i].regex, REG_EXTENDED)) |
324 | { | 330 | { |
diff --git a/src/regex/test_regex_graph_api.c b/src/regex/test_regex_graph_api.c index c2c1c74e1..3ae607352 100644 --- a/src/regex/test_regex_graph_api.c +++ b/src/regex/test_regex_graph_api.c | |||
@@ -28,7 +28,7 @@ | |||
28 | #include "gnunet_regex_lib.h" | 28 | #include "gnunet_regex_lib.h" |
29 | #include "regex_internal.h" | 29 | #include "regex_internal.h" |
30 | 30 | ||
31 | #define KEEP_FILES 0 | 31 | #define KEEP_FILES 1 |
32 | 32 | ||
33 | /** | 33 | /** |
34 | * Check if 'filename' exists and is not empty. | 34 | * Check if 'filename' exists and is not empty. |
@@ -43,7 +43,7 @@ filecheck (const char *filename) | |||
43 | int error = 0; | 43 | int error = 0; |
44 | FILE *fp; | 44 | FILE *fp; |
45 | 45 | ||
46 | // Check if file was created and delete it again | 46 | /* Check if file was created and delete it again */ |
47 | if (NULL == (fp = fopen (filename, "r"))) | 47 | if (NULL == (fp = fopen (filename, "r"))) |
48 | { | 48 | { |
49 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not find graph %s\n", filename); | 49 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not find graph %s\n", filename); |
@@ -54,18 +54,16 @@ filecheck (const char *filename) | |||
54 | if (1 > ftell (fp)) | 54 | if (1 > ftell (fp)) |
55 | { | 55 | { |
56 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 56 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
57 | "Graph writing failed, got empty file (%s)!\n", | 57 | "Graph writing failed, got empty file (%s)!\n", filename); |
58 | filename); | ||
59 | error = 2; | 58 | error = 2; |
60 | } | 59 | } |
61 | 60 | ||
62 | GNUNET_assert (0 == fclose (fp)); | 61 | GNUNET_assert (0 == fclose (fp)); |
63 | 62 | ||
64 | if (!KEEP_FILES) | 63 | if (!KEEP_FILES) |
65 | { | 64 | { |
66 | if (0 != unlink (filename)) | 65 | if (0 != unlink (filename)) |
67 | GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, | 66 | GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "unlink", filename); |
68 | "unlink", filename); | ||
69 | } | 67 | } |
70 | return error; | 68 | return error; |
71 | } | 69 | } |
@@ -78,6 +76,7 @@ main (int argc, char *argv[]) | |||
78 | struct GNUNET_REGEX_Automaton *a; | 76 | struct GNUNET_REGEX_Automaton *a; |
79 | unsigned int i; | 77 | unsigned int i; |
80 | const char *filename = "test_graph.dot"; | 78 | const char *filename = "test_graph.dot"; |
79 | |||
81 | const char *regex[12] = { | 80 | const char *regex[12] = { |
82 | "ab(c|d)+c*(a(b|c)+d)+(bla)+", | 81 | "ab(c|d)+c*(a(b|c)+d)+(bla)+", |
83 | "(bla)*", | 82 | "(bla)*", |
@@ -90,7 +89,6 @@ main (int argc, char *argv[]) | |||
90 | "a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", | 89 | "a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", |
91 | "a", | 90 | "a", |
92 | "a|b", | 91 | "a|b", |
93 | // "abc(d+|e)fgh" | ||
94 | "PADPADPADPADPADPabcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd" | 92 | "PADPADPADPADPADPabcdefghixxxxxxxxxxxxxjklmnop*qstoisdjfguisdfguihsdfgbdsuivggsd" |
95 | }; | 93 | }; |
96 | 94 | ||
@@ -98,7 +96,7 @@ main (int argc, char *argv[]) | |||
98 | error = 0; | 96 | error = 0; |
99 | for (i = 0; i < 12; i++) | 97 | for (i = 0; i < 12; i++) |
100 | { | 98 | { |
101 | // Check NFA graph creation | 99 | /* Check NFA graph creation */ |
102 | a = GNUNET_REGEX_construct_nfa (regex[i], strlen (regex[i])); | 100 | a = GNUNET_REGEX_construct_nfa (regex[i], strlen (regex[i])); |
103 | GNUNET_REGEX_automaton_save_graph (a, filename, GNUNET_REGEX_GRAPH_DEFAULT); | 101 | GNUNET_REGEX_automaton_save_graph (a, filename, GNUNET_REGEX_GRAPH_DEFAULT); |
104 | GNUNET_REGEX_automaton_destroy (a); | 102 | GNUNET_REGEX_automaton_destroy (a); |
@@ -127,7 +125,7 @@ main (int argc, char *argv[]) | |||
127 | error += filecheck (filename); | 125 | error += filecheck (filename); |
128 | 126 | ||
129 | 127 | ||
130 | // Check DFA graph creation | 128 | /* Check DFA graph creation */ |
131 | a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 0); | 129 | a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 0); |
132 | GNUNET_REGEX_automaton_save_graph (a, filename, GNUNET_REGEX_GRAPH_DEFAULT); | 130 | GNUNET_REGEX_automaton_save_graph (a, filename, GNUNET_REGEX_GRAPH_DEFAULT); |
133 | GNUNET_REGEX_automaton_destroy (a); | 131 | GNUNET_REGEX_automaton_destroy (a); |
@@ -148,10 +146,8 @@ main (int argc, char *argv[]) | |||
148 | error += filecheck (filename); | 146 | error += filecheck (filename); |
149 | 147 | ||
150 | 148 | ||
151 | a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 0); | 149 | a = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i]), 4); |
152 | GNUNET_REGEX_automaton_save_graph (a, filename, GNUNET_REGEX_GRAPH_DEFAULT); //| | 150 | GNUNET_REGEX_automaton_save_graph (a, filename, GNUNET_REGEX_GRAPH_DEFAULT); |
153 | // GNUNET_REGEX_GRAPH_VERBOSE | | ||
154 | //GNUNET_REGEX_GRAPH_COLORING); | ||
155 | GNUNET_REGEX_automaton_destroy (a); | 151 | GNUNET_REGEX_automaton_destroy (a); |
156 | error += filecheck (filename); | 152 | error += filecheck (filename); |
157 | 153 | ||
diff --git a/src/regex/test_regex_iterate_api.c b/src/regex/test_regex_iterate_api.c index 09abdb7c7..a680ca9f8 100644 --- a/src/regex/test_regex_iterate_api.c +++ b/src/regex/test_regex_iterate_api.c | |||
@@ -158,7 +158,7 @@ main (int argc, char *argv[]) | |||
158 | rxstr[i].regex); | 158 | rxstr[i].regex); |
159 | 159 | ||
160 | 160 | ||
161 | // Create graph | 161 | /* Create graph */ |
162 | if (GNUNET_YES == GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH) | 162 | if (GNUNET_YES == GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH) |
163 | { | 163 | { |
164 | GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i); | 164 | GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i); |
@@ -183,12 +183,13 @@ main (int argc, char *argv[]) | |||
183 | ctx.graph_filep = NULL; | 183 | ctx.graph_filep = NULL; |
184 | } | 184 | } |
185 | 185 | ||
186 | // Iterate over DFA edges | 186 | /* Iterate over DFA edges */ |
187 | transition_counter = 0; | 187 | transition_counter = 0; |
188 | ctx.string_count = rxstr[i].string_count; | 188 | ctx.string_count = rxstr[i].string_count; |
189 | ctx.strings = rxstr[i].strings; | 189 | ctx.strings = rxstr[i].strings; |
190 | ctx.match_count = 0; | 190 | ctx.match_count = 0; |
191 | dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0); | 191 | dfa = |
192 | GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0); | ||
192 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); | 193 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); |
193 | num_transitions = | 194 | num_transitions = |
194 | GNUNET_REGEX_get_transition_count (dfa) - dfa->start->transition_count; | 195 | GNUNET_REGEX_get_transition_count (dfa) - dfa->start->transition_count; |
@@ -217,7 +218,7 @@ main (int argc, char *argv[]) | |||
217 | 218 | ||
218 | GNUNET_REGEX_automaton_destroy (dfa); | 219 | GNUNET_REGEX_automaton_destroy (dfa); |
219 | 220 | ||
220 | // Finish graph | 221 | /* Finish graph */ |
221 | if (GNUNET_YES == ctx.should_save_graph) | 222 | if (GNUNET_YES == ctx.should_save_graph) |
222 | { | 223 | { |
223 | fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep); | 224 | fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep); |
@@ -234,7 +235,8 @@ main (int argc, char *argv[]) | |||
234 | ctx.strings = rxstr[i].strings; | 235 | ctx.strings = rxstr[i].strings; |
235 | ctx.match_count = 0; | 236 | ctx.match_count = 0; |
236 | 237 | ||
237 | dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0); | 238 | dfa = |
239 | GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex), 0); | ||
238 | GNUNET_REGEX_dfa_add_multi_strides (NULL, dfa, 2); | 240 | GNUNET_REGEX_dfa_add_multi_strides (NULL, dfa, 2); |
239 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); | 241 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); |
240 | 242 | ||