aboutsummaryrefslogtreecommitdiff
path: root/src/regex/regex_internal.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/regex/regex_internal.c')
-rw-r--r--src/regex/regex_internal.c62
1 files changed, 31 insertions, 31 deletions
diff --git a/src/regex/regex_internal.c b/src/regex/regex_internal.c
index 78c2de8ab..1dd4f6a97 100644
--- a/src/regex/regex_internal.c
+++ b/src/regex/regex_internal.c
@@ -121,7 +121,7 @@ state_add_transition (struct REGEX_INTERNAL_Context *ctx,
121 /* Do not add duplicate state transitions */ 121 /* Do not add duplicate state transitions */
122 for (t = from_state->transitions_head; NULL != t; t = t->next) 122 for (t = from_state->transitions_head; NULL != t; t = t->next)
123 { 123 {
124 if ((t->to_state == to_state) &&(0 == nullstrcmp (t->label, label)) && 124 if ((t->to_state == to_state) && (0 == nullstrcmp (t->label, label)) &&
125 (t->from_state == from_state) ) 125 (t->from_state == from_state) )
126 return; 126 return;
127 } 127 }
@@ -162,7 +162,7 @@ static void
162state_remove_transition (struct REGEX_INTERNAL_State *state, 162state_remove_transition (struct REGEX_INTERNAL_State *state,
163 struct REGEX_INTERNAL_Transition *transition) 163 struct REGEX_INTERNAL_Transition *transition)
164{ 164{
165 if ((NULL == state)||(NULL == transition)) 165 if ((NULL == state) || (NULL == transition))
166 return; 166 return;
167 167
168 if (transition->from_state != state) 168 if (transition->from_state != state)
@@ -247,7 +247,7 @@ state_set_compare (struct REGEX_INTERNAL_StateSet *sset1,
247 int result; 247 int result;
248 unsigned int i; 248 unsigned int i;
249 249
250 if ((NULL == sset1)||(NULL == sset2)) 250 if ((NULL == sset1) || (NULL == sset2))
251 return 1; 251 return 1;
252 252
253 result = sset1->off - sset2->off; 253 result = sset1->off - sset2->off;
@@ -339,7 +339,7 @@ automaton_remove_state (struct REGEX_INTERNAL_Automaton *a,
339 struct REGEX_INTERNAL_Transition *t_check; 339 struct REGEX_INTERNAL_Transition *t_check;
340 struct REGEX_INTERNAL_Transition *t_check_next; 340 struct REGEX_INTERNAL_Transition *t_check_next;
341 341
342 if ((NULL == a)||(NULL == s)) 342 if ((NULL == a) || (NULL == s))
343 return; 343 return;
344 344
345 /* remove all transitions leading to this state */ 345 /* remove all transitions leading to this state */
@@ -399,7 +399,7 @@ automaton_merge_states (struct REGEX_INTERNAL_Context *ctx,
399 is_dup = GNUNET_NO; 399 is_dup = GNUNET_NO;
400 for (t = t_check->from_state->transitions_head; NULL != t; t = t->next) 400 for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
401 { 401 {
402 if ((t->to_state == s1) &&(0 == strcmp (t_check->label, t->label)) ) 402 if ((t->to_state == s1) && (0 == strcmp (t_check->label, t->label)) )
403 is_dup = GNUNET_YES; 403 is_dup = GNUNET_YES;
404 } 404 }
405 if (GNUNET_NO == is_dup) 405 if (GNUNET_NO == is_dup)
@@ -487,7 +487,7 @@ automaton_state_traverse (struct REGEX_INTERNAL_State *s,
487 for (t = s->transitions_head; NULL != t; t = t->next) 487 for (t = s->transitions_head; NULL != t; t = t->next)
488 { 488 {
489 if ((NULL == check) || 489 if ((NULL == check) ||
490 ((NULL != check) &&(GNUNET_YES == check (check_cls, s, t)) )) 490 ((NULL != check) && (GNUNET_YES == check (check_cls, s, t)) ))
491 { 491 {
492 automaton_state_traverse (t->to_state, 492 automaton_state_traverse (t->to_state,
493 marks, 493 marks,
@@ -525,7 +525,7 @@ REGEX_INTERNAL_automaton_traverse (const struct REGEX_INTERNAL_Automaton *a,
525 unsigned int count; 525 unsigned int count;
526 struct REGEX_INTERNAL_State *s; 526 struct REGEX_INTERNAL_State *s;
527 527
528 if ((NULL == a)||(0 == a->state_count)) 528 if ((NULL == a) || (0 == a->state_count))
529 return; 529 return;
530 530
531 int marks[a->state_count]; 531 int marks[a->state_count];
@@ -1197,9 +1197,7 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
1197 * R_cur_ij = R_cur_l | R_cur_r 1197 * R_cur_ij = R_cur_l | R_cur_r
1198 * R_cur_l == R^{(k-1)}_{ij} 1198 * R_cur_l == R^{(k-1)}_{ij}
1199 * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} 1199 * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1200 */ 1200 */if ((GNUNET_YES == R_last_ij->null_flag) &&
1201
1202 if ((GNUNET_YES == R_last_ij->null_flag) &&
1203 ((GNUNET_YES == R_last_ik->null_flag) || 1201 ((GNUNET_YES == R_last_ik->null_flag) ||
1204 (GNUNET_YES == R_last_kj->null_flag))) 1202 (GNUNET_YES == R_last_kj->null_flag)))
1205 { 1203 {
@@ -1283,8 +1281,7 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
1283 * (e|a)|(e|a)a*a = a* 1281 * (e|a)|(e|a)a*a = a*
1284 * (e|a)|(e|a)a*(e|a) = a* 1282 * (e|a)|(e|a)a*(e|a) = a*
1285 * (e|a)|(e|a)(e|a)*(e|a) = a* 1283 * (e|a)|(e|a)(e|a)*(e|a) = a*
1286 */ 1284 */if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1287 if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1288 sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_ij); 1285 sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_ij);
1289 else 1286 else
1290 sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_ij); 1287 sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_ij);
@@ -1297,8 +1294,7 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
1297 * a|aa*(e|a) = a+ 1294 * a|aa*(e|a) = a+
1298 * a|(e|a)(e|a)*a = a+ 1295 * a|(e|a)(e|a)*a = a+
1299 * a|a(e|a)*(e|a) = a+ 1296 * a|a(e|a)*(e|a) = a+
1300 */ 1297 */if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1301 if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1302 sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_ij); 1298 sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_ij);
1303 else 1299 else
1304 sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_ij); 1300 sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_ij);
@@ -1435,8 +1431,7 @@ automaton_create_proofs_simplify (const struct StringBuffer *R_last_ij,
1435 * aa*(e|a) = a+ 1431 * aa*(e|a) = a+
1436 * a(e|a)*(e|a) = a+ 1432 * a(e|a)*(e|a) = a+
1437 * (e|a)a*a = a+ 1433 * (e|a)a*a = a+
1438 */ 1434 */else
1439 else
1440 { 1435 {
1441 eps_check = (has_epsilon (R_last_ik) + has_epsilon (R_last_kk) 1436 eps_check = (has_epsilon (R_last_ik) + has_epsilon (R_last_kk)
1442 + has_epsilon (R_last_kj)); 1437 + has_epsilon (R_last_kj));
@@ -1922,7 +1917,7 @@ dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a)
1922 dead = 1; 1917 dead = 1;
1923 for (t = s->transitions_head; NULL != t; t = t->next) 1918 for (t = s->transitions_head; NULL != t; t = t->next)
1924 { 1919 {
1925 if ((NULL != t->to_state) &&(t->to_state != s) ) 1920 if ((NULL != t->to_state) && (t->to_state != s) )
1926 { 1921 {
1927 dead = 0; 1922 dead = 0;
1928 break; 1923 break;
@@ -2201,7 +2196,7 @@ REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx,
2201 struct REGEX_INTERNAL_Transition *t; 2196 struct REGEX_INTERNAL_Transition *t;
2202 struct REGEX_INTERNAL_Transition *t_next; 2197 struct REGEX_INTERNAL_Transition *t_next;
2203 2198
2204 if ((1 > stride_len)||(GNUNET_YES == dfa->is_multistrided)) 2199 if ((1 > stride_len) || (GNUNET_YES == dfa->is_multistrided))
2205 return; 2200 return;
2206 2201
2207 /* Compute the new transitions of given stride_len */ 2202 /* Compute the new transitions of given stride_len */
@@ -2226,6 +2221,7 @@ REGEX_INTERNAL_dfa_add_multi_strides (struct REGEX_INTERNAL_Context *regex_ctx,
2226 dfa->is_multistrided = GNUNET_YES; 2221 dfa->is_multistrided = GNUNET_YES;
2227} 2222}
2228 2223
2224
2229/** 2225/**
2230 * Recursive Helper function for DFA path compression. Does DFS on the DFA graph 2226 * Recursive Helper function for DFA path compression. Does DFS on the DFA graph
2231 * and adds new transitions to the given transitions DLL and marks states that 2227 * and adds new transitions to the given transitions DLL and marks states that
@@ -2252,11 +2248,14 @@ dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa,
2252 char *new_label; 2248 char *new_label;
2253 2249
2254 2250
2255 if ((NULL != label)&& 2251 if ((NULL != label) &&
2256 (((cur->incoming_transition_count > 1)||(GNUNET_YES == cur->accepting)|| 2252 (((cur->incoming_transition_count > 1) || (GNUNET_YES ==
2253 cur->accepting) ||
2257 (GNUNET_YES == cur->marked) ) || 2254 (GNUNET_YES == cur->marked) ) ||
2258 ((start != dfa->start)&&(max_len > 0)&&(max_len == strlen (label))) || 2255 ((start != dfa->start) && (max_len > 0) && (max_len == strlen (
2259 ((start == dfa->start)&&(GNUNET_REGEX_INITIAL_BYTES == strlen (label))))) 2256 label))) ||
2257 ((start == dfa->start) && (GNUNET_REGEX_INITIAL_BYTES == strlen (
2258 label)))))
2260 { 2259 {
2261 t = GNUNET_new (struct REGEX_INTERNAL_Transition); 2260 t = GNUNET_new (struct REGEX_INTERNAL_Transition);
2262 t->label = GNUNET_strdup (label); 2261 t->label = GNUNET_strdup (label);
@@ -2279,7 +2278,7 @@ dfa_compress_paths_helper (struct REGEX_INTERNAL_Automaton *dfa,
2279 else if (cur != start) 2278 else if (cur != start)
2280 cur->contained = GNUNET_YES; 2279 cur->contained = GNUNET_YES;
2281 2280
2282 if ((GNUNET_YES == cur->marked)&&(cur != start)) 2281 if ((GNUNET_YES == cur->marked) && (cur != start))
2283 return; 2282 return;
2284 2283
2285 cur->marked = GNUNET_YES; 2284 cur->marked = GNUNET_YES;
@@ -2398,7 +2397,7 @@ nfa_fragment_create (struct REGEX_INTERNAL_State *start,
2398 n->end = NULL; 2397 n->end = NULL;
2399 n->state_count = 0; 2398 n->state_count = 0;
2400 2399
2401 if ((NULL == start)||(NULL == end)) 2400 if ((NULL == start) || (NULL == end))
2402 return n; 2401 return n;
2403 2402
2404 automaton_add_state (n, end); 2403 automaton_add_state (n, end);
@@ -2427,7 +2426,7 @@ nfa_add_states (struct REGEX_INTERNAL_Automaton *n,
2427{ 2426{
2428 struct REGEX_INTERNAL_State *s; 2427 struct REGEX_INTERNAL_State *s;
2429 2428
2430 if ((NULL == n)||(NULL == states_head)) 2429 if ((NULL == n) || (NULL == states_head))
2431 { 2430 {
2432 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n"); 2431 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
2433 return; 2432 return;
@@ -2820,7 +2819,7 @@ REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len)
2820 int atomcount; 2819 int atomcount;
2821 } *p; 2820 } *p;
2822 2821
2823 if ((NULL == regex)||(0 == strlen (regex))||(0 == len)) 2822 if ((NULL == regex) || (0 == strlen (regex)) || (0 == len))
2824 { 2823 {
2825 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, 2824 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
2826 "Could not parse regex. Empty regex string provided.\n"); 2825 "Could not parse regex. Empty regex string provided.\n");
@@ -3009,7 +3008,7 @@ construct_dfa_states (struct REGEX_INTERNAL_Context *ctx,
3009 3008
3010 for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next) 3009 for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
3011 { 3010 {
3012 if ((NULL == ctran->label) ||(NULL != ctran->to_state) ) 3011 if ((NULL == ctran->label) || (NULL != ctran->to_state) )
3013 continue; 3012 continue;
3014 3013
3015 nfa_closure_set_create (&tmp, nfa, &dfa_state->nfa_set, ctran->label); 3014 nfa_closure_set_create (&tmp, nfa, &dfa_state->nfa_set, ctran->label);
@@ -3173,7 +3172,7 @@ evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
3173 s = a->start; 3172 s = a->start;
3174 3173
3175 /* If the string is empty but the starting state is accepting, we accept. */ 3174 /* If the string is empty but the starting state is accepting, we accept. */
3176 if (((NULL == string)||(0 == strlen (string))) && s->accepting) 3175 if (((NULL == string) || (0 == strlen (string))) && s->accepting)
3177 return 0; 3176 return 0;
3178 3177
3179 for (strp = string; NULL != strp && *strp; strp += step_len) 3178 for (strp = string; NULL != strp && *strp; strp += step_len)
@@ -3184,7 +3183,7 @@ evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
3184 break; 3183 break;
3185 } 3184 }
3186 3185
3187 if ((NULL != s)&& s->accepting) 3186 if ((NULL != s) && s->accepting)
3188 return 0; 3187 return 0;
3189 3188
3190 return 1; 3189 return 1;
@@ -3218,7 +3217,7 @@ evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
3218 } 3217 }
3219 3218
3220 /* If the string is empty but the starting state is accepting, we accept. */ 3219 /* If the string is empty but the starting state is accepting, we accept. */
3221 if (((NULL == string)||(0 == strlen (string))) && a->start->accepting) 3220 if (((NULL == string) || (0 == strlen (string))) && a->start->accepting)
3222 return 0; 3221 return 0;
3223 3222
3224 result = 1; 3223 result = 1;
@@ -3644,7 +3643,7 @@ reachability_iterator (void *cls,
3644 /* already visited and marked */ 3643 /* already visited and marked */
3645 return GNUNET_YES; 3644 return GNUNET_YES;
3646 3645
3647 if ((GNUNET_REGEX_INITIAL_BYTES > strlen (state->proof))&& 3646 if ((GNUNET_REGEX_INITIAL_BYTES > strlen (state->proof)) &&
3648 (GNUNET_NO == state->accepting) ) 3647 (GNUNET_NO == state->accepting) )
3649 /* not directly reachable */ 3648 /* not directly reachable */
3650 return GNUNET_YES; 3649 return GNUNET_YES;
@@ -3685,6 +3684,7 @@ iterate_reachables (void *cls, const struct GNUNET_HashCode *key, void *value)
3685 return GNUNET_YES; 3684 return GNUNET_YES;
3686} 3685}
3687 3686
3687
3688/** 3688/**
3689 * Iterate over all edges of automaton 'a' that are reachable from a state with 3689 * Iterate over all edges of automaton 'a' that are reachable from a state with
3690 * a proof of at least GNUNET_REGEX_INITIAL_BYTES characters. 3690 * a proof of at least GNUNET_REGEX_INITIAL_BYTES characters.