diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-12 11:48:01 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-04-12 11:48:01 +0000 |
commit | 60d64e76a9f343c42f2303f3572d26e262c355c7 (patch) | |
tree | f71ce812d9cad57e2733d178a64fce90db0c741f /src/regex/regex.c | |
parent | eaeb12b6ef7108167cff92964dd41b7e49d6f16d (diff) | |
download | gnunet-60d64e76a9f343c42f2303f3572d26e262c355c7.tar.gz gnunet-60d64e76a9f343c42f2303f3572d26e262c355c7.zip |
Added '?' operator
Diffstat (limited to 'src/regex/regex.c')
-rw-r--r-- | src/regex/regex.c | 88 |
1 files changed, 73 insertions, 15 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 7d943160e..a240fcd80 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -314,24 +314,29 @@ state_compare (const void *a, const void *b) | |||
314 | * @param sset1 first state set | 314 | * @param sset1 first state set |
315 | * @param sset2 second state set | 315 | * @param sset2 second state set |
316 | * | 316 | * |
317 | * @return 0 if they are equal, non 0 otherwise | 317 | * @return an integer less than, equal to, or greater than zero |
318 | * if the first argument is considered to be respectively | ||
319 | * less than, equal to, or greater than the second. | ||
318 | */ | 320 | */ |
319 | static int | 321 | static int |
320 | state_set_compare (struct StateSet *sset1, struct StateSet *sset2) | 322 | state_set_compare (struct StateSet *sset1, struct StateSet *sset2) |
321 | { | 323 | { |
324 | int result; | ||
322 | int i; | 325 | int i; |
323 | 326 | ||
324 | if (sset1->len != sset2->len) | 327 | if (NULL == sset1 || NULL == sset2) |
325 | return 1; | 328 | return 1; |
326 | 329 | ||
330 | result = sset1->len - sset2->len; | ||
331 | |||
327 | for (i = 0; i < sset1->len; i++) | 332 | for (i = 0; i < sset1->len; i++) |
328 | { | 333 | { |
329 | if (sset1->states[i]->id != sset2->states[i]->id) | 334 | if (0 != result) |
330 | { | 335 | break; |
331 | return 1; | 336 | |
332 | } | 337 | result = state_compare (&sset1->states[i], &sset2->states[i]); |
333 | } | 338 | } |
334 | return 0; | 339 | return result; |
335 | } | 340 | } |
336 | 341 | ||
337 | /** | 342 | /** |
@@ -412,6 +417,9 @@ add_transition (struct GNUNET_REGEX_Context *ctx, struct State *from_state, | |||
412 | static void | 417 | static void |
413 | automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a) | 418 | automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a) |
414 | { | 419 | { |
420 | if (NULL == a) | ||
421 | return; | ||
422 | |||
415 | a->start = NULL; | 423 | a->start = NULL; |
416 | a->end = NULL; | 424 | a->end = NULL; |
417 | a->states_head = NULL; | 425 | a->states_head = NULL; |
@@ -431,6 +439,9 @@ automaton_destroy_state (struct State *s) | |||
431 | struct Transition *t; | 439 | struct Transition *t; |
432 | struct Transition *next_t; | 440 | struct Transition *next_t; |
433 | 441 | ||
442 | if (NULL == s) | ||
443 | return; | ||
444 | |||
434 | if (NULL != s->name) | 445 | if (NULL != s->name) |
435 | GNUNET_free (s->name); | 446 | GNUNET_free (s->name); |
436 | 447 | ||
@@ -462,6 +473,9 @@ automaton_remove_state (struct GNUNET_REGEX_Automaton *a, struct State *s) | |||
462 | struct State *s_check; | 473 | struct State *s_check; |
463 | struct Transition *t_check; | 474 | struct Transition *t_check; |
464 | 475 | ||
476 | if (NULL == a || NULL == s) | ||
477 | return; | ||
478 | |||
465 | // remove state | 479 | // remove state |
466 | ss = s; | 480 | ss = s; |
467 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); | 481 | GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s); |
@@ -710,12 +724,9 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | |||
710 | s->marked = 1; // mark s as visited | 724 | s->marked = 1; // mark s as visited |
711 | for (t = s->transitions_head; NULL != t; t = t->next) | 725 | for (t = s->transitions_head; NULL != t; t = t->next) |
712 | { | 726 | { |
727 | // add next states to stack | ||
713 | if (NULL != t->state && 0 == t->state->marked) | 728 | if (NULL != t->state && 0 == t->state->marked) |
714 | { | 729 | stack[++stack_len] = t->state; |
715 | // add next states to stack | ||
716 | stack[stack_len] = t->state; | ||
717 | stack_len++; | ||
718 | } | ||
719 | } | 730 | } |
720 | } | 731 | } |
721 | 732 | ||
@@ -965,13 +976,13 @@ nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting) | |||
965 | } | 976 | } |
966 | 977 | ||
967 | /** | 978 | /** |
968 | * Calculates the NFA closure set for the given state | 979 | * Calculates the NFA closure set for the given state. |
969 | * | 980 | * |
970 | * @param s starting point state | 981 | * @param s starting point state |
971 | * @param literal transitioning literal on which to base the closure on, | 982 | * @param literal transitioning literal on which to base the closure on, |
972 | * pass 0 for epsilon transition | 983 | * pass 0 for epsilon transition |
973 | * | 984 | * |
974 | * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0) | 985 | * @return sorted nfa closure on 'literal' (epsilon closure if 'literal' is 0) |
975 | */ | 986 | */ |
976 | static struct StateSet * | 987 | static struct StateSet * |
977 | nfa_closure_create (struct State *s, const char literal) | 988 | nfa_closure_create (struct State *s, const char literal) |
@@ -1030,7 +1041,7 @@ nfa_closure_create (struct State *s, const char literal) | |||
1030 | * @param literal transitioning literal for which to base the closure on, | 1041 | * @param literal transitioning literal for which to base the closure on, |
1031 | * pass 0 for epsilon transition | 1042 | * pass 0 for epsilon transition |
1032 | * | 1043 | * |
1033 | * @return nfa closure on 'literal' (epsilon closure if 'literal' is 0) | 1044 | * @return sorted nfa closure on 'literal' (epsilon closure if 'literal' is 0) |
1034 | */ | 1045 | */ |
1035 | static struct StateSet * | 1046 | static struct StateSet * |
1036 | nfa_closure_set_create (struct StateSet *states, const char literal) | 1047 | nfa_closure_set_create (struct StateSet *states, const char literal) |
@@ -1168,6 +1179,45 @@ nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx) | |||
1168 | } | 1179 | } |
1169 | 1180 | ||
1170 | /** | 1181 | /** |
1182 | * Pops an NFA fragment (a) from the stack and adds a new fragment (a?) | ||
1183 | * | ||
1184 | * @param ctx context | ||
1185 | */ | ||
1186 | static void | ||
1187 | nfa_add_question_op (struct GNUNET_REGEX_Context *ctx) | ||
1188 | { | ||
1189 | struct GNUNET_REGEX_Automaton *a; | ||
1190 | struct GNUNET_REGEX_Automaton *new; | ||
1191 | struct State *start; | ||
1192 | struct State *end; | ||
1193 | |||
1194 | a = ctx->stack_tail; | ||
1195 | GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a); | ||
1196 | |||
1197 | if (NULL == a) | ||
1198 | { | ||
1199 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | ||
1200 | "nfa_add_question_op failed, because there was no element on the stack"); | ||
1201 | return; | ||
1202 | } | ||
1203 | |||
1204 | start = nfa_state_create (ctx, 0); | ||
1205 | end = nfa_state_create (ctx, 1); | ||
1206 | |||
1207 | add_transition (ctx, start, 0, a->start); | ||
1208 | add_transition (ctx, start, 0, end); | ||
1209 | add_transition (ctx, a->end, 0, end); | ||
1210 | |||
1211 | a->end->accepting = 0; | ||
1212 | |||
1213 | new = nfa_fragment_create (start, end); | ||
1214 | nfa_add_states (new, a->states_head, a->states_tail); | ||
1215 | automaton_fragment_clear (a); | ||
1216 | |||
1217 | GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new); | ||
1218 | } | ||
1219 | |||
1220 | /** | ||
1171 | * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment | 1221 | * Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment |
1172 | * that alternates between a and b (a|b) | 1222 | * that alternates between a and b (a|b) |
1173 | * | 1223 | * |
@@ -1330,6 +1380,14 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) | |||
1330 | } | 1380 | } |
1331 | nfa_add_plus_op (&ctx); | 1381 | nfa_add_plus_op (&ctx); |
1332 | break; | 1382 | break; |
1383 | case '?': | ||
1384 | if (atomcount == 0) | ||
1385 | { | ||
1386 | error_msg = "Cannot append '?' to nothing"; | ||
1387 | goto error; | ||
1388 | } | ||
1389 | nfa_add_question_op (&ctx); | ||
1390 | break; | ||
1333 | case 92: /* escape: \ */ | 1391 | case 92: /* escape: \ */ |
1334 | regexp++; | 1392 | regexp++; |
1335 | count++; | 1393 | count++; |