aboutsummaryrefslogtreecommitdiff
path: root/src/regex/regex.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/regex/regex.c')
-rw-r--r--src/regex/regex.c571
1 files changed, 231 insertions, 340 deletions
diff --git a/src/regex/regex.c b/src/regex/regex.c
index 711e5458b..ecb3044e3 100644
--- a/src/regex/regex.c
+++ b/src/regex/regex.c
@@ -24,11 +24,12 @@
24 * @author Maximilian Szengel 24 * @author Maximilian Szengel
25 */ 25 */
26#include "platform.h" 26#include "platform.h"
27#include "gnunet_container_lib.h" 27#include "gnunet_util_lib.h"
28#include "gnunet_crypto_lib.h" 28#include "gnunet_regex_service.h"
29#include "gnunet_regex_lib.h" 29#include "regex_internal_lib.h"
30#include "regex_internal.h" 30#include "regex_internal.h"
31 31
32
32/** 33/**
33 * Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA 34 * Set this to GNUNET_YES to enable state naming. Used to debug NFA->DFA
34 * creation. Disabled by default for better performance. 35 * creation. Disabled by default for better performance.
@@ -38,17 +39,17 @@
38/** 39/**
39 * Set of states using MDLL API. 40 * Set of states using MDLL API.
40 */ 41 */
41struct GNUNET_REGEX_StateSet_MDLL 42struct REGEX_ITERNAL_StateSet_MDLL
42{ 43{
43 /** 44 /**
44 * MDLL of states. 45 * MDLL of states.
45 */ 46 */
46 struct GNUNET_REGEX_State *head; 47 struct REGEX_ITERNAL_State *head;
47 48
48 /** 49 /**
49 * MDLL of states. 50 * MDLL of states.
50 */ 51 */
51 struct GNUNET_REGEX_State *tail; 52 struct REGEX_ITERNAL_State *tail;
52 53
53 /** 54 /**
54 * Length of the MDLL. 55 * Length of the MDLL.
@@ -64,8 +65,8 @@ struct GNUNET_REGEX_StateSet_MDLL
64 * @param state state to be appended 65 * @param state state to be appended
65 */ 66 */
66static void 67static void
67state_set_append (struct GNUNET_REGEX_StateSet *set, 68state_set_append (struct REGEX_ITERNAL_StateSet *set,
68 struct GNUNET_REGEX_State *state) 69 struct REGEX_ITERNAL_State *state)
69{ 70{
70 if (set->off == set->size) 71 if (set->off == set->size)
71 GNUNET_array_grow (set->states, set->size, set->size * 2 + 4); 72 GNUNET_array_grow (set->states, set->size, set->size * 2 + 4);
@@ -103,12 +104,12 @@ nullstrcmp (const char *str1, const char *str2)
103 * @param to_state state to where the transition should point to 104 * @param to_state state to where the transition should point to
104 */ 105 */
105static void 106static void
106state_add_transition (struct GNUNET_REGEX_Context *ctx, 107state_add_transition (struct REGEX_ITERNAL_Context *ctx,
107 struct GNUNET_REGEX_State *from_state, const char *label, 108 struct REGEX_ITERNAL_State *from_state, const char *label,
108 struct GNUNET_REGEX_State *to_state) 109 struct REGEX_ITERNAL_State *to_state)
109{ 110{
110 struct GNUNET_REGEX_Transition *t; 111 struct REGEX_ITERNAL_Transition *t;
111 struct GNUNET_REGEX_Transition *oth; 112 struct REGEX_ITERNAL_Transition *oth;
112 113
113 if (NULL == from_state) 114 if (NULL == from_state)
114 { 115 {
@@ -131,7 +132,7 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx,
131 break; 132 break;
132 } 133 }
133 134
134 t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); 135 t = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Transition));
135 if (NULL != ctx) 136 if (NULL != ctx)
136 t->id = ctx->transition_id++; 137 t->id = ctx->transition_id++;
137 if (NULL != label) 138 if (NULL != label)
@@ -155,8 +156,8 @@ state_add_transition (struct GNUNET_REGEX_Context *ctx,
155 * @param transition transition that should be removed from state 'state'. 156 * @param transition transition that should be removed from state 'state'.
156 */ 157 */
157static void 158static void
158state_remove_transition (struct GNUNET_REGEX_State *state, 159state_remove_transition (struct REGEX_ITERNAL_State *state,
159 struct GNUNET_REGEX_Transition *transition) 160 struct REGEX_ITERNAL_Transition *transition)
160{ 161{
161 if (NULL == state || NULL == transition) 162 if (NULL == state || NULL == transition)
162 return; 163 return;
@@ -187,8 +188,8 @@ state_remove_transition (struct GNUNET_REGEX_State *state,
187static int 188static int
188state_compare (const void *a, const void *b) 189state_compare (const void *a, const void *b)
189{ 190{
190 struct GNUNET_REGEX_State **s1 = (struct GNUNET_REGEX_State **) a; 191 struct REGEX_ITERNAL_State **s1 = (struct REGEX_ITERNAL_State **) a;
191 struct GNUNET_REGEX_State **s2 = (struct GNUNET_REGEX_State **) b; 192 struct REGEX_ITERNAL_State **s2 = (struct REGEX_ITERNAL_State **) b;
192 193
193 return (*s1)->id - (*s2)->id; 194 return (*s1)->id - (*s2)->id;
194} 195}
@@ -204,9 +205,9 @@ state_compare (const void *a, const void *b)
204 * @return number of edges. 205 * @return number of edges.
205 */ 206 */
206static unsigned int 207static unsigned int
207state_get_edges (struct GNUNET_REGEX_State *s, struct GNUNET_REGEX_Edge *edges) 208state_get_edges (struct REGEX_ITERNAL_State *s, struct REGEX_ITERNAL_Edge *edges)
208{ 209{
209 struct GNUNET_REGEX_Transition *t; 210 struct REGEX_ITERNAL_Transition *t;
210 unsigned int count; 211 unsigned int count;
211 212
212 if (NULL == s) 213 if (NULL == s)
@@ -236,8 +237,8 @@ state_get_edges (struct GNUNET_REGEX_State *s, struct GNUNET_REGEX_Edge *edges)
236 * @return 0 if the sets are equal, otherwise non-zero 237 * @return 0 if the sets are equal, otherwise non-zero
237 */ 238 */
238static int 239static int
239state_set_compare (struct GNUNET_REGEX_StateSet *sset1, 240state_set_compare (struct REGEX_ITERNAL_StateSet *sset1,
240 struct GNUNET_REGEX_StateSet *sset2) 241 struct REGEX_ITERNAL_StateSet *sset2)
241{ 242{
242 int result; 243 int result;
243 unsigned int i; 244 unsigned int i;
@@ -263,7 +264,7 @@ state_set_compare (struct GNUNET_REGEX_StateSet *sset1,
263 * @param set set to be cleared 264 * @param set set to be cleared
264 */ 265 */
265static void 266static void
266state_set_clear (struct GNUNET_REGEX_StateSet *set) 267state_set_clear (struct REGEX_ITERNAL_StateSet *set)
267{ 268{
268 GNUNET_array_grow (set->states, set->size, 0); 269 GNUNET_array_grow (set->states, set->size, 0);
269 set->off = 0; 270 set->off = 0;
@@ -277,7 +278,7 @@ state_set_clear (struct GNUNET_REGEX_StateSet *set)
277 * @param a automaton to be cleared 278 * @param a automaton to be cleared
278 */ 279 */
279static void 280static void
280automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a) 281automaton_fragment_clear (struct REGEX_ITERNAL_Automaton *a)
281{ 282{
282 if (NULL == a) 283 if (NULL == a)
283 return; 284 return;
@@ -297,10 +298,10 @@ automaton_fragment_clear (struct GNUNET_REGEX_Automaton *a)
297 * @param s state that should be destroyed 298 * @param s state that should be destroyed
298 */ 299 */
299static void 300static void
300automaton_destroy_state (struct GNUNET_REGEX_State *s) 301automaton_destroy_state (struct REGEX_ITERNAL_State *s)
301{ 302{
302 struct GNUNET_REGEX_Transition *t; 303 struct REGEX_ITERNAL_Transition *t;
303 struct GNUNET_REGEX_Transition *next_t; 304 struct REGEX_ITERNAL_Transition *next_t;
304 305
305 if (NULL == s) 306 if (NULL == s)
306 return; 307 return;
@@ -327,12 +328,12 @@ automaton_destroy_state (struct GNUNET_REGEX_State *s)
327 * @param s state to remove 328 * @param s state to remove
328 */ 329 */
329static void 330static void
330automaton_remove_state (struct GNUNET_REGEX_Automaton *a, 331automaton_remove_state (struct REGEX_ITERNAL_Automaton *a,
331 struct GNUNET_REGEX_State *s) 332 struct REGEX_ITERNAL_State *s)
332{ 333{
333 struct GNUNET_REGEX_State *s_check; 334 struct REGEX_ITERNAL_State *s_check;
334 struct GNUNET_REGEX_Transition *t_check; 335 struct REGEX_ITERNAL_Transition *t_check;
335 struct GNUNET_REGEX_Transition *t_check_next; 336 struct REGEX_ITERNAL_Transition *t_check_next;
336 337
337 if (NULL == a || NULL == s) 338 if (NULL == a || NULL == s)
338 return; 339 return;
@@ -367,15 +368,15 @@ automaton_remove_state (struct GNUNET_REGEX_Automaton *a,
367 * @param s2 second state, will be destroyed 368 * @param s2 second state, will be destroyed
368 */ 369 */
369static void 370static void
370automaton_merge_states (struct GNUNET_REGEX_Context *ctx, 371automaton_merge_states (struct REGEX_ITERNAL_Context *ctx,
371 struct GNUNET_REGEX_Automaton *a, 372 struct REGEX_ITERNAL_Automaton *a,
372 struct GNUNET_REGEX_State *s1, 373 struct REGEX_ITERNAL_State *s1,
373 struct GNUNET_REGEX_State *s2) 374 struct REGEX_ITERNAL_State *s2)
374{ 375{
375 struct GNUNET_REGEX_State *s_check; 376 struct REGEX_ITERNAL_State *s_check;
376 struct GNUNET_REGEX_Transition *t_check; 377 struct REGEX_ITERNAL_Transition *t_check;
377 struct GNUNET_REGEX_Transition *t; 378 struct REGEX_ITERNAL_Transition *t;
378 struct GNUNET_REGEX_Transition *t_next; 379 struct REGEX_ITERNAL_Transition *t_next;
379 int is_dup; 380 int is_dup;
380 381
381 if (s1 == s2) 382 if (s1 == s2)
@@ -436,8 +437,8 @@ automaton_merge_states (struct GNUNET_REGEX_Context *ctx,
436 * @param s state that should be added 437 * @param s state that should be added
437 */ 438 */
438static void 439static void
439automaton_add_state (struct GNUNET_REGEX_Automaton *a, 440automaton_add_state (struct REGEX_ITERNAL_Automaton *a,
440 struct GNUNET_REGEX_State *s) 441 struct REGEX_ITERNAL_State *s)
441{ 442{
442 GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s); 443 GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
443 a->state_count++; 444 a->state_count++;
@@ -459,12 +460,12 @@ automaton_add_state (struct GNUNET_REGEX_Automaton *a,
459 * @param action_cls closure for action. 460 * @param action_cls closure for action.
460 */ 461 */
461static void 462static void
462automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks, 463automaton_state_traverse (struct REGEX_ITERNAL_State *s, int *marks,
463 unsigned int *count, 464 unsigned int *count,
464 GNUNET_REGEX_traverse_check check, void *check_cls, 465 REGEX_ITERNAL_traverse_check check, void *check_cls,
465 GNUNET_REGEX_traverse_action action, void *action_cls) 466 REGEX_ITERNAL_traverse_action action, void *action_cls)
466{ 467{
467 struct GNUNET_REGEX_Transition *t; 468 struct REGEX_ITERNAL_Transition *t;
468 469
469 if (GNUNET_YES == marks[s->traversal_id]) 470 if (GNUNET_YES == marks[s->traversal_id])
470 return; 471 return;
@@ -502,15 +503,15 @@ automaton_state_traverse (struct GNUNET_REGEX_State *s, int *marks,
502 * @param action_cls closure for action 503 * @param action_cls closure for action
503 */ 504 */
504void 505void
505GNUNET_REGEX_automaton_traverse (const struct GNUNET_REGEX_Automaton *a, 506REGEX_ITERNAL_automaton_traverse (const struct REGEX_ITERNAL_Automaton *a,
506 struct GNUNET_REGEX_State *start, 507 struct REGEX_ITERNAL_State *start,
507 GNUNET_REGEX_traverse_check check, 508 REGEX_ITERNAL_traverse_check check,
508 void *check_cls, 509 void *check_cls,
509 GNUNET_REGEX_traverse_action action, 510 REGEX_ITERNAL_traverse_action action,
510 void *action_cls) 511 void *action_cls)
511{ 512{
512 unsigned int count; 513 unsigned int count;
513 struct GNUNET_REGEX_State *s; 514 struct REGEX_ITERNAL_State *s;
514 515
515 if (NULL == a || 0 == a->state_count) 516 if (NULL == a || 0 == a->state_count)
516 return; 517 return;
@@ -1155,7 +1156,7 @@ sb_strkcmp (const struct StringBuffer *str1,
1155 1156
1156 1157
1157/** 1158/**
1158 * Helper function used as 'action' in 'GNUNET_REGEX_automaton_traverse' 1159 * Helper function used as 'action' in 'REGEX_ITERNAL_automaton_traverse'
1159 * function to create the depth-first numbering of the states. 1160 * function to create the depth-first numbering of the states.
1160 * 1161 *
1161 * @param cls states array. 1162 * @param cls states array.
@@ -1164,9 +1165,9 @@ sb_strkcmp (const struct StringBuffer *str1,
1164 */ 1165 */
1165static void 1166static void
1166number_states (void *cls, const unsigned int count, 1167number_states (void *cls, const unsigned int count,
1167 struct GNUNET_REGEX_State *s) 1168 struct REGEX_ITERNAL_State *s)
1168{ 1169{
1169 struct GNUNET_REGEX_State **states = cls; 1170 struct REGEX_ITERNAL_State **states = cls;
1170 1171
1171 s->dfs_id = count; 1172 s->dfs_id = count;
1172 if (NULL != states) 1173 if (NULL != states)
@@ -1603,16 +1604,16 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
1603 * @param a automaton for which to assign proofs and hashes, must not be NULL 1604 * @param a automaton for which to assign proofs and hashes, must not be NULL
1604 */ 1605 */
1605static int 1606static int
1606automaton_create_proofs (struct GNUNET_REGEX_Automaton *a) 1607automaton_create_proofs (struct REGEX_ITERNAL_Automaton *a)
1607{ 1608{
1608 unsigned int n = a->state_count; 1609 unsigned int n = a->state_count;
1609 struct GNUNET_REGEX_State *states[n]; 1610 struct REGEX_ITERNAL_State *states[n];
1610 struct StringBuffer *R_last; 1611 struct StringBuffer *R_last;
1611 struct StringBuffer *R_cur; 1612 struct StringBuffer *R_cur;
1612 struct StringBuffer R_cur_r; 1613 struct StringBuffer R_cur_r;
1613 struct StringBuffer R_cur_l; 1614 struct StringBuffer R_cur_l;
1614 struct StringBuffer *R_swap; 1615 struct StringBuffer *R_swap;
1615 struct GNUNET_REGEX_Transition *t; 1616 struct REGEX_ITERNAL_Transition *t;
1616 struct StringBuffer complete_regex; 1617 struct StringBuffer complete_regex;
1617 unsigned int i; 1618 unsigned int i;
1618 unsigned int j; 1619 unsigned int j;
@@ -1630,7 +1631,7 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a)
1630 } 1631 }
1631 1632
1632 /* create depth-first numbering of the states, initializes 'state' */ 1633 /* create depth-first numbering of the states, initializes 'state' */
1633 GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &number_states, 1634 REGEX_ITERNAL_automaton_traverse (a, a->start, NULL, NULL, &number_states,
1634 states); 1635 states);
1635 1636
1636 for (i = 0; i < n; i++) 1637 for (i = 0; i < n; i++)
@@ -1762,18 +1763,18 @@ automaton_create_proofs (struct GNUNET_REGEX_Automaton *a)
1762 * 1763 *
1763 * @return new DFA state 1764 * @return new DFA state
1764 */ 1765 */
1765static struct GNUNET_REGEX_State * 1766static struct REGEX_ITERNAL_State *
1766dfa_state_create (struct GNUNET_REGEX_Context *ctx, 1767dfa_state_create (struct REGEX_ITERNAL_Context *ctx,
1767 struct GNUNET_REGEX_StateSet *nfa_states) 1768 struct REGEX_ITERNAL_StateSet *nfa_states)
1768{ 1769{
1769 struct GNUNET_REGEX_State *s; 1770 struct REGEX_ITERNAL_State *s;
1770 char *pos; 1771 char *pos;
1771 size_t len; 1772 size_t len;
1772 struct GNUNET_REGEX_State *cstate; 1773 struct REGEX_ITERNAL_State *cstate;
1773 struct GNUNET_REGEX_Transition *ctran; 1774 struct REGEX_ITERNAL_Transition *ctran;
1774 unsigned int i; 1775 unsigned int i;
1775 1776
1776 s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State)); 1777 s = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_State));
1777 s->id = ctx->state_id++; 1778 s->id = ctx->state_id++;
1778 s->index = -1; 1779 s->index = -1;
1779 s->lowlink = -1; 1780 s->lowlink = -1;
@@ -1815,7 +1816,7 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx,
1815 pos[-1] = '}'; 1816 pos[-1] = '}';
1816 s->name = GNUNET_realloc (s->name, strlen (s->name) + 1); 1817 s->name = GNUNET_realloc (s->name, strlen (s->name) + 1);
1817 1818
1818 memset (nfa_states, 0, sizeof (struct GNUNET_REGEX_StateSet)); 1819 memset (nfa_states, 0, sizeof (struct REGEX_ITERNAL_StateSet));
1819 return s; 1820 return s;
1820} 1821}
1821 1822
@@ -1834,10 +1835,10 @@ dfa_state_create (struct GNUNET_REGEX_Context *ctx,
1834 * @return length of the substring comsumed from 'str' 1835 * @return length of the substring comsumed from 'str'
1835 */ 1836 */
1836static unsigned int 1837static unsigned int
1837dfa_move (struct GNUNET_REGEX_State **s, const char *str) 1838dfa_move (struct REGEX_ITERNAL_State **s, const char *str)
1838{ 1839{
1839 struct GNUNET_REGEX_Transition *t; 1840 struct REGEX_ITERNAL_Transition *t;
1840 struct GNUNET_REGEX_State *new_s; 1841 struct REGEX_ITERNAL_State *new_s;
1841 unsigned int len; 1842 unsigned int len;
1842 unsigned int max_len; 1843 unsigned int max_len;
1843 1844
@@ -1875,7 +1876,7 @@ dfa_move (struct GNUNET_REGEX_State **s, const char *str)
1875 * @param s state where the marked attribute will be set to GNUNET_YES. 1876 * @param s state where the marked attribute will be set to GNUNET_YES.
1876 */ 1877 */
1877static void 1878static void
1878mark_states (void *cls, const unsigned int count, struct GNUNET_REGEX_State *s) 1879mark_states (void *cls, const unsigned int count, struct REGEX_ITERNAL_State *s)
1879{ 1880{
1880 s->marked = GNUNET_YES; 1881 s->marked = GNUNET_YES;
1881} 1882}
@@ -1888,17 +1889,17 @@ mark_states (void *cls, const unsigned int count, struct GNUNET_REGEX_State *s)
1888 * @param a DFA automaton 1889 * @param a DFA automaton
1889 */ 1890 */
1890static void 1891static void
1891dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a) 1892dfa_remove_unreachable_states (struct REGEX_ITERNAL_Automaton *a)
1892{ 1893{
1893 struct GNUNET_REGEX_State *s; 1894 struct REGEX_ITERNAL_State *s;
1894 struct GNUNET_REGEX_State *s_next; 1895 struct REGEX_ITERNAL_State *s_next;
1895 1896
1896 /* 1. unmark all states */ 1897 /* 1. unmark all states */
1897 for (s = a->states_head; NULL != s; s = s->next) 1898 for (s = a->states_head; NULL != s; s = s->next)
1898 s->marked = GNUNET_NO; 1899 s->marked = GNUNET_NO;
1899 1900
1900 /* 2. traverse dfa from start state and mark all visited states */ 1901 /* 2. traverse dfa from start state and mark all visited states */
1901 GNUNET_REGEX_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL); 1902 REGEX_ITERNAL_automaton_traverse (a, a->start, NULL, NULL, &mark_states, NULL);
1902 1903
1903 /* 3. delete all states that were not visited */ 1904 /* 3. delete all states that were not visited */
1904 for (s = a->states_head; NULL != s; s = s_next) 1905 for (s = a->states_head; NULL != s; s = s_next)
@@ -1917,11 +1918,11 @@ dfa_remove_unreachable_states (struct GNUNET_REGEX_Automaton *a)
1917 * @param a DFA automaton 1918 * @param a DFA automaton
1918 */ 1919 */
1919static void 1920static void
1920dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a) 1921dfa_remove_dead_states (struct REGEX_ITERNAL_Automaton *a)
1921{ 1922{
1922 struct GNUNET_REGEX_State *s; 1923 struct REGEX_ITERNAL_State *s;
1923 struct GNUNET_REGEX_State *s_next; 1924 struct REGEX_ITERNAL_State *s_next;
1924 struct GNUNET_REGEX_Transition *t; 1925 struct REGEX_ITERNAL_Transition *t;
1925 int dead; 1926 int dead;
1926 1927
1927 GNUNET_assert (DFA == a->type); 1928 GNUNET_assert (DFA == a->type);
@@ -1960,16 +1961,16 @@ dfa_remove_dead_states (struct GNUNET_REGEX_Automaton *a)
1960 * @return GNUNET_OK on success 1961 * @return GNUNET_OK on success
1961 */ 1962 */
1962static int 1963static int
1963dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx, 1964dfa_merge_nondistinguishable_states (struct REGEX_ITERNAL_Context *ctx,
1964 struct GNUNET_REGEX_Automaton *a) 1965 struct REGEX_ITERNAL_Automaton *a)
1965{ 1966{
1966 uint32_t *table; 1967 uint32_t *table;
1967 struct GNUNET_REGEX_State *s1; 1968 struct REGEX_ITERNAL_State *s1;
1968 struct GNUNET_REGEX_State *s2; 1969 struct REGEX_ITERNAL_State *s2;
1969 struct GNUNET_REGEX_Transition *t1; 1970 struct REGEX_ITERNAL_Transition *t1;
1970 struct GNUNET_REGEX_Transition *t2; 1971 struct REGEX_ITERNAL_Transition *t2;
1971 struct GNUNET_REGEX_State *s1_next; 1972 struct REGEX_ITERNAL_State *s1_next;
1972 struct GNUNET_REGEX_State *s2_next; 1973 struct REGEX_ITERNAL_State *s2_next;
1973 int change; 1974 int change;
1974 unsigned int num_equal_edges; 1975 unsigned int num_equal_edges;
1975 unsigned int i; 1976 unsigned int i;
@@ -2077,8 +2078,8 @@ dfa_merge_nondistinguishable_states (struct GNUNET_REGEX_Context *ctx,
2077 * @return GNUNET_OK on success 2078 * @return GNUNET_OK on success
2078 */ 2079 */
2079static int 2080static int
2080dfa_minimize (struct GNUNET_REGEX_Context *ctx, 2081dfa_minimize (struct REGEX_ITERNAL_Context *ctx,
2081 struct GNUNET_REGEX_Automaton *a) 2082 struct REGEX_ITERNAL_Automaton *a)
2082{ 2083{
2083 if (NULL == a) 2084 if (NULL == a)
2084 return GNUNET_SYSERR; 2085 return GNUNET_SYSERR;
@@ -2101,7 +2102,7 @@ dfa_minimize (struct GNUNET_REGEX_Context *ctx,
2101/** 2102/**
2102 * Context for adding strided transitions to a DFA. 2103 * Context for adding strided transitions to a DFA.
2103 */ 2104 */
2104struct GNUNET_REGEX_Strided_Context 2105struct REGEX_ITERNAL_Strided_Context
2105{ 2106{
2106 /** 2107 /**
2107 * Length of the strides. 2108 * Length of the strides.
@@ -2112,12 +2113,12 @@ struct GNUNET_REGEX_Strided_Context
2112 * Strided transitions DLL. New strided transitions will be stored in this DLL 2113 * Strided transitions DLL. New strided transitions will be stored in this DLL
2113 * and afterwards added to the DFA. 2114 * and afterwards added to the DFA.
2114 */ 2115 */
2115 struct GNUNET_REGEX_Transition *transitions_head; 2116 struct REGEX_ITERNAL_Transition *transitions_head;
2116 2117
2117 /** 2118 /**
2118 * Strided transitions DLL. 2119 * Strided transitions DLL.
2119 */ 2120 */
2120 struct GNUNET_REGEX_Transition *transitions_tail; 2121 struct REGEX_ITERNAL_Transition *transitions_tail;
2121}; 2122};
2122 2123
2123 2124
@@ -2133,16 +2134,16 @@ struct GNUNET_REGEX_Strided_Context
2133 */ 2134 */
2134void 2135void
2135dfa_add_multi_strides_helper (void *cls, const unsigned int depth, char *label, 2136dfa_add_multi_strides_helper (void *cls, const unsigned int depth, char *label,
2136 struct GNUNET_REGEX_State *start, 2137 struct REGEX_ITERNAL_State *start,
2137 struct GNUNET_REGEX_State *s) 2138 struct REGEX_ITERNAL_State *s)
2138{ 2139{
2139 struct GNUNET_REGEX_Strided_Context *ctx = cls; 2140 struct REGEX_ITERNAL_Strided_Context *ctx = cls;
2140 struct GNUNET_REGEX_Transition *t; 2141 struct REGEX_ITERNAL_Transition *t;
2141 char *new_label; 2142 char *new_label;
2142 2143
2143 if (depth == ctx->stride) 2144 if (depth == ctx->stride)
2144 { 2145 {
2145 t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); 2146 t = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Transition));
2146 t->label = GNUNET_strdup (label); 2147 t->label = GNUNET_strdup (label);
2147 t->to_state = s; 2148 t->to_state = s;
2148 t->from_state = start; 2149 t->from_state = start;
@@ -2183,7 +2184,7 @@ dfa_add_multi_strides_helper (void *cls, const unsigned int depth, char *label,
2183 */ 2184 */
2184void 2185void
2185dfa_add_multi_strides (void *cls, const unsigned int count, 2186dfa_add_multi_strides (void *cls, const unsigned int count,
2186 struct GNUNET_REGEX_State *s) 2187 struct REGEX_ITERNAL_State *s)
2187{ 2188{
2188 dfa_add_multi_strides_helper (cls, 0, NULL, s, s); 2189 dfa_add_multi_strides_helper (cls, 0, NULL, s, s);
2189} 2190}
@@ -2197,19 +2198,19 @@ dfa_add_multi_strides (void *cls, const unsigned int count,
2197 * @param stride_len length of the strides. 2198 * @param stride_len length of the strides.
2198 */ 2199 */
2199void 2200void
2200GNUNET_REGEX_dfa_add_multi_strides (struct GNUNET_REGEX_Context *regex_ctx, 2201REGEX_ITERNAL_dfa_add_multi_strides (struct REGEX_ITERNAL_Context *regex_ctx,
2201 struct GNUNET_REGEX_Automaton *dfa, 2202 struct REGEX_ITERNAL_Automaton *dfa,
2202 const unsigned int stride_len) 2203 const unsigned int stride_len)
2203{ 2204{
2204 struct GNUNET_REGEX_Strided_Context ctx = { stride_len, NULL, NULL }; 2205 struct REGEX_ITERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
2205 struct GNUNET_REGEX_Transition *t; 2206 struct REGEX_ITERNAL_Transition *t;
2206 struct GNUNET_REGEX_Transition *t_next; 2207 struct REGEX_ITERNAL_Transition *t_next;
2207 2208
2208 if (1 > stride_len || GNUNET_YES == dfa->is_multistrided) 2209 if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
2209 return; 2210 return;
2210 2211
2211 /* Compute the new transitions of given stride_len */ 2212 /* Compute the new transitions of given stride_len */
2212 GNUNET_REGEX_automaton_traverse (dfa, dfa->start, NULL, NULL, 2213 REGEX_ITERNAL_automaton_traverse (dfa, dfa->start, NULL, NULL,
2213 &dfa_add_multi_strides, &ctx); 2214 &dfa_add_multi_strides, &ctx);
2214 2215
2215 /* Add all the new transitions to the automaton. */ 2216 /* Add all the new transitions to the automaton. */
@@ -2240,14 +2241,14 @@ GNUNET_REGEX_dfa_add_multi_strides (struct GNUNET_REGEX_Context *regex_ctx,
2240 * @param transitions_tail transitions DLL. 2241 * @param transitions_tail transitions DLL.
2241 */ 2242 */
2242void 2243void
2243dfa_compress_paths_helper (struct GNUNET_REGEX_Automaton *dfa, 2244dfa_compress_paths_helper (struct REGEX_ITERNAL_Automaton *dfa,
2244 struct GNUNET_REGEX_State *start, 2245 struct REGEX_ITERNAL_State *start,
2245 struct GNUNET_REGEX_State *cur, char *label, 2246 struct REGEX_ITERNAL_State *cur, char *label,
2246 unsigned int max_len, 2247 unsigned int max_len,
2247 struct GNUNET_REGEX_Transition **transitions_head, 2248 struct REGEX_ITERNAL_Transition **transitions_head,
2248 struct GNUNET_REGEX_Transition **transitions_tail) 2249 struct REGEX_ITERNAL_Transition **transitions_tail)
2249{ 2250{
2250 struct GNUNET_REGEX_Transition *t; 2251 struct REGEX_ITERNAL_Transition *t;
2251 char *new_label; 2252 char *new_label;
2252 2253
2253 2254
@@ -2257,7 +2258,7 @@ dfa_compress_paths_helper (struct GNUNET_REGEX_Automaton *dfa,
2257 max_len == strlen (label)) || 2258 max_len == strlen (label)) ||
2258 (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label)))) 2259 (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen (label))))
2259 { 2260 {
2260 t = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Transition)); 2261 t = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Transition));
2261 t->label = GNUNET_strdup (label); 2262 t->label = GNUNET_strdup (label);
2262 t->to_state = cur; 2263 t->to_state = cur;
2263 t->from_state = start; 2264 t->from_state = start;
@@ -2305,15 +2306,15 @@ dfa_compress_paths_helper (struct GNUNET_REGEX_Automaton *dfa,
2305 * @param max_len maximal length of the compressed paths. 2306 * @param max_len maximal length of the compressed paths.
2306 */ 2307 */
2307static void 2308static void
2308dfa_compress_paths (struct GNUNET_REGEX_Context *regex_ctx, 2309dfa_compress_paths (struct REGEX_ITERNAL_Context *regex_ctx,
2309 struct GNUNET_REGEX_Automaton *dfa, unsigned int max_len) 2310 struct REGEX_ITERNAL_Automaton *dfa, unsigned int max_len)
2310{ 2311{
2311 struct GNUNET_REGEX_State *s; 2312 struct REGEX_ITERNAL_State *s;
2312 struct GNUNET_REGEX_State *s_next; 2313 struct REGEX_ITERNAL_State *s_next;
2313 struct GNUNET_REGEX_Transition *t; 2314 struct REGEX_ITERNAL_Transition *t;
2314 struct GNUNET_REGEX_Transition *t_next; 2315 struct REGEX_ITERNAL_Transition *t_next;
2315 struct GNUNET_REGEX_Transition *transitions_head = NULL; 2316 struct REGEX_ITERNAL_Transition *transitions_head = NULL;
2316 struct GNUNET_REGEX_Transition *transitions_tail = NULL; 2317 struct REGEX_ITERNAL_Transition *transitions_tail = NULL;
2317 2318
2318 if (NULL == dfa) 2319 if (NULL == dfa)
2319 return; 2320 return;
@@ -2368,13 +2369,13 @@ dfa_compress_paths (struct GNUNET_REGEX_Context *regex_ctx,
2368 * 2369 *
2369 * @return new NFA fragment 2370 * @return new NFA fragment
2370 */ 2371 */
2371static struct GNUNET_REGEX_Automaton * 2372static struct REGEX_ITERNAL_Automaton *
2372nfa_fragment_create (struct GNUNET_REGEX_State *start, 2373nfa_fragment_create (struct REGEX_ITERNAL_State *start,
2373 struct GNUNET_REGEX_State *end) 2374 struct REGEX_ITERNAL_State *end)
2374{ 2375{
2375 struct GNUNET_REGEX_Automaton *n; 2376 struct REGEX_ITERNAL_Automaton *n;
2376 2377
2377 n = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton)); 2378 n = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Automaton));
2378 2379
2379 n->type = NFA; 2380 n->type = NFA;
2380 n->start = NULL; 2381 n->start = NULL;
@@ -2404,11 +2405,11 @@ nfa_fragment_create (struct GNUNET_REGEX_State *start,
2404 * @param states_tail tail of the DLL of states 2405 * @param states_tail tail of the DLL of states
2405 */ 2406 */
2406static void 2407static void
2407nfa_add_states (struct GNUNET_REGEX_Automaton *n, 2408nfa_add_states (struct REGEX_ITERNAL_Automaton *n,
2408 struct GNUNET_REGEX_State *states_head, 2409 struct REGEX_ITERNAL_State *states_head,
2409 struct GNUNET_REGEX_State *states_tail) 2410 struct REGEX_ITERNAL_State *states_tail)
2410{ 2411{
2411 struct GNUNET_REGEX_State *s; 2412 struct REGEX_ITERNAL_State *s;
2412 2413
2413 if (NULL == n || NULL == states_head) 2414 if (NULL == n || NULL == states_head)
2414 { 2415 {
@@ -2442,12 +2443,12 @@ nfa_add_states (struct GNUNET_REGEX_Automaton *n,
2442 * 2443 *
2443 * @return new NFA state 2444 * @return new NFA state
2444 */ 2445 */
2445static struct GNUNET_REGEX_State * 2446static struct REGEX_ITERNAL_State *
2446nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting) 2447nfa_state_create (struct REGEX_ITERNAL_Context *ctx, int accepting)
2447{ 2448{
2448 struct GNUNET_REGEX_State *s; 2449 struct REGEX_ITERNAL_State *s;
2449 2450
2450 s = GNUNET_malloc (sizeof (struct GNUNET_REGEX_State)); 2451 s = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_State));
2451 s->id = ctx->state_id++; 2452 s->id = ctx->state_id++;
2452 s->accepting = accepting; 2453 s->accepting = accepting;
2453 s->marked = GNUNET_NO; 2454 s->marked = GNUNET_NO;
@@ -2472,18 +2473,18 @@ nfa_state_create (struct GNUNET_REGEX_Context *ctx, int accepting)
2472 * pass NULL for epsilon transition 2473 * pass NULL for epsilon transition
2473 */ 2474 */
2474static void 2475static void
2475nfa_closure_set_create (struct GNUNET_REGEX_StateSet *ret, 2476nfa_closure_set_create (struct REGEX_ITERNAL_StateSet *ret,
2476 struct GNUNET_REGEX_Automaton *nfa, 2477 struct REGEX_ITERNAL_Automaton *nfa,
2477 struct GNUNET_REGEX_StateSet *states, const char *label) 2478 struct REGEX_ITERNAL_StateSet *states, const char *label)
2478{ 2479{
2479 struct GNUNET_REGEX_State *s; 2480 struct REGEX_ITERNAL_State *s;
2480 unsigned int i; 2481 unsigned int i;
2481 struct GNUNET_REGEX_StateSet_MDLL cls_stack; 2482 struct REGEX_ITERNAL_StateSet_MDLL cls_stack;
2482 struct GNUNET_REGEX_State *clsstate; 2483 struct REGEX_ITERNAL_State *clsstate;
2483 struct GNUNET_REGEX_State *currentstate; 2484 struct REGEX_ITERNAL_State *currentstate;
2484 struct GNUNET_REGEX_Transition *ctran; 2485 struct REGEX_ITERNAL_Transition *ctran;
2485 2486
2486 memset (ret, 0, sizeof (struct GNUNET_REGEX_StateSet)); 2487 memset (ret, 0, sizeof (struct REGEX_ITERNAL_StateSet));
2487 if (NULL == states) 2488 if (NULL == states)
2488 return; 2489 return;
2489 2490
@@ -2527,7 +2528,7 @@ nfa_closure_set_create (struct GNUNET_REGEX_StateSet *ret,
2527 ret->states[i]->contained = 0; 2528 ret->states[i]->contained = 0;
2528 2529
2529 if (ret->off > 1) 2530 if (ret->off > 1)
2530 qsort (ret->states, ret->off, sizeof (struct GNUNET_REGEX_State *), 2531 qsort (ret->states, ret->off, sizeof (struct REGEX_ITERNAL_State *),
2531 &state_compare); 2532 &state_compare);
2532} 2533}
2533 2534
@@ -2538,11 +2539,11 @@ nfa_closure_set_create (struct GNUNET_REGEX_StateSet *ret,
2538 * @param ctx context 2539 * @param ctx context
2539 */ 2540 */
2540static void 2541static void
2541nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx) 2542nfa_add_concatenation (struct REGEX_ITERNAL_Context *ctx)
2542{ 2543{
2543 struct GNUNET_REGEX_Automaton *a; 2544 struct REGEX_ITERNAL_Automaton *a;
2544 struct GNUNET_REGEX_Automaton *b; 2545 struct REGEX_ITERNAL_Automaton *b;
2545 struct GNUNET_REGEX_Automaton *new_nfa; 2546 struct REGEX_ITERNAL_Automaton *new_nfa;
2546 2547
2547 b = ctx->stack_tail; 2548 b = ctx->stack_tail;
2548 GNUNET_assert (NULL != b); 2549 GNUNET_assert (NULL != b);
@@ -2574,12 +2575,12 @@ nfa_add_concatenation (struct GNUNET_REGEX_Context *ctx)
2574 * @param ctx context 2575 * @param ctx context
2575 */ 2576 */
2576static void 2577static void
2577nfa_add_star_op (struct GNUNET_REGEX_Context *ctx) 2578nfa_add_star_op (struct REGEX_ITERNAL_Context *ctx)
2578{ 2579{
2579 struct GNUNET_REGEX_Automaton *a; 2580 struct REGEX_ITERNAL_Automaton *a;
2580 struct GNUNET_REGEX_Automaton *new_nfa; 2581 struct REGEX_ITERNAL_Automaton *new_nfa;
2581 struct GNUNET_REGEX_State *start; 2582 struct REGEX_ITERNAL_State *start;
2582 struct GNUNET_REGEX_State *end; 2583 struct REGEX_ITERNAL_State *end;
2583 2584
2584 a = ctx->stack_tail; 2585 a = ctx->stack_tail;
2585 2586
@@ -2617,9 +2618,9 @@ nfa_add_star_op (struct GNUNET_REGEX_Context *ctx)
2617 * @param ctx context 2618 * @param ctx context
2618 */ 2619 */
2619static void 2620static void
2620nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx) 2621nfa_add_plus_op (struct REGEX_ITERNAL_Context *ctx)
2621{ 2622{
2622 struct GNUNET_REGEX_Automaton *a; 2623 struct REGEX_ITERNAL_Automaton *a;
2623 2624
2624 a = ctx->stack_tail; 2625 a = ctx->stack_tail;
2625 2626
@@ -2644,12 +2645,12 @@ nfa_add_plus_op (struct GNUNET_REGEX_Context *ctx)
2644 * @param ctx context 2645 * @param ctx context
2645 */ 2646 */
2646static void 2647static void
2647nfa_add_question_op (struct GNUNET_REGEX_Context *ctx) 2648nfa_add_question_op (struct REGEX_ITERNAL_Context *ctx)
2648{ 2649{
2649 struct GNUNET_REGEX_Automaton *a; 2650 struct REGEX_ITERNAL_Automaton *a;
2650 struct GNUNET_REGEX_Automaton *new_nfa; 2651 struct REGEX_ITERNAL_Automaton *new_nfa;
2651 struct GNUNET_REGEX_State *start; 2652 struct REGEX_ITERNAL_State *start;
2652 struct GNUNET_REGEX_State *end; 2653 struct REGEX_ITERNAL_State *end;
2653 2654
2654 a = ctx->stack_tail; 2655 a = ctx->stack_tail;
2655 2656
@@ -2685,13 +2686,13 @@ nfa_add_question_op (struct GNUNET_REGEX_Context *ctx)
2685 * @param ctx context 2686 * @param ctx context
2686 */ 2687 */
2687static void 2688static void
2688nfa_add_alternation (struct GNUNET_REGEX_Context *ctx) 2689nfa_add_alternation (struct REGEX_ITERNAL_Context *ctx)
2689{ 2690{
2690 struct GNUNET_REGEX_Automaton *a; 2691 struct REGEX_ITERNAL_Automaton *a;
2691 struct GNUNET_REGEX_Automaton *b; 2692 struct REGEX_ITERNAL_Automaton *b;
2692 struct GNUNET_REGEX_Automaton *new_nfa; 2693 struct REGEX_ITERNAL_Automaton *new_nfa;
2693 struct GNUNET_REGEX_State *start; 2694 struct REGEX_ITERNAL_State *start;
2694 struct GNUNET_REGEX_State *end; 2695 struct REGEX_ITERNAL_State *end;
2695 2696
2696 b = ctx->stack_tail; 2697 b = ctx->stack_tail;
2697 GNUNET_assert (NULL != b); 2698 GNUNET_assert (NULL != b);
@@ -2729,11 +2730,11 @@ nfa_add_alternation (struct GNUNET_REGEX_Context *ctx)
2729 * @param label label for nfa transition 2730 * @param label label for nfa transition
2730 */ 2731 */
2731static void 2732static void
2732nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char *label) 2733nfa_add_label (struct REGEX_ITERNAL_Context *ctx, const char *label)
2733{ 2734{
2734 struct GNUNET_REGEX_Automaton *n; 2735 struct REGEX_ITERNAL_Automaton *n;
2735 struct GNUNET_REGEX_State *start; 2736 struct REGEX_ITERNAL_State *start;
2736 struct GNUNET_REGEX_State *end; 2737 struct REGEX_ITERNAL_State *end;
2737 2738
2738 GNUNET_assert (NULL != ctx); 2739 GNUNET_assert (NULL != ctx);
2739 2740
@@ -2752,7 +2753,7 @@ nfa_add_label (struct GNUNET_REGEX_Context *ctx, const char *label)
2752 * @param ctx context 2753 * @param ctx context
2753 */ 2754 */
2754static void 2755static void
2755GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx) 2756REGEX_ITERNAL_context_init (struct REGEX_ITERNAL_Context *ctx)
2756{ 2757{
2757 if (NULL == ctx) 2758 if (NULL == ctx)
2758 { 2759 {
@@ -2772,13 +2773,13 @@ GNUNET_REGEX_context_init (struct GNUNET_REGEX_Context *ctx)
2772 * @param regex regular expression string 2773 * @param regex regular expression string
2773 * @param len length of the string 2774 * @param len length of the string
2774 * 2775 *
2775 * @return NFA, needs to be freed using GNUNET_REGEX_destroy_automaton 2776 * @return NFA, needs to be freed using REGEX_ITERNAL_destroy_automaton
2776 */ 2777 */
2777struct GNUNET_REGEX_Automaton * 2778struct REGEX_ITERNAL_Automaton *
2778GNUNET_REGEX_construct_nfa (const char *regex, const size_t len) 2779REGEX_ITERNAL_construct_nfa (const char *regex, const size_t len)
2779{ 2780{
2780 struct GNUNET_REGEX_Context ctx; 2781 struct REGEX_ITERNAL_Context ctx;
2781 struct GNUNET_REGEX_Automaton *nfa; 2782 struct REGEX_ITERNAL_Automaton *nfa;
2782 const char *regexp; 2783 const char *regexp;
2783 char curlabel[2]; 2784 char curlabel[2];
2784 char *error_msg; 2785 char *error_msg;
@@ -2800,7 +2801,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
2800 2801
2801 return NULL; 2802 return NULL;
2802 } 2803 }
2803 GNUNET_REGEX_context_init (&ctx); 2804 REGEX_ITERNAL_context_init (&ctx);
2804 2805
2805 regexp = regex; 2806 regexp = regex;
2806 curlabel[1] = '\0'; 2807 curlabel[1] = '\0';
@@ -2923,7 +2924,7 @@ GNUNET_REGEX_construct_nfa (const char *regex, const size_t len)
2923 nfa->regex = GNUNET_strdup (regex); 2924 nfa->regex = GNUNET_strdup (regex);
2924 2925
2925 /* create depth-first numbering of the states for pretty printing */ 2926 /* create depth-first numbering of the states for pretty printing */
2926 GNUNET_REGEX_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL); 2927 REGEX_ITERNAL_automaton_traverse (nfa, NULL, NULL, NULL, &number_states, NULL);
2927 2928
2928 /* No multistriding added so far */ 2929 /* No multistriding added so far */
2929 nfa->is_multistrided = GNUNET_NO; 2930 nfa->is_multistrided = GNUNET_NO;
@@ -2940,7 +2941,7 @@ error:
2940 while (NULL != (nfa = ctx.stack_head)) 2941 while (NULL != (nfa = ctx.stack_head))
2941 { 2942 {
2942 GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa); 2943 GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2943 GNUNET_REGEX_automaton_destroy (nfa); 2944 REGEX_ITERNAL_automaton_destroy (nfa);
2944 } 2945 }
2945 2946
2946 return NULL; 2947 return NULL;
@@ -2957,17 +2958,17 @@ error:
2957 * for starting. 2958 * for starting.
2958 */ 2959 */
2959static void 2960static void
2960construct_dfa_states (struct GNUNET_REGEX_Context *ctx, 2961construct_dfa_states (struct REGEX_ITERNAL_Context *ctx,
2961 struct GNUNET_REGEX_Automaton *nfa, 2962 struct REGEX_ITERNAL_Automaton *nfa,
2962 struct GNUNET_REGEX_Automaton *dfa, 2963 struct REGEX_ITERNAL_Automaton *dfa,
2963 struct GNUNET_REGEX_State *dfa_state) 2964 struct REGEX_ITERNAL_State *dfa_state)
2964{ 2965{
2965 struct GNUNET_REGEX_Transition *ctran; 2966 struct REGEX_ITERNAL_Transition *ctran;
2966 struct GNUNET_REGEX_State *new_dfa_state; 2967 struct REGEX_ITERNAL_State *new_dfa_state;
2967 struct GNUNET_REGEX_State *state_contains; 2968 struct REGEX_ITERNAL_State *state_contains;
2968 struct GNUNET_REGEX_State *state_iter; 2969 struct REGEX_ITERNAL_State *state_iter;
2969 struct GNUNET_REGEX_StateSet tmp; 2970 struct REGEX_ITERNAL_StateSet tmp;
2970 struct GNUNET_REGEX_StateSet nfa_set; 2971 struct REGEX_ITERNAL_StateSet nfa_set;
2971 2972
2972 for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next) 2973 for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
2973 { 2974 {
@@ -3019,23 +3020,23 @@ construct_dfa_states (struct GNUNET_REGEX_Context *ctx,
3019 * @param max_path_len limit the path compression length to the 3020 * @param max_path_len limit the path compression length to the
3020 * given value. If set to 1, no path compression is applied. Set to 0 for 3021 * given value. If set to 1, no path compression is applied. Set to 0 for
3021 * maximal possible path compression (generally not desireable). 3022 * maximal possible path compression (generally not desireable).
3022 * @return DFA, needs to be freed using GNUNET_REGEX_automaton_destroy. 3023 * @return DFA, needs to be freed using REGEX_ITERNAL_automaton_destroy.
3023 */ 3024 */
3024struct GNUNET_REGEX_Automaton * 3025struct REGEX_ITERNAL_Automaton *
3025GNUNET_REGEX_construct_dfa (const char *regex, const size_t len, 3026REGEX_ITERNAL_construct_dfa (const char *regex, const size_t len,
3026 unsigned int max_path_len) 3027 unsigned int max_path_len)
3027{ 3028{
3028 struct GNUNET_REGEX_Context ctx; 3029 struct REGEX_ITERNAL_Context ctx;
3029 struct GNUNET_REGEX_Automaton *dfa; 3030 struct REGEX_ITERNAL_Automaton *dfa;
3030 struct GNUNET_REGEX_Automaton *nfa; 3031 struct REGEX_ITERNAL_Automaton *nfa;
3031 struct GNUNET_REGEX_StateSet nfa_start_eps_cls; 3032 struct REGEX_ITERNAL_StateSet nfa_start_eps_cls;
3032 struct GNUNET_REGEX_StateSet singleton_set; 3033 struct REGEX_ITERNAL_StateSet singleton_set;
3033 3034
3034 GNUNET_REGEX_context_init (&ctx); 3035 REGEX_ITERNAL_context_init (&ctx);
3035 3036
3036 /* Create NFA */ 3037 /* Create NFA */
3037 // fprintf (stderr, "N"); 3038 // fprintf (stderr, "N");
3038 nfa = GNUNET_REGEX_construct_nfa (regex, len); 3039 nfa = REGEX_ITERNAL_construct_nfa (regex, len);
3039 3040
3040 if (NULL == nfa) 3041 if (NULL == nfa)
3041 { 3042 {
@@ -3044,12 +3045,12 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len,
3044 return NULL; 3045 return NULL;
3045 } 3046 }
3046 3047
3047 dfa = GNUNET_malloc (sizeof (struct GNUNET_REGEX_Automaton)); 3048 dfa = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Automaton));
3048 dfa->type = DFA; 3049 dfa->type = DFA;
3049 dfa->regex = GNUNET_strdup (regex); 3050 dfa->regex = GNUNET_strdup (regex);
3050 3051
3051 /* Create DFA start state from epsilon closure */ 3052 /* Create DFA start state from epsilon closure */
3052 memset (&singleton_set, 0, sizeof (struct GNUNET_REGEX_StateSet)); 3053 memset (&singleton_set, 0, sizeof (struct REGEX_ITERNAL_StateSet));
3053 state_set_append (&singleton_set, nfa->start); 3054 state_set_append (&singleton_set, nfa->start);
3054 nfa_closure_set_create (&nfa_start_eps_cls, nfa, &singleton_set, NULL); 3055 nfa_closure_set_create (&nfa_start_eps_cls, nfa, &singleton_set, NULL);
3055 state_set_clear (&singleton_set); 3056 state_set_clear (&singleton_set);
@@ -3058,20 +3059,20 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len,
3058 3059
3059 // fprintf (stderr, "D"); 3060 // fprintf (stderr, "D");
3060 construct_dfa_states (&ctx, nfa, dfa, dfa->start); 3061 construct_dfa_states (&ctx, nfa, dfa, dfa->start);
3061 GNUNET_REGEX_automaton_destroy (nfa); 3062 REGEX_ITERNAL_automaton_destroy (nfa);
3062 3063
3063 /* Minimize DFA */ 3064 /* Minimize DFA */
3064 // fprintf (stderr, "M"); 3065 // fprintf (stderr, "M");
3065 if (GNUNET_OK != dfa_minimize (&ctx, dfa)) 3066 if (GNUNET_OK != dfa_minimize (&ctx, dfa))
3066 { 3067 {
3067 GNUNET_REGEX_automaton_destroy (dfa); 3068 REGEX_ITERNAL_automaton_destroy (dfa);
3068 return NULL; 3069 return NULL;
3069 } 3070 }
3070 3071
3071 /* Create proofs and hashes for all states */ 3072 /* Create proofs and hashes for all states */
3072 if (GNUNET_OK != automaton_create_proofs (dfa)) 3073 if (GNUNET_OK != automaton_create_proofs (dfa))
3073 { 3074 {
3074 GNUNET_REGEX_automaton_destroy (dfa); 3075 REGEX_ITERNAL_automaton_destroy (dfa);
3075 return NULL; 3076 return NULL;
3076 } 3077 }
3077 3078
@@ -3084,16 +3085,16 @@ GNUNET_REGEX_construct_dfa (const char *regex, const size_t len,
3084 3085
3085 3086
3086/** 3087/**
3087 * Free the memory allocated by constructing the GNUNET_REGEX_Automaton data 3088 * Free the memory allocated by constructing the REGEX_ITERNAL_Automaton data
3088 * structure. 3089 * structure.
3089 * 3090 *
3090 * @param a automaton to be destroyed 3091 * @param a automaton to be destroyed
3091 */ 3092 */
3092void 3093void
3093GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a) 3094REGEX_ITERNAL_automaton_destroy (struct REGEX_ITERNAL_Automaton *a)
3094{ 3095{
3095 struct GNUNET_REGEX_State *s; 3096 struct REGEX_ITERNAL_State *s;
3096 struct GNUNET_REGEX_State *next_state; 3097 struct REGEX_ITERNAL_State *next_state;
3097 3098
3098 if (NULL == a) 3099 if (NULL == a)
3099 return; 3100 return;
@@ -3121,10 +3122,10 @@ GNUNET_REGEX_automaton_destroy (struct GNUNET_REGEX_Automaton *a)
3121 * @return 0 if string matches, non 0 otherwise 3122 * @return 0 if string matches, non 0 otherwise
3122 */ 3123 */
3123static int 3124static int
3124evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string) 3125evaluate_dfa (struct REGEX_ITERNAL_Automaton *a, const char *string)
3125{ 3126{
3126 const char *strp; 3127 const char *strp;
3127 struct GNUNET_REGEX_State *s; 3128 struct REGEX_ITERNAL_State *s;
3128 unsigned int step_len; 3129 unsigned int step_len;
3129 3130
3130 if (DFA != a->type) 3131 if (DFA != a->type)
@@ -3164,14 +3165,14 @@ evaluate_dfa (struct GNUNET_REGEX_Automaton *a, const char *string)
3164 * @return 0 if string matches, non 0 otherwise 3165 * @return 0 if string matches, non 0 otherwise
3165 */ 3166 */
3166static int 3167static int
3167evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string) 3168evaluate_nfa (struct REGEX_ITERNAL_Automaton *a, const char *string)
3168{ 3169{
3169 const char *strp; 3170 const char *strp;
3170 char str[2]; 3171 char str[2];
3171 struct GNUNET_REGEX_State *s; 3172 struct REGEX_ITERNAL_State *s;
3172 struct GNUNET_REGEX_StateSet sset; 3173 struct REGEX_ITERNAL_StateSet sset;
3173 struct GNUNET_REGEX_StateSet new_sset; 3174 struct REGEX_ITERNAL_StateSet new_sset;
3174 struct GNUNET_REGEX_StateSet singleton_set; 3175 struct REGEX_ITERNAL_StateSet singleton_set;
3175 unsigned int i; 3176 unsigned int i;
3176 int result; 3177 int result;
3177 3178
@@ -3187,7 +3188,7 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
3187 return 0; 3188 return 0;
3188 3189
3189 result = 1; 3190 result = 1;
3190 memset (&singleton_set, 0, sizeof (struct GNUNET_REGEX_StateSet)); 3191 memset (&singleton_set, 0, sizeof (struct REGEX_ITERNAL_StateSet));
3191 state_set_append (&singleton_set, a->start); 3192 state_set_append (&singleton_set, a->start);
3192 nfa_closure_set_create (&sset, a, &singleton_set, NULL); 3193 nfa_closure_set_create (&sset, a, &singleton_set, NULL);
3193 state_set_clear (&singleton_set); 3194 state_set_clear (&singleton_set);
@@ -3226,7 +3227,7 @@ evaluate_nfa (struct GNUNET_REGEX_Automaton *a, const char *string)
3226 * @return 0 if string matches, non 0 otherwise 3227 * @return 0 if string matches, non 0 otherwise
3227 */ 3228 */
3228int 3229int
3229GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string) 3230REGEX_ITERNAL_eval (struct REGEX_ITERNAL_Automaton *a, const char *string)
3230{ 3231{
3231 int result; 3232 int result;
3232 3233
@@ -3261,7 +3262,7 @@ GNUNET_REGEX_eval (struct GNUNET_REGEX_Automaton *a, const char *string)
3261 * @return 3262 * @return
3262 */ 3263 */
3263const char * 3264const char *
3264GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a) 3265REGEX_ITERNAL_get_canonical_regex (struct REGEX_ITERNAL_Automaton *a)
3265{ 3266{
3266 if (NULL == a) 3267 if (NULL == a)
3267 return NULL; 3268 return NULL;
@@ -3278,10 +3279,10 @@ GNUNET_REGEX_get_canonical_regex (struct GNUNET_REGEX_Automaton *a)
3278 * @return number of transitions in the given automaton. 3279 * @return number of transitions in the given automaton.
3279 */ 3280 */
3280unsigned int 3281unsigned int
3281GNUNET_REGEX_get_transition_count (struct GNUNET_REGEX_Automaton *a) 3282REGEX_ITERNAL_get_transition_count (struct REGEX_ITERNAL_Automaton *a)
3282{ 3283{
3283 unsigned int t_count; 3284 unsigned int t_count;
3284 struct GNUNET_REGEX_State *s; 3285 struct REGEX_ITERNAL_State *s;
3285 3286
3286 if (NULL == a) 3287 if (NULL == a)
3287 return 0; 3288 return 0;
@@ -3306,7 +3307,7 @@ GNUNET_REGEX_get_transition_count (struct GNUNET_REGEX_Automaton *a)
3306 * to construct the key 3307 * to construct the key
3307 */ 3308 */
3308size_t 3309size_t
3309GNUNET_REGEX_get_first_key (const char *input_string, size_t string_len, 3310REGEX_ITERNAL_get_first_key (const char *input_string, size_t string_len,
3310 struct GNUNET_HashCode * key) 3311 struct GNUNET_HashCode * key)
3311{ 3312{
3312 unsigned int size; 3313 unsigned int size;
@@ -3336,7 +3337,7 @@ GNUNET_REGEX_get_first_key (const char *input_string, size_t string_len,
3336 * @return GNUNET_OK if the proof is valid for the given key. 3337 * @return GNUNET_OK if the proof is valid for the given key.
3337 */ 3338 */
3338int 3339int
3339GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key) 3340REGEX_ITERNAL_check_proof (const char *proof, const struct GNUNET_HashCode *key)
3340{ 3341{
3341 struct GNUNET_HashCode key_check; 3342 struct GNUNET_HashCode key_check;
3342 3343
@@ -3364,15 +3365,15 @@ GNUNET_REGEX_check_proof (const char *proof, const struct GNUNET_HashCode *key)
3364 */ 3365 */
3365static void 3366static void
3366iterate_initial_edge (const unsigned int min_len, const unsigned int max_len, 3367iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
3367 char *consumed_string, struct GNUNET_REGEX_State *state, 3368 char *consumed_string, struct REGEX_ITERNAL_State *state,
3368 GNUNET_REGEX_KeyIterator iterator, void *iterator_cls) 3369 REGEX_ITERNAL_KeyIterator iterator, void *iterator_cls)
3369{ 3370{
3370 unsigned int i; 3371 unsigned int i;
3371 char *temp; 3372 char *temp;
3372 struct GNUNET_REGEX_Transition *t; 3373 struct REGEX_ITERNAL_Transition *t;
3373 unsigned int num_edges = state->transition_count; 3374 unsigned int num_edges = state->transition_count;
3374 struct GNUNET_REGEX_Edge edges[num_edges]; 3375 struct REGEX_ITERNAL_Edge edges[num_edges];
3375 struct GNUNET_REGEX_Edge edge[1]; 3376 struct REGEX_ITERNAL_Edge edge[1];
3376 struct GNUNET_HashCode hash; 3377 struct GNUNET_HashCode hash;
3377 struct GNUNET_HashCode hash_new; 3378 struct GNUNET_HashCode hash_new;
3378 3379
@@ -3454,15 +3455,15 @@ iterate_initial_edge (const unsigned int min_len, const unsigned int max_len,
3454 * @param iterator_cls closure. 3455 * @param iterator_cls closure.
3455 */ 3456 */
3456void 3457void
3457GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a, 3458REGEX_ITERNAL_iterate_all_edges (struct REGEX_ITERNAL_Automaton *a,
3458 GNUNET_REGEX_KeyIterator iterator, 3459 REGEX_ITERNAL_KeyIterator iterator,
3459 void *iterator_cls) 3460 void *iterator_cls)
3460{ 3461{
3461 struct GNUNET_REGEX_State *s; 3462 struct REGEX_ITERNAL_State *s;
3462 3463
3463 for (s = a->states_head; NULL != s; s = s->next) 3464 for (s = a->states_head; NULL != s; s = s->next)
3464 { 3465 {
3465 struct GNUNET_REGEX_Edge edges[s->transition_count]; 3466 struct REGEX_ITERNAL_Edge edges[s->transition_count];
3466 unsigned int num_edges; 3467 unsigned int num_edges;
3467 3468
3468 num_edges = state_get_edges (s, edges); 3469 num_edges = state_get_edges (s, edges);
@@ -3479,116 +3480,6 @@ GNUNET_REGEX_iterate_all_edges (struct GNUNET_REGEX_Automaton *a,
3479} 3480}
3480 3481
3481 3482
3482/**
3483 * Create a string with binary IP notation for the given 'addr' in 'str'.
3484 *
3485 * @param af address family of the given 'addr'.
3486 * @param addr address that should be converted to a string.
3487 * struct in_addr * for IPv4 and struct in6_addr * for IPv6.
3488 * @param str string that will contain binary notation of 'addr'. Expected
3489 * to be at least 33 bytes long for IPv4 and 129 bytes long for IPv6.
3490 */
3491static void
3492iptobinstr (const int af, const void *addr, char *str)
3493{
3494 int i;
3495
3496 switch (af)
3497 {
3498 case AF_INET:
3499 {
3500 uint32_t b = htonl (((struct in_addr *) addr)->s_addr);
3501
3502 str[32] = '\0';
3503 str += 31;
3504 for (i = 31; i >= 0; i--)
3505 {
3506 *str = (b & 1) + '0';
3507 str--;
3508 b >>= 1;
3509 }
3510 break;
3511 }
3512 case AF_INET6:
3513 {
3514 struct in6_addr b = *(const struct in6_addr *) addr;
3515
3516 str[128] = '\0';
3517 str += 127;
3518 for (i = 127; i >= 0; i--)
3519 {
3520 *str = (b.s6_addr[i / 8] & 1) + '0';
3521 str--;
3522 b.s6_addr[i / 8] >>= 1;
3523 }
3524 break;
3525 }
3526 }
3527}
3528
3529
3530/**
3531 * Get the ipv4 network prefix from the given 'netmask'.
3532 *
3533 * @param netmask netmask for which to get the prefix len.
3534 *
3535 * @return length of ipv4 prefix for 'netmask'.
3536 */
3537static unsigned int
3538ipv4netmasktoprefixlen (const char *netmask)
3539{
3540 struct in_addr a;
3541 unsigned int len;
3542 uint32_t t;
3543
3544 if (1 != inet_pton (AF_INET, netmask, &a))
3545 return 0;
3546 len = 32;
3547 for (t = htonl (~a.s_addr); 0 != t; t >>= 1)
3548 len--;
3549 return len;
3550}
3551
3552
3553/**
3554 * Create a regex in 'rxstr' from the given 'ip' and 'netmask'.
3555 *
3556 * @param ip IPv4 representation.
3557 * @param netmask netmask for the ip.
3558 * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV4_REGEXLEN
3559 * bytes long.
3560 */
3561void
3562GNUNET_REGEX_ipv4toregex (const struct in_addr *ip, const char *netmask,
3563 char *rxstr)
3564{
3565 unsigned int pfxlen;
3566
3567 pfxlen = ipv4netmasktoprefixlen (netmask);
3568 iptobinstr (AF_INET, ip, rxstr);
3569 rxstr[pfxlen] = '\0';
3570 if (pfxlen < 32)
3571 strcat (rxstr, "(0|1)+");
3572}
3573
3574
3575/**
3576 * Create a regex in 'rxstr' from the given 'ipv6' and 'prefixlen'.
3577 *
3578 * @param ipv6 IPv6 representation.
3579 * @param prefixlen length of the ipv6 prefix.
3580 * @param rxstr generated regex, must be at least GNUNET_REGEX_IPV6_REGEXLEN
3581 * bytes long.
3582 */
3583void
3584GNUNET_REGEX_ipv6toregex (const struct in6_addr *ipv6, unsigned int prefixlen,
3585 char *rxstr)
3586{
3587 iptobinstr (AF_INET6, ipv6, rxstr);
3588 rxstr[prefixlen] = '\0';
3589 if (prefixlen < 128)
3590 strcat (rxstr, "(0|1)+");
3591}
3592 3483
3593 3484
3594/* end of regex.c */ 3485/* end of regex.c */