aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorMaximilian Szengel <gnunet@maxsz.de>2012-04-02 10:19:19 +0000
committerMaximilian Szengel <gnunet@maxsz.de>2012-04-02 10:19:19 +0000
commit04dfdb6bd627565890b11094967487fecdd802e8 (patch)
treea031dadff93c42e10d34df875ffd37c8a9e05802 /src
parentc66c137ef5b07040897e2af3fafbeaca5b4a84d1 (diff)
downloadgnunet-04dfdb6bd627565890b11094967487fecdd802e8.tar.gz
gnunet-04dfdb6bd627565890b11094967487fecdd802e8.zip
NFA evaluation
Diffstat (limited to 'src')
-rw-r--r--src/regex/regex.c100
-rw-r--r--src/regex/test_regex.c4
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 */
253void
254state_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 */
1128int 1137int
1129evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) 1138evaluate_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 */
1151int 1173int
1152evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) 1174evaluate_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)+"; */