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)
1272 sb_printf1 (R_cur_r,
"(%.*s)*", 3, &R_temp_ij);
1274 sb_printf1 (R_cur_r,
"%.*s*", 1, &R_temp_ij);
1285 sb_printf1 (R_cur_r,
"(%.*s)+", 3, &R_temp_ij);
1287 sb_printf1 (R_cur_r,
"%.*s+", 1, &R_temp_ij);
1290 else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) &&
1291 (0 != clean_ik_kk_cmp))
1294 if (0 == R_last_kk->
slen)
1297 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1299 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ij, R_last_kk);
1302 else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) &&
1303 (0 != clean_kk_kj_cmp))
1306 if (R_last_kk->
slen < 1)
1311 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1313 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1317 else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) &&
1322 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1324 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
1327 else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) &&
1332 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
1334 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
1352 length = R_temp_kk.
slen - R_last_ik->
slen;
1358 (0 < R_last_ik->
slen) &&
1359 (0 ==
sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
1360 (0 ==
sb_strncmp (&R_temp_kk, R_last_kj, length)))
1371 temp_a.
slen = length_l;
1373 length_r = R_last_kj->
slen - length;
1376 temp_b.
slen = length_r;
1382 sb_printf2 (R_cur_r,
"(%.*s%.*s)*", 3, R_last_ik, &temp_a);
1388 sb_printf3 (R_cur_r,
"(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
1393 else if ((0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1394 (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj)) )
1403 sb_printf1 (R_cur_r,
"(%.*s)*", 3, &R_temp_kk);
1405 sb_printf1 (R_cur_r,
"%.*s*", 1, &R_temp_kk);
1408 else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) &&
1412 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
1414 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
1429 sb_printf1 (R_cur_r,
"(%.*s)+", 3, &R_temp_kk);
1431 sb_printf1 (R_cur_r,
"%.*s+", 1, &R_temp_kk);
1439 else if (0 ==
sb_strcmp (&R_temp_ik, &R_temp_kk))
1444 sb_printf2 (R_cur_r,
"(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1446 sb_printf2 (R_cur_r,
"%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1451 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
1453 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
1460 else if (0 ==
sb_strcmp (&R_temp_kk, &R_temp_kj))
1465 sb_printf2 (R_cur_r,
"%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
1467 sb_printf2 (R_cur_r,
"%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
1472 sb_printf2 (R_cur_r,
"(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
1474 sb_printf2 (R_cur_r,
"%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
1479 if (0 < R_temp_kk.
slen)
1502 sb_printf2 (R_cur_r,
"%.*s%.*s", 0, R_last_ik, R_last_kj);
1522 *R_cur_ij = *R_cur_l;
1532 *R_cur_ij = *R_cur_r;
1542 *R_cur_ij = *R_cur_l;
1546 sb_printf2 (R_cur_ij,
"(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
1579 if ((NULL == R_last) || (NULL == R_cur))
1595 for (i = 0; i < n; i++)
1597 for (i = 0; i < n; i++)
1598 for (j = 0; j < n; j++)
1602 for (i = 0; i < n; i++)
1604 for (
t = states[i]->transitions_head; NULL !=
t;
t =
t->
next)
1606 j =
t->to_state->dfs_id;
1620 R_last[i * n + i].
slen = 0;
1625 sb_wrap (&R_last[i * n + i],
"(|%.*s)", 3);
1628 for (i = 0; i < n; i++)
1629 for (j = 0; j < n; j++)
1631 sb_wrap (&R_last[i * n + j],
"(%.*s)", 2);
1636 for (k = 0; k < n; k++)
1638 for (i = 0; i < n; i++)
1640 for (j = 0; j < n; j++)
1662 for (i = 0; i < n; i++)
1663 for (j = 0; j < n; j++)
1669 for (i = 0; i < n; i++)
1676 strlen (states[i]->
proof),
1683 sb_init (&complete_regex, 16 * n);
1684 for (i = 0; i < n; i++)
1686 if (states[i]->accepting)
1688 if ((0 == complete_regex.
slen) &&
1706 for (i = 0; i < n; i++)
1707 for (j = 0; j < n; j++)
1739 s->
id =
ctx->state_id++;
1743 if (NULL == nfa_states)
1751 if (nfa_states->
off < 1)
1755 len = nfa_states->
off * 14 + 4;
1757 strcat (s->
name,
"{");
1760 for (i = 0; i < nfa_states->
off; i++)
1762 cstate = nfa_states->
states[i];
1764 pos += strlen (pos);
1768 if (NULL != ctran->
label)
1803 unsigned int max_len;
1810 for (
t = (*s)->transitions_head; NULL !=
t;
t =
t->
next)
1812 len = strlen (
t->label);
1814 if (0 == strncmp (
t->label, str, len))
1819 new_s =
t->to_state;
1840 const unsigned int count,
1907 if ((NULL !=
t->to_state) && (
t->to_state != s) )
1942 unsigned int num_equal_edges;
1944 unsigned int state_cnt;
1945 unsigned long long idx;
1946 unsigned long long idx1;
1951 "Could not merge nondistinguishable states, automaton was NULL.\n");
1957 (
sizeof(uint32_t) * state_cnt * state_cnt / 32) +
sizeof(uint32_t));
1973 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
1974 table[idx / 32] |= (1U << (idx % 32));
1986 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
1987 if (0 != (
table[idx / 32] & (1U << (idx % 32))))
1989 num_equal_edges = 0;
2005 if (0 != (
table[idx1 / 32] & (1U << (idx1 % 32))))
2007 table[idx / 32] |= (1U << (idx % 32));
2017 table[idx / 32] |= (1U << (idx % 32));
2025 for (s1 = a->
states_head; NULL != s1; s1 = s1_next)
2028 for (s2 = a->
states_head; NULL != s2 && s1 != s2; s2 = s2_next)
2031 idx = (
unsigned long long) s1->
marked * state_cnt + s2->
marked;
2032 if (0 == (
table[idx / 32] & (1U << (idx % 32))))
2107 const unsigned int depth,
2116 if (depth ==
ctx->stride)
2123 ctx->transitions_tail,
2132 if (
t->to_state ==
t->from_state)
2163 const unsigned int count,
2180 const unsigned int stride_len)
2198 for (
t =
ctx.transitions_head; NULL !=
t;
t = t_next)
2230 unsigned int max_len,
2238 if ((NULL !=
label) &&
2242 ((
start != dfa->
start) && (max_len > 0) && (max_len == strlen (
2265 else if (cur !=
start)
2281 if (
t->to_state != cur)
2307 unsigned int max_len)
2324 if (NULL !=
t->to_state)
2325 t->to_state->incoming_transition_count++;
2346 for (
t = transitions_head; NULL !=
t;
t = t_next)
2387 if ((NULL ==
start) || (NULL ==
end))
2416 if ((NULL == n) || (NULL == states_head))
2429 if (NULL != states_head)
2435 for (s = states_head; NULL != s; s = s->
next)
2454 s->
id =
ctx->state_id++;
2494 for (i = 0; i < states->
off; i++)
2503 cls_stack.
head = NULL;
2504 cls_stack.
tail = NULL;
2508 while (NULL != (currentstate = cls_stack.
tail))
2516 ctran = ctran->
next)
2518 if (NULL == (clsstate = ctran->
to_state))
2534 for (i = 0; i <
ret->off; i++)
2535 ret->states[i]->contained = 0;
2557 b =
ctx->stack_tail;
2560 a =
ctx->stack_tail;
2594 a =
ctx->stack_tail;
2600 "nfa_add_star_op failed, because there was no element on the stack");
2635 a =
ctx->stack_tail;
2641 "nfa_add_plus_op failed, because there was no element on the stack");
2666 a =
ctx->stack_tail;
2671 "nfa_add_question_op failed, because there was no element on the stack");
2708 b =
ctx->stack_tail;
2711 a =
ctx->stack_tail;
2775 ctx->transition_id = 0;
2776 ctx->stack_head = NULL;
2777 ctx->stack_tail = NULL;
2798 unsigned int altcount;
2799 unsigned int atomcount;
2809 if ((NULL ==
regex) || (0 == strlen (
regex)) || (0 == len))
2812 "Could not parse regex. Empty regex string provided.\n");
2827 for (count = 0; count < len && *regexp; count++, regexp++)
2839 p[poff].altcount = altcount;
2840 p[poff].atomcount = atomcount;
2849 error_msg =
"Cannot append '|' to nothing";
2852 while (--atomcount > 0)
2860 error_msg =
"Missing opening '('";
2867 altcount =
p[poff].altcount;
2868 atomcount =
p[poff].atomcount;
2871 while (--atomcount > 0)
2873 for (; altcount > 0; altcount--)
2876 altcount =
p[poff].altcount;
2877 atomcount =
p[poff].atomcount;
2884 error_msg =
"Cannot append '*' to nothing";
2893 error_msg =
"Cannot append '+' to nothing";
2902 error_msg =
"Cannot append '?' to nothing";
2914 curlabel[0] = *regexp;
2922 error_msg =
"Unbalanced parenthesis";
2925 while (--atomcount > 0)
2927 for (; altcount > 0; altcount--)
2932 nfa =
ctx.stack_tail;
2935 if (NULL !=
ctx.stack_head)
2937 error_msg =
"Creating the NFA failed. NFA stack was not empty!";
2959 if (NULL != error_msg)
2964 while (NULL != (nfa =
ctx.stack_head))
3005 state_contains = NULL;
3006 for (state_iter = dfa->
states_head; NULL != state_iter;
3007 state_iter = state_iter->
next)
3011 state_contains = state_iter;
3015 if (NULL == state_contains)
3034 unsigned int max_path_len)
3050 "Could not create DFA, because NFA creation failed\n");
3084 if (1 != max_path_len)
3103 for (s = a->
states_head; NULL != s; s = next_state)
3105 next_state = s->
next;
3127 unsigned int step_len;
3132 "Tried to evaluate DFA, but NFA automaton given");
3139 if (((NULL ==
string) || (0 == strlen (
string))) && s->
accepting)
3142 for (strp =
string; NULL != strp && *strp; strp += step_len)
3179 "Tried to evaluate NFA, but DFA automaton given");
3184 if (((NULL ==
string) || (0 == strlen (
string))) && a->
start->
accepting)
3194 for (strp =
string; NULL != strp && *strp; strp++)
3203 for (i = 0; i < sset.
off; i++)
3235 "Evaluating regex failed, automaton has no type!\n");
3264 unsigned int t_count;
3297 if (NULL == input_string)
3320 unsigned int max_len,
3321 char *consumed_string,
3328 unsigned int num_edges =
state->transition_count;
3333 unsigned int cur_len;
3335 if (NULL != consumed_string)
3336 cur_len = strlen (consumed_string);
3341 (cur_len > 0) && (NULL != consumed_string))
3343 if (cur_len <= max_len)
3345 if ((NULL !=
state->proof) &&
3346 (0 != strcmp (consumed_string,
state->proof)))
3351 "Start state for string `%s' is %s\n",
3354 iterator (iterator_cls,
3363 (
state->transition_count < 1) && (cur_len < max_len))
3367 edge[0].
label = &consumed_string[cur_len - 1];
3370 temp[cur_len - 1] =
'\0';
3373 "Start state for short string `%s' is %s\n",
3376 iterator (iterator_cls, &hash_new, temp,
GNUNET_NO, 1, edge);
3383 edge[0].
label = &consumed_string[max_len];
3386 temp[max_len] =
'\0';
3389 "Start state at split edge `%s'-`%s` is %s\n",
3393 iterator (iterator_cls, &hash, temp,
GNUNET_NO, 1, edge);
3398 if (cur_len < max_len)
3402 if (NULL != strchr (
t->label, (
int)
'.'))
3408 if (NULL != consumed_string)
3450 unsigned int num_edges;
3453 if (((NULL != s->proof) && (0 < strlen (s->proof))) || s->accepting)
3456 "Creating DFA edges at `%s' under key %s\n",
3459 iterator (iterator_cls,
3513 unsigned int num_edges,
3557 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...
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 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 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