diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-06-06 13:05:24 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-06-06 13:05:24 +0000 |
commit | 7fbde9df055e9edf9e59994052c9d951697e8802 (patch) | |
tree | ad6a59e89412274a06ac9b5542f39a45c8c4bd68 /src | |
parent | 93f5382bea48b79e65e3f634f0fa9af4f25d255d (diff) | |
download | gnunet-7fbde9df055e9edf9e59994052c9d951697e8802.tar.gz gnunet-7fbde9df055e9edf9e59994052c9d951697e8802.zip |
even better proofs
Diffstat (limited to 'src')
-rw-r--r-- | src/regex/regex.c | 80 |
1 files changed, 54 insertions, 26 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 72ed0f81c..67cadfc5e 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -817,7 +817,10 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
817 | char *R_last[a->state_count][a->state_count]; | 817 | char *R_last[a->state_count][a->state_count]; |
818 | char *R_cur[a->state_count][a->state_count]; | 818 | char *R_cur[a->state_count][a->state_count]; |
819 | char *temp; | 819 | char *temp; |
820 | int length; | 820 | char *R_cur_l; |
821 | char *R_cur_r; | ||
822 | int length_l; | ||
823 | int length_r; | ||
821 | 824 | ||
822 | k = 0; | 825 | k = 0; |
823 | n = a->state_count; | 826 | n = a->state_count; |
@@ -850,17 +853,23 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
850 | } | 853 | } |
851 | } | 854 | } |
852 | 855 | ||
853 | if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) | ||
854 | { | ||
855 | temp = R_last[i][j]; | ||
856 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | ||
857 | GNUNET_free (temp); | ||
858 | } | ||
859 | 856 | ||
860 | if (i == j) | 857 | if (i == j) |
861 | { | 858 | { |
862 | if (NULL == R_last[i][j]) | 859 | if (NULL == R_last[i][j]) |
863 | GNUNET_asprintf (&R_last[i][j], ""); | 860 | GNUNET_asprintf (&R_last[i][j], ""); |
861 | else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) | ||
862 | { | ||
863 | temp = R_last[i][j]; | ||
864 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | ||
865 | GNUNET_free (temp); | ||
866 | } | ||
867 | } | ||
868 | else if (NULL != R_last[i][j] && 1 < strlen (R_last[i][j])) | ||
869 | { | ||
870 | temp = R_last[i][j]; | ||
871 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | ||
872 | GNUNET_free (temp); | ||
864 | } | 873 | } |
865 | } | 874 | } |
866 | } | 875 | } |
@@ -882,41 +891,60 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | |||
882 | else | 891 | else |
883 | { | 892 | { |
884 | // R(k)ij = R(k-1)ij + R(k-1)ik (R(k-1)kk)* R(k-1)kj | 893 | // R(k)ij = R(k-1)ij + R(k-1)ik (R(k-1)kk)* R(k-1)kj |
885 | length = | 894 | length_l = (NULL == R_last[i][j]) ? 1 : strlen (R_last[i][j]) + 1; |
886 | snprintf (NULL, 0, "(%s|%s(%s)*%s)", R_last[i][j], R_last[i][k], | 895 | length_r = |
887 | R_last[k][k], R_last[k][j]) + 1; | 896 | snprintf (NULL, 0, "%s(%s)*%s", R_last[i][k], R_last[k][k], |
888 | char *left = GNUNET_malloc (length); | 897 | R_last[k][j]) + 1; |
889 | char *right = GNUNET_malloc (length); | 898 | R_cur_l = GNUNET_malloc (length_l); |
899 | R_cur_r = GNUNET_malloc (length_r); | ||
890 | 900 | ||
891 | if (NULL != R_last[i][j]) | 901 | if (NULL != R_last[i][j]) |
892 | strcat (left, R_last[i][j]); | 902 | strcat (R_cur_l, R_last[i][j]); |
893 | 903 | ||
894 | if (NULL != R_last[i][k]) | 904 | if (NULL != R_last[i][k]) |
895 | strcat (right, R_last[i][k]); | 905 | strcat (R_cur_r, R_last[i][k]); |
896 | 906 | ||
897 | if (NULL != R_last[k][k] && 0 != strcmp (R_last[k][k], "")) | 907 | if (NULL != R_last[k][k] && 0 != strcmp (R_last[k][k], "")) |
898 | { | 908 | { |
899 | strcat (right, "("); | 909 | strcat (R_cur_r, "("); |
900 | strcat (right, R_last[k][k]); | 910 | strcat (R_cur_r, R_last[k][k]); |
901 | strcat (right, ")*"); | 911 | strcat (R_cur_r, ")*"); |
902 | } | 912 | } |
903 | 913 | ||
904 | if (NULL != R_last[k][j]) | 914 | if (NULL != R_last[k][j]) |
905 | strcat (right, R_last[k][j]); | 915 | strcat (R_cur_r, R_last[k][j]); |
906 | 916 | ||
907 | if (0 == strcmp (left, right) || 0 == strcmp (left, "") || | 917 | // | is idempotent: a | a = a for all a in A |
908 | 0 == strcmp (right, "")) | 918 | if (0 == strcmp (R_cur_l, R_cur_r) || 0 == strcmp (R_cur_l, "") || |
919 | 0 == strcmp (R_cur_r, "")) | ||
909 | { | 920 | { |
910 | if (0 == strcmp (left, "")) | 921 | if (0 == strcmp (R_cur_l, "")) |
911 | GNUNET_asprintf (&R_cur[i][j], "%s", right); | 922 | GNUNET_asprintf (&R_cur[i][j], "%s", R_cur_r); |
912 | else | 923 | else |
913 | GNUNET_asprintf (&R_cur[i][j], "%s", left); | 924 | GNUNET_asprintf (&R_cur[i][j], "%s", R_cur_l); |
925 | } | ||
926 | // a | a a* a = a+ | ||
927 | else if (R_last[i][j] == R_last[i][k] && R_last[i][k] == R_last[k][k] | ||
928 | && R_last[k][k] == R_last[k][j]) | ||
929 | { | ||
930 | GNUNET_asprintf (&R_cur[i][j], "%s+", R_last[i][j]); | ||
931 | } | ||
932 | // a | a b* b => a | a b | a b b | ... => a b* | ||
933 | else if (R_last[i][j] == R_last[i][k] && R_last[k][k] == R_last[k][j]) | ||
934 | { | ||
935 | GNUNET_asprintf (&R_cur[i][j], "%s%s*", R_last[i][k], R_last[k][k]); | ||
936 | } | ||
937 | // a | b b* a => a | b a | b b a | ... => b* a | ||
938 | else if (R_last[i][j] == R_last[k][j] && R_last[i][k] == R_last[k][k]) | ||
939 | { | ||
940 | GNUNET_asprintf (&R_cur[i][j], "%s*%s", R_last[k][k], R_last[k][j]); | ||
914 | } | 941 | } |
915 | else | 942 | else |
916 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", left, right); | 943 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s)", R_cur_l, R_cur_r); |
944 | |||
945 | GNUNET_free_non_null (R_cur_l); | ||
946 | GNUNET_free_non_null (R_cur_r); | ||
917 | 947 | ||
918 | GNUNET_free_non_null (left); | ||
919 | GNUNET_free_non_null (right); | ||
920 | } | 948 | } |
921 | } | 949 | } |
922 | } | 950 | } |