diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-07-09 15:18:37 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-07-09 15:18:37 +0000 |
commit | 143251dbfe59ffe6e31b4497caa1312f9652df09 (patch) | |
tree | 73f71067e01b9b41e265f0948c22fbd682a3e1c1 /src/regex/regex.c | |
parent | 4c888f99b9c42fae1e5bd419a7c3ce5416b89152 (diff) | |
download | gnunet-143251dbfe59ffe6e31b4497caa1312f9652df09.tar.gz gnunet-143251dbfe59ffe6e31b4497caa1312f9652df09.zip |
regex: fixed iterating over the initial states.
Diffstat (limited to 'src/regex/regex.c')
-rw-r--r-- | src/regex/regex.c | 99 |
1 files changed, 70 insertions, 29 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index 77c90418c..ceaeedf6d 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -1420,7 +1420,7 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) | |||
1420 | 1420 | ||
1421 | /** | 1421 | /** |
1422 | * Remove all dead states from the DFA 'a'. Dead states are those states that do | 1422 | * Remove all dead states from the DFA 'a'. Dead states are those states that do |
1423 | * not transition to any other state but themselfes. | 1423 | * not transition to any other state but themselves. |
1424 | * | 1424 | * |
1425 | * @param a DFA automaton | 1425 | * @param a DFA automaton |
1426 | */ | 1426 | */ |
@@ -2522,68 +2522,73 @@ GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key) | |||
2522 | GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO; | 2522 | GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO; |
2523 | } | 2523 | } |
2524 | 2524 | ||
2525 | |||
2525 | /** | 2526 | /** |
2526 | * Recursive helper function for iterate_initial_edges. Will call iterator | 2527 | * Recursive helper function for iterate_initial_edges. Will call iterator |
2527 | * function for each initial state. | 2528 | * function for each initial state. |
2528 | * | 2529 | * |
2530 | * @param min_len minimum length of the path in the graph. | ||
2529 | * @param max_len maximum length of the path in the graph. | 2531 | * @param max_len maximum length of the path in the graph. |
2530 | * @param cur_len current length of the path already traversed. | 2532 | * @param cur_len current length of the path already traversed. |
2531 | * @param consumed_string string consumed by traversing the graph till this state. | 2533 | * @param consumed_string string consumed by traversing the graph till this state. |
2532 | * @param next_state next state in the graph that is reachable with 'label' transition. | 2534 | * @param state current state of the automaton. |
2533 | * @param label label of the transition to the next state. | ||
2534 | * @param iterator iterator function called for each edge. | 2535 | * @param iterator iterator function called for each edge. |
2535 | * @param iterator_cls closure for the iterator function. | 2536 | * @param iterator_cls closure for the iterator function. |
2536 | */ | 2537 | */ |
2537 | static void | 2538 | static void |
2538 | iterate_initial_edge (const unsigned int max_len, unsigned int cur_len, | 2539 | iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, |
2539 | char *consumed_string, | 2540 | unsigned int cur_len, char *consumed_string, |
2540 | struct GNUNET_REGEX_State *next_state, const char label, | 2541 | struct GNUNET_REGEX_State *state, |
2541 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) | 2542 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) |
2542 | { | 2543 | { |
2544 | unsigned int i; | ||
2545 | char label[2]; | ||
2543 | char *temp; | 2546 | char *temp; |
2544 | struct GNUNET_REGEX_Transition *t; | 2547 | struct GNUNET_REGEX_Transition *t; |
2545 | struct GNUNET_REGEX_Edge edge; | 2548 | unsigned int num_edges = state->transition_count; |
2549 | struct GNUNET_REGEX_Edge edges[num_edges]; | ||
2546 | struct GNUNET_HashCode hash; | 2550 | struct GNUNET_HashCode hash; |
2547 | size_t constr_len; | ||
2548 | |||
2549 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
2550 | "max_len: %u, cur_len: %u, consumed_string: %s\n", max_len, | ||
2551 | cur_len, consumed_string); | ||
2552 | 2551 | ||
2553 | if (max_len == cur_len) | 2552 | if (cur_len > min_len && NULL != consumed_string && cur_len <= max_len) |
2554 | { | 2553 | { |
2555 | constr_len = strlen (consumed_string); | 2554 | for (i = 0, t = state->transitions_head; NULL != t; t = t->next, i++) |
2556 | GNUNET_CRYPTO_hash (consumed_string, constr_len - 1, &hash); | 2555 | { |
2557 | GNUNET_asprintf (&temp, "%c", label); | 2556 | label[0] = t->label; |
2558 | edge.label = temp; | 2557 | label[1] = '\0'; |
2559 | edge.destination = next_state->hash; | 2558 | edges[i].label = label; |
2560 | consumed_string[constr_len - 1] = '\0'; | 2559 | edges[i].destination = t->to_state->hash; |
2561 | iterator (iterator_cls, &hash, consumed_string, 0, 1, &edge); | 2560 | } |
2562 | GNUNET_free (temp); | ||
2563 | 2561 | ||
2564 | return; | 2562 | GNUNET_CRYPTO_hash (consumed_string, strlen (consumed_string), &hash); |
2563 | iterator (iterator_cls, &hash, consumed_string, state->accepting, num_edges, | ||
2564 | edges); | ||
2565 | } | 2565 | } |
2566 | else if (cur_len <= max_len) | 2566 | |
2567 | if (cur_len < max_len) | ||
2567 | { | 2568 | { |
2568 | cur_len++; | 2569 | cur_len++; |
2569 | for (t = next_state->transitions_head; NULL != t; t = t->next) | 2570 | for (t = state->transitions_head; NULL != t; t = t->next) |
2570 | { | 2571 | { |
2571 | if (NULL != consumed_string) | 2572 | if (NULL != consumed_string) |
2572 | GNUNET_asprintf (&temp, "%s%c", consumed_string, t->label); | 2573 | GNUNET_asprintf (&temp, "%s%c", consumed_string, t->label); |
2573 | else | 2574 | else |
2574 | GNUNET_asprintf (&temp, "%c", t->label); | 2575 | GNUNET_asprintf (&temp, "%c", t->label); |
2575 | 2576 | ||
2576 | iterate_initial_edge (max_len, cur_len, temp, t->to_state, t->label, | 2577 | iterate_initial_edge (min_len, max_len, cur_len, temp, t->to_state, |
2577 | iterator, iterator_cls); | 2578 | iterator, iterator_cls); |
2578 | GNUNET_free (temp); | 2579 | GNUNET_free (temp); |
2579 | } | 2580 | } |
2580 | } | 2581 | } |
2581 | } | 2582 | } |
2582 | 2583 | ||
2584 | |||
2583 | /** | 2585 | /** |
2584 | * Iterate over all initial edges that aren't actually part of the automaton. | 2586 | * Iterate over all initial edges that aren't actually part of the automaton. |
2585 | * This is needed to find the initial states returned by | 2587 | * This is needed to find the initial states returned by |
2586 | * GNUNET_REGEX_get_first_key. | 2588 | * GNUNET_REGEX_get_first_key. Iteration will start at the first branch state (a |
2589 | * state that has more than one outgoing edge, can be the first state), because | ||
2590 | * all previous states will have the same proof and be iterated over in | ||
2591 | * iterate_all_edges. | ||
2587 | * | 2592 | * |
2588 | * @param a the automaton for which the initial states should be computed. | 2593 | * @param a the automaton for which the initial states should be computed. |
2589 | * @param initial_len length of the initial state string. | 2594 | * @param initial_len length of the initial state string. |
@@ -2595,8 +2600,42 @@ iterate_initial_edges (struct GNUNET_REGEX_Automaton *a, | |||
2595 | const unsigned int initial_len, | 2600 | const unsigned int initial_len, |
2596 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) | 2601 | GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) |
2597 | { | 2602 | { |
2598 | iterate_initial_edge (initial_len + 1, 0, NULL, a->start, 0, iterator, | 2603 | char *consumed_string; |
2599 | iterator_cls); | 2604 | char *temp; |
2605 | struct GNUNET_REGEX_State *s; | ||
2606 | unsigned int cur_len; | ||
2607 | |||
2608 | if (1 > initial_len) | ||
2609 | return; | ||
2610 | |||
2611 | consumed_string = NULL; | ||
2612 | s = a->start; | ||
2613 | cur_len = 0; | ||
2614 | |||
2615 | if (1 == s->transition_count) | ||
2616 | { | ||
2617 | do | ||
2618 | { | ||
2619 | if (NULL != consumed_string) | ||
2620 | { | ||
2621 | temp = consumed_string; | ||
2622 | GNUNET_asprintf (&consumed_string, "%s%c", consumed_string, | ||
2623 | s->transitions_head->label); | ||
2624 | GNUNET_free (temp); | ||
2625 | } | ||
2626 | else | ||
2627 | GNUNET_asprintf (&consumed_string, "%c", s->transitions_head->label); | ||
2628 | |||
2629 | s = s->transitions_head->to_state; | ||
2630 | cur_len++; | ||
2631 | } | ||
2632 | while (cur_len < initial_len && 1 == s->transition_count); | ||
2633 | } | ||
2634 | |||
2635 | iterate_initial_edge (cur_len, initial_len, cur_len, consumed_string, s, | ||
2636 | iterator, iterator_cls); | ||
2637 | |||
2638 | GNUNET_free_non_null (consumed_string); | ||
2600 | } | 2639 | } |
2601 | 2640 | ||
2602 | 2641 | ||
@@ -2622,7 +2661,9 @@ iterate_edge (struct GNUNET_REGEX_State *s, GNUNET_REGEX_KeyIterator iterator, | |||
2622 | 2661 | ||
2623 | num_edges = state_get_edges (s, edges); | 2662 | num_edges = state_get_edges (s, edges); |
2624 | 2663 | ||
2625 | iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges, edges); | 2664 | if (0 < strlen (s->proof) || s->accepting) |
2665 | iterator (iterator_cls, &s->hash, s->proof, s->accepting, num_edges, | ||
2666 | edges); | ||
2626 | 2667 | ||
2627 | for (t = s->transitions_head; NULL != t; t = t->next) | 2668 | for (t = s->transitions_head; NULL != t; t = t->next) |
2628 | iterate_edge (t->to_state, iterator, iterator_cls); | 2669 | iterate_edge (t->to_state, iterator, iterator_cls); |