diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-17 20:43:56 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-17 20:43:56 +0000 |
commit | 07971e5de7c792b9f591404f3f79e587f48e8d70 (patch) | |
tree | 5c21e83348b07895cbb515c39b33bb90b29bc8ec | |
parent | 3375c4e198484859e2c59d42aacdec7ab79645fc (diff) | |
download | gnunet-07971e5de7c792b9f591404f3f79e587f48e8d70.tar.gz gnunet-07971e5de7c792b9f591404f3f79e587f48e8d70.zip |
api changes
-rw-r--r-- | src/include/gnunet_regex_lib.h | 101 | ||||
-rw-r--r-- | src/regex/regex.c | 300 |
2 files changed, 239 insertions, 162 deletions
diff --git a/src/include/gnunet_regex_lib.h b/src/include/gnunet_regex_lib.h index 100b73f50..dbeaf58a2 100644 --- a/src/include/gnunet_regex_lib.h +++ b/src/include/gnunet_regex_lib.h | |||
@@ -43,9 +43,20 @@ extern "C" | |||
43 | struct GNUNET_REGEX_Automaton; | 43 | struct GNUNET_REGEX_Automaton; |
44 | 44 | ||
45 | /** | 45 | /** |
46 | * State representation. | 46 | * Edge representation. |
47 | */ | 47 | */ |
48 | struct GNUNET_REGEX_State; | 48 | struct GNUNET_REGEX_Edge |
49 | { | ||
50 | /** | ||
51 | * Label of the edge. | ||
52 | */ | ||
53 | const char *label; | ||
54 | |||
55 | /** | ||
56 | * Destionation of the edge. | ||
57 | */ | ||
58 | GNUNET_HashCode destination; | ||
59 | }; | ||
49 | 60 | ||
50 | /** | 61 | /** |
51 | * Construct an NFA by parsing the regex string of length 'len'. | 62 | * Construct an NFA by parsing the regex string of length 'len'. |
@@ -100,87 +111,57 @@ int | |||
100 | GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, | 111 | GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, |
101 | const char *string); | 112 | const char *string); |
102 | 113 | ||
103 | |||
104 | |||
105 | /** | ||
106 | * Get the starting state of the given automaton 'a'. | ||
107 | * | ||
108 | * @param a automaton. | ||
109 | * | ||
110 | * @return starting state. | ||
111 | */ | ||
112 | struct GNUNET_REGEX_State * | ||
113 | GNUNET_REGEX_automaton_get_start (struct GNUNET_REGEX_Automaton *a); | ||
114 | |||
115 | |||
116 | /** | 114 | /** |
117 | * @return number of bits of 'input_string' that have been consumed | 115 | * @return number of bits of 'input_string' that have been consumed |
118 | * to construct the key | 116 | * to construct the key |
119 | */ | 117 | */ |
120 | unsigned int | 118 | unsigned int |
121 | GNUNET_REGEX_get_first_key (const char *input_string, | 119 | GNUNET_REGEX_get_first_key (const char *input_string, |
122 | GNUNET_HashCode *key); | 120 | unsigned int string_len, |
123 | 121 | GNUNET_HashCode *key); | |
124 | 122 | ||
125 | 123 | ||
126 | /** | 124 | /** |
125 | * Check if the given 'proof' matches the given 'key'. | ||
126 | * | ||
127 | * @param proof partial regex | ||
128 | * @param key hash | ||
129 | * | ||
127 | * @return GNUNET_OK if the proof is valid for the given key | 130 | * @return GNUNET_OK if the proof is valid for the given key |
128 | */ | 131 | */ |
129 | int | 132 | int |
130 | GNUNET_REGEX_check_proof (const char *proof, | 133 | GNUNET_REGEX_check_proof (const char *proof, |
131 | const GNUNET_HashCode *key); | 134 | const GNUNET_HashCode *key); |
132 | |||
133 | |||
134 | struct GNUNET_REGEX_Edge | ||
135 | { | ||
136 | const char *label; | ||
137 | GNUNET_HashCode destination; | ||
138 | }; | ||
139 | |||
140 | |||
141 | typedef void (*GNUNET_REGEX_KeyIterator)(void *cls, | ||
142 | const GNUNET_HashCode *key, | ||
143 | const char *proof, | ||
144 | unsigned int num_edges, | ||
145 | const struct GNUNET_REGEX_Edge *edges); | ||
146 | |||
147 | |||
148 | int | ||
149 | GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a, | ||
150 | GNUNET_REGEX_KeyIterator iterator, | ||
151 | void *iterator_cls); | ||
152 | 135 | ||
153 | 136 | ||
154 | /** | 137 | /** |
155 | * Get the next states, starting from states 's'. | 138 | * Iterator callback function. |
156 | * | ||
157 | * @param a automaton. | ||
158 | * @param s states. | ||
159 | * @param count number of states given in 's'. Will contain number of | ||
160 | * states that were returned upon return. | ||
161 | * | 139 | * |
162 | * @return next states, 'count' will contain the number of states. | 140 | * @param cls closure. |
141 | * @param key hash for current state. | ||
142 | * @param proof proof for current state. | ||
143 | * @param num_edges number of edges leaving current state. | ||
144 | * @param edges edges leaving current state. | ||
163 | */ | 145 | */ |
164 | struct GNUNET_REGEX_State ** | 146 | typedef void (*GNUNET_REGEX_KeyIterator)(void *cls, |
165 | GNUNET_REGEX_automaton_states_get_next (struct GNUNET_REGEX_Automaton *a, | 147 | const GNUNET_HashCode *key, |
166 | struct GNUNET_REGEX_State **s, | 148 | const char *proof, |
167 | unsigned int *count); | 149 | unsigned int num_edges, |
150 | const struct GNUNET_REGEX_Edge *edges); | ||
151 | |||
168 | 152 | ||
169 | /** | 153 | /** |
170 | * Hash a set of states. | 154 | * Iterate over all edges starting from start state of automaton 'a'. Calling |
155 | * iterator for each edge. | ||
171 | * | 156 | * |
172 | * @param a automaton. | 157 | * @param a automaton. |
173 | * @param s states. | 158 | * @param iterator iterator called for each edge. |
174 | * @param count number of states. | 159 | * @param iterator_cls closure. |
175 | * | ||
176 | * @return hash. | ||
177 | */ | 160 | */ |
178 | struct GNUNET_HashCode | 161 | void |
179 | GNUNET_REGEX_automaton_states_hash (struct GNUNET_REGEX_Automaton *a, | 162 | GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a, |
180 | struct GNUNET_REGEX_State **s, | 163 | GNUNET_REGEX_KeyIterator iterator, |
181 | unsigned int count); | 164 | void *iterator_cls); |
182 | |||
183 | |||
184 | 165 | ||
185 | 166 | ||
186 | #if 0 /* keep Emacsens' auto-indent happy */ | 167 | #if 0 /* keep Emacsens' auto-indent happy */ |
diff --git a/src/regex/regex.c b/src/regex/regex.c index 673cebc00..e9b262f95 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -24,9 +24,12 @@ | |||
24 | */ | 24 | */ |
25 | #include "platform.h" | 25 | #include "platform.h" |
26 | #include "gnunet_container_lib.h" | 26 | #include "gnunet_container_lib.h" |
27 | #include "gnunet_crypto_lib.h" | ||
27 | #include "gnunet_regex_lib.h" | 28 | #include "gnunet_regex_lib.h" |
28 | #include "regex.h" | 29 | #include "regex.h" |
29 | 30 | ||
31 | #define initial_bits 10 | ||
32 | |||
30 | /** | 33 | /** |
31 | * Context that contains an id counter for states and transitions | 34 | * Context that contains an id counter for states and transitions |
32 | * as well as a DLL of automatons used as a stack for NFA construction. | 35 | * as well as a DLL of automatons used as a stack for NFA construction. |
@@ -177,6 +180,8 @@ struct GNUNET_REGEX_State | |||
177 | */ | 180 | */ |
178 | char *name; | 181 | char *name; |
179 | 182 | ||
183 | GNUNET_HashCode hash; | ||
184 | |||
180 | /** | 185 | /** |
181 | * Number of transitions from this state to other states. | 186 | * Number of transitions from this state to other states. |
182 | */ | 187 | */ |
@@ -201,7 +206,7 @@ struct GNUNET_REGEX_State | |||
201 | 206 | ||
202 | /** | 207 | /** |
203 | * Transition between two states. Each state can have 0-n transitions. | 208 | * Transition between two states. Each state can have 0-n transitions. |
204 | * If literal is 0, this is considered to be an epsilon transition. | 209 | * If label is 0, this is considered to be an epsilon transition. |
205 | */ | 210 | */ |
206 | struct Transition | 211 | struct Transition |
207 | { | 212 | { |
@@ -221,10 +226,10 @@ struct Transition | |||
221 | unsigned int id; | 226 | unsigned int id; |
222 | 227 | ||
223 | /** | 228 | /** |
224 | * Literal for this transition. This is basically the edge label for | 229 | * label for this transition. This is basically the edge label for |
225 | * the graph. | 230 | * the graph. |
226 | */ | 231 | */ |
227 | char literal; | 232 | char label; |
228 | 233 | ||
229 | /** | 234 | /** |
230 | * State to which this transition leads. | 235 | * State to which this transition leads. |
@@ -279,14 +284,14 @@ debug_print_transitions (struct GNUNET_REGEX_State *s) | |||
279 | { | 284 | { |
280 | struct Transition *t; | 285 | struct Transition *t; |
281 | char *state; | 286 | char *state; |
282 | char literal; | 287 | char label; |
283 | 288 | ||
284 | for (t = s->transitions_head; NULL != t; t = t->next) | 289 | for (t = s->transitions_head; NULL != t; t = t->next) |
285 | { | 290 | { |
286 | if (0 == t->literal) | 291 | if (0 == t->label) |
287 | literal = '0'; | 292 | label = '0'; |
288 | else | 293 | else |
289 | literal = t->literal; | 294 | label = t->label; |
290 | 295 | ||
291 | if (NULL == t->to_state) | 296 | if (NULL == t->to_state) |
292 | state = "NULL"; | 297 | state = "NULL"; |
@@ -294,7 +299,7 @@ debug_print_transitions (struct GNUNET_REGEX_State *s) | |||
294 | state = t->to_state->name; | 299 | state = t->to_state->name; |
295 | 300 | ||
296 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id, | 301 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transition %i: On %c to %s\n", t->id, |
297 | literal, state); | 302 | label, state); |
298 | } | 303 | } |
299 | } | 304 | } |
300 | 305 | ||
@@ -460,16 +465,16 @@ state_set_clear (struct GNUNET_REGEX_StateSet *set) | |||
460 | } | 465 | } |
461 | 466 | ||
462 | /** | 467 | /** |
463 | * Adds a transition from one state to another on 'literal' | 468 | * Adds a transition from one state to another on 'label' |
464 | * | 469 | * |
465 | * @param ctx context | 470 | * @param ctx context |
466 | * @param from_state starting state for the transition | 471 | * @param from_state starting state for the transition |
467 | * @param literal transition label | 472 | * @param label transition label |
468 | * @param to_state state to where the transition should point to | 473 | * @param to_state state to where the transition should point to |
469 | */ | 474 | */ |
470 | static void | 475 | static void |
471 | state_add_transition (struct GNUNET_REGEX_Context *ctx, | 476 | state_add_transition (struct GNUNET_REGEX_Context *ctx, |
472 | struct GNUNET_REGEX_State *from_state, const char literal, | 477 | struct GNUNET_REGEX_State *from_state, const char label, |
473 | struct GNUNET_REGEX_State *to_state) | 478 | struct GNUNET_REGEX_State *to_state) |
474 | { | 479 | { |
475 | struct Transition *t; | 480 | struct Transition *t; |
@@ -483,7 +488,7 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx, | |||
483 | t = GNUNET_malloc (sizeof (struct Transition)); | 488 | t = GNUNET_malloc (sizeof (struct Transition)); |
484 | 489 | ||
485 | t->id = ctx->transition_id++; | 490 | t->id = ctx->transition_id++; |
486 | t->literal = literal; | 491 | t->label = label; |
487 | t->to_state = to_state; | 492 | t->to_state = to_state; |
488 | t->from_state = from_state; | 493 | t->from_state = from_state; |
489 | 494 | ||
@@ -620,10 +625,10 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx, | |||
620 | { | 625 | { |
621 | for (t = s1->transitions_head; NULL != t; t = t->next) | 626 | for (t = s1->transitions_head; NULL != t; t = t->next) |
622 | { | 627 | { |
623 | if (t_check->literal != t->literal && NULL != t_check->to_state && | 628 | if (t_check->label != t->label && NULL != t_check->to_state && |
624 | t_check->to_state != t->to_state && t_check->to_state != s2) | 629 | t_check->to_state != t->to_state && t_check->to_state != s2) |
625 | { | 630 | { |
626 | state_add_transition (ctx, s1, t_check->literal, t_check->to_state); | 631 | state_add_transition (ctx, s1, t_check->label, t_check->to_state); |
627 | } | 632 | } |
628 | } | 633 | } |
629 | } | 634 | } |
@@ -658,6 +663,54 @@ automaton_add_state (struct GNUNET_REGEX_Automaton *a, | |||
658 | a->state_count++; | 663 | a->state_count++; |
659 | } | 664 | } |
660 | 665 | ||
666 | typedef void (*GNUNET_REGEX_traverse_action)(void *cls, struct | ||
667 | GNUNET_REGEX_State *s); | ||
668 | |||
669 | /** | ||
670 | * Traverses all states that are reachable from state 's'. Expects | ||
671 | * the states to be unmarked (s->marked == GNUNET_NO). Performs | ||
672 | * 'action' on each visited state. | ||
673 | * | ||
674 | * @param s start state. | ||
675 | * @param action action to be performed on each state. | ||
676 | */ | ||
677 | static void | ||
678 | automaton_state_traverse (void *cls, struct GNUNET_REGEX_State *s, | ||
679 | GNUNET_REGEX_traverse_action action) | ||
680 | { | ||
681 | struct Transition *t; | ||
682 | |||
683 | if (GNUNET_NO == s->marked) | ||
684 | { | ||
685 | s->marked = GNUNET_YES; | ||
686 | |||
687 | if (NULL != action) | ||
688 | action (cls, s); | ||
689 | |||
690 | for (t = s->transitions_head; NULL != t; t = t->next) | ||
691 | automaton_state_traverse (cls, t->to_state, action); | ||
692 | } | ||
693 | } | ||
694 | |||
695 | /** | ||
696 | * Traverses the given automaton from it's start state, visiting all | ||
697 | * reachable states and calling 'action' on each one of them. | ||
698 | * | ||
699 | * @param a automaton. | ||
700 | * @param action action to be performed on each state. | ||
701 | */ | ||
702 | static void | ||
703 | automaton_traverse (void *cls, struct GNUNET_REGEX_Automaton *a, | ||
704 | GNUNET_REGEX_traverse_action action) | ||
705 | { | ||
706 | struct GNUNET_REGEX_State *s; | ||
707 | |||
708 | for (s = a->start; NULL != s; s = s->next) | ||
709 | s->marked = GNUNET_NO; | ||
710 | |||
711 | automaton_state_traverse (cls, a->start, action); | ||
712 | } | ||
713 | |||
661 | /** | 714 | /** |
662 | * Creates a new DFA state based on a set of NFA states. Needs to be freed | 715 | * Creates a new DFA state based on a set of NFA states. Needs to be freed |
663 | * using automaton_destroy_state. | 716 | * using automaton_destroy_state. |
@@ -720,16 +773,16 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
720 | name = NULL; | 773 | name = NULL; |
721 | } | 774 | } |
722 | 775 | ||
723 | // Add a transition for each distinct literal to NULL state | 776 | // Add a transition for each distinct label to NULL state |
724 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) | 777 | for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next) |
725 | { | 778 | { |
726 | if (0 != ctran->literal) | 779 | if (0 != ctran->label) |
727 | { | 780 | { |
728 | insert = 1; | 781 | insert = 1; |
729 | 782 | ||
730 | for (t = s->transitions_head; NULL != t; t = t->next) | 783 | for (t = s->transitions_head; NULL != t; t = t->next) |
731 | { | 784 | { |
732 | if (t->literal == ctran->literal) | 785 | if (t->label == ctran->label) |
733 | { | 786 | { |
734 | insert = 0; | 787 | insert = 0; |
735 | break; | 788 | break; |
@@ -737,7 +790,7 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
737 | } | 790 | } |
738 | 791 | ||
739 | if (insert) | 792 | if (insert) |
740 | state_add_transition (ctx, s, ctran->literal, NULL); | 793 | state_add_transition (ctx, s, ctran->label, NULL); |
741 | } | 794 | } |
742 | } | 795 | } |
743 | 796 | ||
@@ -753,15 +806,15 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx, | |||
753 | 806 | ||
754 | /** | 807 | /** |
755 | * Move from the given state 's' to the next state on | 808 | * Move from the given state 's' to the next state on |
756 | * transition 'literal' | 809 | * transition 'label' |
757 | * | 810 | * |
758 | * @param s starting state | 811 | * @param s starting state |
759 | * @param literal edge label to follow | 812 | * @param label edge label to follow |
760 | * | 813 | * |
761 | * @return new state or NULL, if transition on literal not possible | 814 | * @return new state or NULL, if transition on label not possible |
762 | */ | 815 | */ |
763 | static struct GNUNET_REGEX_State * | 816 | static struct GNUNET_REGEX_State * |
764 | dfa_move (struct GNUNET_REGEX_State *s, const char literal) | 817 | dfa_move (struct GNUNET_REGEX_State *s, const char label) |
765 | { | 818 | { |
766 | struct Transition *t; | 819 | struct Transition *t; |
767 | struct GNUNET_REGEX_State *new_s; | 820 | struct GNUNET_REGEX_State *new_s; |
@@ -773,7 +826,7 @@ dfa_move (struct GNUNET_REGEX_State *s, const char literal) | |||
773 | 826 | ||
774 | for (t = s->transitions_head; NULL != t; t = t->next) | 827 | for (t = s->transitions_head; NULL != t; t = t->next) |
775 | { | 828 | { |
776 | if (literal == t->literal) | 829 | if (label == t->label) |
777 | { | 830 | { |
778 | new_s = t->to_state; | 831 | new_s = t->to_state; |
779 | break; | 832 | break; |
@@ -783,6 +836,7 @@ dfa_move (struct GNUNET_REGEX_State *s, const char literal) | |||
783 | return new_s; | 836 | return new_s; |
784 | } | 837 | } |
785 | 838 | ||
839 | |||
786 | /** | 840 | /** |
787 | * Remove all unreachable states from DFA 'a'. Unreachable states | 841 | * Remove all unreachable states from DFA 'a'. Unreachable states |
788 | * are those states that are not reachable from the starting state. | 842 | * are those states that are not reachable from the starting state. |
@@ -792,37 +846,21 @@ dfa_move (struct GNUNET_REGEX_State *s, const char literal) | |||
792 | static void | 846 | static void |
793 | dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | 847 | dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) |
794 | { | 848 | { |
795 | struct GNUNET_REGEX_State *stack[a->state_count * a->state_count]; | ||
796 | int stack_len; | ||
797 | struct GNUNET_REGEX_State *s; | 849 | struct GNUNET_REGEX_State *s; |
798 | struct GNUNET_REGEX_State *s_next; | 850 | struct GNUNET_REGEX_State *s_next; |
799 | struct Transition *t; | ||
800 | |||
801 | stack_len = 0; | ||
802 | 851 | ||
803 | // 1. unmark all states | 852 | // 1. unmark all states |
804 | for (s = a->states_head; NULL != s; s = s->next) | 853 | for (s = a->states_head; NULL != s; s = s->next) |
805 | s->marked = 0; | 854 | s->marked = GNUNET_NO; |
806 | 855 | ||
807 | // 2. traverse dfa from start state and mark all visited states | 856 | // 2. traverse dfa from start state and mark all visited states |
808 | stack[stack_len++] = a->start; | 857 | automaton_traverse (NULL, a, NULL); |
809 | while (stack_len > 0) | ||
810 | { | ||
811 | s = stack[--stack_len]; | ||
812 | s->marked = 1; // mark s as visited | ||
813 | for (t = s->transitions_head; NULL != t; t = t->next) | ||
814 | { | ||
815 | // add next states to stack | ||
816 | if (NULL != t->to_state && 0 == t->to_state->marked) | ||
817 | stack[stack_len++] = t->to_state; | ||
818 | } | ||
819 | } | ||
820 | 858 | ||
821 | // 3. delete all states that were not visited | 859 | // 3. delete all states that were not visited |
822 | for (s = a->states_head; NULL != s; s = s_next) | 860 | for (s = a->states_head; NULL != s; s = s_next) |
823 | { | 861 | { |
824 | s_next = s->next; | 862 | s_next = s->next; |
825 | if (0 == s->marked) | 863 | if (GNUNET_NO == s->marked) |
826 | { | 864 | { |
827 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Removed state %s\n", s->name); | 865 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Removed state %s\n", s->name); |
828 | automaton_remove_state (a, s); | 866 | automaton_remove_state (a, s); |
@@ -920,14 +958,14 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, | |||
920 | { | 958 | { |
921 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) | 959 | for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next) |
922 | { | 960 | { |
923 | if (t1->literal == t2->literal && t1->to_state == t2->to_state && | 961 | if (t1->label == t2->label && t1->to_state == t2->to_state && |
924 | (0 != table[t1->to_state->marked][t2->to_state->marked] || | 962 | (0 != table[t1->to_state->marked][t2->to_state->marked] || |
925 | 0 != table[t2->to_state->marked][t1->to_state->marked])) | 963 | 0 != table[t2->to_state->marked][t1->to_state->marked])) |
926 | { | 964 | { |
927 | table[s1->marked][s2->marked] = t1->literal; | 965 | table[s1->marked][s2->marked] = t1->label; |
928 | change = 1; | 966 | change = 1; |
929 | } | 967 | } |
930 | else if (t1->literal != t2->literal && t1->to_state != t2->to_state) | 968 | else if (t1->label != t2->label && t1->to_state != t2->to_state) |
931 | { | 969 | { |
932 | table[s1->marked][s2->marked] = -1; | 970 | table[s1->marked][s2->marked] = -1; |
933 | change = 1; | 971 | change = 1; |
@@ -1078,14 +1116,14 @@ nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting) | |||
1078 | * | 1116 | * |
1079 | * @param nfa the NFA containing 's' | 1117 | * @param nfa the NFA containing 's' |
1080 | * @param s starting point state | 1118 | * @param s starting point state |
1081 | * @param literal transitioning literal on which to base the closure on, | 1119 | * @param label transitioning label on which to base the closure on, |
1082 | * pass 0 for epsilon transition | 1120 | * pass 0 for epsilon transition |
1083 | * | 1121 | * |
1084 | * @return sorted nfa closure on 'literal' (epsilon closure if 'literal' is 0) | 1122 | * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0) |
1085 | */ | 1123 | */ |
1086 | static struct GNUNET_REGEX_StateSet * | 1124 | static struct GNUNET_REGEX_StateSet * |
1087 | nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | 1125 | nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, |
1088 | struct GNUNET_REGEX_State *s, const char literal) | 1126 | struct GNUNET_REGEX_State *s, const char label) |
1089 | { | 1127 | { |
1090 | struct GNUNET_REGEX_StateSet *cls; | 1128 | struct GNUNET_REGEX_StateSet *cls; |
1091 | struct GNUNET_REGEX_StateSet *cls_check; | 1129 | struct GNUNET_REGEX_StateSet *cls_check; |
@@ -1103,7 +1141,7 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1103 | clsstate->contained = 0; | 1141 | clsstate->contained = 0; |
1104 | 1142 | ||
1105 | // Add start state to closure only for epsilon closure | 1143 | // Add start state to closure only for epsilon closure |
1106 | if (0 == literal) | 1144 | if (0 == label) |
1107 | GNUNET_array_append (cls->states, cls->len, s); | 1145 | GNUNET_array_append (cls->states, cls->len, s); |
1108 | 1146 | ||
1109 | GNUNET_array_append (cls_check->states, cls_check->len, s); | 1147 | GNUNET_array_append (cls_check->states, cls_check->len, s); |
@@ -1115,7 +1153,7 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1115 | for (ctran = currentstate->transitions_head; NULL != ctran; | 1153 | for (ctran = currentstate->transitions_head; NULL != ctran; |
1116 | ctran = ctran->next) | 1154 | ctran = ctran->next) |
1117 | { | 1155 | { |
1118 | if (NULL != ctran->to_state && literal == ctran->literal) | 1156 | if (NULL != ctran->to_state && label == ctran->label) |
1119 | { | 1157 | { |
1120 | clsstate = ctran->to_state; | 1158 | clsstate = ctran->to_state; |
1121 | 1159 | ||
@@ -1143,15 +1181,15 @@ nfa_closure_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1143 | * | 1181 | * |
1144 | * @param nfa the NFA containing 's' | 1182 | * @param nfa the NFA containing 's' |
1145 | * @param states list of states on which to base the closure on | 1183 | * @param states list of states on which to base the closure on |
1146 | * @param literal transitioning literal for which to base the closure on, | 1184 | * @param label transitioning label for which to base the closure on, |
1147 | * pass 0 for epsilon transition | 1185 | * pass 0 for epsilon transition |
1148 | * | 1186 | * |
1149 | * @return sorted nfa closure on 'literal' (epsilon closure if 'literal' is 0) | 1187 | * @return sorted nfa closure on 'label' (epsilon closure if 'label' is 0) |
1150 | */ | 1188 | */ |
1151 | static struct GNUNET_REGEX_StateSet * | 1189 | static struct GNUNET_REGEX_StateSet * |
1152 | nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa, | 1190 | nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa, |
1153 | struct GNUNET_REGEX_StateSet *states, | 1191 | struct GNUNET_REGEX_StateSet *states, |
1154 | const char literal) | 1192 | const char label) |
1155 | { | 1193 | { |
1156 | struct GNUNET_REGEX_State *s; | 1194 | struct GNUNET_REGEX_State *s; |
1157 | struct GNUNET_REGEX_StateSet *sset; | 1195 | struct GNUNET_REGEX_StateSet *sset; |
@@ -1169,7 +1207,7 @@ nfa_closure_set_create (struct GNUNET_REGEX_Automaton *nfa, | |||
1169 | for (i = 0; i < states->len; i++) | 1207 | for (i = 0; i < states->len; i++) |
1170 | { | 1208 | { |
1171 | s = states->states[i]; | 1209 | s = states->states[i]; |
1172 | sset = nfa_closure_create (nfa, s, literal); | 1210 | sset = nfa_closure_create (nfa, s, label); |
1173 | 1211 | ||
1174 | for (j = 0; j < sset->len; j++) | 1212 | for (j = 0; j < sset->len; j++) |
1175 | { | 1213 | { |
@@ -1370,10 +1408,10 @@ nfa_add_alternation (struct GNUNET_REGEX_Context *ctx) | |||
1370 | * Adds a new nfa fragment to the stack | 1408 | * Adds a new nfa fragment to the stack |
1371 | * | 1409 | * |
1372 | * @param ctx context | 1410 | * @param ctx context |
1373 | * @param lit literal for nfa transition | 1411 | * @param lit label for nfa transition |
1374 | */ | 1412 | */ |
1375 | static void | 1413 | static void |
1376 | nfa_add_literal (struct GNUNET_REGEX_Context *ctx, const char lit) | 1414 | nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char lit) |
1377 | { | 1415 | { |
1378 | struct GNUNET_REGEX_Automaton *n; | 1416 | struct GNUNET_REGEX_Automaton *n; |
1379 | struct GNUNET_REGEX_State *start; | 1417 | struct GNUNET_REGEX_State *start; |
@@ -1525,7 +1563,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
1525 | --atomcount; | 1563 | --atomcount; |
1526 | nfa_add_concatenation (&ctx); | 1564 | nfa_add_concatenation (&ctx); |
1527 | } | 1565 | } |
1528 | nfa_add_literal (&ctx, *regexp); | 1566 | nfa_add_label (&ctx, *regexp); |
1529 | atomcount++; | 1567 | atomcount++; |
1530 | break; | 1568 | break; |
1531 | } | 1569 | } |
@@ -1624,9 +1662,9 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len) | |||
1624 | for (ctran = dfa_state->transitions_head; NULL != ctran; | 1662 | for (ctran = dfa_state->transitions_head; NULL != ctran; |
1625 | ctran = ctran->next) | 1663 | ctran = ctran->next) |
1626 | { | 1664 | { |
1627 | if (0 != ctran->literal && NULL == ctran->to_state) | 1665 | if (0 != ctran->label && NULL == ctran->to_state) |
1628 | { | 1666 | { |
1629 | tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->literal); | 1667 | tmp = nfa_closure_set_create (nfa, dfa_state->nfa_set, ctran->label); |
1630 | nfa_set = nfa_closure_set_create (nfa, tmp, 0); | 1668 | nfa_set = nfa_closure_set_create (nfa, tmp, 0); |
1631 | state_set_clear (tmp); | 1669 | state_set_clear (tmp); |
1632 | new_dfa_state = dfa_state_create (&ctx, nfa_set); | 1670 | new_dfa_state = dfa_state_create (&ctx, nfa_set); |
@@ -1761,7 +1799,7 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | |||
1761 | continue; | 1799 | continue; |
1762 | } | 1800 | } |
1763 | 1801 | ||
1764 | if (ctran->literal == 0) | 1802 | if (ctran->label == 0) |
1765 | { | 1803 | { |
1766 | GNUNET_asprintf (&s_tran, | 1804 | GNUNET_asprintf (&s_tran, |
1767 | "\"%s\" -> \"%s\" [label = \"epsilon\", color=\"0.%i 0.8 0.95\"];\n", | 1805 | "\"%s\" -> \"%s\" [label = \"epsilon\", color=\"0.%i 0.8 0.95\"];\n", |
@@ -1771,7 +1809,7 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | |||
1771 | { | 1809 | { |
1772 | GNUNET_asprintf (&s_tran, | 1810 | GNUNET_asprintf (&s_tran, |
1773 | "\"%s\" -> \"%s\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n", | 1811 | "\"%s\" -> \"%s\" [label = \"%c\", color=\"0.%i 0.8 0.95\"];\n", |
1774 | s->name, ctran->to_state->name, ctran->literal, | 1812 | s->name, ctran->to_state->name, ctran->label, |
1775 | s->scc_id); | 1813 | s->scc_id); |
1776 | } | 1814 | } |
1777 | 1815 | ||
@@ -1904,72 +1942,130 @@ GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1904 | } | 1942 | } |
1905 | 1943 | ||
1906 | /** | 1944 | /** |
1907 | * Get the starting state of the given automaton 'a'. | 1945 | * Get the first key for the given 'input_string'. This hashes |
1946 | * the first x bits of the 'input_strings'. | ||
1908 | * | 1947 | * |
1909 | * @param a automaton. | 1948 | * @param input_string string. |
1949 | * @param string_len length of the 'input_string'. | ||
1950 | * @param key pointer to where to write the hash code. | ||
1910 | * | 1951 | * |
1911 | * @return starting state. | 1952 | * @return number of bits of 'input_string' that have been consumed |
1953 | * to construct the key | ||
1912 | */ | 1954 | */ |
1913 | struct GNUNET_REGEX_State * | 1955 | unsigned int |
1914 | GNUNET_REGEX_automaton_get_start (struct GNUNET_REGEX_Automaton *a) | 1956 | GNUNET_REGEX_get_first_key (const char *input_string, |
1957 | unsigned int string_len, | ||
1958 | GNUNET_HashCode *key) | ||
1915 | { | 1959 | { |
1916 | return a->start; | 1960 | unsigned int size; |
1961 | |||
1962 | size = string_len < initial_bits ? string_len : initial_bits; | ||
1963 | |||
1964 | if (NULL == input_string) | ||
1965 | { | ||
1966 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Given input string was NULL!\n"); | ||
1967 | return 0; | ||
1968 | } | ||
1969 | |||
1970 | GNUNET_CRYPTO_hash (input_string, size, key); | ||
1971 | |||
1972 | return size; | ||
1917 | } | 1973 | } |
1918 | 1974 | ||
1919 | /** | 1975 | /** |
1920 | * Get the next states, starting from states 's'. | 1976 | * Check if the given 'proof' matches the given 'key'. |
1921 | * | 1977 | * |
1922 | * @param a automaton. | 1978 | * @param proof partial regex |
1923 | * @param s states. | 1979 | * @param key hash |
1924 | * @param count number of states given in 's'. Will contain number of | 1980 | * |
1925 | * states that were returned upon return. | 1981 | * @return GNUNET_OK if the proof is valid for the given key |
1982 | */ | ||
1983 | int | ||
1984 | GNUNET_REGEX_check_proof (const char *proof, | ||
1985 | const GNUNET_HashCode *key) | ||
1986 | { | ||
1987 | return GNUNET_OK; | ||
1988 | } | ||
1989 | |||
1990 | /** | ||
1991 | * Get all edges leaving state 's'. | ||
1992 | * | ||
1993 | * @param s state. | ||
1994 | * @param edges all edges leaving 's'. | ||
1926 | * | 1995 | * |
1927 | * @return next states, 'count' will contain the number of states. | 1996 | * @return number of edges. |
1928 | */ | 1997 | */ |
1929 | struct GNUNET_REGEX_State ** | 1998 | static unsigned int |
1930 | GNUNET_REGEX_automaton_states_get_next (struct GNUNET_REGEX_Automaton *a, | 1999 | state_get_edges (struct GNUNET_REGEX_State *s, struct GNUNET_REGEX_Edge *edges) |
1931 | struct GNUNET_REGEX_State **s, | ||
1932 | unsigned int *count) | ||
1933 | { | 2000 | { |
1934 | struct GNUNET_REGEX_State *states[a->state_count]; | ||
1935 | struct GNUNET_REGEX_State *state; | ||
1936 | struct Transition *t; | 2001 | struct Transition *t; |
1937 | unsigned int cnt; | 2002 | unsigned int count; |
1938 | int i; | 2003 | |
2004 | if (NULL == s) | ||
2005 | return 0; | ||
1939 | 2006 | ||
2007 | count = 0; | ||
1940 | 2008 | ||
1941 | for (cnt = 0, i = 0; i < *count; i++) | 2009 | for (t = s->transitions_head; NULL != t; t = t->next) |
1942 | { | 2010 | { |
1943 | state = s[i]; | 2011 | if (NULL != t->to_state) |
1944 | for (t = state->transitions_head; NULL != t; t = t->next) | ||
1945 | { | 2012 | { |
1946 | if (NULL != t && NULL != t->to_state) | 2013 | edges[count].label = &t->label; |
1947 | { | 2014 | edges[count].destination = t->to_state->hash; |
1948 | states[cnt++] = t->to_state; | 2015 | count++; |
1949 | } | ||
1950 | } | 2016 | } |
1951 | } | 2017 | } |
2018 | return count; | ||
2019 | } | ||
1952 | 2020 | ||
1953 | *count = cnt; | 2021 | /** |
2022 | * Iterate over all edges helper function starting from state 's', calling | ||
2023 | * iterator on for each edge. | ||
2024 | * | ||
2025 | * @param s state. | ||
2026 | * @param iterator iterator function called for each edge. | ||
2027 | * @param iterator_cls closure. | ||
2028 | */ | ||
2029 | static void | ||
2030 | iterate_edge (struct GNUNET_REGEX_State *s, | ||
2031 | GNUNET_REGEX_KeyIterator iterator, | ||
2032 | void *iterator_cls) | ||
2033 | { | ||
2034 | struct Transition *t; | ||
2035 | struct GNUNET_REGEX_Edge edges[s->transition_count]; | ||
2036 | unsigned int num_edges; | ||
1954 | 2037 | ||
1955 | return NULL; | 2038 | if (GNUNET_NO == s->marked) |
2039 | { | ||
2040 | s->marked = GNUNET_YES; | ||
2041 | |||
2042 | num_edges = state_get_edges (s, edges); | ||
2043 | |||
2044 | iterator (iterator_cls, | ||
2045 | &s->hash, | ||
2046 | NULL, | ||
2047 | |||
2048 | num_edges, | ||
2049 | edges); | ||
2050 | |||
2051 | |||
2052 | for (t = s->transitions_head; NULL != t; t = t->next) | ||
2053 | iterate_edge (t->to_state, iterator, iterator_cls); | ||
2054 | } | ||
1956 | } | 2055 | } |
1957 | 2056 | ||
1958 | /** | 2057 | /** |
1959 | * Hash a set of states. | 2058 | * Iterate over all edges starting from start state of automaton 'a'. Calling |
2059 | * iterator for each edge. | ||
1960 | * | 2060 | * |
1961 | * @param a automaton. | 2061 | * @param a automaton. |
1962 | * @param s states. | 2062 | * @param iterator iterator called for each edge. |
1963 | * @param count number of states. | 2063 | * @param iterator_cls closure. |
1964 | * | ||
1965 | * @return hash. | ||
1966 | */ | 2064 | */ |
1967 | struct GNUNET_HashCode | 2065 | void |
1968 | GNUNET_REGEX_automaton_states_hash (struct GNUNET_REGEX_Automaton *a, | 2066 | GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a, |
1969 | struct GNUNET_REGEX_State **s, | 2067 | GNUNET_REGEX_KeyIterator iterator, |
1970 | unsigned int count) | 2068 | void *iterator_cls) |
1971 | { | 2069 | { |
1972 | struct GNUNET_HashCode hash; | 2070 | iterate_edge (a->start, iterator, iterator_cls); |
1973 | |||
1974 | return hash; | ||
1975 | } | 2071 | } |