diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-09-24 19:11:42 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-09-24 19:11:42 +0000 |
commit | 357582e58b08cdfce08b67412fd60305c3470809 (patch) | |
tree | 48f0ae9c9918dc0ebc45c73956b529b370c919f9 /src/regex | |
parent | dbe7cda38fe4464992c8798306f1641162cdce41 (diff) | |
download | gnunet-357582e58b08cdfce08b67412fd60305c3470809.tar.gz gnunet-357582e58b08cdfce08b67412fd60305c3470809.zip |
regex: iteration improvements/fixes
Diffstat (limited to 'src/regex')
-rw-r--r-- | src/regex/regex.c | 188 | ||||
-rw-r--r-- | src/regex/test_regex_iterate_api.c | 165 |
2 files changed, 203 insertions, 150 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 580e9a65f..a4126e02d 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -86,7 +86,6 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
86 | struct GNUNET_REGEX_State *from_state, const char *label, | 86 | struct GNUNET_REGEX_State *from_state, const char *label, |
87 | struct GNUNET_REGEX_State *to_state) | 87 | struct GNUNET_REGEX_State *to_state) |
88 | { | 88 | { |
89 | int is_dup; | ||
90 | struct GNUNET_REGEX_Transition *t; | 89 | struct GNUNET_REGEX_Transition *t; |
91 | struct GNUNET_REGEX_Transition *oth; | 90 | struct GNUNET_REGEX_Transition *oth; |
92 | 91 | ||
@@ -97,20 +96,13 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
97 | } | 96 | } |
98 | 97 | ||
99 | // Do not add duplicate state transitions | 98 | // Do not add duplicate state transitions |
100 | is_dup = GNUNET_NO; | ||
101 | for (t = from_state->transitions_head; NULL != t; t = t->next) | 99 | for (t = from_state->transitions_head; NULL != t; t = t->next) |
102 | { | 100 | { |
103 | if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) && | 101 | if (t->to_state == to_state && 0 == nullstrcmp (t->label, label) && |
104 | t->from_state == from_state) | 102 | t->from_state == from_state) |
105 | { | 103 | return; |
106 | is_dup = GNUNET_YES; | ||
107 | break; | ||
108 | } | ||
109 | } | 104 | } |
110 | 105 | ||
111 | if (GNUNET_YES == is_dup) | ||
112 | return; | ||
113 | |||
114 | // sort transitions by label | 106 | // sort transitions by label |
115 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) | 107 | for (oth = from_state->transitions_head; NULL != oth; oth = oth->next) |
116 | { | 108 | { |
@@ -151,10 +143,11 @@ state_remove_transition (struct GNUNET_REGEX_State *state, | |||
151 | if (transition->from_state != state) | 143 | if (transition->from_state != state) |
152 | return; | 144 | return; |
153 | 145 | ||
146 | GNUNET_free_non_null (transition->label); | ||
147 | |||
154 | state->transition_count--; | 148 | state->transition_count--; |
155 | GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail, | 149 | GNUNET_CONTAINER_DLL_remove (state->transitions_head, state->transitions_tail, |
156 | transition); | 150 | transition); |
157 | GNUNET_free_non_null (transition->label); | ||
158 | GNUNET_free (transition); | 151 | GNUNET_free (transition); |
159 | } | 152 | } |
160 | 153 | ||
@@ -257,11 +250,12 @@ state_set_compare (struct GNUNET_REGEX_StateSet *sset1, | |||
257 | static void | 250 | static void |
258 | state_set_clear (struct GNUNET_REGEX_StateSet *set) | 251 | state_set_clear (struct GNUNET_REGEX_StateSet *set) |
259 | { | 252 | { |
260 | if (NULL != set) | 253 | if (NULL == set) |
261 | { | 254 | return; |
262 | GNUNET_free_non_null (set->states); | 255 | |
263 | GNUNET_free (set); | 256 | if (set->len > 0) |
264 | } | 257 | GNUNET_array_grow (set->states, set->len, 0); |
258 | GNUNET_free (set); | ||
265 | } | 259 | } |
266 | 260 | ||
267 | 261 | ||
@@ -302,17 +296,14 @@ automaton_destroy_state (struct GNUNET_REGEX_State *s) | |||
302 | 296 | ||
303 | GNUNET_free_non_null (s->name); | 297 | GNUNET_free_non_null (s->name); |
304 | GNUNET_free_non_null (s->proof); | 298 | GNUNET_free_non_null (s->proof); |
299 | state_set_clear (s->nfa_set); | ||
305 | 300 | ||
306 | for (t = s->transitions_head; NULL != t; t = next_t) | 301 | for (t = s->transitions_head; NULL != t; t = next_t) |
307 | { | 302 | { |
308 | next_t = t->next; | 303 | next_t = t->next; |
309 | GNUNET_CONTAINER_DLL_remove (s->transitions_head, s->transitions_tail, t); | 304 | state_remove_transition (s, t); |
310 | GNUNET_free_non_null (t->label); | ||
311 | GNUNET_free (t); | ||
312 | } | 305 | } |
313 | 306 | ||
314 | state_set_clear (s->nfa_set); | ||
315 | |||
316 | GNUNET_free (s); | 307 | GNUNET_free (s); |
317 | } | 308 | } |
318 | 309 | ||
@@ -329,34 +320,30 @@ static void | |||
329 | automaton_remove_state (struct GNUNET_REGEX_Automaton *a, | 320 | automaton_remove_state (struct GNUNET_REGEX_Automaton *a, |
330 | struct GNUNET_REGEX_State *s) | 321 | struct GNUNET_REGEX_State *s) |
331 | { | 322 | { |
332 | struct GNUNET_REGEX_State *ss; | ||
333 | struct GNUNET_REGEX_State *s_check; | 323 | struct GNUNET_REGEX_State *s_check; |
334 | struct GNUNET_REGEX_Transition *t_check; | 324 | struct GNUNET_REGEX_Transition *t_check; |
325 | struct GNUNET_REGEX_Transition *t_check_next; | ||
335 | 326 | ||
336 | if (NULL == a || NULL == s) | 327 | if (NULL == a || NULL == s) |
337 | return; | 328 | return; |
338 | 329 | ||
339 | // remove state | ||
340 | ss = s; | ||
341 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | ||
342 | a->state_count--; | ||
343 | |||
344 | // remove all transitions leading to this state | 330 | // remove all transitions leading to this state |
345 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) | 331 | for (s_check = a->states_head; NULL != s_check; s_check = s_check->next) |
346 | { | 332 | { |
347 | for (t_check = s_check->transitions_head; NULL != t_check; | 333 | for (t_check = s_check->transitions_head; NULL != t_check; |
348 | t_check = t_check->next) | 334 | t_check = t_check_next) |
349 | { | 335 | { |
350 | if (t_check->to_state == ss) | 336 | t_check_next = t_check->next; |
351 | { | 337 | if (t_check->to_state == s) |
352 | GNUNET_CONTAINER_DLL_remove (s_check->transitions_head, | 338 | state_remove_transition (s_check, t_check); |
353 | s_check->transitions_tail, t_check); | ||
354 | s_check->transition_count--; | ||
355 | } | ||
356 | } | 339 | } |
357 | } | 340 | } |
358 | 341 | ||
359 | automaton_destroy_state (ss); | 342 | // remove state |
343 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | ||
344 | a->state_count--; | ||
345 | |||
346 | automaton_destroy_state (s); | ||
360 | } | 347 | } |
361 | 348 | ||
362 | 349 | ||
@@ -1703,8 +1690,6 @@ dfa_compress_paths_helper (struct GNUNET_REGEX_State *start, | |||
1703 | t->from_state = start; | 1690 | t->from_state = start; |
1704 | GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t); | 1691 | GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t); |
1705 | 1692 | ||
1706 | GNUNET_free_non_null (label); | ||
1707 | |||
1708 | if (GNUNET_NO == cur->marked) | 1693 | if (GNUNET_NO == cur->marked) |
1709 | { | 1694 | { |
1710 | dfa_compress_paths_helper (cur, cur, NULL, transitions_head, | 1695 | dfa_compress_paths_helper (cur, cur, NULL, transitions_head, |
@@ -1733,6 +1718,7 @@ dfa_compress_paths_helper (struct GNUNET_REGEX_State *start, | |||
1733 | dfa_compress_paths_helper (start, t->to_state, new_label, | 1718 | dfa_compress_paths_helper (start, t->to_state, new_label, |
1734 | transitions_head, transitions_tail); | 1719 | transitions_head, transitions_tail); |
1735 | } | 1720 | } |
1721 | GNUNET_free (new_label); | ||
1736 | } | 1722 | } |
1737 | } | 1723 | } |
1738 | 1724 | ||
@@ -2563,11 +2549,11 @@ GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a) | |||
2563 | GNUNET_free_non_null (a->regex); | 2549 | GNUNET_free_non_null (a->regex); |
2564 | GNUNET_free_non_null (a->canonical_regex); | 2550 | GNUNET_free_non_null (a->canonical_regex); |
2565 | 2551 | ||
2566 | for (s = a->states_head; NULL != s;) | 2552 | for (s = a->states_head; NULL != s; s = next_state) |
2567 | { | 2553 | { |
2568 | next_state = s->next; | 2554 | next_state = s->next; |
2555 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | ||
2569 | automaton_destroy_state (s); | 2556 | automaton_destroy_state (s); |
2570 | s = next_state; | ||
2571 | } | 2557 | } |
2572 | 2558 | ||
2573 | GNUNET_free (a); | 2559 | GNUNET_free (a); |
@@ -2815,7 +2801,6 @@ GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key) | |||
2815 | * | 2801 | * |
2816 | * @param min_len minimum length of the path in the graph. | 2802 | * @param min_len minimum length of the path in the graph. |
2817 | * @param max_len maximum length of the path in the graph. | 2803 | * @param max_len maximum length of the path in the graph. |
2818 | * @param cur_len current length of the path already traversed. | ||
2819 | * @param consumed_string string consumed by traversing the graph till this state. | 2804 | * @param consumed_string string consumed by traversing the graph till this state. |
2820 | * @param state current state of the automaton. | 2805 | * @param state current state of the automaton. |
2821 | * @param iterator iterator function called for each edge. | 2806 | * @param iterator iterator function called for each edge. |
@@ -2823,8 +2808,7 @@ GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key) | |||
2823 | */ | 2808 | */ |
2824 | static void | 2809 | static void |
2825 | iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | 2810 | iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, |
2826 | unsigned int cur_len, char *consumed_string, | 2811 | char *consumed_string, struct GNUNET_REGEX_State *state, |
2827 | struct GNUNET_REGEX_State *state, | ||
2828 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) | 2812 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) |
2829 | { | 2813 | { |
2830 | unsigned int i; | 2814 | unsigned int i; |
@@ -2834,22 +2818,56 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2834 | struct GNUNET_REGEX_Edge edges[num_edges]; | 2818 | struct GNUNET_REGEX_Edge edges[num_edges]; |
2835 | struct GNUNET_HashCode hash; | 2819 | struct GNUNET_HashCode hash; |
2836 | 2820 | ||
2837 | if (cur_len > min_len && NULL != consumed_string && cur_len <= max_len) | 2821 | unsigned int cur_len; |
2822 | |||
2823 | if (NULL != consumed_string) | ||
2824 | cur_len = strlen (consumed_string); | ||
2825 | else | ||
2826 | cur_len = 0; | ||
2827 | |||
2828 | if (cur_len > min_len && NULL != consumed_string) | ||
2838 | { | 2829 | { |
2839 | for (i = 0, t = state->transitions_head; NULL != t; t = t->next, i++) | 2830 | |
2831 | if (cur_len <= max_len) | ||
2840 | { | 2832 | { |
2841 | edges[i].label = t->label; | 2833 | for (i = 0, t = state->transitions_head; NULL != t && i < num_edges; |
2842 | edges[i].destination = t->to_state->hash; | 2834 | t = t->next, i++) |
2843 | } | 2835 | { |
2836 | edges[i].label = t->label; | ||
2837 | edges[i].destination = t->to_state->hash; | ||
2838 | } | ||
2844 | 2839 | ||
2845 | GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash); | 2840 | GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash); |
2846 | iterator (iterator_cls, &hash, consumed_string, state->accepting, num_edges, | 2841 | iterator (iterator_cls, &hash, consumed_string, state->accepting, |
2847 | edges); | 2842 | num_edges, edges); |
2843 | |||
2844 | // Special case for regex consisting of just a string that is shorter than max_len | ||
2845 | if (GNUNET_YES == state->accepting && cur_len > 1 && | ||
2846 | state->transition_count < 1) | ||
2847 | { | ||
2848 | edges[0].label = &consumed_string[cur_len - 1]; | ||
2849 | edges[0].destination = state->hash; | ||
2850 | temp = GNUNET_strdup (consumed_string); | ||
2851 | temp[cur_len - 1] = '\0'; | ||
2852 | GNUNET_CRYPTO_hash (temp, cur_len - 1, &hash); | ||
2853 | iterator (iterator_cls, &hash, temp, GNUNET_NO, 1, edges); | ||
2854 | GNUNET_free (temp); | ||
2855 | } | ||
2856 | } | ||
2857 | else | ||
2858 | { | ||
2859 | edges[0].label = &consumed_string[max_len]; | ||
2860 | edges[0].destination = state->hash; | ||
2861 | temp = GNUNET_strdup (consumed_string); | ||
2862 | temp[max_len] = '\0'; | ||
2863 | GNUNET_CRYPTO_hash (temp, max_len, &hash); | ||
2864 | iterator (iterator_cls, &hash, temp, GNUNET_NO, 1, edges); | ||
2865 | GNUNET_free (temp); | ||
2866 | } | ||
2848 | } | 2867 | } |
2849 | 2868 | ||
2850 | if (cur_len < max_len) | 2869 | if (cur_len < max_len) |
2851 | { | 2870 | { |
2852 | cur_len++; | ||
2853 | for (t = state->transitions_head; NULL != t; t = t->next) | 2871 | for (t = state->transitions_head; NULL != t; t = t->next) |
2854 | { | 2872 | { |
2855 | if (NULL != consumed_string) | 2873 | if (NULL != consumed_string) |
@@ -2857,8 +2875,8 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2857 | else | 2875 | else |
2858 | GNUNET_asprintf (&temp, "%s", t->label); | 2876 | GNUNET_asprintf (&temp, "%s", t->label); |
2859 | 2877 | ||
2860 | iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state, | 2878 | iterate_initial_edge (min_len, max_len, temp, t->to_state, iterator, |
2861 | iterator, iterator_cls); | 2879 | iterator_cls); |
2862 | GNUNET_free (temp); | 2880 | GNUNET_free (temp); |
2863 | } | 2881 | } |
2864 | } | 2882 | } |
@@ -2866,69 +2884,8 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, | |||
2866 | 2884 | ||
2867 | 2885 | ||
2868 | /** | 2886 | /** |
2869 | * Iterate over all initial edges that aren't actually part of the automaton. | ||
2870 | * This is needed to find the initial states returned by | ||
2871 | * GNUNET_REGEX_get_first_key. Iteration will start at the first state that has | ||
2872 | * more than one outgoing edge, i.e. the state that branches the graph. | ||
2873 | * For example consider the following graph: | ||
2874 | * a -> b -> c -> d -> ... | ||
2875 | * \-> e -> ... | ||
2876 | * | ||
2877 | * This function will not iterate over the edges leading to "c", because these | ||
2878 | * will be covered by the iterate_edges function. | ||
2879 | * | ||
2880 | * @param a the automaton for which the initial states should be computed. | ||
2881 | * @param initial_len length of the initial state string. | ||
2882 | * @param iterator iterator function called for each edge. | ||
2883 | * @param iterator_cls closure for the iterator function. | ||
2884 | */ | ||
2885 | void | ||
2886 | iterate_initial_edges (struct GNUNET_REGEX_Automaton *a, | ||
2887 | const unsigned int initial_len, | ||
2888 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) | ||
2889 | { | ||
2890 | char *consumed_string; | ||
2891 | char *temp; | ||
2892 | struct GNUNET_REGEX_State *s; | ||
2893 | unsigned int cur_len; | ||
2894 | |||
2895 | if (1 > initial_len) | ||
2896 | return; | ||
2897 | |||
2898 | consumed_string = NULL; | ||
2899 | s = a->start; | ||
2900 | cur_len = 0; | ||
2901 | |||
2902 | if (1 == s->transition_count) | ||
2903 | { | ||
2904 | do | ||
2905 | { | ||
2906 | if (NULL != consumed_string) | ||
2907 | { | ||
2908 | temp = consumed_string; | ||
2909 | GNUNET_asprintf (&consumed_string, "%s%s", consumed_string, | ||
2910 | s->transitions_head->label); | ||
2911 | GNUNET_free (temp); | ||
2912 | } | ||
2913 | else | ||
2914 | GNUNET_asprintf (&consumed_string, "%s", s->transitions_head->label); | ||
2915 | |||
2916 | s = s->transitions_head->to_state; | ||
2917 | cur_len += strlen (s->transitions_head->label); | ||
2918 | } | ||
2919 | while (cur_len < initial_len && 1 == s->transition_count); | ||
2920 | } | ||
2921 | |||
2922 | iterate_initial_edge (cur_len, initial_len, cur_len, consumed_string, s, | ||
2923 | iterator, iterator_cls); | ||
2924 | |||
2925 | GNUNET_free_non_null (consumed_string); | ||
2926 | } | ||
2927 | |||
2928 | |||
2929 | /** | ||
2930 | * Iterate over all edges helper function starting from state 's', calling | 2887 | * Iterate over all edges helper function starting from state 's', calling |
2931 | * iterator function for each edge. | 2888 | * iterator function for each edge if the automaton. |
2932 | * | 2889 | * |
2933 | * @param s state. | 2890 | * @param s state. |
2934 | * @param iterator iterator function called for each edge. | 2891 | * @param iterator iterator function called for each edge. |
@@ -2976,6 +2933,7 @@ GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a, | |||
2976 | for (s = a->states_head; NULL != s; s = s->next) | 2933 | for (s = a->states_head; NULL != s; s = s->next) |
2977 | s->marked = GNUNET_NO; | 2934 | s->marked = GNUNET_NO; |
2978 | 2935 | ||
2979 | iterate_initial_edges (a, INITIAL_BITS, iterator, iterator_cls); | 2936 | iterate_initial_edge (0, INITIAL_BITS, NULL, a->start, iterator, |
2937 | iterator_cls); | ||
2980 | iterate_edge (a->start, iterator, iterator_cls); | 2938 | iterate_edge (a->start, iterator, iterator_cls); |
2981 | } | 2939 | } |
diff --git a/src/regex/test_regex_iterate_api.c b/src/regex/test_regex_iterate_api.c index b8f3cd266..84bb6e9fb 100644 --- a/src/regex/test_regex_iterate_api.c +++ b/src/regex/test_regex_iterate_api.c | |||
@@ -28,13 +28,25 @@ | |||
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 GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH GNUNET_NO | ||
32 | |||
31 | static unsigned int transition_counter; | 33 | static unsigned int transition_counter; |
32 | 34 | ||
33 | struct IteratorContext | 35 | struct IteratorContext |
34 | { | 36 | { |
35 | int error; | 37 | int error; |
36 | int should_save_graph; | 38 | int should_save_graph; |
37 | FILE *graph_file; | 39 | FILE *graph_filep; |
40 | unsigned int string_count; | ||
41 | char *const *strings; | ||
42 | unsigned int match_count; | ||
43 | }; | ||
44 | |||
45 | struct RegexStringPair | ||
46 | { | ||
47 | char *regex; | ||
48 | unsigned int string_count; | ||
49 | char *strings[20]; | ||
38 | }; | 50 | }; |
39 | 51 | ||
40 | void | 52 | void |
@@ -44,21 +56,41 @@ key_iterator (void *cls, const struct GNUNET_HashCode *key, const char *proof, | |||
44 | { | 56 | { |
45 | unsigned int i; | 57 | unsigned int i; |
46 | struct IteratorContext *ctx = cls; | 58 | struct IteratorContext *ctx = cls; |
59 | char *out_str; | ||
60 | char *state_id = GNUNET_strdup (GNUNET_h2s (key)); | ||
47 | 61 | ||
48 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Iterating... (accepting: %i)\n", | 62 | if (GNUNET_YES == ctx->should_save_graph) |
49 | accepting); | 63 | { |
64 | if (GNUNET_YES == accepting) | ||
65 | GNUNET_asprintf (&out_str, "\"%s\" [shape=doublecircle]\n", state_id); | ||
66 | else | ||
67 | GNUNET_asprintf (&out_str, "\"%s\" [shape=circle]\n", state_id); | ||
68 | fwrite (out_str, strlen (out_str), 1, ctx->graph_filep); | ||
69 | GNUNET_free (out_str); | ||
70 | |||
71 | for (i = 0; i < num_edges; i++) | ||
72 | { | ||
73 | transition_counter++; | ||
74 | GNUNET_asprintf (&out_str, "\"%s\" -> \"%s\" [label = \"%s (%s)\"]\n", | ||
75 | state_id, GNUNET_h2s (&edges[i].destination), | ||
76 | edges[i].label, proof); | ||
77 | fwrite (out_str, strlen (out_str), 1, ctx->graph_filep); | ||
50 | 78 | ||
51 | if (NULL != proof) | 79 | GNUNET_free (out_str); |
52 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Proof: %s\n", proof); | 80 | } |
81 | } | ||
82 | else | ||
83 | { | ||
84 | for (i = 0; i < num_edges; i++) | ||
85 | transition_counter++; | ||
86 | } | ||
53 | 87 | ||
54 | if (NULL != key) | 88 | GNUNET_free (state_id); |
55 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Hash: %s\n", GNUNET_h2s (key)); | ||
56 | 89 | ||
57 | for (i = 0; i < num_edges; i++) | 90 | for (i = 0; i < ctx->string_count; i++) |
58 | { | 91 | { |
59 | transition_counter++; | 92 | if (0 == strcmp (proof, ctx->strings[i])) |
60 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Edge %i: Label: %s Destination: %s\n", | 93 | ctx->match_count++; |
61 | i, edges[i].label, GNUNET_h2s (&edges[i].destination)); | ||
62 | } | 94 | } |
63 | 95 | ||
64 | ctx->error += (GNUNET_OK == GNUNET_REGEX_check_proof (proof, key)) ? 0 : 1; | 96 | ctx->error += (GNUNET_OK == GNUNET_REGEX_check_proof (proof, key)) ? 0 : 1; |
@@ -80,49 +112,112 @@ main (int argc, char *argv[]) | |||
80 | unsigned int i; | 112 | unsigned int i; |
81 | unsigned int num_transitions; | 113 | unsigned int num_transitions; |
82 | struct IteratorContext ctx = { 0, 0, NULL }; | 114 | struct IteratorContext ctx = { 0, 0, NULL }; |
115 | char *filename = NULL; | ||
83 | 116 | ||
84 | error = 0; | 117 | error = 0; |
85 | 118 | ||
86 | const char *regex[17] = { | 119 | const struct RegexStringPair rxstr[10] = { |
87 | "ab(c|d)+c*(a(b|c)+d)+(bla)+", | 120 | {"ab(c|d)+c*(a(b|c)+d)+(bla)+", 2, {"abcdcdca", "abcabdbl"}}, |
88 | "(bla)*", | 121 | {"abcdefghijklmnop*qst", 1, {"abcdefgh"}}, |
89 | "b(lab)*la", | 122 | {"VPN-4-1(0|1)*", 2, {"VPN-4-10", "VPN-4-11"}}, |
90 | "(ab)*", | 123 | {"a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", 4, |
91 | "ab(c|d)+c*(a(b|c)+d)+(bla)(bla)*", | 124 | {"aaaaaaaa", "aaXXyyyc", "p", "Y"}}, |
92 | "z(abc|def)?xyz", | 125 | {"a*", 8, |
93 | "1*0(0|1)*", | 126 | {"a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa"}}, |
94 | "a*b*", | 127 | {"xzxzxzxzxz", 1, {"xzxzxzxz"}}, |
95 | "a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*", | 128 | {"xyz*", 2, {"xy", "xyz"}}, |
96 | "abcd:(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1):(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)", | 129 | {"ab", 1, {"a"}}, |
97 | "abc(1|0)*def", | 130 | {"abcd:(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1):(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)(0|1)", 2, {"abcd:000", "abcd:101"}}, |
98 | "ab|ac", | 131 | {"x*|(0|1|2)(a|b|c|d)", 2, {"xxxxxxxx", "0a"}} |
99 | "(ab)(ab)*", | ||
100 | "ab|cd|ef|gh", | ||
101 | "a|b|c|d|e|f|g", | ||
102 | "(ab)|(ac)", | ||
103 | "x*|(0|1|2)(a|b|c|d)" | ||
104 | }; | 132 | }; |
105 | 133 | ||
106 | for (i = 0; i < 17; i++) | 134 | const char *graph_start_str = "digraph G {\nrankdir=LR\n"; |
135 | const char *graph_end_str = "\n}\n"; | ||
136 | |||
137 | for (i = 0; i < 10; i++) | ||
107 | { | 138 | { |
139 | // Create graph | ||
140 | if (GNUNET_YES == GNUNET_REGEX_ITERATE_SAVE_DEBUG_GRAPH) | ||
141 | { | ||
142 | GNUNET_asprintf (&filename, "iteration_graph_%u.dot", i); | ||
143 | ctx.graph_filep = fopen (filename, "w"); | ||
144 | if (NULL == ctx.graph_filep) | ||
145 | { | ||
146 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
147 | "Could not open file %s for saving iteration graph.\n", | ||
148 | filename); | ||
149 | ctx.should_save_graph = GNUNET_NO; | ||
150 | } | ||
151 | else | ||
152 | { | ||
153 | ctx.should_save_graph = GNUNET_YES; | ||
154 | fwrite (graph_start_str, strlen (graph_start_str), 1, ctx.graph_filep); | ||
155 | } | ||
156 | GNUNET_free (filename); | ||
157 | } | ||
158 | else | ||
159 | { | ||
160 | ctx.should_save_graph = GNUNET_NO; | ||
161 | } | ||
162 | |||
163 | // Iterate over DFA edges | ||
108 | transition_counter = 0; | 164 | transition_counter = 0; |
109 | dfa = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i])); | 165 | ctx.string_count = rxstr[i].string_count; |
166 | ctx.strings = rxstr[i].strings; | ||
167 | ctx.match_count = 0; | ||
168 | dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex)); | ||
110 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); | 169 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); |
111 | num_transitions = GNUNET_REGEX_get_transition_count (dfa); | 170 | num_transitions = GNUNET_REGEX_get_transition_count (dfa); |
112 | if (transition_counter != num_transitions) | 171 | |
172 | if (transition_counter < num_transitions) | ||
113 | { | 173 | { |
114 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 174 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
115 | "Automaton has %d transitions, iterated over %d transitions\n", | 175 | "Automaton has %d transitions, iterated over %d transitions\n", |
116 | num_transitions, transition_counter); | 176 | num_transitions, transition_counter); |
177 | error += 1; | ||
178 | break; | ||
179 | } | ||
180 | |||
181 | if (ctx.match_count < ctx.string_count) | ||
182 | { | ||
183 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
184 | "Missing initial states for regex %s\n", rxstr[i].regex); | ||
185 | error += (ctx.string_count - ctx.match_count); | ||
117 | } | 186 | } |
187 | else if (ctx.match_count > ctx.string_count) | ||
188 | { | ||
189 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
190 | "Doublicate initial transitions for regex %s\n", | ||
191 | rxstr[i].regex); | ||
192 | error += (ctx.string_count - ctx.match_count); | ||
193 | } | ||
194 | |||
118 | GNUNET_REGEX_automaton_destroy (dfa); | 195 | GNUNET_REGEX_automaton_destroy (dfa); |
196 | |||
197 | // Finish graph | ||
198 | if (GNUNET_YES == ctx.should_save_graph) | ||
199 | { | ||
200 | fwrite (graph_end_str, strlen (graph_end_str), 1, ctx.graph_filep); | ||
201 | fclose (ctx.graph_filep); | ||
202 | ctx.graph_filep = NULL; | ||
203 | ctx.should_save_graph = GNUNET_NO; | ||
204 | } | ||
119 | } | 205 | } |
120 | 206 | ||
121 | for (i = 0; i < 17; i++) | 207 | |
208 | for (i = 0; i < 10; i++) | ||
122 | { | 209 | { |
123 | dfa = GNUNET_REGEX_construct_dfa (regex[i], strlen (regex[i])); | 210 | dfa = GNUNET_REGEX_construct_dfa (rxstr[i].regex, strlen (rxstr[i].regex)); |
124 | GNUNET_REGEX_dfa_add_multi_strides (NULL, dfa, 2); | 211 | GNUNET_REGEX_dfa_add_multi_strides (NULL, dfa, 2); |
125 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); | 212 | GNUNET_REGEX_iterate_all_edges (dfa, key_iterator, &ctx); |
213 | |||
214 | if (ctx.match_count < ctx.string_count) | ||
215 | { | ||
216 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
217 | "Missing initial states for regex %s\n", rxstr[i].regex); | ||
218 | error += (ctx.string_count - ctx.match_count); | ||
219 | } | ||
220 | |||
126 | GNUNET_REGEX_automaton_destroy (dfa); | 221 | GNUNET_REGEX_automaton_destroy (dfa); |
127 | } | 222 | } |
128 | 223 | ||