37 #define REGEX_DEBUG_DFA GNUNET_NO 71 if (set->off == set->size)
73 set->states[
set->off++] =
state;
88 if ((NULL == str1) != (NULL == str2))
90 if ((NULL == str1) && (NULL == str2))
93 return strcmp (str1, str2);
115 if (NULL == from_state)
165 if ((NULL == state) || (NULL == transition))
198 return (*s1)->
id - (*s2)->id;
250 if ((NULL == sset1) || (NULL == sset2))
253 result = sset1->
off - sset2->
off;
258 for (i = 0; i < sset1->
off; i++)
342 if ((NULL == a) || (NULL == s))
346 for (s_check = a->
states_head; NULL != s_check; s_check = s_check->
next)
349 t_check = t_check_next)
351 t_check_next = t_check->
next;
391 for (s_check = a->
states_head; NULL != s_check; s_check = s_check->
next)
393 for (t_check = s_check->
transitions_head; NULL != t_check; t_check = t_next)
395 t_next = t_check->
next;
483 action (action_cls, *count, s);
489 if ((NULL == check) ||
490 ((NULL != check) && (
GNUNET_YES == check (check_cls, s, t)) ))
533 for (count = 0, s = a->
states_head; NULL != s && count < a->state_count;
534 s = s->
next, count++)
693 size_t cstr_len = strlen (cstr);
698 if (ret->
blen < cstr_len + ret->
slen)
701 ret->
slen += cstr_len;
725 ret->
slen + extra_chars + 1,
732 ret->
blen = ret->
slen + extra_chars + 1;
733 ret->
slen = ret->
slen + extra_chars;
752 if (ret->
blen < sarg->
slen + extra_chars + 1)
756 ret->
slen = sarg->
slen + extra_chars;
777 if (ret->
blen < sarg1->
slen + sarg2->
slen + extra_chars + 1)
882 out->
slen = strlen (cstr);
915 end = str->
sbuf + slen;
920 cl = memchr (pos,
')', end - pos);
927 while ((NULL != (op = memchr (pos,
'(', end - pos))) && (op < cl))
964 (
'(' != str->
sbuf[0]) || (
')' != str->
sbuf[slen - 1]))
968 end = &sbuf[slen - 1];
969 op = memchr (pos,
'(', end - pos);
970 cp = memchr (pos,
')', end - pos);
973 while ((NULL != op) && (op < cp))
977 op = memchr (pos,
'(', end - pos);
979 while ((NULL != cp) && ((NULL == op) || (cp < op)))
985 cp = memchr (pos,
')', end - pos);
1010 (
'(' == str->
sbuf[0]) && (
'|' == str->
sbuf[1]) &&
1032 if ((str->
slen > 1) && (
'(' == str->
sbuf[0]) && (
'|' == str->
sbuf[1]) &&
1070 return memcmp (str1->
sbuf, str2->
sbuf, max);
1088 return memcmp (str1->
sbuf, str2, n);
1126 return memcmp (&str1->
sbuf[k], str2->
sbuf, str2->
slen);
1140 const unsigned int count,
1152 ((GNUNET_YES == a.null_flag) ? 6 : (int) a.slen), \ 1153 ((GNUNET_YES == a.null_flag) ? "(null)" : a.sbuf) 1188 int clean_ik_kk_cmp;
1189 int clean_kk_kj_cmp;
1264 if ((0 ==
sb_strcmp (&R_temp_ij, &R_temp_ik)) &&
1265 (0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1266 (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj)))
1268 if (0 == R_temp_ij.
slen)
1285 sb_printf1 (R_cur_r,
"(%.*s)*", 3, &R_temp_ij);
1287 sb_printf1 (R_cur_r,
"%.*s*", 1, &R_temp_ij);
1298 sb_printf1 (R_cur_r,
"(%.*s)+", 3, &R_temp_ij);
1300 sb_printf1 (R_cur_r,
"%.*s+", 1, &R_temp_ij);
1303 else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) &&
1304 (0 != clean_ik_kk_cmp))
1307 if (0 == R_last_kk->
slen)
1310 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1312 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ij, R_last_kk);
1315 else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) &&
1316 (0 != clean_kk_kj_cmp))
1319 if (R_last_kk->
slen < 1)
1324 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1326 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1330 else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) &&
1335 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1337 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
1340 else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) &&
1345 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
1347 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
1365 length = R_temp_kk.
slen - R_last_ik->
slen;
1371 (0 < R_last_ik->
slen) &&
1372 (0 ==
sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
1373 (0 ==
sb_strncmp (&R_temp_kk, R_last_kj, length)))
1384 temp_a.
slen = length_l;
1386 length_r = R_last_kj->
slen - length;
1389 temp_b.
slen = length_r;
1395 sb_printf2 (R_cur_r,
"(%.*s%.*s)*", 3, R_last_ik, &temp_a);
1401 sb_printf3 (R_cur_r,
"(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
1406 else if ((0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1407 (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj)) )
1416 sb_printf1 (R_cur_r,
"(%.*s)*", 3, &R_temp_kk);
1418 sb_printf1 (R_cur_r,
"%.*s*", 1, &R_temp_kk);
1421 else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) &&
1425 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
1427 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
1442 sb_printf1 (R_cur_r,
"(%.*s)+", 3, &R_temp_kk);
1444 sb_printf1 (R_cur_r,
"%.*s+", 1, &R_temp_kk);
1452 else if (0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk))
1457 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1459 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1464 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
1466 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
1473 else if (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj))
1478 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
1480 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
1485 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
1487 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
1492 if (0 < R_temp_kk.
slen)
1515 sb_printf2 (R_cur_r,
"%.*s%.*s", 0, R_last_ik, R_last_kj);
1535 *R_cur_ij = *R_cur_l;
1545 *R_cur_ij = *R_cur_r;
1555 *R_cur_ij = *R_cur_l;
1559 sb_printf2 (R_cur_ij,
"(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
1592 if ((NULL == R_last) || (NULL == R_cur))
1608 for (i = 0; i < n; i++)
1610 for (i = 0; i < n; i++)
1611 for (j = 0; j < n; j++)
1615 for (i = 0; i < n; i++)
1617 for (t = states[i]->transitions_head; NULL !=
t; t = t->
next)
1633 R_last[i * n + i].
slen = 0;
1638 sb_wrap (&R_last[i * n + i],
"(|%.*s)", 3);
1641 for (i = 0; i < n; i++)
1642 for (j = 0; j < n; j++)
1644 sb_wrap (&R_last[i * n + j],
"(%.*s)", 2);
1649 for (k = 0; k < n; k++)
1651 for (i = 0; i < n; i++)
1653 for (j = 0; j < n; j++)
1675 for (i = 0; i < n; i++)
1676 for (j = 0; j < n; j++)
1682 for (i = 0; i < n; i++)
1689 strlen (states[i]->
proof),
1696 sb_init (&complete_regex, 16 * n);
1697 for (i = 0; i < n; i++)
1699 if (states[i]->accepting)
1701 if ((0 == complete_regex.
slen) &&
1719 for (i = 0; i < n; i++)
1720 for (j = 0; j < n; j++)
1756 if (NULL == nfa_states)
1764 if (nfa_states->
off < 1)
1768 len = nfa_states->
off * 14 + 4;
1770 strcat (s->
name,
"{");
1773 for (i = 0; i < nfa_states->
off; i++)
1775 cstate = nfa_states->
states[i];
1777 pos += strlen (pos);
1781 if (NULL != ctran->
label)
1816 unsigned int max_len;
1823 for (t = (*s)->transitions_head; NULL != t; t = t->
next)
1825 len = strlen (t->
label);
1827 if (0 == strncmp (t->
label, str, len))
1853 const unsigned int count,
1955 unsigned int num_equal_edges;
1957 unsigned int state_cnt;
1958 unsigned long long idx;
1959 unsigned long long idx1;
1964 "Could not merge nondistinguishable states, automaton was NULL.\n");
1970 (
sizeof(uint32_t) * state_cnt * state_cnt / 32) +
sizeof(uint32_t));
1986 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
1987 table[idx / 32] |= (1U << (idx % 32));
1999 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
2000 if (0 != (table[idx / 32] & (1U << (idx % 32))))
2002 num_equal_edges = 0;
2018 if (0 != (table[idx1 / 32] & (1U << (idx1 % 32))))
2020 table[idx / 32] |= (1U << (idx % 32));
2030 table[idx / 32] |= (1U << (idx % 32));
2038 for (s1 = a->
states_head; NULL != s1; s1 = s1_next)
2041 for (s2 = a->
states_head; NULL != s2 && s1 != s2; s2 = s2_next)
2044 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
2045 if (0 == (table[idx / 32] & (1U << (idx % 32))))
2120 const unsigned int depth,
2129 if (depth == ctx->
stride)
2176 const unsigned int count,
2193 const unsigned int stride_len)
2243 unsigned int max_len,
2251 if ((NULL != label) &&
2255 ((start != dfa->
start) && (max_len > 0) && (max_len == strlen (
2278 else if (cur != start)
2320 unsigned int max_len)
2359 for (t = transitions_head; NULL !=
t; t = t_next)
2400 if ((NULL == start) || (NULL == end))
2429 if ((NULL == n) || (NULL == states_head))
2442 if (NULL != states_head)
2448 for (s = states_head; NULL != s; s = s->
next)
2507 for (i = 0; i < states->
off; i++)
2516 cls_stack.
head = NULL;
2517 cls_stack.
tail = NULL;
2521 while (NULL != (currentstate = cls_stack.
tail))
2529 ctran = ctran->
next)
2531 if (NULL == (clsstate = ctran->
to_state))
2547 for (i = 0; i < ret->
off; i++)
2613 "nfa_add_star_op failed, because there was no element on the stack");
2654 "nfa_add_plus_op failed, because there was no element on the stack");
2684 "nfa_add_question_op failed, because there was no element on the stack");
2811 unsigned int altcount;
2812 unsigned int atomcount;
2822 if ((NULL == regex) || (0 == strlen (regex)) || (0 == len))
2825 "Could not parse regex. Empty regex string provided.\n");
2840 for (count = 0; count < len && *regexp; count++, regexp++)
2852 p[poff].altcount = altcount;
2853 p[poff].atomcount = atomcount;
2862 error_msg =
"Cannot append '|' to nothing";
2865 while (--atomcount > 0)
2873 error_msg =
"Missing opening '('";
2880 altcount =
p[poff].altcount;
2881 atomcount =
p[poff].atomcount;
2884 while (--atomcount > 0)
2886 for (; altcount > 0; altcount--)
2889 altcount =
p[poff].altcount;
2890 atomcount =
p[poff].atomcount;
2897 error_msg =
"Cannot append '*' to nothing";
2906 error_msg =
"Cannot append '+' to nothing";
2915 error_msg =
"Cannot append '?' to nothing";
2927 curlabel[0] = *regexp;
2935 error_msg =
"Unbalanced parenthesis";
2938 while (--atomcount > 0)
2940 for (; altcount > 0; altcount--)
2950 error_msg =
"Creating the NFA failed. NFA stack was not empty!";
2972 if (NULL != error_msg)
3018 state_contains = NULL;
3019 for (state_iter = dfa->
states_head; NULL != state_iter;
3020 state_iter = state_iter->
next)
3024 state_contains = state_iter;
3028 if (NULL == state_contains)
3064 unsigned int max_path_len)
3080 "Could not create DFA, because NFA creation failed\n");
3114 if (1 != max_path_len)
3139 for (s = a->
states_head; NULL != s; s = next_state)
3141 next_state = s->
next;
3163 unsigned int step_len;
3168 "Tried to evaluate DFA, but NFA automaton given");
3175 if (((NULL ==
string) || (0 == strlen (
string))) && s->
accepting)
3178 for (strp =
string; NULL != strp && *strp; strp += step_len)
3215 "Tried to evaluate NFA, but DFA automaton given");
3220 if (((NULL ==
string) || (0 == strlen (
string))) && a->
start->
accepting)
3230 for (strp =
string; NULL != strp && *strp; strp++)
3239 for (i = 0; i < sset.
off; i++)
3278 "Evaluating regex failed, automaton has no type!\n");
3318 unsigned int t_count;
3351 if (NULL == input_string)
3374 unsigned int max_len,
3375 char *consumed_string,
3387 unsigned int cur_len;
3389 if (NULL != consumed_string)
3390 cur_len = strlen (consumed_string);
3395 (cur_len > 0) && (NULL != consumed_string))
3397 if (cur_len <= max_len)
3399 if ((NULL != state->
proof) &&
3400 (0 != strcmp (consumed_string, state->
proof)))
3405 "Start state for string `%s' is %s\n",
3421 edge[0].
label = &consumed_string[cur_len - 1];
3424 temp[cur_len - 1] =
'\0';
3427 "Start state for short string `%s' is %s\n",
3437 edge[0].
label = &consumed_string[max_len];
3440 temp[max_len] =
'\0';
3443 "Start state at split edge `%s'-`%s` is %s\n",
3452 if (cur_len < max_len)
3456 if (NULL != strchr (t->
label, (
int)
'.'))
3462 if (NULL != consumed_string)
3504 unsigned int num_edges;
3507 if (((NULL != s->proof) && (0 < strlen (s->proof))) || s->accepting)
3510 "Creating DFA edges at `%s' under key %s\n",
3567 unsigned int num_edges,
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
unsigned int state_count
Number of states in the automaton.
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
static void store_all_states(void *cls, const struct GNUNET_HashCode *key, const char *proof, int accepting, unsigned int num_edges, const struct REGEX_BLOCK_Edge *edges)
Iterator over all edges of a dfa.
static int automaton_create_proofs(struct REGEX_INTERNAL_Automaton *a)
Create proofs for all states in the given automaton.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
static int iterate_reachables(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
unsigned int incoming_transition_count
Number of incoming transitions.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
struct GNUNET_HashCode destination
Destionation of the edge.
static void remove_epsilon(const struct StringBuffer *str, struct StringBuffer *ret)
Remove an epsilon from the string str.
int index
Used for SCC detection.
size_t REGEX_INTERNAL_get_first_key(const char *input_string, size_t string_len, struct GNUNET_HashCode *key)
Get the first key for the given input_string.
static void nfa_closure_set_create(struct REGEX_INTERNAL_StateSet *ret, struct REGEX_INTERNAL_Automaton *nfa, struct REGEX_INTERNAL_StateSet *states, const char *label)
Calculates the closure set for the given set of states.
unsigned int traversal_id
Unique state id that is used for traversing the automaton.
static int end
Set if we are to shutdown all services (including ARM).
static void dfa_remove_unreachable_states(struct REGEX_INTERNAL_Automaton *a)
Remove all unreachable states from DFA 'a'.
#define GNUNET_CONTAINER_DLL_insert(head, tail, element)
Insert an element at the head of a DLL.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
unsigned int transition_id
Unique transition id.
static void nfa_add_plus_op(struct REGEX_INTERNAL_Context *ctx)
Pops an NFA fragment (a) from the stack and adds a new fragment (a+)
struct GNUNET_HashCode hash
Hash of the state.
unsigned int REGEX_INTERNAL_get_transition_count(struct REGEX_INTERNAL_Automaton *a)
Get the number of transitions that are contained in the given automaton.
int accepting
If this is an accepting state or not.
static int state_set_compare(struct REGEX_INTERNAL_StateSet *sset1, struct REGEX_INTERNAL_StateSet *sset2)
Compare to state sets by comparing the id's of the states that are contained in each set...
unsigned int state_id
Unique state id.
struct REGEX_INTERNAL_Transition * transitions_tail
Strided transitions DLL.
static int start
Set if we are to start default services (including ARM).
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
enum REGEX_INTERNAL_AutomatonType type
Type of the automaton.
#define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element)
Insert an element into a DLL before the given other element.
static int evaluate_nfa(struct REGEX_INTERNAL_Automaton *a, const char *string)
Evaluates the given string using the given NFA automaton.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
struct REGEX_INTERNAL_Automaton * REGEX_INTERNAL_construct_nfa(const char *regex, const size_t len)
Construct an NFA by parsing the regex string of length 'len'.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton's used as a stack.
static void automaton_add_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Add a state to the automaton 'a', always use this function to alter the states DLL of the automaton...
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
static int ret
Return value of the commandline.
int contained
Marking the state as contained.
static void sb_printf1(struct StringBuffer *ret, const char *format, size_t extra_chars, const struct StringBuffer *sarg)
Format a string buffer.
static void state_set_clear(struct REGEX_INTERNAL_StateSet *set)
Clears the given StateSet 'set'.
struct REGEX_INTERNAL_StateSet nfa_set
Set of states on which this state is based on.
static void nfa_add_star_op(struct REGEX_INTERNAL_Context *ctx)
Pops a NFA fragment from the stack (a) and adds a new fragment (a*)
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#define GNUNET_new(type)
Allocate a struct or union of the given type.
Automaton representation.
static void automaton_create_proofs_simplify(const struct StringBuffer *R_last_ij, const struct StringBuffer *R_last_ik, const struct StringBuffer *R_last_kk, const struct StringBuffer *R_last_kj, struct StringBuffer *R_cur_ij, struct StringBuffer *R_cur_l, struct StringBuffer *R_cur_r)
Construct the regular expression given the inductive step, $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}...
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
static void automaton_destroy_state(struct REGEX_INTERNAL_State *s)
Frees the memory used by State s.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
char * proof
Proof for this state.
int marked
Marking of the state.
Internal representation of the hash map.
static unsigned int dfa_move(struct REGEX_INTERNAL_State **s, const char *str)
Move from the given state 's' to the next state on transition 'str'.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
static void dfa_add_multi_strides(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Function called for each state in the DFA.
static void mark_as_reachable(struct temporal_state_store *state, struct GNUNET_CONTAINER_MultiHashMap *hm)
Mark state as reachable and call recursively on all its edges.
static void nfa_add_alternation(struct REGEX_INTERNAL_Context *ctx)
Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment that alternates between a an...
struct REGEX_INTERNAL_State * states_tail
DLL of states.
void * GNUNET_CONTAINER_multihashmap_get(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Given a key find a value in the map matching the key.
int GNUNET_snprintf(char *buf, size_t size, const char *format,...) __attribute__((format(printf
Like snprintf, just aborts if the buffer is of insufficient size.
struct REGEX_INTERNAL_State * head
MDLL of states.
Set of states using MDLL API.
void REGEX_INTERNAL_automaton_traverse(const struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *start, REGEX_INTERNAL_traverse_check check, void *check_cls, REGEX_INTERNAL_traverse_action action, void *action_cls)
Traverses the given automaton using depth-first-search (DFS) from it's start state, visiting all reachable states and calling 'action' on each one of them.
#define GNUNET_log_strerror(level, cmd)
Log an error message at log-level 'level' that indicates a failure of the command 'cmd' with the mess...
static void sb_strdup(struct StringBuffer *out, const struct StringBuffer *in)
Copy the given string buffer from 'in' to 'out'.
Context that contains an id counter for states and transitions as well as a DLL of automatons used as...
#define GNUNET_CONTAINER_MDLL_insert(mdll, head, tail, element)
Insert an element at the head of a MDLL.
#define GNUNET_CONTAINER_MDLL_insert_tail(mdll, head, tail, element)
Insert an element at the tail of a MDLL.
static void sb_append(struct StringBuffer *ret, const struct StringBuffer *sarg)
Append a string.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
enum State state
current state of profiling
static struct GNUNET_OS_Process * p
Helper process we started.
, ' bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_...
Store regex iterator and cls in one place to pass to the hashmap iterator.
static char * value
Value of the record to add/remove.
const unsigned int stride
Length of the strides.
library to parse regular expressions into dfa
char * name
Human readable name of the state.
static void sb_printf2(struct StringBuffer *ret, const char *format, size_t extra_chars, const struct StringBuffer *sarg1, const struct StringBuffer *sarg2)
Format a string buffer.
unsigned int transition_count
Number of transitions from this state to other states.
static int state_compare(const void *a, const void *b)
Compare two states.
static void sb_strdup_cstr(struct StringBuffer *out, const char *cstr)
Copy the given string buffer from 'in' to 'out'.
#define GNUNET_realloc(ptr, size)
Wrapper around realloc.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
static void sb_wrap(struct StringBuffer *ret, const char *format, size_t extra_chars)
Wrap a string buffer, that is, set ret to the format string which contains an "%s" which is to be rep...
static int nullstrcmp(const char *str1, const char *str2)
Compare two strings for equality.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
static struct PeerEntry ** table
Table with our interned peer IDs.
#define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element)
Remove an element from a MDLL.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
static void dfa_remove_dead_states(struct REGEX_INTERNAL_Automaton *a)
Remove all dead states from the DFA 'a'.
void(* REGEX_INTERNAL_KeyIterator)(void *cls, const struct GNUNET_HashCode *key, const char *proof, int accepting, unsigned int num_edges, const struct REGEX_BLOCK_Edge *edges)
Iterator callback function.
void REGEX_INTERNAL_dfa_add_multi_strides(struct REGEX_INTERNAL_Context *regex_ctx, struct REGEX_INTERNAL_Automaton *dfa, const unsigned int stride_len)
Adds multi-strided transitions to the given 'dfa'.
static void iterate_initial_edge(unsigned int min_len, unsigned int max_len, char *consumed_string, struct REGEX_INTERNAL_State *state, REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
Recursive function that calls the iterator for each synthetic start state.
struct REGEX_INTERNAL_State ** states
Array of states.
static int result
Global testing status.
static void REGEX_INTERNAL_context_init(struct REGEX_INTERNAL_Context *ctx)
Initialize a new context.
Transition between two states.
static void sb_init(struct StringBuffer *sb, size_t n)
Initialize string buffer for storing strings of up to n characters.
static void automaton_merge_states(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s1, struct REGEX_INTERNAL_State *s2)
Merge two states into one.
Struct to hold all the relevant state information in the HashMap.
#define GNUNET_REGEX_INITIAL_BYTES
Constant for how many bytes the initial string regex should have.
int16_t synced
If this entry is part of the last/current generation array, this flag is GNUNET_YES if the last and c...
static struct REGEX_INTERNAL_State * dfa_state_create(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_StateSet *nfa_states)
Creates a new DFA state based on a set of NFA states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
static int evaluate_dfa(struct REGEX_INTERNAL_Automaton *a, const char *string)
Evaluates the given string using the given DFA automaton.
int int GNUNET_asprintf(char **buf, const char *format,...) __attribute__((format(printf
Like asprintf, just portable.
static int reachability_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries to mark the ones that are reachable.
static int sb_nullstrcmp(const struct StringBuffer *s1, const struct StringBuffer *s2)
Compare two strings for equality.
static void state_set_append(struct REGEX_INTERNAL_StateSet *set, struct REGEX_INTERNAL_State *state)
Append state to the given StateSet.
static void sb_printf3(struct StringBuffer *ret, const char *format, size_t extra_chars, const struct StringBuffer *sarg1, const struct StringBuffer *sarg2, const struct StringBuffer *sarg3)
Format a string buffer.
struct GNUNET_HashCode key
The key used in the DHT.
static unsigned int size
Size of the "table".
static void state_add_transition(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_State *from_state, const char *label, struct REGEX_INTERNAL_State *to_state)
Adds a transition from one state to another on label.
Context for adding strided transitions to a DFA.
static int sb_strncmp(const struct StringBuffer *str1, const struct StringBuffer *str2, size_t n)
Compare n bytes of 'str1' and 'str2'.
static void construct_dfa_states(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_Automaton *nfa, struct REGEX_INTERNAL_Automaton *dfa, struct REGEX_INTERNAL_State *dfa_state)
Create DFA states based on given 'nfa' and starting with 'dfa_state'.
static void nfa_add_question_op(struct REGEX_INTERNAL_Context *ctx)
Pops an NFA fragment (a) from the stack and adds a new fragment (a?)
static int dfa_minimize(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_Automaton *a)
Minimize the given DFA 'a' by removing all unreachable states, removing all dead states and merging a...
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
void REGEX_INTERNAL_automaton_destroy(struct REGEX_INTERNAL_Automaton *a)
Free the memory allocated by constructing the REGEX_INTERNAL_Automaton data structure.
unsigned int off
Number of entries in use in the 'states' array.
void REGEX_INTERNAL_iterate_all_edges(struct REGEX_INTERNAL_Automaton *a, REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
Iterate over all edges starting from start state of automaton 'a'.
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
static int has_epsilon(const struct StringBuffer *str)
Check if the string 'str' starts with an epsilon (empty string).
struct REGEX_BLOCK_Edge * edges
const char * label
Label of the edge.
static int sb_strncmp_cstr(const struct StringBuffer *str1, const char *str2, size_t n)
Compare n bytes of 'str1' and 'str2'.
static void automaton_remove_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Remove a state from the given automaton 'a'.
void(* REGEX_INTERNAL_traverse_action)(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Function that is called with each state, when traversing an automaton.
#define GNUNET_strndup(a, length)
Wrapper around GNUNET_xstrndup_.
unsigned int id
Unique id of this transition.
const char * REGEX_INTERNAL_get_canonical_regex(struct REGEX_INTERNAL_Automaton *a)
Get the canonical regex of the given automaton.
static unsigned int state_get_edges(struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges)
Get all edges leaving state s.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
int is_multistrided
GNUNET_YES, if multi strides have been added to the Automaton.
int REGEX_INTERNAL_eval(struct REGEX_INTERNAL_Automaton *a, const char *string)
Evaluates the given string against the given compiled regex a.
static struct GNUNET_OS_Process * child
The child process we spawn.
static void state_remove_transition(struct REGEX_INTERNAL_State *state, struct REGEX_INTERNAL_Transition *transition)
Remove a 'transition' from 'state'.
static void nfa_add_states(struct REGEX_INTERNAL_Automaton *n, struct REGEX_INTERNAL_State *states_head, struct REGEX_INTERNAL_State *states_tail)
Adds a list of states to the given automaton 'n'.
static int sb_strcmp(const struct StringBuffer *s1, const struct StringBuffer *s2)
Compare two strings for equality.
unsigned int dfs_id
Linear state ID accquired by depth-first-search.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
struct REGEX_INTERNAL_Automaton * REGEX_INTERNAL_construct_dfa(const char *regex, const size_t len, unsigned int max_path_len)
Construct DFA for the given 'regex' of length 'len'.
char * canonical_regex
Canonical regex (result of RX->NFA->DFA->RX)
#define GNUNET_log(kind,...)
static void nfa_add_concatenation(struct REGEX_INTERNAL_Context *ctx)
Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
REGEX_INTERNAL_KeyIterator iterator
static void automaton_state_traverse(struct REGEX_INTERNAL_State *s, int *marks, unsigned int *count, REGEX_INTERNAL_traverse_check check, void *check_cls, REGEX_INTERNAL_traverse_action action, void *action_cls)
Depth-first traversal (DFS) of all states that are reachable from state 's'.
static void mark_states(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Set the given state 'marked' to GNUNET_YES.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
char * label
Label for this transition.
int(* REGEX_INTERNAL_traverse_check)(void *cls, struct REGEX_INTERNAL_State *s, struct REGEX_INTERNAL_Transition *t)
Function that get's passed to automaton traversal and is called before each next traversal from state...
static void automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a)
Clears an automaton fragment.
static void sb_free(struct StringBuffer *sb)
Free resources of the given string buffer.
void REGEX_INTERNAL_iterate_reachable_edges(struct REGEX_INTERNAL_Automaton *a, REGEX_INTERNAL_KeyIterator iterator, void *iterator_cls)
Iterate over all edges of automaton 'a' that are reachable from a state with a proof of at least GNUN...
size_t slen
Length of the string in the buffer.
String container for faster string operations.
static struct GNUNET_ARM_Operation * op
Current operation.
common internal definitions for regex library.
void dfa_compress_paths_helper(struct REGEX_INTERNAL_Automaton *dfa, struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *cur, char *label, unsigned int max_len, struct REGEX_INTERNAL_Transition **transitions_head, struct REGEX_INTERNAL_Transition **transitions_tail)
Recursive Helper function for DFA path compression.
char * abuf
Allocated buffer.
unsigned int len
Length of the MDLL.
static void sb_realloc(struct StringBuffer *ret, size_t nlen)
Reallocate the buffer of 'ret' to fit 'nlen' characters; move the existing string to the beginning of...
static void number_states(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Helper function used as 'action' in 'REGEX_INTERNAL_automaton_traverse' function to create the depth-...
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
int lowlink
Used for SCC detection.
static void remove_parentheses(struct StringBuffer *str)
Remove parentheses surrounding string str.
static int dfa_merge_nondistinguishable_states(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_Automaton *a)
Merge all non distinguishable states in the DFA 'a'.
unsigned int id
Unique state id.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
static void sb_append_cstr(struct StringBuffer *ret, const char *cstr)
Append a C string.
static int sb_strkcmp(const struct StringBuffer *str1, const struct StringBuffer *str2, size_t k)
Compare 'str1', starting from position 'k', with whole 'str2'.
#define GNUNET_malloc(size)
Wrapper around malloc.
static void dfa_compress_paths(struct REGEX_INTERNAL_Context *regex_ctx, struct REGEX_INTERNAL_Automaton *dfa, unsigned int max_len)
Compress paths in the given 'dfa'.
static int needs_parentheses(const struct StringBuffer *str)
Check if the given string str needs parentheses around it when using it to generate a regex...
#define GNUNET_free(ptr)
Wrapper around free.
struct REGEX_INTERNAL_Transition * transitions_tail
DLL of transitions.
static struct REGEX_INTERNAL_State * nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting)
Creates a new NFA state.
static void dfa_add_multi_strides_helper(void *cls, const unsigned int depth, char *label, struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *s)
Recursive helper function to add strides to a DFA.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton's used as a stack.
struct REGEX_INTERNAL_Transition * transitions_head
Strided transitions DLL.
static void nfa_add_label(struct REGEX_INTERNAL_Context *ctx, const char *label)
Adds a new nfa fragment to the stack.
struct REGEX_INTERNAL_State * tail
MDLL of states.