diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-06-13 11:42:49 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-06-13 11:42:49 +0000 |
commit | b411db2bc0ce0902b8e7b432fe91f7037e31ab93 (patch) | |
tree | 55c40aa1baed28d05902e94b61c7c27c30b681a5 /src | |
parent | 16f659aedbacb16d2861ac08b832d2336e583117 (diff) | |
download | gnunet-b411db2bc0ce0902b8e7b432fe91f7037e31ab93.tar.gz gnunet-b411db2bc0ce0902b8e7b432fe91f7037e31ab93.zip |
more regex simplifications. fixes.
Diffstat (limited to 'src')
-rw-r--r-- | src/regex/regex.c | 130 | ||||
-rw-r--r-- | src/regex/test_regex_iterate_api.c | 2 |
2 files changed, 89 insertions, 43 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 80eb01b9c..a3f44c3b0 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -831,12 +831,15 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
831 | int j; | 831 | int j; |
832 | int k; | 832 | int k; |
833 | int n; | 833 | int n; |
834 | int cnt; | ||
834 | struct GNUNET_REGEX_State *states[a->state_count]; | 835 | struct GNUNET_REGEX_State *states[a->state_count]; |
835 | char *R_last[a->state_count][a->state_count]; | 836 | char *R_last[a->state_count][a->state_count]; |
836 | char *R_cur[a->state_count][a->state_count]; | 837 | char *R_cur[a->state_count][a->state_count]; |
837 | char *temp; | ||
838 | char *R_cur_l; | 838 | char *R_cur_l; |
839 | char *R_cur_r; | 839 | char *R_cur_r; |
840 | char *temp_a; | ||
841 | char *temp_b; | ||
842 | int length; | ||
840 | int length_l; | 843 | int length_l; |
841 | int length_r; | 844 | int length_r; |
842 | int s_cnt; | 845 | int s_cnt; |
@@ -868,9 +871,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
868 | GNUNET_asprintf (&R_last[i][j], "%c", t->label); | 871 | GNUNET_asprintf (&R_last[i][j], "%c", t->label); |
869 | else | 872 | else |
870 | { | 873 | { |
871 | temp = R_last[i][j]; | 874 | temp_a = R_last[i][j]; |
872 | GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label); | 875 | GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label); |
873 | GNUNET_free (temp); | 876 | GNUNET_free (temp_a); |
874 | } | 877 | } |
875 | } | 878 | } |
876 | } | 879 | } |
@@ -881,16 +884,16 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
881 | GNUNET_asprintf (&R_last[i][j], ""); | 884 | GNUNET_asprintf (&R_last[i][j], ""); |
882 | else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) | 885 | else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) |
883 | { | 886 | { |
884 | temp = R_last[i][j]; | 887 | temp_a = R_last[i][j]; |
885 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | 888 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); |
886 | GNUNET_free (temp); | 889 | GNUNET_free (temp_a); |
887 | } | 890 | } |
888 | } | 891 | } |
889 | else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) | 892 | else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) |
890 | { | 893 | { |
891 | temp = R_last[i][j]; | 894 | temp_a = R_last[i][j]; |
892 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | 895 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); |
893 | GNUNET_free (temp); | 896 | GNUNET_free (temp_a); |
894 | } | 897 | } |
895 | } | 898 | } |
896 | } | 899 | } |
@@ -911,15 +914,43 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
911 | if (NULL != R_last[i][j]) | 914 | if (NULL != R_last[i][j]) |
912 | R_cur[i][j] = GNUNET_strdup (R_last[i][j]); | 915 | R_cur[i][j] = GNUNET_strdup (R_last[i][j]); |
913 | } | 916 | } |
914 | // a(ba)*b = (ab)+ | 917 | // a(ba)*bx = (ab)+x |
915 | /*else if ((NULL == R_last[i][j] || 0 == strlen (R_last[i][j])) && */ | 918 | else if ((NULL == R_last[i][j] || 0 == strlen (R_last[i][j])) && |
916 | /*NULL != R_last[k][k] && 0 < strlen (R_last[k][k]) && */ | 919 | NULL != R_last[k][k] && 0 < strlen (R_last[k][k]) && |
917 | /*NULL != R_last[k][j] && 0 < strlen (R_last[k][j]) && */ | 920 | NULL != R_last[k][j] && 0 < strlen (R_last[k][j]) && |
918 | /*0 == strncmp (R_last[k][k], R_last[k][j], (strlen (R_last[k][k]) - 1)) && */ | 921 | 0 == strncmp (R_last[k][k], R_last[k][j], |
919 | /*R_last[i][k][0] == R_last[k][k][strlen (R_last[k][k]) - 1]) */ | 922 | (strlen (R_last[k][k]) - 1)) && |
920 | /*{ */ | 923 | R_last[i][k][0] == R_last[k][k][strlen (R_last[k][k]) - 1]) |
921 | /*GNUNET_asprintf (&R_cur[i][j], "(%s%s)+", R_last[i][k], R_last[k][j]); */ | 924 | { |
922 | /*} */ | 925 | length = strlen (R_last[k][k]) - strlen (R_last[i][k]); |
926 | |||
927 | temp_a = GNUNET_malloc (length + 1); | ||
928 | temp_b = GNUNET_malloc ((strlen (R_last[k][j]) - length) + 1); | ||
929 | |||
930 | length_l = 0; | ||
931 | length_r = 0; | ||
932 | |||
933 | for (cnt = 0; cnt < strlen (R_last[k][j]); cnt++) | ||
934 | { | ||
935 | if (cnt < length) | ||
936 | { | ||
937 | temp_a[length_l] = R_last[k][j][cnt]; | ||
938 | length_l++; | ||
939 | } | ||
940 | else | ||
941 | { | ||
942 | temp_b[length_r] = R_last[k][j][cnt]; | ||
943 | length_r++; | ||
944 | } | ||
945 | } | ||
946 | temp_a[length_l] = '\0'; | ||
947 | temp_b[length_r] = '\0'; | ||
948 | |||
949 | GNUNET_asprintf (&R_cur[i][j], "(%s%s)+%s", R_last[i][k], temp_a, | ||
950 | temp_b); | ||
951 | GNUNET_free (temp_a); | ||
952 | GNUNET_free (temp_b); | ||
953 | } | ||
923 | else | 954 | else |
924 | { | 955 | { |
925 | // R(k)ij = R(k-1)ij + R(k-1)ik (R(k-1)kk)* R(k-1)kj | 956 | // R(k)ij = R(k-1)ij + R(k-1)ik (R(k-1)kk)* R(k-1)kj |
@@ -938,8 +969,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
938 | 969 | ||
939 | if (NULL != R_last[k][k] && 0 != strcmp (R_last[k][k], "")) | 970 | if (NULL != R_last[k][k] && 0 != strcmp (R_last[k][k], "")) |
940 | { | 971 | { |
941 | if (R_last[k][k][0] == '(' && | 972 | if (1 >= strlen (R_last[k][k]) || |
942 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')') | 973 | (R_last[k][k][0] == '(' && |
974 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')')) | ||
943 | { | 975 | { |
944 | strcat (R_cur_r, R_last[k][k]); | 976 | strcat (R_cur_r, R_last[k][k]); |
945 | } | 977 | } |
@@ -980,7 +1012,9 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
980 | if (1 >= strlen (R_last[k][k]) || | 1012 | if (1 >= strlen (R_last[k][k]) || |
981 | (R_last[k][k][0] == '(' && | 1013 | (R_last[k][k][0] == '(' && |
982 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')')) | 1014 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')')) |
1015 | { | ||
983 | GNUNET_asprintf (&R_cur[i][j], "%s*", R_last[k][k]); | 1016 | GNUNET_asprintf (&R_cur[i][j], "%s*", R_last[k][k]); |
1017 | } | ||
984 | else | 1018 | else |
985 | GNUNET_asprintf (&R_cur[i][j], "(%s)*", R_last[k][k]); | 1019 | GNUNET_asprintf (&R_cur[i][j], "(%s)*", R_last[k][k]); |
986 | } | 1020 | } |
@@ -1003,16 +1037,18 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1003 | else | 1037 | else |
1004 | strcat (R_cur[i][j], R_last[i][k]); | 1038 | strcat (R_cur[i][j], R_last[i][k]); |
1005 | 1039 | ||
1006 | if (1 >= strlen (R_last[k][k]) && | 1040 | if (1 >= strlen (R_last[k][k]) || |
1007 | !(R_last[k][k][0] == '(' && | 1041 | (R_last[k][k][0] == '(' && |
1008 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')')) | 1042 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')')) |
1009 | { | 1043 | { |
1010 | strcat (R_cur[i][j], "("); | ||
1011 | strcat (R_cur[i][j], R_last[k][k]); | 1044 | strcat (R_cur[i][j], R_last[k][k]); |
1012 | strcat (R_cur[i][j], ")"); | ||
1013 | } | 1045 | } |
1014 | else | 1046 | else |
1047 | { | ||
1048 | strcat (R_cur[i][j], "("); | ||
1015 | strcat (R_cur[i][j], R_last[k][k]); | 1049 | strcat (R_cur[i][j], R_last[k][k]); |
1050 | strcat (R_cur[i][j], ")"); | ||
1051 | } | ||
1016 | 1052 | ||
1017 | if (0 == s_cnt && 0 <= l_cnt) | 1053 | if (0 == s_cnt && 0 <= l_cnt) |
1018 | strcat (R_cur[i][j], "+"); | 1054 | strcat (R_cur[i][j], "+"); |
@@ -1024,16 +1060,13 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1024 | { | 1060 | { |
1025 | // if a is bx then b* a becomes b+ x | 1061 | // if a is bx then b* a becomes b+ x |
1026 | 1062 | ||
1027 | temp = NULL; | ||
1028 | s_cnt = strlen (R_last[k][k]); | 1063 | s_cnt = strlen (R_last[k][k]); |
1029 | l_cnt = strlen (R_last[k][j]); | 1064 | l_cnt = strlen (R_last[k][j]); |
1030 | R_cur[i][j] = GNUNET_malloc (s_cnt + l_cnt + 4); | 1065 | R_cur[i][j] = GNUNET_malloc (s_cnt + l_cnt + 4); |
1031 | 1066 | ||
1032 | int bla; | ||
1033 | |||
1034 | if (l_cnt > 0 && s_cnt >= l_cnt) | 1067 | if (l_cnt > 0 && s_cnt >= l_cnt) |
1035 | for (bla = 0; bla < s_cnt; bla++) | 1068 | for (cnt = 0; cnt < s_cnt; cnt++) |
1036 | if (R_last[k][k][bla] != R_last[k][j][bla]) | 1069 | if (R_last[k][k][cnt] != R_last[k][j][cnt]) |
1037 | break; | 1070 | break; |
1038 | 1071 | ||
1039 | if (1 >= strlen (R_last[k][k]) && | 1072 | if (1 >= strlen (R_last[k][k]) && |
@@ -1047,18 +1080,31 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1047 | else | 1080 | else |
1048 | strcat (R_cur[i][j], R_last[k][k]); | 1081 | strcat (R_cur[i][j], R_last[k][k]); |
1049 | 1082 | ||
1050 | if (bla == s_cnt) | 1083 | if (cnt == s_cnt) |
1051 | strcat (R_cur[i][j], "+"); | 1084 | strcat (R_cur[i][j], "+"); |
1052 | else | 1085 | else |
1053 | strcat (R_cur[i][j], "*"); | 1086 | strcat (R_cur[i][j], "*"); |
1054 | 1087 | ||
1055 | if (strlen (R_last[k][j]) > 0 && bla == s_cnt) | 1088 | if (strlen (R_last[k][j]) > 0 && cnt == s_cnt) |
1056 | strcat (R_cur[i][j], &R_last[k][j][bla]); | 1089 | strcat (R_cur[i][j], &R_last[k][j][cnt]); |
1057 | else | 1090 | else |
1058 | strcat (R_cur[i][j], R_last[k][j]); | 1091 | strcat (R_cur[i][j], R_last[k][j]); |
1059 | } | 1092 | } |
1060 | else | 1093 | else |
1061 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", R_cur_l, R_cur_r); | 1094 | { |
1095 | if (R_cur_l[0] == '(' && R_cur_l[strlen (R_cur_l) - 1] == ')') | ||
1096 | { | ||
1097 | temp_a = GNUNET_malloc (strlen (R_cur_l) - 1); | ||
1098 | for (cnt = 0; cnt < strlen (R_cur_l) - 2; cnt++) | ||
1099 | { | ||
1100 | temp_a[cnt] = R_cur_l[cnt + 1]; | ||
1101 | } | ||
1102 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", temp_a, R_cur_r); | ||
1103 | GNUNET_free (temp_a); | ||
1104 | } | ||
1105 | else | ||
1106 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", R_cur_l, R_cur_r); | ||
1107 | } | ||
1062 | 1108 | ||
1063 | GNUNET_free_non_null (R_cur_l); | 1109 | GNUNET_free_non_null (R_cur_l); |
1064 | GNUNET_free_non_null (R_cur_r); | 1110 | GNUNET_free_non_null (R_cur_r); |
@@ -1102,10 +1148,10 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
1102 | else if (NULL != R_last[a->start->marked][i] && | 1148 | else if (NULL != R_last[a->start->marked][i] && |
1103 | 0 != strcmp (R_last[a->start->marked][i], "")) | 1149 | 0 != strcmp (R_last[a->start->marked][i], "")) |
1104 | { | 1150 | { |
1105 | temp = complete_regex; | 1151 | temp_a = complete_regex; |
1106 | GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex, | 1152 | GNUNET_asprintf (&complete_regex, "%s|%s", complete_regex, |
1107 | R_last[a->start->marked][i]); | 1153 | R_last[a->start->marked][i]); |
1108 | GNUNET_free (temp); | 1154 | GNUNET_free (temp_a); |
1109 | } | 1155 | } |
1110 | } | 1156 | } |
1111 | } | 1157 | } |
@@ -2011,18 +2057,18 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
2011 | return nfa; | 2057 | return nfa; |
2012 | 2058 | ||
2013 | error: | 2059 | error: |
2014 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n"); | 2060 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: %s\n", regex); |
2015 | if (NULL != error_msg) | 2061 | if (NULL != error_msg) |
2016 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg); | 2062 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg); |
2017 | 2063 | ||
2018 | GNUNET_free_non_null (p); | 2064 | GNUNET_free_non_null (p); |
2019 | 2065 | ||
2020 | while (NULL != ctx.stack_tail) | 2066 | while (NULL != (nfa = ctx.stack_head)) |
2021 | { | 2067 | { |
2022 | GNUNET_REGEX_automaton_destroy (ctx.stack_tail); | 2068 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); |
2023 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, | 2069 | GNUNET_REGEX_automaton_destroy (nfa); |
2024 | ctx.stack_tail); | ||
2025 | } | 2070 | } |
2071 | |||
2026 | return NULL; | 2072 | return NULL; |
2027 | } | 2073 | } |
2028 | 2074 | ||
@@ -2147,7 +2193,7 @@ GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a) | |||
2147 | if (NULL == a) | 2193 | if (NULL == a) |
2148 | return; | 2194 | return; |
2149 | 2195 | ||
2150 | GNUNET_free (a->regex); | 2196 | GNUNET_free_non_null (a->regex); |
2151 | GNUNET_free_non_null (a->computed_regex); | 2197 | GNUNET_free_non_null (a->computed_regex); |
2152 | 2198 | ||
2153 | for (s = a->states_head; NULL != s;) | 2199 | for (s = a->states_head; NULL != s;) |
@@ -2435,7 +2481,7 @@ GNUNET_REGEX_get_computed_regex (struct GNUNET_REGEX_Automaton *a) | |||
2435 | */ | 2481 | */ |
2436 | unsigned int | 2482 | unsigned int |
2437 | GNUNET_REGEX_get_first_key (const char *input_string, unsigned int string_len, | 2483 | GNUNET_REGEX_get_first_key (const char *input_string, unsigned int string_len, |
2438 | struct GNUNET_HashCode * key) | 2484 | struct GNUNET_HashCode *key) |
2439 | { | 2485 | { |
2440 | unsigned int size; | 2486 | unsigned int size; |
2441 | 2487 | ||
@@ -2461,7 +2507,7 @@ GNUNET_REGEX_get_first_key (const char *input_string, unsigned int string_len, | |||
2461 | * @return GNUNET_OK if the proof is valid for the given key | 2507 | * @return GNUNET_OK if the proof is valid for the given key |
2462 | */ | 2508 | */ |
2463 | int | 2509 | int |
2464 | GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode * key) | 2510 | GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key) |
2465 | { | 2511 | { |
2466 | return GNUNET_OK; | 2512 | return GNUNET_OK; |
2467 | } | 2513 | } |
diff --git a/src/regex/test_regex_iterate_api.c b/src/regex/test_regex_iterate_api.c index a4cef5a51..a36419a95 100644 --- a/src/regex/test_regex_iterate_api.c +++ b/src/regex/test_regex_iterate_api.c | |||
@@ -28,7 +28,7 @@ | |||
28 | #include "gnunet_regex_lib.h" | 28 | #include "gnunet_regex_lib.h" |
29 | 29 | ||
30 | void | 30 | void |
31 | key_iterator (void *cls, const struct GNUNET_HashCode * key, const char *proof, | 31 | key_iterator (void *cls, const struct GNUNET_HashCode *key, const char *proof, |
32 | int accepting, unsigned int num_edges, | 32 | int accepting, unsigned int num_edges, |
33 | const struct GNUNET_REGEX_Edge *edges) | 33 | const struct GNUNET_REGEX_Edge *edges) |
34 | { | 34 | { |