diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-02 10:19:19 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-02 10:19:19 +0000 |
commit | 04dfdb6bd627565890b11094967487fecdd802e8 (patch) | |
tree | a031dadff93c42e10d34df875ffd37c8a9e05802 /src | |
parent | c66c137ef5b07040897e2af3fafbeaca5b4a84d1 (diff) | |
download | gnunet-04dfdb6bd627565890b11094967487fecdd802e8.tar.gz gnunet-04dfdb6bd627565890b11094967487fecdd802e8.zip |
NFA evaluation
Diffstat (limited to 'src')
-rw-r--r-- | src/regex/regex.c | 100 | ||||
-rw-r--r-- | src/regex/test_regex.c | 4 |
2 files changed, 82 insertions, 22 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 596acb323..4ad063e3c 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -246,6 +246,22 @@ state_set_contains (struct StateSet *set, struct State *elem) | |||
246 | } | 246 | } |
247 | 247 | ||
248 | /** | 248 | /** |
249 | * Clears the given StateSet 'set' | ||
250 | * | ||
251 | * @param set set to be cleared | ||
252 | */ | ||
253 | void | ||
254 | state_set_clear (struct StateSet *set) | ||
255 | { | ||
256 | if (NULL != set) | ||
257 | { | ||
258 | if (NULL != set->states) | ||
259 | GNUNET_free (set->states); | ||
260 | GNUNET_free (set); | ||
261 | } | ||
262 | } | ||
263 | |||
264 | /** | ||
249 | * Adds a transition from one state to another on 'literal' | 265 | * Adds a transition from one state to another on 'literal' |
250 | * | 266 | * |
251 | * @param ctx context | 267 | * @param ctx context |
@@ -313,12 +329,7 @@ automaton_destroy_state (struct State *s) | |||
313 | t = next_t; | 329 | t = next_t; |
314 | } | 330 | } |
315 | 331 | ||
316 | if (NULL != s->nfa_set) | 332 | state_set_clear (s->nfa_set); |
317 | { | ||
318 | if (s->nfa_set->len > 0) | ||
319 | GNUNET_free (s->nfa_set->states); | ||
320 | GNUNET_free (s->nfa_set); | ||
321 | } | ||
322 | 333 | ||
323 | GNUNET_free (s); | 334 | GNUNET_free (s); |
324 | } | 335 | } |
@@ -758,12 +769,7 @@ nfa_closure_set_create (struct StateSet *states, const char literal) | |||
758 | for (j = 0; j < sset->len; j++) | 769 | for (j = 0; j < sset->len; j++) |
759 | GNUNET_array_append (cls->states, cls->len, sset->states[j]); | 770 | GNUNET_array_append (cls->states, cls->len, sset->states[j]); |
760 | 771 | ||
761 | if (NULL != sset) | 772 | state_set_clear (sset); |
762 | { | ||
763 | if (sset->len > 0) | ||
764 | GNUNET_free (sset->states); | ||
765 | GNUNET_free (sset); | ||
766 | } | ||
767 | } | 773 | } |
768 | 774 | ||
769 | return cls; | 775 | return cls; |
@@ -999,12 +1005,7 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len) | |||
999 | { | 1005 | { |
1000 | tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal); | 1006 | tmp = nfa_closure_set_create (dfa_state->nfa_set, ctran->literal); |
1001 | nfa_set = nfa_closure_set_create (tmp, 0); | 1007 | nfa_set = nfa_closure_set_create (tmp, 0); |
1002 | if (NULL != tmp) | 1008 | state_set_clear (tmp); |
1003 | { | ||
1004 | if (tmp->len > 0) | ||
1005 | GNUNET_free (tmp->states); | ||
1006 | GNUNET_free (tmp); | ||
1007 | } | ||
1008 | new_dfa_state = dfa_state_create (&ctx, nfa_set); | 1009 | new_dfa_state = dfa_state_create (&ctx, nfa_set); |
1009 | state_contains = NULL; | 1010 | state_contains = NULL; |
1010 | for (state_iter = dfa->states_head; NULL != state_iter; | 1011 | for (state_iter = dfa->states_head; NULL != state_iter; |
@@ -1125,13 +1126,26 @@ GNUNET_REGEX_automaton_save_graph (struct GNUNET_REGEX_Automaton *a, | |||
1125 | fclose (p); | 1126 | fclose (p); |
1126 | } | 1127 | } |
1127 | 1128 | ||
1129 | /** | ||
1130 | * Evaluates the given string using the given DFA automaton | ||
1131 | * | ||
1132 | * @param a automaton, type must be DFA | ||
1133 | * @param string string that should be evaluated | ||
1134 | * | ||
1135 | * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise | ||
1136 | */ | ||
1128 | int | 1137 | int |
1129 | evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | 1138 | evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) |
1130 | { | 1139 | { |
1131 | const char *strp; | 1140 | const char *strp; |
1132 | struct State *s; | 1141 | struct State *s; |
1133 | 1142 | ||
1134 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Evaluating '%s' using DFA\n", string); | 1143 | if (DFA != a->type) |
1144 | { | ||
1145 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
1146 | "Tried to evaluate NFA, but DFA automaton given"); | ||
1147 | return GNUNET_SYSERR; | ||
1148 | } | ||
1135 | 1149 | ||
1136 | s = a->start; | 1150 | s = a->start; |
1137 | 1151 | ||
@@ -1148,12 +1162,56 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) | |||
1148 | return GNUNET_NO; | 1162 | return GNUNET_NO; |
1149 | } | 1163 | } |
1150 | 1164 | ||
1165 | /** | ||
1166 | * Evaluates the given string using the given NFA automaton | ||
1167 | * | ||
1168 | * @param a automaton, type must be NFA | ||
1169 | * @param string string that should be evaluated | ||
1170 | * | ||
1171 | * @return GNUNET_YES if string matches, GNUNET_NO if not, GNUNET_SYSERR otherwise | ||
1172 | */ | ||
1151 | int | 1173 | int |
1152 | evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) | 1174 | evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) |
1153 | { | 1175 | { |
1154 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Evaluating '%s' using NFA\n", string); | 1176 | const char *strp; |
1177 | struct State *s; | ||
1178 | struct StateSet *sset; | ||
1179 | struct StateSet *new_sset; | ||
1180 | int i; | ||
1181 | int eval; | ||
1182 | |||
1183 | if (NFA != a->type) | ||
1184 | { | ||
1185 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
1186 | "Tried to evaluate NFA, but DFA automaton given"); | ||
1187 | return GNUNET_SYSERR; | ||
1188 | } | ||
1189 | |||
1190 | eval = GNUNET_NO; | ||
1191 | strp = string; | ||
1192 | sset = GNUNET_malloc (sizeof (struct StateSet)); | ||
1193 | GNUNET_array_append (sset->states, sset->len, a->start); | ||
1194 | |||
1195 | for (strp = string; NULL != strp && *strp; strp++) | ||
1196 | { | ||
1197 | new_sset = nfa_closure_set_create (sset, *strp); | ||
1198 | state_set_clear (sset); | ||
1199 | sset = nfa_closure_set_create (new_sset, 0); | ||
1200 | state_set_clear (new_sset); | ||
1201 | } | ||
1202 | |||
1203 | for (i = 0; i < sset->len; i++) | ||
1204 | { | ||
1205 | s = sset->states[i]; | ||
1206 | if (NULL != s && s->accepting) | ||
1207 | { | ||
1208 | eval = GNUNET_YES; | ||
1209 | break; | ||
1210 | } | ||
1211 | } | ||
1155 | 1212 | ||
1156 | return GNUNET_YES; | 1213 | state_set_clear (sset); |
1214 | return eval; | ||
1157 | } | 1215 | } |
1158 | 1216 | ||
1159 | 1217 | ||
diff --git a/src/regex/test_regex.c b/src/regex/test_regex.c index 56aea52a7..6835d1b83 100644 --- a/src/regex/test_regex.c +++ b/src/regex/test_regex.c | |||
@@ -48,7 +48,9 @@ main (int argc, char *argv[]) | |||
48 | dfa = NULL; | 48 | dfa = NULL; |
49 | 49 | ||
50 | regex = "a\\*b(c|d)+c*(a(b|c)d)+"; | 50 | regex = "a\\*b(c|d)+c*(a(b|c)d)+"; |
51 | string = "a*bcabd"; | 51 | string = "a*bcdcdcdcdddddabd"; |
52 | /*regex = "VPN TCP (IPv4|IPv6) Port53"; */ | ||
53 | /*string = "VPN TCP IPv4 Port53"; */ | ||
52 | /*regex = "\\*a(a|b)b"; */ | 54 | /*regex = "\\*a(a|b)b"; */ |
53 | /*regex = "a(a|b)c"; */ | 55 | /*regex = "a(a|b)c"; */ |
54 | /*regex = "(a|aa)+"; */ | 56 | /*regex = "(a|aa)+"; */ |