diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-06-04 13:30:54 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-06-04 13:30:54 +0000 |
commit | 64c0a28f57b9642ae2acda9d5d213201268226b7 (patch) | |
tree | 1062294f72df4b5bc8389fc7ce9849b1ac106287 /src | |
parent | f50643947d805e2f027c6bcd165f36d4b3d4cc3b (diff) | |
download | gnunet-64c0a28f57b9642ae2acda9d5d213201268226b7.tar.gz gnunet-64c0a28f57b9642ae2acda9d5d213201268226b7.zip |
Towards new proof algorithm
Diffstat (limited to 'src')
-rw-r--r-- | src/regex/regex.c | 197 | ||||
-rw-r--r-- | src/regex/test_regex_iterate_api.c | 5 |
2 files changed, 116 insertions, 86 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 5244c2662..c1f2801c6 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -576,8 +576,7 @@ state_set_clear (struct GNUNET_REGEX_StateSet *set) | |||
576 | { | 576 | { |
577 | if (NULL != set) | 577 | if (NULL != set) |
578 | { | 578 | { |
579 | if (NULL != set->states) | 579 | GNUNET_free_non_null (set->states); |
580 | GNUNET_free (set->states); | ||
581 | GNUNET_free (set); | 580 | GNUNET_free (set); |
582 | } | 581 | } |
583 | } | 582 | } |
@@ -616,11 +615,8 @@ automaton_destroy_state (struct GNUNET_REGEX_State *s) | |||
616 | if (NULL == s) | 615 | if (NULL == s) |
617 | return; | 616 | return; |
618 | 617 | ||
619 | if (NULL != s->name) | 618 | GNUNET_free_non_null (s->name); |
620 | GNUNET_free (s->name); | 619 | GNUNET_free_non_null (s->proof); |
621 | |||
622 | if (NULL != s->proof) | ||
623 | GNUNET_free (s->proof); | ||
624 | 620 | ||
625 | for (t = s->transitions_head; NULL != t; t = next_t) | 621 | for (t = s->transitions_head; NULL != t; t = next_t) |
626 | { | 622 | { |
@@ -720,11 +716,7 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
720 | 716 | ||
721 | // 3. Rename s1 to {s1,s2} | 717 | // 3. Rename s1 to {s1,s2} |
722 | new_name = GNUNET_strdup (s1->name); | 718 | new_name = GNUNET_strdup (s1->name); |
723 | if (NULL != s1->name) | 719 | GNUNET_free_non_null (s1->name); |
724 | { | ||
725 | GNUNET_free (s1->name); | ||
726 | s1->name = NULL; | ||
727 | } | ||
728 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); | 720 | GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name); |
729 | GNUNET_free (new_name); | 721 | GNUNET_free (new_name); |
730 | 722 | ||
@@ -806,98 +798,133 @@ automaton_traverse (void *cls, struct GNUNET_REGEX_Automaton *a, | |||
806 | } | 798 | } |
807 | 799 | ||
808 | /** | 800 | /** |
809 | * Reverses all transitions of the given automaton. | 801 | * Create proofs for all states in the given automaton. Implementation of the |
802 | * algorithms descriped in chapter 3.2.1 of "Automata Theory, Languages, and | ||
803 | * Computation 3rd Edition" by Hopcroft, Motwani and Ullman. | ||
810 | * | 804 | * |
811 | * @param a automaton. | 805 | * @param a automaton. |
812 | */ | 806 | */ |
813 | static void | 807 | static void |
814 | automaton_reverse (struct GNUNET_REGEX_Automaton *a) | 808 | automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) |
815 | { | 809 | { |
816 | struct GNUNET_REGEX_State *s; | 810 | struct GNUNET_REGEX_State *s; |
817 | struct Transition *t; | 811 | struct Transition *t; |
818 | struct Transition *t_next; | 812 | int i; |
819 | struct GNUNET_REGEX_State *s_swp; | 813 | int j; |
814 | int k; | ||
815 | int n; | ||
816 | struct GNUNET_REGEX_State *states[a->state_count]; | ||
817 | char *R_last[a->state_count][a->state_count]; | ||
818 | char *R_cur[a->state_count][a->state_count]; | ||
819 | char *temp; | ||
820 | 820 | ||
821 | for (s = a->states_head; NULL != s; s = s->next) | 821 | k = 0; |
822 | for (t = s->transitions_head; NULL != t; t = t->next) | 822 | n = a->state_count; |
823 | t->mark = GNUNET_NO; | ||
824 | 823 | ||
825 | for (s = a->states_head; NULL != s; s = s->next) | 824 | for (i = 0, s = a->states_head; NULL != s; s = s->next, i++) |
826 | { | 825 | { |
827 | for (t = s->transitions_head; NULL != t; t = t_next) | 826 | s->marked = i; |
827 | states[i] = s; | ||
828 | } | ||
829 | |||
830 | // BASIS | ||
831 | for (i = 0; i < n; i++) | ||
832 | { | ||
833 | for (j = 0; j < n; j++) | ||
828 | { | 834 | { |
829 | t_next = t->next; | 835 | R_cur[i][j] = NULL; |
836 | R_last[i][j] = NULL; | ||
837 | for (t = states[i]->transitions_head; NULL != t; t = t->next) | ||
838 | { | ||
839 | if (t->to_state == states[j]) | ||
840 | { | ||
841 | if (NULL == R_last[i][j]) | ||
842 | GNUNET_asprintf (&R_last[i][j], "%c", t->label); | ||
843 | else | ||
844 | { | ||
845 | temp = R_last[i][j]; | ||
846 | GNUNET_asprintf (&R_last[i][j], "%s|%c", R_last[i][j], t->label); | ||
847 | GNUNET_free (temp); | ||
848 | } | ||
849 | } | ||
850 | } | ||
830 | 851 | ||
831 | if (GNUNET_YES == t->mark || t->from_state == t->to_state) | 852 | if (i == j) |
832 | continue; | 853 | { |
854 | if (NULL == R_last[i][j]) | ||
855 | GNUNET_asprintf (&R_last[i][j], ""); | ||
856 | else if (1 < strlen (R_last[i][j])) | ||
857 | { | ||
858 | temp = R_last[i][j]; | ||
859 | GNUNET_asprintf (&R_last[i][j], "(%s)", R_last[i][j]); | ||
860 | GNUNET_free (temp); | ||
861 | } | ||
862 | } | ||
863 | } | ||
864 | } | ||
833 | 865 | ||
834 | t->mark = GNUNET_YES; | 866 | // INDUCTION |
867 | for (k = 0; k < n; k++) | ||
868 | { | ||
869 | for (i = 0; i < n; i++) | ||
870 | { | ||
871 | for (j = 0; j < n; j++) | ||
872 | { | ||
873 | if (NULL == R_last[i][k] || NULL == R_last[k][j]) | ||
874 | { | ||
875 | if (NULL != R_last[i][j]) | ||
876 | R_cur[i][j] = GNUNET_strdup (R_last[i][j]); | ||
877 | } | ||
878 | else if (NULL == R_last[i][j] || | ||
879 | 0 == strcmp (R_last[i][j], R_last[i][k])) | ||
880 | { | ||
881 | if ((R_last[k][k][0] == '(' && | ||
882 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')') || | ||
883 | (1 == strlen (R_last[k][k]))) | ||
884 | GNUNET_asprintf (&R_cur[i][j], "(%s%s*%s)", R_last[i][k], | ||
885 | R_last[k][k], R_last[k][j]); | ||
886 | else | ||
887 | GNUNET_asprintf (&R_cur[i][j], "(%s(%s)*%s)", R_last[i][k], | ||
888 | R_last[k][k], R_last[k][j]); | ||
889 | } | ||
890 | else | ||
891 | { | ||
892 | if ((R_last[k][k][0] == '(' && | ||
893 | R_last[k][k][strlen (R_last[k][k]) - 1] == ')') || | ||
894 | (1 == strlen (R_last[k][k]))) | ||
895 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s%s*%s)", R_last[i][j], | ||
896 | R_last[i][k], R_last[k][k], R_last[k][j]); | ||
897 | else | ||
898 | GNUNET_asprintf (&R_cur[i][j], "(%s|%s(%s)*%s)", R_last[i][j], | ||
899 | R_last[i][k], R_last[k][k], R_last[k][j]); | ||
900 | } | ||
901 | } | ||
902 | } | ||
835 | 903 | ||
836 | GNUNET_CONTAINER_DLL_remove (t->from_state->transitions_head, | 904 | for (i = 0; i < n; i++) |
837 | t->from_state->transitions_tail, t); | 905 | { |
838 | t->from_state->transition_count--; | 906 | for (j = 0; j < n; j++) |
839 | GNUNET_CONTAINER_DLL_insert (t->to_state->transitions_head, | 907 | { |
840 | t->to_state->transitions_tail, t); | 908 | GNUNET_free_non_null (R_last[i][j]); |
841 | t->to_state->transition_count++; | ||
842 | 909 | ||
843 | s_swp = t->from_state; | 910 | if (NULL != R_cur[i][j]) |
844 | t->from_state = t->to_state; | 911 | { |
845 | t->to_state = s_swp; | 912 | R_last[i][j] = GNUNET_strdup (R_cur[i][j]); |
913 | GNUNET_free (R_cur[i][j]); | ||
914 | R_cur[i][j] = NULL; | ||
915 | } | ||
916 | } | ||
846 | } | 917 | } |
847 | } | 918 | } |
848 | } | ||
849 | |||
850 | /** | ||
851 | * Create proof for the given state. | ||
852 | * | ||
853 | * @param cls closure. | ||
854 | * @param s state. | ||
855 | */ | ||
856 | static void | ||
857 | automaton_create_proofs_step (void *cls, struct GNUNET_REGEX_State *s) | ||
858 | { | ||
859 | struct Transition *t; | ||
860 | int i; | ||
861 | char *tmp; | ||
862 | 919 | ||
863 | for (i = 0, t = s->transitions_head; NULL != t; t = t->next, i++) | 920 | for (i = 0; i < n; i++) |
864 | { | 921 | { |
865 | if (t->to_state == s) | 922 | for (j = 0; j < n; j++) |
866 | GNUNET_asprintf (&tmp, "%c*", t->label); | 923 | GNUNET_free_non_null (R_last[i][j]); |
867 | else if (i != s->transition_count - 1) | ||
868 | GNUNET_asprintf (&tmp, "%c|", t->label); | ||
869 | else | ||
870 | GNUNET_asprintf (&tmp, "%c", t->label); | ||
871 | |||
872 | if (NULL != s->proof) | ||
873 | s->proof = | ||
874 | GNUNET_realloc (s->proof, strlen (s->proof) + strlen (tmp) + 1); | ||
875 | else | ||
876 | s->proof = GNUNET_malloc (strlen (tmp) + 1); | ||
877 | strcat (s->proof, tmp); | ||
878 | GNUNET_free (tmp); | ||
879 | } | 924 | } |
880 | } | 925 | } |
881 | 926 | ||
882 | /** | 927 | /** |
883 | * Create proofs for all states in the given automaton. | ||
884 | * | ||
885 | * @param a automaton. | ||
886 | */ | ||
887 | static void | ||
888 | automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) | ||
889 | { | ||
890 | struct GNUNET_REGEX_State *s; | ||
891 | |||
892 | automaton_reverse (a); | ||
893 | |||
894 | for (s = a->states_head; NULL != s; s = s->next) | ||
895 | automaton_create_proofs_step (NULL, s); | ||
896 | |||
897 | automaton_reverse (a); | ||
898 | } | ||
899 | |||
900 | /** | ||
901 | * Creates a new DFA state based on a set of NFA states. Needs to be freed using | 928 | * Creates a new DFA state based on a set of NFA states. Needs to be freed using |
902 | * automaton_destroy_state. | 929 | * automaton_destroy_state. |
903 | * | 930 | * |
@@ -1772,8 +1799,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
1772 | for (; altcount > 0; altcount--) | 1799 | for (; altcount > 0; altcount--) |
1773 | nfa_add_alternation (&ctx); | 1800 | nfa_add_alternation (&ctx); |
1774 | 1801 | ||
1775 | if (NULL != p) | 1802 | GNUNET_free_non_null (p); |
1776 | GNUNET_free (p); | ||
1777 | 1803 | ||
1778 | nfa = ctx.stack_tail; | 1804 | nfa = ctx.stack_tail; |
1779 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); | 1805 | GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); |
@@ -1790,8 +1816,9 @@ error: | |||
1790 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n"); | 1816 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex\n"); |
1791 | if (NULL != error_msg) | 1817 | if (NULL != error_msg) |
1792 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg); | 1818 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg); |
1793 | if (NULL != p) | 1819 | |
1794 | GNUNET_free (p); | 1820 | GNUNET_free_non_null (p); |
1821 | |||
1795 | while (NULL != ctx.stack_tail) | 1822 | while (NULL != ctx.stack_tail) |
1796 | { | 1823 | { |
1797 | GNUNET_REGEX_automaton_destroy (ctx.stack_tail); | 1824 | GNUNET_REGEX_automaton_destroy (ctx.stack_tail); |
diff --git a/src/regex/test_regex_iterate_api.c b/src/regex/test_regex_iterate_api.c index b214d6a93..51ebbcd88 100644 --- a/src/regex/test_regex_iterate_api.c +++ b/src/regex/test_regex_iterate_api.c | |||
@@ -60,7 +60,10 @@ main (int argc, char *argv[]) | |||
60 | struct GNUNET_REGEX_Automaton *dfa; | 60 | struct GNUNET_REGEX_Automaton *dfa; |
61 | 61 | ||
62 | error = 0; | 62 | error = 0; |
63 | regex = "ab(c|d)+c*(a(b|c)d)+"; | 63 | /*regex = "ab(c|d)+c*(a(b|c)+d)+(bla)+"; */ |
64 | /*regex = "z(abc|def)?xyz"; */ | ||
65 | regex = "1*0(0|1)*"; | ||
66 | /*regex = "a+X*y+c|p|R|Z*K*y*R+w|Y*6+n+h*k*w+V*F|W*B*e*"; */ | ||
64 | 67 | ||
65 | dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex)); | 68 | dfa = GNUNET_REGEX_construct_dfa (regex, strlen (regex)); |
66 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa.dot"); | 69 | GNUNET_REGEX_automaton_save_graph (dfa, "dfa.dot"); |