37#define REGEX_DEBUG_DFA GNUNET_NO
88 if ((NULL == str1) != (NULL == str2))
90 if ((NULL == str1) && (NULL == str2))
93 return strcmp (str1, str2);
138 t->id =
ctx->transition_id++;
165 if ((NULL ==
state) || (NULL == transition))
173 state->transition_count--;
175 state->transitions_tail,
198 return (*s1)->
id - (*s2)->id;
224 if (NULL !=
t->to_state)
226 edges[count].
label =
t->label;
250 if ((NULL == sset1) || (NULL == sset2))
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;
402 if ((
t->to_state == s1) && (0 == strcmp (t_check->
label,
t->label)) )
483 action (action_cls, *count, s);
489 if ((NULL == check) ||
490 ((NULL != check) && (
GNUNET_YES == check (check_cls, s,
t)) ))
520 for (count = 0, s = a->
states_head; NULL != s && count < a->state_count;
521 s = s->
next, count++)
680 size_t cstr_len = strlen (cstr);
685 if (
ret->blen < cstr_len +
ret->slen)
688 ret->slen += cstr_len;
712 ret->slen + extra_chars + 1,
719 ret->blen =
ret->slen + extra_chars + 1;
720 ret->slen =
ret->slen + extra_chars;
739 if (
ret->blen < sarg->
slen + extra_chars + 1)
743 ret->slen = sarg->
slen + extra_chars;
764 if (
ret->blen < sarg1->
slen + sarg2->
slen + extra_chars + 1)
767 ret->slen = sarg1->
slen + sarg2->
slen + extra_chars;
798 if (
ret->blen < sarg1->
slen + sarg2->
slen + sarg3->
slen + extra_chars + 1)
869 out->
slen = strlen (cstr);
907 cl = memchr (pos,
')',
end - pos);
914 while ((NULL != (
op = memchr (pos,
'(',
end - pos))) && (
op < cl))
951 (
'(' != str->
sbuf[0]) || (
')' != str->
sbuf[slen - 1]))
955 end = &sbuf[slen - 1];
956 op = memchr (pos,
'(',
end - pos);
957 cp = memchr (pos,
')',
end - pos);
960 while ((NULL !=
op) && (
op < cp))
964 op = memchr (pos,
'(',
end - pos);
966 while ((NULL != cp) && ((NULL ==
op) || (cp <
op)))
972 cp = memchr (pos,
')',
end - pos);
997 (
'(' == str->
sbuf[0]) && (
'|' == str->
sbuf[1]) &&
1019 if ((str->
slen > 1) && (
'(' == str->
sbuf[0]) && (
'|' == str->
sbuf[1]) &&
1023 if (
ret->blen < str->
slen - 3)
1075 return memcmp (str1->
sbuf, str2, n);
1113 return memcmp (&str1->
sbuf[k], str2->
sbuf, str2->
slen);
1127 const unsigned int count,
1139 ((GNUNET_YES == a.null_flag) ? 6 : (int) a.slen), \
1140 ((GNUNET_YES == a.null_flag) ? "(null)" : a.sbuf)
1175 int clean_ik_kk_cmp;
1176 int clean_kk_kj_cmp;
1251 if ((0 ==
sb_strcmp (&R_temp_ij, &R_temp_ik)) &&
1252 (0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1253 (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj)))
1255 if (0 == R_temp_ij.
slen)
1273 sb_printf1 (R_cur_r,
"(%.*s)*", 3, &R_temp_ij);
1275 sb_printf1 (R_cur_r,
"%.*s*", 1, &R_temp_ij);
1287 sb_printf1 (R_cur_r,
"(%.*s)+", 3, &R_temp_ij);
1289 sb_printf1 (R_cur_r,
"%.*s+", 1, &R_temp_ij);
1292 else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) &&
1293 (0 != clean_ik_kk_cmp))
1296 if (0 == R_last_kk->
slen)
1299 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1301 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ij, R_last_kk);
1304 else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) &&
1305 (0 != clean_kk_kj_cmp))
1308 if (R_last_kk->
slen < 1)
1313 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1315 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1319 else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) &&
1324 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1326 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
1329 else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) &&
1334 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
1336 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
1354 length = R_temp_kk.
slen - R_last_ik->
slen;
1360 (0 < R_last_ik->
slen) &&
1361 (0 ==
sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
1362 (0 ==
sb_strncmp (&R_temp_kk, R_last_kj, length)))
1373 temp_a.
slen = length_l;
1375 length_r = R_last_kj->
slen - length;
1378 temp_b.
slen = length_r;
1384 sb_printf2 (R_cur_r,
"(%.*s%.*s)*", 3, R_last_ik, &temp_a);
1390 sb_printf3 (R_cur_r,
"(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
1395 else if ((0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1396 (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj)) )
1405 sb_printf1 (R_cur_r,
"(%.*s)*", 3, &R_temp_kk);
1407 sb_printf1 (R_cur_r,
"%.*s*", 1, &R_temp_kk);
1410 else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) &&
1414 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
1416 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
1432 sb_printf1 (R_cur_r,
"(%.*s)+", 3, &R_temp_kk);
1434 sb_printf1 (R_cur_r,
"%.*s+", 1, &R_temp_kk);
1442 else if (0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk))
1447 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1449 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1454 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
1456 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
1463 else if (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj))
1468 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
1470 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
1475 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
1477 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
1482 if (0 < R_temp_kk.
slen)
1505 sb_printf2 (R_cur_r,
"%.*s%.*s", 0, R_last_ik, R_last_kj);
1525 *R_cur_ij = *R_cur_l;
1535 *R_cur_ij = *R_cur_r;
1545 *R_cur_ij = *R_cur_l;
1549 sb_printf2 (R_cur_ij,
"(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
1582 if ((NULL == R_last) || (NULL == R_cur))
1598 for (i = 0; i < n; i++)
1600 for (i = 0; i < n; i++)
1601 for (j = 0; j < n; j++)
1605 for (i = 0; i < n; i++)
1607 for (
t = states[i]->transitions_head; NULL !=
t;
t =
t->
next)
1609 j =
t->to_state->dfs_id;
1623 R_last[i * n + i].
slen = 0;
1628 sb_wrap (&R_last[i * n + i],
"(|%.*s)", 3);
1631 for (i = 0; i < n; i++)
1632 for (j = 0; j < n; j++)
1634 sb_wrap (&R_last[i * n + j],
"(%.*s)", 2);
1639 for (k = 0; k < n; k++)
1641 for (i = 0; i < n; i++)
1643 for (j = 0; j < n; j++)
1665 for (i = 0; i < n; i++)
1666 for (j = 0; j < n; j++)
1672 for (i = 0; i < n; i++)
1679 strlen (states[i]->
proof),
1686 sb_init (&complete_regex, 16 * n);
1687 for (i = 0; i < n; i++)
1689 if (states[i]->accepting)
1691 if ((0 == complete_regex.
slen) &&
1709 for (i = 0; i < n; i++)
1710 for (j = 0; j < n; j++)
1742 s->
id =
ctx->state_id++;
1746 if (NULL == nfa_states)
1754 if (nfa_states->
off < 1)
1758 len = nfa_states->
off * 14 + 4;
1760 strcat (s->
name,
"{");
1763 for (i = 0; i < nfa_states->
off; i++)
1765 cstate = nfa_states->
states[i];
1767 pos += strlen (pos);
1771 if (NULL != ctran->
label)
1806 unsigned int max_len;
1813 for (
t = (*s)->transitions_head; NULL !=
t;
t =
t->
next)
1815 len = strlen (
t->label);
1817 if (0 == strncmp (
t->label, str, len))
1822 new_s =
t->to_state;
1843 const unsigned int count,
1910 if ((NULL !=
t->to_state) && (
t->to_state != s) )
1945 unsigned int num_equal_edges;
1947 unsigned int state_cnt;
1948 unsigned long long idx;
1949 unsigned long long idx1;
1954 "Could not merge nondistinguishable states, automaton was NULL.\n");
1960 (
sizeof(uint32_t) * state_cnt * state_cnt / 32) +
sizeof(uint32_t));
1976 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
1977 table[idx / 32] |= (1U << (idx % 32));
1989 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
1990 if (0 != (
table[idx / 32] & (1U << (idx % 32))))
1992 num_equal_edges = 0;
2008 if (0 != (
table[idx1 / 32] & (1U << (idx1 % 32))))
2010 table[idx / 32] |= (1U << (idx % 32));
2020 table[idx / 32] |= (1U << (idx % 32));
2028 for (s1 = a->
states_head; NULL != s1; s1 = s1_next)
2031 for (s2 = a->
states_head; NULL != s2 && s1 != s2; s2 = s2_next)
2034 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
2035 if (0 == (
table[idx / 32] & (1U << (idx % 32))))
2110 const unsigned int depth,
2119 if (depth ==
ctx->stride)
2126 ctx->transitions_tail,
2135 if (
t->to_state ==
t->from_state)
2166 const unsigned int count,
2183 const unsigned int stride_len)
2201 for (
t =
ctx.transitions_head; NULL !=
t;
t = t_next)
2233 unsigned int max_len,
2241 if ((NULL !=
label) &&
2245 ((
start != dfa->
start) && (max_len > 0) && (max_len == strlen (
2268 else if (cur !=
start)
2284 if (
t->to_state != cur)
2310 unsigned int max_len)
2327 if (NULL !=
t->to_state)
2328 t->to_state->incoming_transition_count++;
2349 for (
t = transitions_head; NULL !=
t;
t = t_next)
2390 if ((NULL ==
start) || (NULL ==
end))
2419 if ((NULL == n) || (NULL == states_head))
2432 if (NULL != states_head)
2438 for (s = states_head; NULL != s; s = s->
next)
2457 s->
id =
ctx->state_id++;
2497 for (i = 0; i < states->
off; i++)
2506 cls_stack.
head = NULL;
2507 cls_stack.
tail = NULL;
2511 while (NULL != (currentstate = cls_stack.
tail))
2519 ctran = ctran->
next)
2521 if (NULL == (clsstate = ctran->
to_state))
2537 for (i = 0; i <
ret->off; i++)
2538 ret->states[i]->contained = 0;
2560 b =
ctx->stack_tail;
2563 a =
ctx->stack_tail;
2597 a =
ctx->stack_tail;
2603 "nfa_add_star_op failed, because there was no element on the stack");
2638 a =
ctx->stack_tail;
2644 "nfa_add_plus_op failed, because there was no element on the stack");
2669 a =
ctx->stack_tail;
2674 "nfa_add_question_op failed, because there was no element on the stack");
2711 b =
ctx->stack_tail;
2714 a =
ctx->stack_tail;
2778 ctx->transition_id = 0;
2779 ctx->stack_head = NULL;
2780 ctx->stack_tail = NULL;
2799 const char *error_msg;
2801 unsigned int altcount;
2802 unsigned int atomcount;
2812 if ((NULL ==
regex) || (0 == strlen (
regex)) || (0 == len))
2815 "Could not parse regex. Empty regex string provided.\n");
2830 for (count = 0; count < len && *regexp; count++, regexp++)
2842 p[poff].altcount = altcount;
2843 p[poff].atomcount = atomcount;
2852 error_msg =
"Cannot append '|' to nothing";
2855 while (--atomcount > 0)
2863 error_msg =
"Missing opening '('";
2870 altcount =
p[poff].altcount;
2871 atomcount =
p[poff].atomcount;
2874 while (--atomcount > 0)
2876 for (; altcount > 0; altcount--)
2879 altcount =
p[poff].altcount;
2880 atomcount =
p[poff].atomcount;
2887 error_msg =
"Cannot append '*' to nothing";
2896 error_msg =
"Cannot append '+' to nothing";
2905 error_msg =
"Cannot append '?' to nothing";
2917 curlabel[0] = *regexp;
2925 error_msg =
"Unbalanced parenthesis";
2928 while (--atomcount > 0)
2930 for (; altcount > 0; altcount--)
2935 nfa =
ctx.stack_tail;
2938 if (NULL !=
ctx.stack_head)
2940 error_msg =
"Creating the NFA failed. NFA stack was not empty!";
2962 if (NULL != error_msg)
2967 while (NULL != (nfa =
ctx.stack_head))
3008 state_contains = NULL;
3009 for (state_iter = dfa->
states_head; NULL != state_iter;
3010 state_iter = state_iter->
next)
3014 state_contains = state_iter;
3018 if (NULL == state_contains)
3037 unsigned int max_path_len)
3053 "Could not create DFA, because NFA creation failed\n");
3087 if (1 != max_path_len)
3106 for (s = a->
states_head; NULL != s; s = next_state)
3108 next_state = s->
next;
3130 unsigned int step_len;
3135 "Tried to evaluate DFA, but NFA automaton given");
3142 if (((NULL ==
string) || (0 == strlen (
string))) && s->
accepting)
3145 for (strp =
string; NULL != strp && *strp; strp += step_len)
3182 "Tried to evaluate NFA, but DFA automaton given");
3187 if (((NULL ==
string) || (0 == strlen (
string))) && a->
start->
accepting)
3197 for (strp =
string; NULL != strp && *strp; strp++)
3206 for (i = 0; i < sset.
off; i++)
3238 "Evaluating regex failed, automaton has no type!\n");
3267 unsigned int t_count;
3300 if (NULL == input_string)
3323 unsigned int max_len,
3324 char *consumed_string,
3331 unsigned int num_edges =
state->transition_count;
3336 unsigned int cur_len;
3338 if (NULL != consumed_string)
3339 cur_len = strlen (consumed_string);
3344 (cur_len > 0) && (NULL != consumed_string))
3346 if (cur_len <= max_len)
3348 if ((NULL !=
state->proof) &&
3349 (0 != strcmp (consumed_string,
state->proof)))
3354 "Start state for string `%s' is %s\n",
3357 iterator (iterator_cls,
3366 (
state->transition_count < 1) && (cur_len < max_len))
3370 edge[0].
label = &consumed_string[cur_len - 1];
3373 temp[cur_len - 1] =
'\0';
3376 "Start state for short string `%s' is %s\n",
3379 iterator (iterator_cls, &hash_new, temp,
GNUNET_NO, 1, edge);
3386 edge[0].
label = &consumed_string[max_len];
3389 temp[max_len] =
'\0';
3392 "Start state at split edge `%s'-`%s` is %s\n",
3396 iterator (iterator_cls, &hash, temp,
GNUNET_NO, 1, edge);
3401 if (cur_len < max_len)
3405 if (NULL != strchr (
t->label, (
int)
'.'))
3411 if (NULL != consumed_string)
3453 unsigned int num_edges;
3456 if (((NULL != s->proof) && (0 < strlen (s->proof))) || s->accepting)
3459 "Creating DFA edges at `%s' under key %s\n",
3462 iterator (iterator_cls,
3516 unsigned int num_edges,
3560 for (i = 0; i <
state->num_edges; i++)
static struct GNUNET_ARM_Operation * op
Current operation.
static int start
Set if we are to start default services (including ARM).
static int ret
Final status code.
static int end
Set if we are to shutdown all services (including ARM).
struct GNUNET_HashCode key
The key used in the DHT.
static struct GNUNET_FS_Handle * ctx
static char * value
Value of the record to add/remove.
enum State state
current state of profiling
static int result
Global testing status.
static struct GNUNET_OS_Process * p
Helper process we started.
static struct GNUNET_SCHEDULER_Task * t
Main task.
API to access regex service to advertise capabilities via regex and discover respective peers using m...
#define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element)
Remove an element from a MDLL.
#define GNUNET_CONTAINER_MDLL_insert_tail(mdll, head, tail, element)
Insert an element at the tail of a MDLL.
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
#define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element)
Insert an element into a DLL before the given other element.
#define GNUNET_CONTAINER_MDLL_insert(mdll, head, tail, element)
Insert an element at the head of a MDLL.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
#define GNUNET_CONTAINER_DLL_insert(head, tail, element)
Insert an element at the head of a DLL.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
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.
enum GNUNET_GenericReturnValue 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.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
, ' bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE...
#define GNUNET_log(kind,...)
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#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...
@ GNUNET_ERROR_TYPE_ERROR
@ GNUNET_ERROR_TYPE_DEBUG
int int GNUNET_asprintf(char **buf, const char *format,...) __attribute__((format(printf
Like asprintf, just portable.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_strndup(a, length)
Wrapper around GNUNET_xstrndup_.
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.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_realloc(ptr, size)
Wrapper around realloc.
#define GNUNET_free(ptr)
Wrapper around free.
#define GNUNET_REGEX_INITIAL_BYTES
Constant for how many bytes the initial string regex should have.
static struct PeerEntry ** table
Table with our interned peer IDs.
static unsigned int size
Size of the "table".
static void sb_strdup_cstr(struct StringBuffer *out, const char *cstr)
Copy the given string buffer from 'in' to 'out'.
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.
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.
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.
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 state_set_clear(struct REGEX_INTERNAL_StateSet *set)
Clears the given StateSet 'set'.
static void nfa_add_concatenation(struct REGEX_INTERNAL_Context *ctx)
Pops two NFA fragments (a, b) from the stack and concatenates them (ab)
static void remove_parentheses(struct StringBuffer *str)
Remove parentheses surrounding string str.
static void sb_printf1(struct StringBuffer *ret, const char *format, size_t extra_chars, const struct StringBuffer *sarg)
Format a string buffer.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
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_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.
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 sb_append(struct StringBuffer *ret, const struct StringBuffer *sarg)
Append a string.
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'.
static void sb_free(struct StringBuffer *sb)
Free resources of the given string buffer.
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 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'.
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 state_set_append(struct REGEX_INTERNAL_StateSet *set, struct REGEX_INTERNAL_State *state)
Append state to the given StateSet.
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'.
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.
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,...
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.
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'.
int REGEX_INTERNAL_eval(struct REGEX_INTERNAL_Automaton *a, const char *string)
Evaluates the given 'string' against the given compiled regex.
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 nullstrcmp(const char *str1, const char *str2)
Compare two strings for equality.
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'.
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...
static void sb_append_cstr(struct StringBuffer *ret, const char *cstr)
Append a C string.
const char * REGEX_INTERNAL_get_canonical_regex(struct REGEX_INTERNAL_Automaton *a)
Get the canonical regex of the given automaton.
static int sb_nullstrcmp(const struct StringBuffer *s1, const struct StringBuffer *s2)
Compare two strings for equality.
static int automaton_create_proofs(struct REGEX_INTERNAL_Automaton *a)
Create proofs for all states in the given automaton.
static int state_compare(const void *a, const void *b)
Compare two states.
static void dfa_remove_dead_states(struct REGEX_INTERNAL_Automaton *a)
Remove all dead states from the DFA 'a'.
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.
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...
static void remove_epsilon(const struct StringBuffer *str, struct StringBuffer *ret)
Remove an epsilon from the string str.
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 void sb_strdup(struct StringBuffer *out, const struct StringBuffer *in)
Copy the given string buffer from 'in' to 'out'.
static int evaluate_dfa(struct REGEX_INTERNAL_Automaton *a, const char *string)
Evaluates the given string using the given DFA automaton.
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.
static int iterate_reachables(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
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.
static 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.
static unsigned int state_get_edges(struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges)
Get all edges leaving state s.
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)}...
static int sb_strcmp(const struct StringBuffer *s1, const struct StringBuffer *s2)
Compare two strings for equality.
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 evaluate_nfa(struct REGEX_INTERNAL_Automaton *a, const char *string)
Evaluates the given string using the given NFA automaton.
static int sb_strncmp(const struct StringBuffer *str1, const struct StringBuffer *str2, size_t n)
Compare n bytes of 'str1' and 'str2'.
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.
static void state_remove_transition(struct REGEX_INTERNAL_State *state, struct REGEX_INTERNAL_Transition *transition)
Remove a 'transition' from 'state'.
static struct REGEX_INTERNAL_State * nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting)
Creates a new NFA state.
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.
static void mark_states(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Set the given state 'marked' to GNUNET_YES.
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.
static void dfa_remove_unreachable_states(struct REGEX_INTERNAL_Automaton *a)
Remove all unreachable states from DFA 'a'.
void REGEX_INTERNAL_automaton_destroy(struct REGEX_INTERNAL_Automaton *a)
Free the memory allocated by constructing the REGEX_INTERNAL_Automaton.
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'.
unsigned int REGEX_INTERNAL_get_transition_count(struct REGEX_INTERNAL_Automaton *a)
Get the number of transitions that are contained in the given automaton.
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*)
static int has_epsilon(const struct StringBuffer *str)
Check if the string 'str' starts with an epsilon (empty string).
static void automaton_destroy_state(struct REGEX_INTERNAL_State *s)
Frees the memory used by State s.
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'.
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...
static void sb_init(struct StringBuffer *sb, size_t n)
Initialize string buffer for storing strings of up to n characters.
static void nfa_add_label(struct REGEX_INTERNAL_Context *ctx, const char *label)
Adds a new nfa fragment to the stack.
static int sb_strkcmp(const struct StringBuffer *str1, const struct StringBuffer *str2, size_t k)
Compare 'str1', starting from position 'k', with whole 'str2'.
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 automaton_remove_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Remove a state from the given automaton 'a'.
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 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-...
static void REGEX_INTERNAL_context_init(struct REGEX_INTERNAL_Context *ctx)
Initialize a new context.
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+)
static void automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a)
Clears an automaton fragment.
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.
int(* REGEX_INTERNAL_traverse_check)(void *cls, struct REGEX_INTERNAL_State *s, struct REGEX_INTERNAL_Transition *t)
Function that gets passed to automaton traversal and is called before each next traversal from state ...
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.
library to parse regular expressions into dfa
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.
Internal representation of the hash map.
struct GNUNET_SCHEDULER_Task * next
This is a linked list.
const char * label
Label of the edge.
struct GNUNET_HashCode destination
Destination of the edge.
Automaton representation.
struct REGEX_INTERNAL_State * start
First state of the automaton.
char * canonical_regex
Canonical regex (result of RX->NFA->DFA->RX)
int is_multistrided
GNUNET_YES, if multi strides have been added to the Automaton.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
enum REGEX_INTERNAL_AutomatonType type
Type of the automaton.
Context that contains an id counter for states and transitions as well as a DLL of automatons used as...
Set of states using MDLL API.
struct REGEX_INTERNAL_State * head
MDLL of states.
struct REGEX_INTERNAL_State * tail
MDLL of states.
unsigned int len
Length of the MDLL.
unsigned int size
Length of the 'states' array.
struct REGEX_INTERNAL_State ** states
Array of states.
unsigned int off
Number of entries in use in the 'states' array.
unsigned int incoming_transition_count
Number of incoming transitions.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
char * proof
Proof for this state.
unsigned int transition_count
Number of transitions from this state to other states.
unsigned int traversal_id
Unique state id that is used for traversing the automaton.
struct REGEX_INTERNAL_StateSet nfa_set
Set of states on which this state is based on.
unsigned int dfs_id
Linear state ID acquired by depth-first-search.
char * name
Human readable name of the state.
int marked
Marking of the state.
unsigned int id
Unique state id.
struct REGEX_INTERNAL_Transition * transitions_tail
DLL of transitions.
int accepting
If this is an accepting state or not.
int lowlink
Used for SCC detection.
int contained
Marking the state as contained.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
int index
Used for SCC detection.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
Context for adding strided transitions to a DFA.
struct REGEX_INTERNAL_Transition * transitions_tail
Strided transitions DLL.
struct REGEX_INTERNAL_Transition * transitions_head
Strided transitions DLL.
const unsigned int stride
Length of the strides.
Transition between two states.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
char * label
Label for this transition.
String container for faster string operations.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
size_t slen
Length of the string in the buffer.
unsigned int blen
Number of bytes allocated for sbuf.
char * abuf
Allocated buffer.
int16_t synced
If this entry is part of the last/current generation array, this flag is GNUNET_YES if the last and c...
Store regex iterator and cls in one place to pass to the hashmap iterator.
REGEX_INTERNAL_KeyIterator iterator
Struct to hold all the relevant state information in the HashMap.
struct REGEX_BLOCK_Edge * edges