diff options
author | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-27 09:58:39 +0000 |
---|---|---|
committer | Maximilian Szengel <gnunet@maxsz.de> | 2012-08-27 09:58:39 +0000 |
commit | d8f4240d4e37ef783723cb5190ffd378a4388b66 (patch) | |
tree | f2f41c65a945a73747281a6f0e0887e53269986d /src/regex | |
parent | 93292d53e8470b6e7302ccf1c86f7cb12535c7f1 (diff) | |
download | gnunet-d8f4240d4e37ef783723cb5190ffd378a4388b66.tar.gz gnunet-d8f4240d4e37ef783723cb5190ffd378a4388b66.zip |
Fixes
Diffstat (limited to 'src/regex')
-rw-r--r-- | src/regex/regex.c | 58 | ||||
-rw-r--r-- | src/regex/regex_internal.h | 54 |
2 files changed, 83 insertions, 29 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c index f8177305e..d9c776efd 100644 --- a/src/regex/regex.c +++ b/src/regex/regex.c | |||
@@ -36,34 +36,6 @@ | |||
36 | 36 | ||
37 | 37 | ||
38 | /** | 38 | /** |
39 | * Context that contains an id counter for states and transitions as well as a | ||
40 | * DLL of automatons used as a stack for NFA construction. | ||
41 | */ | ||
42 | struct GNUNET_REGEX_Context | ||
43 | { | ||
44 | /** | ||
45 | * Unique state id. | ||
46 | */ | ||
47 | unsigned int state_id; | ||
48 | |||
49 | /** | ||
50 | * Unique transition id. | ||
51 | */ | ||
52 | unsigned int transition_id; | ||
53 | |||
54 | /** | ||
55 | * DLL of GNUNET_REGEX_Automaton's used as a stack. | ||
56 | */ | ||
57 | struct GNUNET_REGEX_Automaton *stack_head; | ||
58 | |||
59 | /** | ||
60 | * DLL of GNUNET_REGEX_Automaton's used as a stack. | ||
61 | */ | ||
62 | struct GNUNET_REGEX_Automaton *stack_tail; | ||
63 | }; | ||
64 | |||
65 | |||
66 | /** | ||
67 | * Set of states. | 39 | * Set of states. |
68 | */ | 40 | */ |
69 | struct GNUNET_REGEX_StateSet | 41 | struct GNUNET_REGEX_StateSet |
@@ -770,9 +742,14 @@ GNUNET_REGEX_add_multi_strides_to_dfa (struct GNUNET_REGEX_Context *regex_ctx, | |||
770 | struct GNUNET_REGEX_Transition *t; | 742 | struct GNUNET_REGEX_Transition *t; |
771 | struct GNUNET_REGEX_Transition *t_next; | 743 | struct GNUNET_REGEX_Transition *t_next; |
772 | 744 | ||
745 | if (1 > stride_len) | ||
746 | return; | ||
747 | |||
748 | // Compute the new transitions. | ||
773 | GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, | 749 | GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, |
774 | &add_multi_strides_to_dfa, &ctx); | 750 | &add_multi_strides_to_dfa, &ctx); |
775 | 751 | ||
752 | // Add all the new transitions to the automaton. | ||
776 | for (t = ctx.transitions_head; NULL != t; t = t_next) | 753 | for (t = ctx.transitions_head; NULL != t; t = t_next) |
777 | { | 754 | { |
778 | t_next = t->next; | 755 | t_next = t->next; |
@@ -2700,6 +2677,31 @@ GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a) | |||
2700 | 2677 | ||
2701 | 2678 | ||
2702 | /** | 2679 | /** |
2680 | * Get the number of transitions that are contained in the given automaton. | ||
2681 | * | ||
2682 | * @param a automaton for which the number of transitions should be returned. | ||
2683 | * | ||
2684 | * @return number of transitions in the given automaton. | ||
2685 | */ | ||
2686 | unsigned int | ||
2687 | GNUNET_REGEX_get_transition_count (struct GNUNET_REGEX_Automaton *a) | ||
2688 | { | ||
2689 | unsigned int t_count; | ||
2690 | struct GNUNET_REGEX_State *s; | ||
2691 | |||
2692 | if (NULL == a) | ||
2693 | return 0; | ||
2694 | |||
2695 | for (t_count = 0, s = a->states_head; NULL != s; s = s->next) | ||
2696 | { | ||
2697 | t_count += s->transition_count; | ||
2698 | } | ||
2699 | |||
2700 | return t_count; | ||
2701 | } | ||
2702 | |||
2703 | |||
2704 | /** | ||
2703 | * Get the first key for the given 'input_string'. This hashes the first x bits | 2705 | * Get the first key for the given 'input_string'. This hashes the first x bits |
2704 | * of the 'input_string'. | 2706 | * of the 'input_string'. |
2705 | * | 2707 | * |
diff --git a/src/regex/regex_internal.h b/src/regex/regex_internal.h index 20e81d93c..c132f2e23 100644 --- a/src/regex/regex_internal.h +++ b/src/regex/regex_internal.h | |||
@@ -315,13 +315,65 @@ GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, | |||
315 | * | 315 | * |
316 | * @param a automaton for which the canonical regex should be returned. | 316 | * @param a automaton for which the canonical regex should be returned. |
317 | * | 317 | * |
318 | * @return | 318 | * @return canonical regex string. |
319 | */ | 319 | */ |
320 | const char * | 320 | const char * |
321 | GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a); | 321 | GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a); |
322 | 322 | ||
323 | 323 | ||
324 | /** | 324 | /** |
325 | * Get the number of transitions that are contained in the given automaton. | ||
326 | * | ||
327 | * @param a automaton for which the number of transitions should be returned. | ||
328 | * | ||
329 | * @return number of transitions in the given automaton. | ||
330 | */ | ||
331 | unsigned int | ||
332 | GNUNET_REGEX_get_transition_count (struct GNUNET_REGEX_Automaton *a); | ||
333 | |||
334 | |||
335 | /** | ||
336 | * Context that contains an id counter for states and transitions as well as a | ||
337 | * DLL of automatons used as a stack for NFA construction. | ||
338 | */ | ||
339 | struct GNUNET_REGEX_Context | ||
340 | { | ||
341 | /** | ||
342 | * Unique state id. | ||
343 | */ | ||
344 | unsigned int state_id; | ||
345 | |||
346 | /** | ||
347 | * Unique transition id. | ||
348 | */ | ||
349 | unsigned int transition_id; | ||
350 | |||
351 | /** | ||
352 | * DLL of GNUNET_REGEX_Automaton's used as a stack. | ||
353 | */ | ||
354 | struct GNUNET_REGEX_Automaton *stack_head; | ||
355 | |||
356 | /** | ||
357 | * DLL of GNUNET_REGEX_Automaton's used as a stack. | ||
358 | */ | ||
359 | struct GNUNET_REGEX_Automaton *stack_tail; | ||
360 | }; | ||
361 | |||
362 | |||
363 | /** | ||
364 | * Adds multi-strided transitions to the given 'dfa'. | ||
365 | * | ||
366 | * @param regex_ctx regex context needed to add transitions to the automaton. | ||
367 | * @param dfa DFA to which the multi strided transitions should be added. | ||
368 | * @param stride_len length of the strides. | ||
369 | */ | ||
370 | void | ||
371 | GNUNET_REGEX_add_multi_strides_to_dfa (struct GNUNET_REGEX_Context *regex_ctx, | ||
372 | struct GNUNET_REGEX_Automaton *dfa, | ||
373 | const unsigned int stride_len); | ||
374 | |||
375 | |||
376 | /** | ||
325 | * Generate a (pseudo) random regular expression of length 'rx_length', as well | 377 | * Generate a (pseudo) random regular expression of length 'rx_length', as well |
326 | * as a (optional) string that will be matched by the generated regex. The | 378 | * as a (optional) string that will be matched by the generated regex. The |
327 | * returned regex needs to be freed. | 379 | * returned regex needs to be freed. |