GNUnet  0.10.x
Data Structures | Macros | Functions
regex_internal.c File Reference

library to create Deterministic Finite Automatons (DFAs) from regular expressions (regexes). More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_regex_service.h"
#include "regex_internal_lib.h"
#include "regex_internal.h"
Include dependency graph for regex_internal.c:

Go to the source code of this file.

Data Structures

struct  REGEX_INTERNAL_StateSet_MDLL
 Set of states using MDLL API. More...
 
struct  StringBuffer
 String container for faster string operations. More...
 
struct  REGEX_INTERNAL_Strided_Context
 Context for adding strided transitions to a DFA. More...
 
struct  temporal_state_store
 Struct to hold all the relevant state information in the HashMap. More...
 
struct  client_iterator
 Store regex iterator and cls in one place to pass to the hashmap iterator. More...
 

Macros

#define REGEX_DEBUG_DFA   GNUNET_NO
 Set this to GNUNET_YES to enable state naming. More...
 
#define PRIS(a)
 

Functions

static void state_set_append (struct REGEX_INTERNAL_StateSet *set, struct REGEX_INTERNAL_State *state)
 Append state to the given StateSet. More...
 
static int nullstrcmp (const char *str1, const char *str2)
 Compare two strings for equality. More...
 
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. More...
 
static void state_remove_transition (struct REGEX_INTERNAL_State *state, struct REGEX_INTERNAL_Transition *transition)
 Remove a 'transition' from 'state'. More...
 
static int state_compare (const void *a, const void *b)
 Compare two states. More...
 
static unsigned int state_get_edges (struct REGEX_INTERNAL_State *s, struct REGEX_BLOCK_Edge *edges)
 Get all edges leaving state s. More...
 
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. More...
 
static void state_set_clear (struct REGEX_INTERNAL_StateSet *set)
 Clears the given StateSet 'set'. More...
 
static void automaton_fragment_clear (struct REGEX_INTERNAL_Automaton *a)
 Clears an automaton fragment. More...
 
static void automaton_destroy_state (struct REGEX_INTERNAL_State *s)
 Frees the memory used by State s. More...
 
static void automaton_remove_state (struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
 Remove a state from the given automaton 'a'. More...
 
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. More...
 
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. More...
 
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'. More...
 
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. More...
 
static int sb_nullstrcmp (const struct StringBuffer *s1, const struct StringBuffer *s2)
 Compare two strings for equality. More...
 
static int sb_strcmp (const struct StringBuffer *s1, const struct StringBuffer *s2)
 Compare two strings for equality. More...
 
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 the new buffer. More...
 
static void sb_append (struct StringBuffer *ret, const struct StringBuffer *sarg)
 Append a string. More...
 
static void sb_append_cstr (struct StringBuffer *ret, const char *cstr)
 Append a C string. More...
 
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 replaced with the original content of 'ret'. More...
 
static void sb_printf1 (struct StringBuffer *ret, const char *format, size_t extra_chars, const struct StringBuffer *sarg)
 Format a string buffer. More...
 
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. More...
 
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. More...
 
static void sb_free (struct StringBuffer *sb)
 Free resources of the given string buffer. More...
 
static void sb_strdup (struct StringBuffer *out, const struct StringBuffer *in)
 Copy the given string buffer from 'in' to 'out'. More...
 
static void sb_strdup_cstr (struct StringBuffer *out, const char *cstr)
 Copy the given string buffer from 'in' to 'out'. More...
 
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. More...
 
static void remove_parentheses (struct StringBuffer *str)
 Remove parentheses surrounding string str. More...
 
static int has_epsilon (const struct StringBuffer *str)
 Check if the string 'str' starts with an epsilon (empty string). More...
 
static void remove_epsilon (const struct StringBuffer *str, struct StringBuffer *ret)
 Remove an epsilon from the string str. More...
 
static int sb_strncmp (const struct StringBuffer *str1, const struct StringBuffer *str2, size_t n)
 Compare n bytes of 'str1' and 'str2'. More...
 
static int sb_strncmp_cstr (const struct StringBuffer *str1, const char *str2, size_t n)
 Compare n bytes of 'str1' and 'str2'. More...
 
static void sb_init (struct StringBuffer *sb, size_t n)
 Initialize string buffer for storing strings of up to n characters. More...
 
static int sb_strkcmp (const struct StringBuffer *str1, const struct StringBuffer *str2, size_t k)
 Compare 'str1', starting from position 'k', with whole 'str2'. More...
 
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-first numbering of the states. More...
 
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)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}, and simplify the resulting expression saved in R_cur_ij. More...
 
static int automaton_create_proofs (struct REGEX_INTERNAL_Automaton *a)
 Create proofs for all states in the given automaton. More...
 
static struct REGEX_INTERNAL_Statedfa_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. More...
 
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'. More...
 
static void mark_states (void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
 Set the given state 'marked' to GNUNET_YES. More...
 
static void dfa_remove_unreachable_states (struct REGEX_INTERNAL_Automaton *a)
 Remove all unreachable states from DFA 'a'. More...
 
static void dfa_remove_dead_states (struct REGEX_INTERNAL_Automaton *a)
 Remove all dead states from the DFA 'a'. More...
 
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'. More...
 
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 all non distinguishable states. More...
 
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. More...
 
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. More...
 
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'. More...
 
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. More...
 
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'. More...
 
static struct REGEX_INTERNAL_Automatonnfa_fragment_create (struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
 Creates a new NFA fragment. More...
 
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'. More...
 
static struct REGEX_INTERNAL_Statenfa_state_create (struct REGEX_INTERNAL_Context *ctx, int accepting)
 Creates a new NFA state. More...
 
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. More...
 
static void nfa_add_concatenation (struct REGEX_INTERNAL_Context *ctx)
 Pops two NFA fragments (a, b) from the stack and concatenates them (ab) More...
 
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*) More...
 
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+) More...
 
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?) More...
 
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 and b (a|b) More...
 
static void nfa_add_label (struct REGEX_INTERNAL_Context *ctx, const char *label)
 Adds a new nfa fragment to the stack. More...
 
static void REGEX_INTERNAL_context_init (struct REGEX_INTERNAL_Context *ctx)
 Initialize a new context. More...
 
struct REGEX_INTERNAL_AutomatonREGEX_INTERNAL_construct_nfa (const char *regex, const size_t len)
 Construct an NFA by parsing the regex string of length 'len'. More...
 
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'. More...
 
struct REGEX_INTERNAL_AutomatonREGEX_INTERNAL_construct_dfa (const char *regex, const size_t len, unsigned int max_path_len)
 Construct DFA for the given 'regex' of length 'len'. More...
 
void REGEX_INTERNAL_automaton_destroy (struct REGEX_INTERNAL_Automaton *a)
 Free the memory allocated by constructing the REGEX_INTERNAL_Automaton data structure. More...
 
static int evaluate_dfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
 Evaluates the given string using the given DFA automaton. More...
 
static int evaluate_nfa (struct REGEX_INTERNAL_Automaton *a, const char *string)
 Evaluates the given string using the given NFA automaton. More...
 
int REGEX_INTERNAL_eval (struct REGEX_INTERNAL_Automaton *a, const char *string)
 Evaluates the given string against the given compiled regex a. More...
 
const char * REGEX_INTERNAL_get_canonical_regex (struct REGEX_INTERNAL_Automaton *a)
 Get the canonical regex of the given automaton. More...
 
unsigned int REGEX_INTERNAL_get_transition_count (struct REGEX_INTERNAL_Automaton *a)
 Get the number of transitions that are contained in the given automaton. More...
 
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. More...
 
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. More...
 
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'. More...
 
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. More...
 
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. More...
 
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. More...
 
static int iterate_reachables (void *cls, const struct GNUNET_HashCode *key, void *value)
 Iterator over hash map entries. More...
 
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 GNUNET_REGEX_INITIAL_BYTES characters. More...
 

Detailed Description

library to create Deterministic Finite Automatons (DFAs) from regular expressions (regexes).

Author
Maximilian Szengel

Definition in file regex_internal.c.

Macro Definition Documentation

◆ REGEX_DEBUG_DFA

#define REGEX_DEBUG_DFA   GNUNET_NO

Set this to GNUNET_YES to enable state naming.

Used to debug NFA->DFA creation. Disabled by default for better performance.

Definition at line 37 of file regex_internal.c.

◆ PRIS

#define PRIS (   a)
Value:
((GNUNET_YES == a.null_flag) ? 6 : (int)a.slen), \
((GNUNET_YES == a.null_flag) ? "(null)" : a.sbuf)
#define GNUNET_YES
Definition: gnunet_common.h:77

Definition at line 1149 of file regex_internal.c.

Function Documentation

◆ state_set_append()

static void state_set_append ( struct REGEX_INTERNAL_StateSet set,
struct REGEX_INTERNAL_State state 
)
static

Append state to the given StateSet.

Parameters
setset to be modified
statestate to be appended

Definition at line 67 of file regex_internal.c.

References GNUNET_array_grow, and state.

Referenced by evaluate_nfa(), nfa_closure_set_create(), and REGEX_INTERNAL_construct_dfa().

69 {
70  if (set->off == set->size)
71  GNUNET_array_grow(set->states, set->size, set->size * 2 + 4);
72  set->states[set->off++] = state;
73 }
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
enum State state
current state of profiling
struct REGEX_INTERNAL_State ** states
Array of states.
unsigned int off
Number of entries in use in the 'states' array.
unsigned int size
Length of the 'states' array.
Here is the caller graph for this function:

◆ nullstrcmp()

static int nullstrcmp ( const char *  str1,
const char *  str2 
)
static

Compare two strings for equality.

If either is NULL they are not equal.

Parameters
str1first string for comparison.
str2second string for comparison.
Returns
0 if the strings are the same or both NULL, 1 or -1 if not.

Definition at line 85 of file regex_internal.c.

Referenced by nfa_closure_set_create(), and state_add_transition().

86 {
87  if ((NULL == str1) != (NULL == str2))
88  return -1;
89  if ((NULL == str1) && (NULL == str2))
90  return 0;
91 
92  return strcmp(str1, str2);
93 }
Here is the caller graph for this function:

◆ state_add_transition()

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 
)
static

Adds a transition from one state to another on label.

Does not add duplicate states.

Parameters
ctxcontext
from_statestarting state for the transition
labeltransition label
to_statestate to where the transition should point to

Definition at line 106 of file regex_internal.c.

References REGEX_INTERNAL_Transition::from_state, GNUNET_CONTAINER_DLL_insert_before, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_new, GNUNET_strdup, REGEX_INTERNAL_Transition::id, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_Transition::next, nullstrcmp(), t, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_State::transition_count, REGEX_INTERNAL_Context::transition_id, REGEX_INTERNAL_State::transitions_head, and REGEX_INTERNAL_State::transitions_tail.

Referenced by automaton_merge_states(), dfa_compress_paths(), dfa_state_create(), nfa_add_alternation(), nfa_add_concatenation(), nfa_add_label(), nfa_add_plus_op(), nfa_add_question_op(), nfa_add_star_op(), and REGEX_INTERNAL_dfa_add_multi_strides().

110 {
112  struct REGEX_INTERNAL_Transition *oth;
113 
114  if (NULL == from_state)
115  {
116  GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
117  return;
118  }
119 
120  /* Do not add duplicate state transitions */
121  for (t = from_state->transitions_head; NULL != t; t = t->next)
122  {
123  if (t->to_state == to_state && 0 == nullstrcmp(t->label, label) &&
124  t->from_state == from_state)
125  return;
126  }
127 
128  /* sort transitions by label */
129  for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
130  {
131  if (0 < nullstrcmp(oth->label, label))
132  break;
133  }
134 
136  if (NULL != ctx)
137  t->id = ctx->transition_id++;
138  if (NULL != label)
139  t->label = GNUNET_strdup(label);
140  else
141  t->label = NULL;
142  t->to_state = to_state;
143  t->from_state = from_state;
144 
145  /* Add outgoing transition to 'from_state' */
146  from_state->transition_count++;
148  from_state->transitions_tail,
149  oth,
150  t);
151 }
struct REGEX_INTERNAL_Transition * next
This is a linked list.
unsigned int transition_id
Unique transition id.
#define GNUNET_CONTAINER_DLL_insert_before(head, tail, other, element)
Insert an element into a DLL before the given other element.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
unsigned int transition_count
Number of transitions from this state to other states.
static int nullstrcmp(const char *str1, const char *str2)
Compare two strings for equality.
Transition between two states.
unsigned int id
Unique id of this transition.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
#define GNUNET_log(kind,...)
char * label
Label for this transition.
struct REGEX_INTERNAL_Transition * transitions_tail
DLL of transitions.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ state_remove_transition()

static void state_remove_transition ( struct REGEX_INTERNAL_State state,
struct REGEX_INTERNAL_Transition transition 
)
static

Remove a 'transition' from 'state'.

Parameters
statestate from which the to-be-removed transition originates.
transitiontransition that should be removed from state 'state'.

Definition at line 161 of file regex_internal.c.

References REGEX_INTERNAL_Transition::from_state, GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_free_non_null, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_State::transition_count, REGEX_INTERNAL_State::transitions_head, and REGEX_INTERNAL_State::transitions_tail.

Referenced by automaton_destroy_state(), automaton_merge_states(), and automaton_remove_state().

163 {
164  if (NULL == state || NULL == transition)
165  return;
166 
167  if (transition->from_state != state)
168  return;
169 
170  GNUNET_free_non_null(transition->label);
171 
172  state->transition_count--;
174  state->transitions_tail,
175  transition);
176 
177  GNUNET_free(transition);
178 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
unsigned int transition_count
Number of transitions from this state to other states.
char * label
Label for this transition.
#define GNUNET_free(ptr)
Wrapper around free.
struct REGEX_INTERNAL_Transition * transitions_tail
DLL of transitions.
Here is the caller graph for this function:

◆ state_compare()

static int state_compare ( const void *  a,
const void *  b 
)
static

Compare two states.

Used for sorting.

Parameters
afirst state
bsecond state
Returns
an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

Definition at line 192 of file regex_internal.c.

References REGEX_INTERNAL_State::id.

Referenced by nfa_closure_set_create(), and state_set_compare().

193 {
194  struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **)a;
195  struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **)b;
196 
197  return (*s1)->id - (*s2)->id;
198 }
unsigned int id
Unique state id.
Here is the caller graph for this function:

◆ state_get_edges()

static unsigned int state_get_edges ( struct REGEX_INTERNAL_State s,
struct REGEX_BLOCK_Edge edges 
)
static

Get all edges leaving state s.

Parameters
sstate.
edgesall edges leaving s, expected to be allocated and have enough space for s->transitions_count elements.
Returns
number of edges.

Definition at line 211 of file regex_internal.c.

References REGEX_BLOCK_Edge::destination, REGEX_INTERNAL_State::hash, REGEX_BLOCK_Edge::label, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_Transition::next, t, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by iterate_initial_edge(), and REGEX_INTERNAL_iterate_all_edges().

212 {
214  unsigned int count;
215 
216  if (NULL == s)
217  return 0;
218 
219  count = 0;
220 
221  for (t = s->transitions_head; NULL != t; t = t->next)
222  {
223  if (NULL != t->to_state)
224  {
225  edges[count].label = t->label;
226  edges[count].destination = t->to_state->hash;
227  count++;
228  }
229  }
230  return count;
231 }
struct GNUNET_HashCode destination
Destionation of the edge.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct GNUNET_HashCode hash
Hash of the state.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static struct GNUNET_SCHEDULER_Task * t
Main task.
Transition between two states.
const char * label
Label of the edge.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
Here is the caller graph for this function:

◆ state_set_compare()

static int state_set_compare ( struct REGEX_INTERNAL_StateSet sset1,
struct REGEX_INTERNAL_StateSet sset2 
)
static

Compare to state sets by comparing the id's of the states that are contained in each set.

Both sets are expected to be sorted by id!

Parameters
sset1first state set
sset2second state set
Returns
0 if the sets are equal, otherwise non-zero

Definition at line 243 of file regex_internal.c.

References REGEX_INTERNAL_StateSet::off, result, state_compare(), and REGEX_INTERNAL_StateSet::states.

Referenced by construct_dfa_states().

245 {
246  int result;
247  unsigned int i;
248 
249  if (NULL == sset1 || NULL == sset2)
250  return 1;
251 
252  result = sset1->off - sset2->off;
253  if (result < 0)
254  return -1;
255  if (result > 0)
256  return 1;
257  for (i = 0; i < sset1->off; i++)
258  if (0 != (result = state_compare(&sset1->states[i], &sset2->states[i])))
259  break;
260  return result;
261 }
static int state_compare(const void *a, const void *b)
Compare two states.
struct REGEX_INTERNAL_State ** states
Array of states.
static int result
Global testing status.
unsigned int off
Number of entries in use in the &#39;states&#39; array.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ state_set_clear()

static void state_set_clear ( struct REGEX_INTERNAL_StateSet set)
static

Clears the given StateSet 'set'.

Parameters
setset to be cleared

Definition at line 270 of file regex_internal.c.

References GNUNET_array_grow.

Referenced by automaton_destroy_state(), construct_dfa_states(), evaluate_nfa(), and REGEX_INTERNAL_construct_dfa().

271 {
272  GNUNET_array_grow(set->states, set->size, 0);
273  set->off = 0;
274 }
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
struct REGEX_INTERNAL_State ** states
Array of states.
unsigned int size
Length of the &#39;states&#39; array.
Here is the caller graph for this function:

◆ automaton_fragment_clear()

static void automaton_fragment_clear ( struct REGEX_INTERNAL_Automaton a)
static

Clears an automaton fragment.

Does not destroy the states inside the automaton.

Parameters
aautomaton to be cleared

Definition at line 284 of file regex_internal.c.

References REGEX_INTERNAL_Automaton::end, GNUNET_free, REGEX_INTERNAL_Automaton::start, REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by nfa_add_alternation(), nfa_add_concatenation(), nfa_add_question_op(), and nfa_add_star_op().

285 {
286  if (NULL == a)
287  return;
288 
289  a->start = NULL;
290  a->end = NULL;
291  a->states_head = NULL;
292  a->states_tail = NULL;
293  a->state_count = 0;
294  GNUNET_free(a);
295 }
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.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the caller graph for this function:

◆ automaton_destroy_state()

static void automaton_destroy_state ( struct REGEX_INTERNAL_State s)
static

Frees the memory used by State s.

Parameters
sstate that should be destroyed

Definition at line 304 of file regex_internal.c.

References GNUNET_free, GNUNET_free_non_null, REGEX_INTERNAL_State::name, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::nfa_set, REGEX_INTERNAL_State::proof, state_remove_transition(), state_set_clear(), t, and REGEX_INTERNAL_State::transitions_head.

Referenced by automaton_merge_states(), automaton_remove_state(), and REGEX_INTERNAL_automaton_destroy().

305 {
307  struct REGEX_INTERNAL_Transition *next_t;
308 
309  if (NULL == s)
310  return;
311 
315  for (t = s->transitions_head; NULL != t; t = next_t)
316  {
317  next_t = t->next;
319  }
320 
321  GNUNET_free(s);
322 }
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static void state_set_clear(struct REGEX_INTERNAL_StateSet *set)
Clears the given StateSet &#39;set&#39;.
struct REGEX_INTERNAL_StateSet nfa_set
Set of states on which this state is based on.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
static struct GNUNET_SCHEDULER_Task * t
Main task.
char * proof
Proof for this state.
char * name
Human readable name of the state.
Transition between two states.
static void state_remove_transition(struct REGEX_INTERNAL_State *state, struct REGEX_INTERNAL_Transition *transition)
Remove a &#39;transition&#39; from &#39;state&#39;.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ automaton_remove_state()

static void automaton_remove_state ( struct REGEX_INTERNAL_Automaton a,
struct REGEX_INTERNAL_State s 
)
static

Remove a state from the given automaton 'a'.

Always use this function when altering the states of an automaton. Will also remove all transitions leading to this state, before destroying it.

Parameters
aautomaton
sstate to remove

Definition at line 334 of file regex_internal.c.

References automaton_destroy_state(), GNUNET_CONTAINER_DLL_remove, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::state_count, state_remove_transition(), REGEX_INTERNAL_Automaton::states_head, REGEX_INTERNAL_Automaton::states_tail, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by dfa_compress_paths(), dfa_remove_dead_states(), and dfa_remove_unreachable_states().

336 {
337  struct REGEX_INTERNAL_State *s_check;
338  struct REGEX_INTERNAL_Transition *t_check;
339  struct REGEX_INTERNAL_Transition *t_check_next;
340 
341  if (NULL == a || NULL == s)
342  return;
343 
344  /* remove all transitions leading to this state */
345  for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
346  {
347  for (t_check = s_check->transitions_head; NULL != t_check;
348  t_check = t_check_next)
349  {
350  t_check_next = t_check->next;
351  if (t_check->to_state == s)
352  state_remove_transition(s_check, t_check);
353  }
354  }
355 
356  /* remove state */
358  a->state_count--;
359 
361 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static void automaton_destroy_state(struct REGEX_INTERNAL_State *s)
Frees the memory used by State s.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
Transition between two states.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
static void state_remove_transition(struct REGEX_INTERNAL_State *state, struct REGEX_INTERNAL_Transition *transition)
Remove a &#39;transition&#39; from &#39;state&#39;.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ automaton_merge_states()

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 
)
static

Merge two states into one.

Will merge 's1' and 's2' into 's1' and destroy 's2'. 's1' will contain all (non-duplicate) outgoing transitions of 's2'.

Parameters
ctxcontext
aautomaton
s1first state
s2second state, will be destroyed

Definition at line 374 of file regex_internal.c.

References automaton_destroy_state(), REGEX_INTERNAL_Transition::from_state, GNUNET_asprintf(), GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_NO, GNUNET_YES, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_State::name, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::next, state_add_transition(), REGEX_INTERNAL_Automaton::state_count, state_remove_transition(), REGEX_INTERNAL_Automaton::states_head, REGEX_INTERNAL_Automaton::states_tail, t, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by dfa_merge_nondistinguishable_states().

378 {
379  struct REGEX_INTERNAL_State *s_check;
380  struct REGEX_INTERNAL_Transition *t_check;
382  struct REGEX_INTERNAL_Transition *t_next;
383  int is_dup;
384 
385  if (s1 == s2)
386  return;
387 
388  /* 1. Make all transitions pointing to s2 point to s1, unless this transition
389  * does not already exists, if it already exists remove transition. */
390  for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
391  {
392  for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next)
393  {
394  t_next = t_check->next;
395 
396  if (s2 == t_check->to_state)
397  {
398  is_dup = GNUNET_NO;
399  for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
400  {
401  if (t->to_state == s1 && 0 == strcmp(t_check->label, t->label))
402  is_dup = GNUNET_YES;
403  }
404  if (GNUNET_NO == is_dup)
405  t_check->to_state = s1;
406  else
407  state_remove_transition(t_check->from_state, t_check);
408  }
409  }
410  }
411 
412  /* 2. Add all transitions from s2 to sX to s1 */
413  for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next)
414  {
415  if (t_check->to_state != s1)
416  state_add_transition(ctx, s1, t_check->label, t_check->to_state);
417  }
418 
419  /* 3. Rename s1 to {s1,s2} */
420 #if REGEX_DEBUG_DFA
421  char *new_name;
422 
423  new_name = s1->name;
424  GNUNET_asprintf(&s1->name, "{%s,%s}", new_name, s2->name);
425  GNUNET_free(new_name);
426 #endif
427 
428  /* remove state */
430  a->state_count--;
432 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
#define GNUNET_NO
Definition: gnunet_common.h:78
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.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
char * name
Human readable name of the state.
Transition between two 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.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
static void state_remove_transition(struct REGEX_INTERNAL_State *state, struct REGEX_INTERNAL_Transition *transition)
Remove a &#39;transition&#39; from &#39;state&#39;.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
#define GNUNET_YES
Definition: gnunet_common.h:77
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ automaton_add_state()

static void automaton_add_state ( struct REGEX_INTERNAL_Automaton a,
struct REGEX_INTERNAL_State s 
)
static

Add a state to the automaton 'a', always use this function to alter the states DLL of the automaton.

Parameters
aautomaton to add the state to
sstate that should be added

Definition at line 443 of file regex_internal.c.

References GNUNET_CONTAINER_DLL_insert, REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by construct_dfa_states(), nfa_fragment_create(), and REGEX_INTERNAL_construct_dfa().

445 {
447  a->state_count++;
448 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
#define GNUNET_CONTAINER_DLL_insert(head, tail, element)
Insert an element at the head of a DLL.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
Here is the caller graph for this function:

◆ automaton_state_traverse()

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 
)
static

Depth-first traversal (DFS) of all states that are reachable from state 's'.

Performs 'action' on each visited state.

Parameters
sstart state.
marksan array of size a->state_count to remember which state was already visited.
countcurrent count of the state.
checkfunction that is checked before advancing on each transition in the DFS.
check_clsclosure for check.
actionaction to be performed on each state.
action_clsclosure for action.

Definition at line 466 of file regex_internal.c.

References GNUNET_YES, REGEX_INTERNAL_Transition::next, t, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_State::transitions_head, and REGEX_INTERNAL_State::traversal_id.

Referenced by REGEX_INTERNAL_automaton_traverse().

473 {
475 
476  if (GNUNET_YES == marks[s->traversal_id])
477  return;
478 
479  marks[s->traversal_id] = GNUNET_YES;
480 
481  if (NULL != action)
482  action(action_cls, *count, s);
483 
484  (*count)++;
485 
486  for (t = s->transitions_head; NULL != t; t = t->next)
487  {
488  if (NULL == check ||
489  (NULL != check && GNUNET_YES == check(check_cls, s, t)))
490  {
492  marks,
493  count,
494  check,
495  check_cls,
496  action,
497  action_cls);
498  }
499  }
500 }
unsigned int traversal_id
Unique state id that is used for traversing the automaton.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static struct GNUNET_SCHEDULER_Task * t
Main task.
Transition between two states.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
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 &#39;s&#39;.
#define GNUNET_YES
Definition: gnunet_common.h:77
Here is the caller graph for this function:

◆ REGEX_INTERNAL_automaton_traverse()

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.

Parameters
aautomaton to be traversed.
startstart state, pass a->start or NULL to traverse the whole automaton.
checkfunction that is checked before advancing on each transition in the DFS.
check_clsclosure for check.
actionaction to be performed on each state.
action_clsclosure for action

Definition at line 517 of file regex_internal.c.

References automaton_state_traverse(), GNUNET_NO, REGEX_INTERNAL_State::next, start, REGEX_INTERNAL_Automaton::start, REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_State::traversal_id.

Referenced by automaton_create_proofs(), dfa_remove_unreachable_states(), REGEX_INTERNAL_construct_nfa(), REGEX_INTERNAL_dfa_add_multi_strides(), and REGEX_TEST_automaton_save_graph().

523 {
524  unsigned int count;
525  struct REGEX_INTERNAL_State *s;
526 
527  if (NULL == a || 0 == a->state_count)
528  return;
529 
530  int marks[a->state_count];
531 
532  for (count = 0, s = a->states_head; NULL != s && count < a->state_count;
533  s = s->next, count++)
534  {
535  s->traversal_id = count;
536  marks[s->traversal_id] = GNUNET_NO;
537  }
538 
539  count = 0;
540 
541  if (NULL == start)
542  s = a->start;
543  else
544  s = start;
545 
547  marks,
548  &count,
549  check,
550  check_cls,
551  action,
552  action_cls);
553 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
unsigned int traversal_id
Unique state id that is used for traversing the automaton.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_NO
Definition: gnunet_common.h:78
struct REGEX_INTERNAL_State * start
First state of the automaton.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
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 &#39;s&#39;.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_nullstrcmp()

static int sb_nullstrcmp ( const struct StringBuffer s1,
const struct StringBuffer s2 
)
static

Compare two strings for equality.

If either is NULL they are not equal.

Parameters
s1first string for comparison.
s2second string for comparison.
Returns
0 if the strings are the same or both NULL, 1 or -1 if not.

Definition at line 608 of file regex_internal.c.

References GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

609 {
610  if ((GNUNET_YES == s1->null_flag) && (GNUNET_YES == s2->null_flag))
611  return 0;
612  if ((GNUNET_YES == s1->null_flag) || (GNUNET_YES == s2->null_flag))
613  return -1;
614  if (s1->slen != s2->slen)
615  return -1;
616  if (0 == s1->slen)
617  return 0;
618  return memcmp(s1->sbuf, s2->sbuf, s1->slen);
619 }
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ sb_strcmp()

static int sb_strcmp ( const struct StringBuffer s1,
const struct StringBuffer s2 
)
static

Compare two strings for equality.

Parameters
s1first string for comparison.
s2second string for comparison.
Returns
0 if the strings are the same, 1 or -1 if not.

Definition at line 631 of file regex_internal.c.

References StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

632 {
633  if (s1->slen != s2->slen)
634  return -1;
635  if (0 == s1->slen)
636  return 0;
637  return memcmp(s1->sbuf, s2->sbuf, s1->slen);
638 }
size_t slen
Length of the string in the buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ sb_realloc()

static void sb_realloc ( struct StringBuffer ret,
size_t  nlen 
)
static

Reallocate the buffer of 'ret' to fit 'nlen' characters; move the existing string to the beginning of the new buffer.

Parameters
retcurrent buffer, to be updated
nlentarget length for the buffer, must be at least ret->slen

Definition at line 649 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_assert, GNUNET_free_non_null, GNUNET_malloc, GNUNET_memcpy, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by sb_append(), sb_append_cstr(), sb_printf1(), sb_printf2(), and sb_printf3().

650 {
651  char *old;
652 
653  GNUNET_assert(nlen >= ret->slen);
654  old = ret->abuf;
655  ret->abuf = GNUNET_malloc(nlen);
656  ret->blen = nlen;
657  GNUNET_memcpy(ret->abuf, ret->sbuf, ret->slen);
658  ret->sbuf = ret->abuf;
660 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
#define GNUNET_malloc(size)
Wrapper around malloc.
Here is the caller graph for this function:

◆ sb_append()

static void sb_append ( struct StringBuffer ret,
const struct StringBuffer sarg 
)
static

Append a string.

Parameters
retwhere to write the result
sargstring to append

Definition at line 670 of file regex_internal.c.

References StringBuffer::blen, GNUNET_memcpy, GNUNET_NO, GNUNET_YES, StringBuffer::null_flag, sb_realloc(), StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs().

671 {
672  if (GNUNET_YES == ret->null_flag)
673  ret->slen = 0;
674  ret->null_flag = GNUNET_NO;
675  if (ret->blen < sarg->slen + ret->slen)
676  sb_realloc(ret, ret->blen + sarg->slen + 128);
677  GNUNET_memcpy(&ret->sbuf[ret->slen], sarg->sbuf, sarg->slen);
678  ret->slen += sarg->slen;
679 }
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_NO
Definition: gnunet_common.h:78
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
static void sb_realloc(struct StringBuffer *ret, size_t nlen)
Reallocate the buffer of &#39;ret&#39; to fit &#39;nlen&#39; characters; move the existing string to the beginning of...
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_append_cstr()

static void sb_append_cstr ( struct StringBuffer ret,
const char *  cstr 
)
static

Append a C string.

Parameters
retwhere to write the result
cstrstring to append

Definition at line 689 of file regex_internal.c.

References StringBuffer::blen, GNUNET_memcpy, GNUNET_NO, GNUNET_YES, StringBuffer::null_flag, sb_realloc(), StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs().

690 {
691  size_t cstr_len = strlen(cstr);
692 
693  if (GNUNET_YES == ret->null_flag)
694  ret->slen = 0;
695  ret->null_flag = GNUNET_NO;
696  if (ret->blen < cstr_len + ret->slen)
697  sb_realloc(ret, ret->blen + cstr_len + 128);
698  GNUNET_memcpy(&ret->sbuf[ret->slen], cstr, cstr_len);
699  ret->slen += cstr_len;
700 }
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_NO
Definition: gnunet_common.h:78
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
static void sb_realloc(struct StringBuffer *ret, size_t nlen)
Reallocate the buffer of &#39;ret&#39; to fit &#39;nlen&#39; characters; move the existing string to the beginning of...
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_wrap()

static void sb_wrap ( struct StringBuffer ret,
const char *  format,
size_t  extra_chars 
)
static

Wrap a string buffer, that is, set ret to the format string which contains an "%s" which is to be replaced with the original content of 'ret'.

Note that optimizing this function is not really worth it, it is rarely called.

Parameters
retwhere to write the result and take the input for %.*s from
formatformat string, fprintf-style, with exactly one "%.*s"
extra_charshow long will the result be, in addition to 'sarg' length

Definition at line 714 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_free_non_null, GNUNET_malloc, GNUNET_NO, GNUNET_snprintf(), GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs().

715 {
716  char *temp;
717 
718  if (GNUNET_YES == ret->null_flag)
719  ret->slen = 0;
720  ret->null_flag = GNUNET_NO;
721  temp = GNUNET_malloc(ret->slen + extra_chars + 1);
722  GNUNET_snprintf(temp,
723  ret->slen + extra_chars + 1,
724  format,
725  (int)ret->slen,
726  ret->sbuf);
728  ret->abuf = temp;
729  ret->sbuf = temp;
730  ret->blen = ret->slen + extra_chars + 1;
731  ret->slen = ret->slen + extra_chars;
732 }
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
#define GNUNET_malloc(size)
Wrapper around malloc.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_printf1()

static void sb_printf1 ( struct StringBuffer ret,
const char *  format,
size_t  extra_chars,
const struct StringBuffer sarg 
)
static

Format a string buffer.

Note that optimizing this function is not really worth it, it is rarely called.

Parameters
retwhere to write the result
formatformat string, fprintf-style, with exactly one "%.*s"
extra_charshow long will the result be, in addition to 'sarg' length
sargstring to print into the format

Definition at line 745 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_NO, GNUNET_snprintf(), StringBuffer::null_flag, sb_realloc(), StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

749 {
750  if (ret->blen < sarg->slen + extra_chars + 1)
751  sb_realloc(ret, sarg->slen + extra_chars + 1);
752  ret->null_flag = GNUNET_NO;
753  ret->sbuf = ret->abuf;
754  ret->slen = sarg->slen + extra_chars;
755  GNUNET_snprintf(ret->sbuf, ret->blen, format, (int)sarg->slen, sarg->sbuf);
756 }
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_NO
Definition: gnunet_common.h:78
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
static void sb_realloc(struct StringBuffer *ret, size_t nlen)
Reallocate the buffer of &#39;ret&#39; to fit &#39;nlen&#39; characters; move the existing string to the beginning of...
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_printf2()

static void sb_printf2 ( struct StringBuffer ret,
const char *  format,
size_t  extra_chars,
const struct StringBuffer sarg1,
const struct StringBuffer sarg2 
)
static

Format a string buffer.

Parameters
retwhere to write the result
formatformat string, fprintf-style, with exactly two "%.*s"
extra_charshow long will the result be, in addition to 'sarg1/2' length
sarg1first string to print into the format
sarg2second string to print into the format

Definition at line 769 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_NO, GNUNET_snprintf(), StringBuffer::null_flag, sb_realloc(), StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

774 {
775  if (ret->blen < sarg1->slen + sarg2->slen + extra_chars + 1)
776  sb_realloc(ret, sarg1->slen + sarg2->slen + extra_chars + 1);
777  ret->null_flag = GNUNET_NO;
778  ret->slen = sarg1->slen + sarg2->slen + extra_chars;
779  ret->sbuf = ret->abuf;
780  GNUNET_snprintf(ret->sbuf,
781  ret->blen,
782  format,
783  (int)sarg1->slen,
784  sarg1->sbuf,
785  (int)sarg2->slen,
786  sarg2->sbuf);
787 }
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_NO
Definition: gnunet_common.h:78
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
static void sb_realloc(struct StringBuffer *ret, size_t nlen)
Reallocate the buffer of &#39;ret&#39; to fit &#39;nlen&#39; characters; move the existing string to the beginning of...
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_printf3()

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 
)
static

Format a string buffer.

Note that optimizing this function is not really worth it, it is rarely called.

Parameters
retwhere to write the result
formatformat string, fprintf-style, with exactly three "%.*s"
extra_charshow long will the result be, in addition to 'sarg1/2/3' length
sarg1first string to print into the format
sarg2second string to print into the format
sarg3third string to print into the format

Definition at line 802 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_NO, GNUNET_snprintf(), StringBuffer::null_flag, sb_realloc(), StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

808 {
809  if (ret->blen < sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1)
810  sb_realloc(ret, sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1);
811  ret->null_flag = GNUNET_NO;
812  ret->slen = sarg1->slen + sarg2->slen + sarg3->slen + extra_chars;
813  ret->sbuf = ret->abuf;
814  GNUNET_snprintf(ret->sbuf,
815  ret->blen,
816  format,
817  (int)sarg1->slen,
818  sarg1->sbuf,
819  (int)sarg2->slen,
820  sarg2->sbuf,
821  (int)sarg3->slen,
822  sarg3->sbuf);
823 }
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_NO
Definition: gnunet_common.h:78
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
static void sb_realloc(struct StringBuffer *ret, size_t nlen)
Reallocate the buffer of &#39;ret&#39; to fit &#39;nlen&#39; characters; move the existing string to the beginning of...
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_free()

static void sb_free ( struct StringBuffer sb)
static

Free resources of the given string buffer.

Parameters
sbbuffer to free (actual pointer is not freed, as they should not be individually allocated)

Definition at line 833 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_array_grow, GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs(), and automaton_create_proofs_simplify().

834 {
835  GNUNET_array_grow(sb->abuf, sb->blen, 0);
836  sb->slen = 0;
837  sb->sbuf = NULL;
838  sb->null_flag = GNUNET_YES;
839 }
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ sb_strdup()

static void sb_strdup ( struct StringBuffer out,
const struct StringBuffer in 
)
static

Copy the given string buffer from 'in' to 'out'.

Parameters
ininput string
outoutput string

Definition at line 849 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_array_grow, GNUNET_memcpy, GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify(), and remove_epsilon().

851 {
852  out->null_flag = in->null_flag;
853  if (GNUNET_YES == out->null_flag)
854  return;
855  if (out->blen < in->slen)
856  {
857  GNUNET_array_grow(out->abuf, out->blen, in->slen);
858  }
859  out->sbuf = out->abuf;
860  out->slen = in->slen;
861  GNUNET_memcpy(out->sbuf, in->sbuf, out->slen);
862 }
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ sb_strdup_cstr()

static void sb_strdup_cstr ( struct StringBuffer out,
const char *  cstr 
)
static

Copy the given string buffer from 'in' to 'out'.

Parameters
cstrinput string
outoutput string

Definition at line 872 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_array_grow, GNUNET_memcpy, GNUNET_NO, GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs().

873 {
874  if (NULL == cstr)
875  {
876  out->null_flag = GNUNET_YES;
877  return;
878  }
879  out->null_flag = GNUNET_NO;
880  out->slen = strlen(cstr);
881  if (out->blen < out->slen)
882  {
883  GNUNET_array_grow(out->abuf, out->blen, out->slen);
884  }
885  out->sbuf = out->abuf;
886  GNUNET_memcpy(out->sbuf, cstr, out->slen);
887 }
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ needs_parentheses()

static int needs_parentheses ( const struct StringBuffer str)
static

Check if the given string str needs parentheses around it when using it to generate a regex.

Parameters
strstring
Returns
GNUNET_YES if parentheses are needed, GNUNET_NO otherwise

Definition at line 899 of file regex_internal.c.

References end, GNUNET_break, GNUNET_NO, GNUNET_YES, StringBuffer::null_flag, op, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs(), and automaton_create_proofs_simplify().

900 {
901  size_t slen;
902  const char *op;
903  const char *cl;
904  const char *pos;
905  const char *end;
906  unsigned int cnt;
907 
908  if ((GNUNET_YES == str->null_flag) || ((slen = str->slen) < 2))
909  return GNUNET_NO;
910  pos = str->sbuf;
911  if ('(' != pos[0])
912  return GNUNET_YES;
913  end = str->sbuf + slen;
914  cnt = 1;
915  pos++;
916  while (cnt > 0)
917  {
918  cl = memchr(pos, ')', end - pos);
919  if (NULL == cl)
920  {
921  GNUNET_break(0);
922  return GNUNET_YES;
923  }
924  /* while '(' before ')', count opening parens */
925  while ((NULL != (op = memchr(pos, '(', end - pos))) && (op < cl))
926  {
927  cnt++;
928  pos = op + 1;
929  }
930  /* got ')' first */
931  cnt--;
932  pos = cl + 1;
933  }
934  return (*pos == '\0') ? GNUNET_NO : GNUNET_YES;
935 }
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:139
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ remove_parentheses()

static void remove_parentheses ( struct StringBuffer str)
static

Remove parentheses surrounding string str.

Example: "(a)" becomes "a", "(a|b)|(a|c)" stays the same. You need to GNUNET_free() the returned string.

Parameters
strstring, modified to contain a
Returns
string without surrounding parentheses, string 'str' if no preceding epsilon could be found, NULL if 'str' was NULL

Definition at line 948 of file regex_internal.c.

References end, GNUNET_break, GNUNET_YES, StringBuffer::null_flag, op, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

949 {
950  size_t slen;
951  const char *pos;
952  const char *end;
953  const char *sbuf;
954  const char *op;
955  const char *cp;
956  unsigned int cnt;
957 
958  if (0)
959  return;
960  sbuf = str->sbuf;
961  if ((GNUNET_YES == str->null_flag) || (1 >= (slen = str->slen)) ||
962  ('(' != str->sbuf[0]) || (')' != str->sbuf[slen - 1]))
963  return;
964  cnt = 0;
965  pos = &sbuf[1];
966  end = &sbuf[slen - 1];
967  op = memchr(pos, '(', end - pos);
968  cp = memchr(pos, ')', end - pos);
969  while (NULL != cp)
970  {
971  while ((NULL != op) && (op < cp))
972  {
973  cnt++;
974  pos = op + 1;
975  op = memchr(pos, '(', end - pos);
976  }
977  while ((NULL != cp) && ((NULL == op) || (cp < op)))
978  {
979  if (0 == cnt)
980  return; /* can't strip parens */
981  cnt--;
982  pos = cp + 1;
983  cp = memchr(pos, ')', end - pos);
984  }
985  }
986  if (0 != cnt)
987  {
988  GNUNET_break(0);
989  return;
990  }
991  str->sbuf++;
992  str->slen -= 2;
993 }
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:139
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ has_epsilon()

static int has_epsilon ( const struct StringBuffer str)
static

Check if the string 'str' starts with an epsilon (empty string).

Example: "(|a)" is starting with an epsilon.

Parameters
strstring to test
Returns
0 if str has no epsilon, 1 if str starts with '(|' and ends with ')'

Definition at line 1005 of file regex_internal.c.

References GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

1006 {
1007  return (GNUNET_YES != str->null_flag) && (0 < str->slen) &&
1008  ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) &&
1009  (')' == str->sbuf[str->slen - 1]);
1010 }
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ remove_epsilon()

static void remove_epsilon ( const struct StringBuffer str,
struct StringBuffer ret 
)
static

Remove an epsilon from the string str.

Where epsilon is an empty string Example: str = "(|a|b|c)", result: "a|b|c" The returned string needs to be freed.

Parameters
stroriginal string
retwhere to return string without preceding epsilon, string 'str' if no preceding epsilon could be found, NULL if 'str' was NULL

Definition at line 1023 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_array_grow, GNUNET_memcpy, GNUNET_YES, StringBuffer::null_flag, sb_strdup(), StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

1024 {
1025  if (GNUNET_YES == str->null_flag)
1026  {
1027  ret->null_flag = GNUNET_YES;
1028  return;
1029  }
1030  if ((str->slen > 1) && ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) &&
1031  (')' == str->sbuf[str->slen - 1]))
1032  {
1033  /* remove epsilon */
1034  if (ret->blen < str->slen - 3)
1035  {
1036  GNUNET_array_grow(ret->abuf, ret->blen, str->slen - 3);
1037  }
1038  ret->sbuf = ret->abuf;
1039  ret->slen = str->slen - 3;
1040  GNUNET_memcpy(ret->sbuf, &str->sbuf[2], ret->slen);
1041  return;
1042  }
1043  sb_strdup(ret, str);
1044 }
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 void sb_strdup(struct StringBuffer *out, const struct StringBuffer *in)
Copy the given string buffer from &#39;in&#39; to &#39;out&#39;.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the call graph for this function:
Here is the caller graph for this function:

◆ sb_strncmp()

static int sb_strncmp ( const struct StringBuffer str1,
const struct StringBuffer str2,
size_t  n 
)
static

Compare n bytes of 'str1' and 'str2'.

Parameters
str1first string to compare
str2second string for comparison
nnumber of bytes to compare
Returns
-1 if any of the strings is NULL, 0 if equal, non 0 otherwise

Definition at line 1057 of file regex_internal.c.

References GNUNET_MAX, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

1060 {
1061  size_t max;
1062 
1063  if ((str1->slen != str2->slen) && ((str1->slen < n) || (str2->slen < n)))
1064  return -1;
1065  max = GNUNET_MAX(str1->slen, str2->slen);
1066  if (max > n)
1067  max = n;
1068  return memcmp(str1->sbuf, str2->sbuf, max);
1069 }
#define GNUNET_MAX(a, b)
Definition: gnunet_common.h:82
size_t slen
Length of the string in the buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ sb_strncmp_cstr()

static int sb_strncmp_cstr ( const struct StringBuffer str1,
const char *  str2,
size_t  n 
)
static

Compare n bytes of 'str1' and 'str2'.

Parameters
str1first string to compare
str2second C string for comparison
nnumber of bytes to compare (and length of str2)
Returns
-1 if any of the strings is NULL, 0 if equal, non 0 otherwise

Definition at line 1082 of file regex_internal.c.

References StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

1083 {
1084  if (str1->slen < n)
1085  return -1;
1086  return memcmp(str1->sbuf, str2, n);
1087 }
size_t slen
Length of the string in the buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ sb_init()

static void sb_init ( struct StringBuffer sb,
size_t  n 
)
static

Initialize string buffer for storing strings of up to n characters.

Parameters
sbbuffer to initialize
ndesired target length

Definition at line 1098 of file regex_internal.c.

References StringBuffer::abuf, StringBuffer::blen, GNUNET_malloc, GNUNET_NO, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs(), and automaton_create_proofs_simplify().

1099 {
1100  sb->null_flag = GNUNET_NO;
1101  sb->abuf = sb->sbuf = (0 == n) ? NULL : GNUNET_malloc(n);
1102  sb->blen = n;
1103  sb->slen = 0;
1104 }
unsigned int blen
Number of bytes allocated for sbuf.
#define GNUNET_NO
Definition: gnunet_common.h:78
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
size_t slen
Length of the string in the buffer.
char * abuf
Allocated buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
#define GNUNET_malloc(size)
Wrapper around malloc.
Here is the caller graph for this function:

◆ sb_strkcmp()

static int sb_strkcmp ( const struct StringBuffer str1,
const struct StringBuffer str2,
size_t  k 
)
static

Compare 'str1', starting from position 'k', with whole 'str2'.

Parameters
str1first string to compare, starting from position 'k'
str2second string for comparison
kstarting position in 'str1'
Returns
-1 if any of the strings is NULL, 0 if equal, non 0 otherwise

Definition at line 1117 of file regex_internal.c.

References GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs_simplify().

1120 {
1121  if ((GNUNET_YES == str1->null_flag) || (GNUNET_YES == str2->null_flag) ||
1122  (k > str1->slen) || (str1->slen - k != str2->slen))
1123  return -1;
1124  return memcmp(&str1->sbuf[k], str2->sbuf, str2->slen);
1125 }
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
Here is the caller graph for this function:

◆ number_states()

static void number_states ( void *  cls,
const unsigned int  count,
struct REGEX_INTERNAL_State s 
)
static

Helper function used as 'action' in 'REGEX_INTERNAL_automaton_traverse' function to create the depth-first numbering of the states.

Parameters
clsstates array.
countcurrent state counter.
scurrent state.

Definition at line 1137 of file regex_internal.c.

References REGEX_INTERNAL_State::dfs_id.

Referenced by automaton_create_proofs(), and REGEX_INTERNAL_construct_nfa().

1140 {
1141  struct REGEX_INTERNAL_State **states = cls;
1142 
1143  s->dfs_id = count;
1144  if (NULL != states)
1145  states[count] = s;
1146 }
unsigned int dfs_id
Linear state ID accquired by depth-first-search.
Here is the caller graph for this function:

◆ automaton_create_proofs_simplify()

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 
)
static

Construct the regular expression given the inductive step, $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}, and simplify the resulting expression saved in R_cur_ij.

Parameters
R_last_ijvalue of $R^{(k-1)_{ij}.
R_last_ikvalue of $R^{(k-1)_{ik}.
R_last_kkvalue of $R^{(k-1)_{kk}.
R_last_kjvalue of $R^{(k-1)_{kj}.
R_cur_ijresult for this inductive step is saved in R_cur_ij, R_cur_ij is expected to be NULL when called!
R_cur_loptimization – kept between iterations to avoid realloc
R_cur_roptimization – kept between iterations to avoid realloc

Definition at line 1169 of file regex_internal.c.

References StringBuffer::abuf, GNUNET_memcpy, GNUNET_NO, GNUNET_YES, has_epsilon(), needs_parentheses(), StringBuffer::null_flag, remove_epsilon(), remove_parentheses(), sb_free(), sb_init(), sb_nullstrcmp(), sb_printf1(), sb_printf2(), sb_printf3(), sb_strcmp(), sb_strdup(), sb_strkcmp(), sb_strncmp(), sb_strncmp_cstr(), StringBuffer::sbuf, StringBuffer::slen, and StringBuffer::synced.

Referenced by automaton_create_proofs().

1176 {
1177  struct StringBuffer R_temp_ij;
1178  struct StringBuffer R_temp_ik;
1179  struct StringBuffer R_temp_kj;
1180  struct StringBuffer R_temp_kk;
1181  int eps_check;
1182  int ij_ik_cmp;
1183  int ij_kj_cmp;
1184  int ik_kk_cmp;
1185  int kk_kj_cmp;
1186  int clean_ik_kk_cmp;
1187  int clean_kk_kj_cmp;
1188  size_t length;
1189  size_t length_l;
1190  size_t length_r;
1191 
1192  /*
1193  * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1194  * R_last == R^{(k-1)}, R_cur == R^{(k)}
1195  * R_cur_ij = R_cur_l | R_cur_r
1196  * R_cur_l == R^{(k-1)}_{ij}
1197  * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1198  */
1199 
1200  if ((GNUNET_YES == R_last_ij->null_flag) &&
1201  ((GNUNET_YES == R_last_ik->null_flag) ||
1202  (GNUNET_YES == R_last_kj->null_flag)))
1203  {
1204  /* R^{(k)}_{ij} = N | N */
1205  R_cur_ij->null_flag = GNUNET_YES;
1206  R_cur_ij->synced = GNUNET_NO;
1207  return;
1208  }
1209 
1210  if ((GNUNET_YES == R_last_ik->null_flag) ||
1211  (GNUNET_YES == R_last_kj->null_flag))
1212  {
1213  /* R^{(k)}_{ij} = R^{(k-1)}_{ij} | N */
1214  if (GNUNET_YES == R_last_ij->synced)
1215  {
1216  R_cur_ij->synced = GNUNET_YES;
1217  R_cur_ij->null_flag = GNUNET_NO;
1218  return;
1219  }
1220  R_cur_ij->synced = GNUNET_YES;
1221  sb_strdup(R_cur_ij, R_last_ij);
1222  return;
1223  }
1224  R_cur_ij->synced = GNUNET_NO;
1225 
1226  /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
1227  * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} */
1228 
1229  R_cur_r->null_flag = GNUNET_YES;
1230  R_cur_r->slen = 0;
1231  R_cur_l->null_flag = GNUNET_YES;
1232  R_cur_l->slen = 0;
1233 
1234  /* cache results from strcmp, we might need these many times */
1235  ij_kj_cmp = sb_nullstrcmp(R_last_ij, R_last_kj);
1236  ij_ik_cmp = sb_nullstrcmp(R_last_ij, R_last_ik);
1237  ik_kk_cmp = sb_nullstrcmp(R_last_ik, R_last_kk);
1238  kk_kj_cmp = sb_nullstrcmp(R_last_kk, R_last_kj);
1239 
1240  /* Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
1241  * as parentheses, so we can better compare the contents */
1242 
1243  memset(&R_temp_ij, 0, sizeof(struct StringBuffer));
1244  memset(&R_temp_ik, 0, sizeof(struct StringBuffer));
1245  memset(&R_temp_kk, 0, sizeof(struct StringBuffer));
1246  memset(&R_temp_kj, 0, sizeof(struct StringBuffer));
1247  remove_epsilon(R_last_ik, &R_temp_ik);
1248  remove_epsilon(R_last_kk, &R_temp_kk);
1249  remove_epsilon(R_last_kj, &R_temp_kj);
1250  remove_parentheses(&R_temp_ik);
1251  remove_parentheses(&R_temp_kk);
1252  remove_parentheses(&R_temp_kj);
1253  clean_ik_kk_cmp = sb_nullstrcmp(R_last_ik, &R_temp_kk);
1254  clean_kk_kj_cmp = sb_nullstrcmp(&R_temp_kk, R_last_kj);
1255 
1256  /* construct R_cur_l (and, if necessary R_cur_r) */
1257  if (GNUNET_YES != R_last_ij->null_flag)
1258  {
1259  /* Assign R_temp_ij to R_last_ij and remove epsilon as well
1260  * as parentheses, so we can better compare the contents */
1261  remove_epsilon(R_last_ij, &R_temp_ij);
1262  remove_parentheses(&R_temp_ij);
1263 
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)))
1267  {
1268  if (0 == R_temp_ij.slen)
1269  {
1270  R_cur_r->null_flag = GNUNET_NO;
1271  }
1272  else if ((0 == sb_strncmp_cstr(R_last_ij, "(|", 2)) ||
1273  (0 == sb_strncmp_cstr(R_last_ik, "(|", 2) &&
1274  0 == sb_strncmp_cstr(R_last_kj, "(|", 2)))
1275  {
1276  /*
1277  * a|(e|a)a*(e|a) = a*
1278  * a|(e|a)(e|a)*(e|a) = a*
1279  * (e|a)|aa*a = a*
1280  * (e|a)|aa*(e|a) = a*
1281  * (e|a)|(e|a)a*a = a*
1282  * (e|a)|(e|a)a*(e|a) = a*
1283  * (e|a)|(e|a)(e|a)*(e|a) = a*
1284  */
1285  if (GNUNET_YES == needs_parentheses(&R_temp_ij))
1286  sb_printf1(R_cur_r, "(%.*s)*", 3, &R_temp_ij);
1287  else
1288  sb_printf1(R_cur_r, "%.*s*", 1, &R_temp_ij);
1289  }
1290  else
1291  {
1292  /*
1293  * a|aa*a = a+
1294  * a|(e|a)a*a = a+
1295  * a|aa*(e|a) = a+
1296  * a|(e|a)(e|a)*a = a+
1297  * a|a(e|a)*(e|a) = a+
1298  */
1299  if (GNUNET_YES == needs_parentheses(&R_temp_ij))
1300  sb_printf1(R_cur_r, "(%.*s)+", 3, &R_temp_ij);
1301  else
1302  sb_printf1(R_cur_r, "%.*s+", 1, &R_temp_ij);
1303  }
1304  }
1305  else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) &&
1306  (0 != clean_ik_kk_cmp))
1307  {
1308  /* a|ab*b = ab* */
1309  if (0 == R_last_kk->slen)
1310  sb_strdup(R_cur_r, R_last_ij);
1311  else if (GNUNET_YES == needs_parentheses(&R_temp_kk))
1312  sb_printf2(R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1313  else
1314  sb_printf2(R_cur_r, "%.*s%.*s*", 1, R_last_ij, R_last_kk);
1315  R_cur_l->null_flag = GNUNET_YES;
1316  }
1317  else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) &&
1318  (0 != clean_kk_kj_cmp))
1319  {
1320  /* a|bb*a = b*a */
1321  if (R_last_kk->slen < 1)
1322  {
1323  sb_strdup(R_cur_r, R_last_kj);
1324  }
1325  else if (GNUNET_YES == needs_parentheses(&R_temp_kk))
1326  sb_printf2(R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1327  else
1328  sb_printf2(R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1329 
1330  R_cur_l->null_flag = GNUNET_YES;
1331  }
1332  else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) &&
1333  (!has_epsilon(R_last_ij)) && has_epsilon(R_last_kk))
1334  {
1335  /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */
1336  if (needs_parentheses(&R_temp_kk))
1337  sb_printf2(R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1338  else
1339  sb_printf2(R_cur_r, "%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
1340  R_cur_l->null_flag = GNUNET_YES;
1341  }
1342  else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) &&
1343  (!has_epsilon(R_last_ij)) && has_epsilon(R_last_kk))
1344  {
1345  /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a */
1346  if (needs_parentheses(&R_temp_kk))
1347  sb_printf2(R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
1348  else
1349  sb_printf2(R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
1350  R_cur_l->null_flag = GNUNET_YES;
1351  }
1352  else
1353  {
1354  sb_strdup(R_cur_l, R_last_ij);
1355  remove_parentheses(R_cur_l);
1356  }
1357  }
1358  else
1359  {
1360  /* we have no left side */
1361  R_cur_l->null_flag = GNUNET_YES;
1362  }
1363 
1364  /* construct R_cur_r, if not already constructed */
1365  if (GNUNET_YES == R_cur_r->null_flag)
1366  {
1367  length = R_temp_kk.slen - R_last_ik->slen;
1368 
1369  /* a(ba)*bx = (ab)+x */
1370  if ((length > 0) && (GNUNET_YES != R_last_kk->null_flag) &&
1371  (0 < R_last_kk->slen) && (GNUNET_YES != R_last_kj->null_flag) &&
1372  (0 < R_last_kj->slen) && (GNUNET_YES != R_last_ik->null_flag) &&
1373  (0 < R_last_ik->slen) &&
1374  (0 == sb_strkcmp(&R_temp_kk, R_last_ik, length)) &&
1375  (0 == sb_strncmp(&R_temp_kk, R_last_kj, length)))
1376  {
1377  struct StringBuffer temp_a;
1378  struct StringBuffer temp_b;
1379 
1380  sb_init(&temp_a, length);
1381  sb_init(&temp_b, R_last_kj->slen - length);
1382 
1383  length_l = length;
1384  temp_a.sbuf = temp_a.abuf;
1385  GNUNET_memcpy(temp_a.sbuf, R_last_kj->sbuf, length_l);
1386  temp_a.slen = length_l;
1387 
1388  length_r = R_last_kj->slen - length;
1389  temp_b.sbuf = temp_b.abuf;
1390  GNUNET_memcpy(temp_b.sbuf, &R_last_kj->sbuf[length], length_r);
1391  temp_b.slen = length_r;
1392 
1393  /* e|(ab)+ = (ab)* */
1394  if ((GNUNET_YES != R_cur_l->null_flag) && (0 == R_cur_l->slen) &&
1395  (0 == temp_b.slen))
1396  {
1397  sb_printf2(R_cur_r, "(%.*s%.*s)*", 3, R_last_ik, &temp_a);
1398  sb_free(R_cur_l);
1399  R_cur_l->null_flag = GNUNET_YES;
1400  }
1401  else
1402  {
1403  sb_printf3(R_cur_r, "(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
1404  }
1405  sb_free(&temp_a);
1406  sb_free(&temp_b);
1407  }
1408  else if (0 == sb_strcmp(&R_temp_ik, &R_temp_kk) &&
1409  0 == sb_strcmp(&R_temp_kk, &R_temp_kj))
1410  {
1411  /*
1412  * (e|a)a*(e|a) = a*
1413  * (e|a)(e|a)*(e|a) = a*
1414  */
1415  if (has_epsilon(R_last_ik) && has_epsilon(R_last_kj))
1416  {
1417  if (needs_parentheses(&R_temp_kk))
1418  sb_printf1(R_cur_r, "(%.*s)*", 3, &R_temp_kk);
1419  else
1420  sb_printf1(R_cur_r, "%.*s*", 1, &R_temp_kk);
1421  }
1422  /* aa*a = a+a */
1423  else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) &&
1424  (!has_epsilon(R_last_ik)))
1425  {
1426  if (needs_parentheses(&R_temp_kk))
1427  sb_printf2(R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
1428  else
1429  sb_printf2(R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
1430  }
1431  /*
1432  * (e|a)a*a = a+
1433  * aa*(e|a) = a+
1434  * a(e|a)*(e|a) = a+
1435  * (e|a)a*a = a+
1436  */
1437  else
1438  {
1439  eps_check = (has_epsilon(R_last_ik) + has_epsilon(R_last_kk) +
1440  has_epsilon(R_last_kj));
1441 
1442  if (1 == eps_check)
1443  {
1444  if (needs_parentheses(&R_temp_kk))
1445  sb_printf1(R_cur_r, "(%.*s)+", 3, &R_temp_kk);
1446  else
1447  sb_printf1(R_cur_r, "%.*s+", 1, &R_temp_kk);
1448  }
1449  }
1450  }
1451  /*
1452  * aa*b = a+b
1453  * (e|a)(e|a)*b = a*b
1454  */
1455  else if (0 == sb_strcmp(&R_temp_ik, &R_temp_kk))
1456  {
1457  if (has_epsilon(R_last_ik))
1458  {
1459  if (needs_parentheses(&R_temp_kk))
1460  sb_printf2(R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1461  else
1462  sb_printf2(R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1463  }
1464  else
1465  {
1466  if (needs_parentheses(&R_temp_kk))
1467  sb_printf2(R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
1468  else
1469  sb_printf2(R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
1470  }
1471  }
1472  /*
1473  * ba*a = ba+
1474  * b(e|a)*(e|a) = ba*
1475  */
1476  else if (0 == sb_strcmp(&R_temp_kk, &R_temp_kj))
1477  {
1478  if (has_epsilon(R_last_kj))
1479  {
1480  if (needs_parentheses(&R_temp_kk))
1481  sb_printf2(R_cur_r, "%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
1482  else
1483  sb_printf2(R_cur_r, "%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
1484  }
1485  else
1486  {
1487  if (needs_parentheses(&R_temp_kk))
1488  sb_printf2(R_cur_r, "(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
1489  else
1490  sb_printf2(R_cur_r, "%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
1491  }
1492  }
1493  else
1494  {
1495  if (0 < R_temp_kk.slen)
1496  {
1497  if (needs_parentheses(&R_temp_kk))
1498  {
1499  sb_printf3(R_cur_r,
1500  "%.*s(%.*s)*%.*s",
1501  3,
1502  R_last_ik,
1503  &R_temp_kk,
1504  R_last_kj);
1505  }
1506  else
1507  {
1508  sb_printf3(R_cur_r,
1509  "%.*s%.*s*%.*s",
1510  1,
1511  R_last_ik,
1512  &R_temp_kk,
1513  R_last_kj);
1514  }
1515  }
1516  else
1517  {
1518  sb_printf2(R_cur_r, "%.*s%.*s", 0, R_last_ik, R_last_kj);
1519  }
1520  }
1521  }
1522  sb_free(&R_temp_ij);
1523  sb_free(&R_temp_ik);
1524  sb_free(&R_temp_kk);
1525  sb_free(&R_temp_kj);
1526 
1527  if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag))
1528  {
1529  R_cur_ij->null_flag = GNUNET_YES;
1530  return;
1531  }
1532 
1533  if ((GNUNET_YES != R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag))
1534  {
1535  struct StringBuffer tmp;
1536 
1537  tmp = *R_cur_ij;
1538  *R_cur_ij = *R_cur_l;
1539  *R_cur_l = tmp;
1540  return;
1541  }
1542 
1543  if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES != R_cur_r->null_flag))
1544  {
1545  struct StringBuffer tmp;
1546 
1547  tmp = *R_cur_ij;
1548  *R_cur_ij = *R_cur_r;
1549  *R_cur_r = tmp;
1550  return;
1551  }
1552 
1553  if (0 == sb_nullstrcmp(R_cur_l, R_cur_r))
1554  {
1555  struct StringBuffer tmp;
1556 
1557  tmp = *R_cur_ij;
1558  *R_cur_ij = *R_cur_l;
1559  *R_cur_l = tmp;
1560  return;
1561  }
1562  sb_printf2(R_cur_ij, "(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
1563 }
static void remove_epsilon(const struct StringBuffer *str, struct StringBuffer *ret)
Remove an epsilon from the string str.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
static void sb_printf1(struct StringBuffer *ret, const char *format, size_t extra_chars, const struct StringBuffer *sarg)
Format a string buffer.
#define GNUNET_NO
Definition: gnunet_common.h:78
static void sb_strdup(struct StringBuffer *out, const struct StringBuffer *in)
Copy the given string buffer from &#39;in&#39; to &#39;out&#39;.
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.
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
static void sb_init(struct StringBuffer *sb, size_t n)
Initialize string buffer for storing strings of up to n characters.
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 int sb_nullstrcmp(const struct StringBuffer *s1, const struct StringBuffer *s2)
Compare two strings for equality.
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 int sb_strncmp(const struct StringBuffer *str1, const struct StringBuffer *str2, size_t n)
Compare n bytes of &#39;str1&#39; and &#39;str2&#39;.
static int has_epsilon(const struct StringBuffer *str)
Check if the string &#39;str&#39; starts with an epsilon (empty string).
static int sb_strncmp_cstr(const struct StringBuffer *str1, const char *str2, size_t n)
Compare n bytes of &#39;str1&#39; and &#39;str2&#39;.
static int sb_strcmp(const struct StringBuffer *s1, const struct StringBuffer *s2)
Compare two strings for equality.
static void sb_free(struct StringBuffer *sb)
Free resources of the given string buffer.
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
String container for faster string operations.
static void remove_parentheses(struct StringBuffer *str)
Remove parentheses surrounding string str.
char * sbuf
Buffer holding the string (may start in the middle!); NOT 0-terminated!
static int sb_strkcmp(const struct StringBuffer *str1, const struct StringBuffer *str2, size_t k)
Compare &#39;str1&#39;, starting from position &#39;k&#39;, with whole &#39;str2&#39;.
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...
Here is the call graph for this function:
Here is the caller graph for this function:

◆ automaton_create_proofs()

static int automaton_create_proofs ( struct REGEX_INTERNAL_Automaton a)
static

Create proofs for all states in the given automaton.

Implementation of the algorithm descriped in chapter 3.2.1 of "Automata Theory, Languages, and Computation 3rd Edition" by Hopcroft, Motwani and Ullman.

Each state in the automaton gets assigned 'proof' and 'hash' (hash of the proof) fields. The starting state will only have a valid proof/hash if it has any incoming transitions.

Parameters
aautomaton for which to assign proofs and hashes, must not be NULL

Definition at line 1578 of file regex_internal.c.

References automaton_create_proofs_simplify(), REGEX_INTERNAL_Automaton::canonical_regex, REGEX_INTERNAL_State::dfs_id, GNUNET_assert, GNUNET_CRYPTO_hash(), GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_free_non_null, GNUNET_log_strerror, GNUNET_malloc_large, GNUNET_NO, GNUNET_OK, GNUNET_strndup, GNUNET_SYSERR, GNUNET_YES, REGEX_INTERNAL_Transition::label, needs_parentheses(), REGEX_INTERNAL_Transition::next, StringBuffer::null_flag, number_states(), proof, REGEX_INTERNAL_State::proof, REGEX_INTERNAL_automaton_traverse(), sb_append(), sb_append_cstr(), sb_free(), sb_init(), sb_strdup_cstr(), sb_wrap(), StringBuffer::sbuf, StringBuffer::slen, REGEX_INTERNAL_Automaton::start, REGEX_INTERNAL_Automaton::state_count, t, and REGEX_INTERNAL_Transition::to_state.

Referenced by REGEX_INTERNAL_construct_dfa().

1579 {
1580  unsigned int n = a->state_count;
1581  struct REGEX_INTERNAL_State *states[n];
1582  struct StringBuffer *R_last;
1583  struct StringBuffer *R_cur;
1584  struct StringBuffer R_cur_r;
1585  struct StringBuffer R_cur_l;
1586  struct StringBuffer *R_swap;
1587  struct REGEX_INTERNAL_Transition *t;
1588  struct StringBuffer complete_regex;
1589  unsigned int i;
1590  unsigned int j;
1591  unsigned int k;
1592 
1593  R_last = GNUNET_malloc_large(sizeof(struct StringBuffer) * n * n);
1594  R_cur = GNUNET_malloc_large(sizeof(struct StringBuffer) * n * n);
1595  if ((NULL == R_last) || (NULL == R_cur))
1596  {
1598  GNUNET_free_non_null(R_cur);
1599  GNUNET_free_non_null(R_last);
1600  return GNUNET_SYSERR;
1601  }
1602 
1603  /* create depth-first numbering of the states, initializes 'state' */
1605  a->start,
1606  NULL,
1607  NULL,
1608  &number_states,
1609  states);
1610 
1611  for (i = 0; i < n; i++)
1612  GNUNET_assert(NULL != states[i]);
1613  for (i = 0; i < n; i++)
1614  for (j = 0; j < n; j++)
1615  R_last[i * n + j].null_flag = GNUNET_YES;
1616 
1617  /* Compute regular expressions of length "1" between each pair of states */
1618  for (i = 0; i < n; i++)
1619  {
1620  for (t = states[i]->transitions_head; NULL != t; t = t->next)
1621  {
1622  j = t->to_state->dfs_id;
1623  if (GNUNET_YES == R_last[i * n + j].null_flag)
1624  {
1625  sb_strdup_cstr(&R_last[i * n + j], t->label);
1626  }
1627  else
1628  {
1629  sb_append_cstr(&R_last[i * n + j], "|");
1630  sb_append_cstr(&R_last[i * n + j], t->label);
1631  }
1632  }
1633  /* add self-loop: i is reachable from i via epsilon-transition */
1634  if (GNUNET_YES == R_last[i * n + i].null_flag)
1635  {
1636  R_last[i * n + i].slen = 0;
1637  R_last[i * n + i].null_flag = GNUNET_NO;
1638  }
1639  else
1640  {
1641  sb_wrap(&R_last[i * n + i], "(|%.*s)", 3);
1642  }
1643  }
1644  for (i = 0; i < n; i++)
1645  for (j = 0; j < n; j++)
1646  if (needs_parentheses(&R_last[i * n + j]))
1647  sb_wrap(&R_last[i * n + j], "(%.*s)", 2);
1648  /* Compute regular expressions of length "k" between each pair of states per
1649  * induction */
1650  memset(&R_cur_l, 0, sizeof(struct StringBuffer));
1651  memset(&R_cur_r, 0, sizeof(struct StringBuffer));
1652  for (k = 0; k < n; k++)
1653  {
1654  for (i = 0; i < n; i++)
1655  {
1656  for (j = 0; j < n; j++)
1657  {
1658  /* Basis for the recursion:
1659  * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1660  * R_last == R^{(k-1)}, R_cur == R^{(k)}
1661  */
1662 
1663  /* Create R_cur[i][j] and simplify the expression */
1664  automaton_create_proofs_simplify(&R_last[i * n + j],
1665  &R_last[i * n + k],
1666  &R_last[k * n + k],
1667  &R_last[k * n + j],
1668  &R_cur[i * n + j],
1669  &R_cur_l,
1670  &R_cur_r);
1671  }
1672  }
1673  /* set R_last = R_cur */
1674  R_swap = R_last;
1675  R_last = R_cur;
1676  R_cur = R_swap;
1677  /* clear 'R_cur' for next iteration */
1678  for (i = 0; i < n; i++)
1679  for (j = 0; j < n; j++)
1680  R_cur[i * n + j].null_flag = GNUNET_YES;
1681  }
1682  sb_free(&R_cur_l);
1683  sb_free(&R_cur_r);
1684  /* assign proofs and hashes */
1685  for (i = 0; i < n; i++)
1686  {
1687  if (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag)
1688  {
1689  states[i]->proof = GNUNET_strndup(R_last[a->start->dfs_id * n + i].sbuf,
1690  R_last[a->start->dfs_id * n + i].slen);
1691  GNUNET_CRYPTO_hash(states[i]->proof,
1692  strlen(states[i]->proof),
1693  &states[i]->hash);
1694  }
1695  }
1696 
1697  /* complete regex for whole DFA: union of all pairs (start state/accepting
1698  * state(s)). */
1699  sb_init(&complete_regex, 16 * n);
1700  for (i = 0; i < n; i++)
1701  {
1702  if (states[i]->accepting)
1703  {
1704  if ((0 == complete_regex.slen) &&
1705  (0 < R_last[a->start->dfs_id * n + i].slen))
1706  {
1707  sb_append(&complete_regex, &R_last[a->start->dfs_id * n + i]);
1708  }
1709  else if ((GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) &&
1710  (0 < R_last[a->start->dfs_id * n + i].slen))
1711  {
1712  sb_append_cstr(&complete_regex, "|");
1713  sb_append(&complete_regex, &R_last[a->start->dfs_id * n + i]);
1714  }
1715  }
1716  }
1717  a->canonical_regex =
1718  GNUNET_strndup(complete_regex.sbuf, complete_regex.slen);
1719 
1720  /* cleanup */
1721  sb_free(&complete_regex);
1722  for (i = 0; i < n; i++)
1723  for (j = 0; j < n; j++)
1724  {
1725  sb_free(&R_cur[i * n + j]);
1726  sb_free(&R_last[i * n + j]);
1727  }
1728  GNUNET_free(R_cur);
1729  GNUNET_free(R_last);
1730  return GNUNET_OK;
1731 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
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 struct GNUNET_SCHEDULER_Task * t
Main task.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
char * proof
Proof for this state.
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&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
#define GNUNET_log_strerror(level, cmd)
Log an error message at log-level &#39;level&#39; that indicates a failure of the command &#39;cmd&#39; with the mess...
static void sb_append(struct StringBuffer *ret, const struct StringBuffer *sarg)
Append a string.
static uint64_t proof
Definition: gnunet-scrypt.c:41
static void sb_strdup_cstr(struct StringBuffer *out, const char *cstr)
Copy the given string buffer from &#39;in&#39; to &#39;out&#39;.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:44
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...
int16_t null_flag
Buffer currently represents "NULL" (not the empty string!)
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.
struct REGEX_INTERNAL_State * start
First state of the automaton.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
#define GNUNET_strndup(a, length)
Wrapper around GNUNET_xstrndup_.
unsigned int dfs_id
Linear state ID accquired by depth-first-search.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * canonical_regex
Canonical regex (result of RX->NFA->DFA->RX)
char * label
Label for this transition.
static void sb_free(struct StringBuffer *sb)
Free resources of the given string buffer.
#define GNUNET_YES
Definition: gnunet_common.h:77
size_t slen
Length of the string in the buffer.
String container for faster string operations.
static void number_states(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Helper function used as &#39;action&#39; in &#39;REGEX_INTERNAL_automaton_traverse&#39; function to create the depth-...
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 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.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_state_create()

static struct REGEX_INTERNAL_State* dfa_state_create ( struct REGEX_INTERNAL_Context ctx,
struct REGEX_INTERNAL_StateSet nfa_states 
)
static

Creates a new DFA state based on a set of NFA states.

Needs to be freed using automaton_destroy_state.

Parameters
ctxcontext
nfa_statesset of NFA states on which the DFA should be based on
Returns
new DFA state

Definition at line 1744 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, GNUNET_asprintf(), GNUNET_malloc, GNUNET_new, GNUNET_realloc, GNUNET_snprintf(), REGEX_INTERNAL_State::id, REGEX_INTERNAL_State::index, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_StateSet_MDLL::len, REGEX_INTERNAL_State::lowlink, REGEX_INTERNAL_State::name, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::nfa_set, REGEX_INTERNAL_StateSet::off, state_add_transition(), REGEX_INTERNAL_Context::state_id, REGEX_INTERNAL_StateSet::states, and REGEX_INTERNAL_State::transitions_head.

Referenced by construct_dfa_states(), and REGEX_INTERNAL_construct_dfa().

1746 {
1747  struct REGEX_INTERNAL_State *s;
1748  char *pos;
1749  size_t len;
1750  struct REGEX_INTERNAL_State *cstate;
1751  struct REGEX_INTERNAL_Transition *ctran;
1752  unsigned int i;
1753 
1754  s = GNUNET_new(struct REGEX_INTERNAL_State);
1755  s->id = ctx->state_id++;
1756  s->index = -1;
1757  s->lowlink = -1;
1758 
1759  if (NULL == nfa_states)
1760  {
1761  GNUNET_asprintf(&s->name, "s%i", s->id);
1762  return s;
1763  }
1764 
1765  s->nfa_set = *nfa_states;
1766 
1767  if (nfa_states->off < 1)
1768  return s;
1769 
1770  /* Create a name based on 'nfa_states' */
1771  len = nfa_states->off * 14 + 4;
1772  s->name = GNUNET_malloc(len);
1773  strcat(s->name, "{");
1774  pos = s->name + 1;
1775 
1776  for (i = 0; i < nfa_states->off; i++)
1777  {
1778  cstate = nfa_states->states[i];
1779  GNUNET_snprintf(pos, pos - s->name + len, "%i,", cstate->id);
1780  pos += strlen(pos);
1781 
1782  /* Add a transition for each distinct label to NULL state */
1783  for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
1784  if (NULL != ctran->label)
1785  state_add_transition(ctx, s, ctran->label, NULL);
1786 
1787  /* If the nfa_states contain an accepting state, the new dfa state is also
1788  * accepting. */
1789  if (cstate->accepting)
1790  s->accepting = 1;
1791  }
1792  pos[-1] = '}';
1793  s->name = GNUNET_realloc(s->name, strlen(s->name) + 1);
1794 
1795  memset(nfa_states, 0, sizeof(struct REGEX_INTERNAL_StateSet));
1796  return s;
1797 }
int index
Used for SCC detection.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
int accepting
If this is an accepting state or not.
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
unsigned int state_id
Unique state id.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
struct REGEX_INTERNAL_StateSet nfa_set
Set of states on which this state is based on.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
char * name
Human readable name of the state.
#define GNUNET_realloc(ptr, size)
Wrapper around realloc.
struct REGEX_INTERNAL_State ** states
Array of states.
Transition between two 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.
unsigned int off
Number of entries in use in the &#39;states&#39; array.
char * label
Label for this transition.
int lowlink
Used for SCC detection.
unsigned int id
Unique state id.
#define GNUNET_malloc(size)
Wrapper around malloc.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_move()

static unsigned int dfa_move ( struct REGEX_INTERNAL_State **  s,
const char *  str 
)
static

Move from the given state 's' to the next state on transition 'str'.

Consumes as much of the given 'str' as possible (usefull for strided DFAs). On return 's' will point to the next state, and the length of the substring used for this transition will be returned. If no transition possible 0 is returned and 's' points to NULL.

Parameters
sstarting state, will point to the next state or NULL (if no transition possible)
stredge label to follow (will match longest common prefix)
Returns
length of the substring comsumed from 'str'

Definition at line 1814 of file regex_internal.c.

References REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_StateSet_MDLL::len, REGEX_INTERNAL_Transition::next, t, and REGEX_INTERNAL_Transition::to_state.

Referenced by evaluate_dfa().

1815 {
1816  struct REGEX_INTERNAL_Transition *t;
1817  struct REGEX_INTERNAL_State *new_s;
1818  unsigned int len;
1819  unsigned int max_len;
1820 
1821  if (NULL == s)
1822  return 0;
1823 
1824  new_s = NULL;
1825  max_len = 0;
1826  for (t = (*s)->transitions_head; NULL != t; t = t->next)
1827  {
1828  len = strlen(t->label);
1829 
1830  if (0 == strncmp(t->label, str, len))
1831  {
1832  if (len >= max_len)
1833  {
1834  max_len = len;
1835  new_s = t->to_state;
1836  }
1837  }
1838  }
1839 
1840  *s = new_s;
1841  return max_len;
1842 }
struct REGEX_INTERNAL_Transition * next
This is a linked list.
static struct GNUNET_SCHEDULER_Task * t
Main task.
Transition between two states.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
Here is the caller graph for this function:

◆ mark_states()

static void mark_states ( void *  cls,
const unsigned int  count,
struct REGEX_INTERNAL_State s 
)
static

Set the given state 'marked' to GNUNET_YES.

Used by the dfa_remove_unreachable_states() function to detect unreachable states in the automaton.

Parameters
clsclosure, not used.
countcount, not used.
sstate where the marked attribute will be set to GNUNET_YES.

Definition at line 1855 of file regex_internal.c.

References GNUNET_YES, and REGEX_INTERNAL_State::marked.

Referenced by dfa_remove_unreachable_states().

1858 {
1859  s->marked = GNUNET_YES;
1860 }
int marked
Marking of the state.
#define GNUNET_YES
Definition: gnunet_common.h:77
Here is the caller graph for this function:

◆ dfa_remove_unreachable_states()

static void dfa_remove_unreachable_states ( struct REGEX_INTERNAL_Automaton a)
static

Remove all unreachable states from DFA 'a'.

Unreachable states are those states that are not reachable from the starting state.

Parameters
aDFA automaton

Definition at line 1870 of file regex_internal.c.

References automaton_remove_state(), GNUNET_NO, mark_states(), REGEX_INTERNAL_State::marked, REGEX_INTERNAL_State::next, REGEX_INTERNAL_automaton_traverse(), REGEX_INTERNAL_Automaton::start, and REGEX_INTERNAL_Automaton::states_head.

Referenced by dfa_minimize().

1871 {
1872  struct REGEX_INTERNAL_State *s;
1873  struct REGEX_INTERNAL_State *s_next;
1874 
1875  /* 1. unmark all states */
1876  for (s = a->states_head; NULL != s; s = s->next)
1877  s->marked = GNUNET_NO;
1878 
1879  /* 2. traverse dfa from start state and mark all visited states */
1881  a->start,
1882  NULL,
1883  NULL,
1884  &mark_states,
1885  NULL);
1886 
1887  /* 3. delete all states that were not visited */
1888  for (s = a->states_head; NULL != s; s = s_next)
1889  {
1890  s_next = s->next;
1891  if (GNUNET_NO == s->marked)
1892  automaton_remove_state(a, s);
1893  }
1894 }
struct REGEX_INTERNAL_State * states_head
DLL of states.
#define GNUNET_NO
Definition: gnunet_common.h:78
int marked
Marking of the state.
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&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
struct REGEX_INTERNAL_State * start
First state of the automaton.
static void automaton_remove_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Remove a state from the given automaton &#39;a&#39;.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
static void mark_states(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Set the given state &#39;marked&#39; to GNUNET_YES.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_remove_dead_states()

static void dfa_remove_dead_states ( struct REGEX_INTERNAL_Automaton a)
static

Remove all dead states from the DFA 'a'.

Dead states are those states that do not transition to any other state but themselves.

Parameters
aDFA automaton

Definition at line 1904 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_remove_state(), DFA, GNUNET_assert, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::states_head, t, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_State::transitions_head, and REGEX_INTERNAL_Automaton::type.

Referenced by dfa_minimize().

1905 {
1906  struct REGEX_INTERNAL_State *s;
1907  struct REGEX_INTERNAL_State *s_next;
1908  struct REGEX_INTERNAL_Transition *t;
1909  int dead;
1910 
1911  GNUNET_assert(DFA == a->type);
1912 
1913  for (s = a->states_head; NULL != s; s = s_next)
1914  {
1915  s_next = s->next;
1916 
1917  if (s->accepting)
1918  continue;
1919 
1920  dead = 1;
1921  for (t = s->transitions_head; NULL != t; t = t->next)
1922  {
1923  if (NULL != t->to_state && t->to_state != s)
1924  {
1925  dead = 0;
1926  break;
1927  }
1928  }
1929 
1930  if (0 == dead)
1931  continue;
1932 
1933  /* state s is dead, remove it */
1934  automaton_remove_state(a, s);
1935  }
1936 }
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
int accepting
If this is an accepting state or not.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
enum REGEX_INTERNAL_AutomatonType type
Type of the automaton.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static struct GNUNET_SCHEDULER_Task * t
Main task.
Transition between two states.
static void automaton_remove_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Remove a state from the given automaton &#39;a&#39;.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_merge_nondistinguishable_states()

static int dfa_merge_nondistinguishable_states ( struct REGEX_INTERNAL_Context ctx,
struct REGEX_INTERNAL_Automaton a 
)
static

Merge all non distinguishable states in the DFA 'a'.

Parameters
ctxcontext
aDFA automaton
Returns
GNUNET_OK on success

Definition at line 1947 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_merge_states(), GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_log, GNUNET_log_strerror, GNUNET_malloc_large, GNUNET_OK, GNUNET_SYSERR, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_State::marked, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, table, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_State::transition_count, and REGEX_INTERNAL_State::transitions_head.

Referenced by dfa_minimize().

1949 {
1950  uint32_t *table;
1951  struct REGEX_INTERNAL_State *s1;
1952  struct REGEX_INTERNAL_State *s2;
1953  struct REGEX_INTERNAL_Transition *t1;
1954  struct REGEX_INTERNAL_Transition *t2;
1955  struct REGEX_INTERNAL_State *s1_next;
1956  struct REGEX_INTERNAL_State *s2_next;
1957  int change;
1958  unsigned int num_equal_edges;
1959  unsigned int i;
1960  unsigned int state_cnt;
1961  unsigned long long idx;
1962  unsigned long long idx1;
1963 
1964  if ((NULL == a) || (0 == a->state_count))
1965  {
1967  "Could not merge nondistinguishable states, automaton was NULL.\n");
1968  return GNUNET_SYSERR;
1969  }
1970 
1971  state_cnt = a->state_count;
1972  table = GNUNET_malloc_large(
1973  (sizeof(uint32_t) * state_cnt * state_cnt / 32) + sizeof(uint32_t));
1974  if (NULL == table)
1975  {
1977  return GNUNET_SYSERR;
1978  }
1979 
1980  for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next)
1981  s1->marked = i++;
1982 
1983  /* Mark all pairs of accepting/!accepting states */
1984  for (s1 = a->states_head; NULL != s1; s1 = s1->next)
1985  for (s2 = a->states_head; NULL != s2; s2 = s2->next)
1986  if ((s1->accepting && !s2->accepting) ||
1987  (!s1->accepting && s2->accepting))
1988  {
1989  idx = (unsigned long long)s1->marked * state_cnt + s2->marked;
1990  table[idx / 32] |= (1U << (idx % 32));
1991  }
1992 
1993  /* Find all equal states */
1994  change = 1;
1995  while (0 != change)
1996  {
1997  change = 0;
1998  for (s1 = a->states_head; NULL != s1; s1 = s1->next)
1999  {
2000  for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
2001  {
2002  idx = (unsigned long long)s1->marked * state_cnt + s2->marked;
2003  if (0 != (table[idx / 32] & (1U << (idx % 32))))
2004  continue;
2005  num_equal_edges = 0;
2006  for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
2007  {
2008  for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
2009  {
2010  if (0 == strcmp(t1->label, t2->label))
2011  {
2012  num_equal_edges++;
2013  /* same edge, but targets definitively different, so we're different
2014  as well */
2015  if (t1->to_state->marked > t2->to_state->marked)
2016  idx1 = (unsigned long long)t1->to_state->marked * state_cnt +
2017  t2->to_state->marked;
2018  else
2019  idx1 = (unsigned long long)t2->to_state->marked * state_cnt +
2020  t1->to_state->marked;
2021  if (0 != (table[idx1 / 32] & (1U << (idx1 % 32))))
2022  {
2023  table[idx / 32] |= (1U << (idx % 32));
2024  change = 1; /* changed a marker, need to run again */
2025  }
2026  }
2027  }
2028  }
2029  if ((num_equal_edges != s1->transition_count) ||
2030  (num_equal_edges != s2->transition_count))
2031  {
2032  /* Make sure ALL edges of possible equal states are the same */
2033  table[idx / 32] |= (1U << (idx % 32));
2034  change = 1; /* changed a marker, need to run again */
2035  }
2036  }
2037  }
2038  }
2039 
2040  /* Merge states that are equal */
2041  for (s1 = a->states_head; NULL != s1; s1 = s1_next)
2042  {
2043  s1_next = s1->next;
2044  for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
2045  {
2046  s2_next = s2->next;
2047  idx = (unsigned long long)s1->marked * state_cnt + s2->marked;
2048  if (0 == (table[idx / 32] & (1U << (idx % 32))))
2049  automaton_merge_states(ctx, a, s1, s2);
2050  }
2051  }
2052 
2053  GNUNET_free(table);
2054  return GNUNET_OK;
2055 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
int accepting
If this is an accepting state or not.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
#define GNUNET_malloc_large(size)
Wrapper around malloc.
int marked
Marking of the state.
#define GNUNET_log_strerror(level, cmd)
Log an error message at log-level &#39;level&#39; that indicates a failure of the command &#39;cmd&#39; with the mess...
unsigned int transition_count
Number of transitions from this state to other states.
static struct PeerEntry ** table
Table with our interned peer IDs.
Definition: peer.c:54
Transition between two states.
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.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
#define GNUNET_log(kind,...)
char * label
Label for this transition.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_minimize()

static int dfa_minimize ( struct REGEX_INTERNAL_Context ctx,
struct REGEX_INTERNAL_Automaton a 
)
static

Minimize the given DFA 'a' by removing all unreachable states, removing all dead states and merging all non distinguishable states.

Parameters
ctxcontext
aDFA automaton
Returns
GNUNET_OK on success

Definition at line 2067 of file regex_internal.c.

References DFA, dfa_merge_nondistinguishable_states(), dfa_remove_dead_states(), dfa_remove_unreachable_states(), GNUNET_assert, GNUNET_OK, GNUNET_SYSERR, and REGEX_INTERNAL_Automaton::type.

Referenced by REGEX_INTERNAL_construct_dfa().

2069 {
2070  if (NULL == a)
2071  return GNUNET_SYSERR;
2072 
2073  GNUNET_assert(DFA == a->type);
2074 
2075  /* 1. remove unreachable states */
2077 
2078  /* 2. remove dead states */
2080 
2081  /* 3. Merge nondistinguishable states */
2083  return GNUNET_SYSERR;
2084  return GNUNET_OK;
2085 }
static void dfa_remove_unreachable_states(struct REGEX_INTERNAL_Automaton *a)
Remove all unreachable states from DFA &#39;a&#39;.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
enum REGEX_INTERNAL_AutomatonType type
Type of the automaton.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
static void dfa_remove_dead_states(struct REGEX_INTERNAL_Automaton *a)
Remove all dead states from the DFA &#39;a&#39;.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
static int dfa_merge_nondistinguishable_states(struct REGEX_INTERNAL_Context *ctx, struct REGEX_INTERNAL_Automaton *a)
Merge all non distinguishable states in the DFA &#39;a&#39;.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_add_multi_strides_helper()

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 
)
static

Recursive helper function to add strides to a DFA.

Parameters
clscontext, contains stride length and strided transitions DLL.
depthcurrent depth of the depth-first traversal of the graph.
labelcurrent label, string that contains all labels on the path from 'start' to 's'.
startstart state for the depth-first traversal of the graph.
scurrent state in the depth-first traversal

Definition at line 2121 of file regex_internal.c.

References ctx, REGEX_INTERNAL_Transition::from_state, GNUNET_asprintf(), GNUNET_CONTAINER_DLL_insert, GNUNET_free_non_null, GNUNET_new, GNUNET_strdup, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_Transition::next, start, REGEX_INTERNAL_Strided_Context::stride, t, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_State::transitions_head, REGEX_INTERNAL_Strided_Context::transitions_head, and REGEX_INTERNAL_Strided_Context::transitions_tail.

Referenced by dfa_add_multi_strides().

2126 {
2127  struct REGEX_INTERNAL_Strided_Context *ctx = cls;
2128  struct REGEX_INTERNAL_Transition *t;
2129  char *new_label;
2130 
2131  if (depth == ctx->stride)
2132  {
2134  t->label = GNUNET_strdup(label);
2135  t->to_state = s;
2136  t->from_state = start;
2138  ctx->transitions_tail,
2139  t);
2140  }
2141  else
2142  {
2143  for (t = s->transitions_head; NULL != t; t = t->next)
2144  {
2145  /* Do not consider self-loops, because it end's up in too many
2146  * transitions */
2147  if (t->to_state == t->from_state)
2148  continue;
2149 
2150  if (NULL != label)
2151  {
2152  GNUNET_asprintf(&new_label, "%s%s", label, t->label);
2153  }
2154  else
2155  new_label = GNUNET_strdup(t->label);
2156 
2158  (depth + 1),
2159  new_label,
2160  start,
2161  t->to_state);
2162  }
2163  }
2165 }
#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.
struct REGEX_INTERNAL_Transition * transitions_tail
Strided transitions DLL.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
const unsigned int stride
Length of the strides.
Transition between two states.
Context for adding strided transitions to a DFA.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
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_Transition * transitions_head
Strided transitions DLL.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_add_multi_strides()

static void dfa_add_multi_strides ( void *  cls,
const unsigned int  count,
struct REGEX_INTERNAL_State s 
)
static

Function called for each state in the DFA.

Starts a traversal of depth set in context starting from state 's'.

Parameters
clscontext.
countnot used.
scurrent state.

Definition at line 2177 of file regex_internal.c.

References dfa_add_multi_strides_helper().

Referenced by REGEX_INTERNAL_dfa_add_multi_strides().

2180 {
2181  dfa_add_multi_strides_helper(cls, 0, NULL, s, s);
2182 }
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.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ REGEX_INTERNAL_dfa_add_multi_strides()

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'.

Parameters
regex_ctxregex context needed to add transitions to the automaton.
dfaDFA to which the multi strided transitions should be added.
stride_lenlength of the strides.

Definition at line 2193 of file regex_internal.c.

References dfa_add_multi_strides(), REGEX_INTERNAL_Transition::from_state, GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_free_non_null, GNUNET_YES, REGEX_INTERNAL_Automaton::is_multistrided, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_automaton_traverse(), REGEX_INTERNAL_Automaton::start, state_add_transition(), t, REGEX_INTERNAL_Transition::to_state, REGEX_INTERNAL_Strided_Context::transitions_head, and REGEX_INTERNAL_Strided_Context::transitions_tail.

2196 {
2197  struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
2198  struct REGEX_INTERNAL_Transition *t;
2199  struct REGEX_INTERNAL_Transition *t_next;
2200 
2201  if (1 > stride_len || GNUNET_YES == dfa->is_multistrided)
2202  return;
2203 
2204  /* Compute the new transitions of given stride_len */
2206  dfa->start,
2207  NULL,
2208  NULL,
2210  &ctx);
2211 
2212  /* Add all the new transitions to the automaton. */
2213  for (t = ctx.transitions_head; NULL != t; t = t_next)
2214  {
2215  t_next = t->next;
2216  state_add_transition(regex_ctx, t->from_state, t->label, t->to_state);
2219  GNUNET_free(t);
2220  }
2221 
2222  /* Mark this automaton as multistrided */
2223  dfa->is_multistrided = GNUNET_YES;
2224 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_tail
Strided transitions DLL.
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
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.
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&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
Transition between two states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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.
int is_multistrided
GNUNET_YES, if multi strides have been added to the Automaton.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
#define GNUNET_YES
Definition: gnunet_common.h:77
#define GNUNET_free(ptr)
Wrapper around free.
struct REGEX_INTERNAL_Transition * transitions_head
Strided transitions DLL.
Here is the call graph for this function:

◆ dfa_compress_paths_helper()

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.

Does DFS on the DFA graph and adds new transitions to the given transitions DLL and marks states that should be removed by setting state->contained to GNUNET_YES.

Parameters
dfaDFA for which the paths should be compressed.
startstarting state for linear path search.
curcurrent state in the recursive DFS.
labelcurrent label (string of traversed labels).
max_lenmaximal path compression length.
transitions_headtransitions DLL.
transitions_tailtransitions DLL.

Definition at line 2240 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, REGEX_INTERNAL_State::contained, REGEX_INTERNAL_Transition::from_state, GNUNET_asprintf(), GNUNET_CONTAINER_DLL_insert, GNUNET_free, GNUNET_new, GNUNET_NO, GNUNET_REGEX_INITIAL_BYTES, GNUNET_strdup, GNUNET_YES, REGEX_INTERNAL_State::incoming_transition_count, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_State::marked, REGEX_INTERNAL_Transition::next, start, REGEX_INTERNAL_Automaton::start, t, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by dfa_compress_paths().

2247 {
2248  struct REGEX_INTERNAL_Transition *t;
2249  char *new_label;
2250 
2251 
2252  if (NULL != label &&
2253  ((cur->incoming_transition_count > 1 || GNUNET_YES == cur->accepting ||
2254  GNUNET_YES == cur->marked) ||
2255  (start != dfa->start && max_len > 0 && max_len == strlen(label)) ||
2256  (start == dfa->start && GNUNET_REGEX_INITIAL_BYTES == strlen(label))))
2257  {
2259  t->label = GNUNET_strdup(label);
2260  t->to_state = cur;
2261  t->from_state = start;
2262  GNUNET_CONTAINER_DLL_insert(*transitions_head, *transitions_tail, t);
2263 
2264  if (GNUNET_NO == cur->marked)
2265  {
2267  cur,
2268  cur,
2269  NULL,
2270  max_len,
2271  transitions_head,
2272  transitions_tail);
2273  }
2274  return;
2275  }
2276  else if (cur != start)
2277  cur->contained = GNUNET_YES;
2278 
2279  if (GNUNET_YES == cur->marked && cur != start)
2280  return;
2281 
2282  cur->marked = GNUNET_YES;
2283 
2284 
2285  for (t = cur->transitions_head; NULL != t; t = t->next)
2286  {
2287  if (NULL != label)
2288  GNUNET_asprintf(&new_label, "%s%s", label, t->label);
2289  else
2290  new_label = GNUNET_strdup(t->label);
2291 
2292  if (t->to_state != cur)
2293  {
2295  start,
2296  t->to_state,
2297  new_label,
2298  max_len,
2299  transitions_head,
2300  transitions_tail);
2301  }
2302  GNUNET_free(new_label);
2303  }
2304 }
unsigned int incoming_transition_count
Number of incoming transitions.
#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.
int accepting
If this is an accepting state or not.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
int contained
Marking the state as contained.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
int marked
Marking of the state.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
Transition between two states.
#define GNUNET_REGEX_INITIAL_BYTES
Constant for how many bytes the initial string regex should have.
struct REGEX_INTERNAL_State * start
First state of the automaton.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
#define GNUNET_YES
Definition: gnunet_common.h:77
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.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ dfa_compress_paths()

static void dfa_compress_paths ( struct REGEX_INTERNAL_Context regex_ctx,
struct REGEX_INTERNAL_Automaton dfa,
unsigned int  max_len 
)
static

Compress paths in the given 'dfa'.

Linear paths like 0->1->2->3 will be compressed to 0->3 by combining transitions.

Parameters
regex_ctxcontext for adding new transitions.
dfaDFA representation, will directly modify the given DFA.
max_lenmaximal length of the compressed paths.

Definition at line 2316 of file regex_internal.c.

References automaton_remove_state(), REGEX_INTERNAL_State::contained, dfa_compress_paths_helper(), REGEX_INTERNAL_Transition::from_state, GNUNET_CONTAINER_DLL_remove, GNUNET_free, GNUNET_free_non_null, GNUNET_NO, GNUNET_YES, REGEX_INTERNAL_State::incoming_transition_count, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_State::marked, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::start, state_add_transition(), REGEX_INTERNAL_Automaton::states_head, t, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by REGEX_INTERNAL_construct_dfa().

2319 {
2320  struct REGEX_INTERNAL_State *s;
2321  struct REGEX_INTERNAL_State *s_next;
2322  struct REGEX_INTERNAL_Transition *t;
2323  struct REGEX_INTERNAL_Transition *t_next;
2324  struct REGEX_INTERNAL_Transition *transitions_head = NULL;
2325  struct REGEX_INTERNAL_Transition *transitions_tail = NULL;
2326 
2327  if (NULL == dfa)
2328  return;
2329 
2330  /* Count the incoming transitions on each state. */
2331  for (s = dfa->states_head; NULL != s; s = s->next)
2332  {
2333  for (t = s->transitions_head; NULL != t; t = t->next)
2334  {
2335  if (NULL != t->to_state)
2337  }
2338  }
2339 
2340  /* Unmark all states. */
2341  for (s = dfa->states_head; NULL != s; s = s->next)
2342  {
2343  s->marked = GNUNET_NO;
2344  s->contained = GNUNET_NO;
2345  }
2346 
2347  /* Add strides and mark states that can be deleted. */
2349  dfa->start,
2350  dfa->start,
2351  NULL,
2352  max_len,
2353  &transitions_head,
2354  &transitions_tail);
2355 
2356  /* Add all the new transitions to the automaton. */
2357  for (t = transitions_head; NULL != t; t = t_next)
2358  {
2359  t_next = t->next;
2360  state_add_transition(regex_ctx, t->from_state, t->label, t->to_state);
2361  GNUNET_CONTAINER_DLL_remove(transitions_head, transitions_tail, t);
2363  GNUNET_free(t);
2364  }
2365 
2366  /* Remove marked states (including their incoming and outgoing transitions). */
2367  for (s = dfa->states_head; NULL != s; s = s_next)
2368  {
2369  s_next = s->next;
2370  if (GNUNET_YES == s->contained)
2371  automaton_remove_state(dfa, s);
2372  }
2373 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
unsigned int incoming_transition_count
Number of incoming transitions.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
int contained
Marking the state as contained.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
int marked
Marking of the state.
Transition between two states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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 automaton_remove_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Remove a state from the given automaton &#39;a&#39;.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
#define GNUNET_YES
Definition: gnunet_common.h:77
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.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_fragment_create()

static struct REGEX_INTERNAL_Automaton* nfa_fragment_create ( struct REGEX_INTERNAL_State start,
struct REGEX_INTERNAL_State end 
)
static

Creates a new NFA fragment.

Needs to be cleared using automaton_fragment_clear.

Parameters
startstarting state
endend state
Returns
new NFA fragment

Definition at line 2386 of file regex_internal.c.

References automaton_add_state(), end, REGEX_INTERNAL_Automaton::end, GNUNET_new, NFA, start, REGEX_INTERNAL_Automaton::start, REGEX_INTERNAL_Automaton::state_count, and REGEX_INTERNAL_Automaton::type.

Referenced by nfa_add_alternation(), nfa_add_concatenation(), nfa_add_label(), nfa_add_question_op(), and nfa_add_star_op().

2388 {
2389  struct REGEX_INTERNAL_Automaton *n;
2390 
2392 
2393  n->type = NFA;
2394  n->start = NULL;
2395  n->end = NULL;
2396  n->state_count = 0;
2397 
2398  if (NULL == start || NULL == end)
2399  return n;
2400 
2401  automaton_add_state(n, end);
2402  automaton_add_state(n, start);
2403 
2404  n->state_count = 2;
2405 
2406  n->start = start;
2407  n->end = end;
2408 
2409  return n;
2410 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
enum REGEX_INTERNAL_AutomatonType type
Type of the automaton.
static void automaton_add_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Add a state to the automaton &#39;a&#39;, always use this function to alter the states DLL of the automaton...
#define GNUNET_new(type)
Allocate a struct or union of the given type.
Automaton representation.
struct REGEX_INTERNAL_State * start
First state of the automaton.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_states()

static void nfa_add_states ( struct REGEX_INTERNAL_Automaton n,
struct REGEX_INTERNAL_State states_head,
struct REGEX_INTERNAL_State states_tail 
)
static

Adds a list of states to the given automaton 'n'.

Parameters
nautomaton to which the states should be added
states_headhead of the DLL of states
states_tailtail of the DLL of states

Definition at line 2421 of file regex_internal.c.

References GNUNET_ERROR_TYPE_ERROR, GNUNET_log, REGEX_INTERNAL_State::next, REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by nfa_add_alternation(), nfa_add_concatenation(), nfa_add_question_op(), and nfa_add_star_op().

2424 {
2425  struct REGEX_INTERNAL_State *s;
2426 
2427  if (NULL == n || NULL == states_head)
2428  {
2429  GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
2430  return;
2431  }
2432 
2433  if (NULL == n->states_head)
2434  {
2435  n->states_head = states_head;
2436  n->states_tail = states_tail;
2437  return;
2438  }
2439 
2440  if (NULL != states_head)
2441  {
2442  n->states_tail->next = states_head;
2443  n->states_tail = states_tail;
2444  }
2445 
2446  for (s = states_head; NULL != s; s = s->next)
2447  n->state_count++;
2448 }
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
#define GNUNET_log(kind,...)
Here is the caller graph for this function:

◆ nfa_state_create()

static struct REGEX_INTERNAL_State* nfa_state_create ( struct REGEX_INTERNAL_Context ctx,
int  accepting 
)
static

Creates a new NFA state.

Needs to be freed using automaton_destroy_state.

Parameters
ctxcontext
acceptingis it an accepting state or not
Returns
new NFA state

Definition at line 2460 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, REGEX_INTERNAL_State::contained, GNUNET_asprintf(), GNUNET_new, GNUNET_NO, REGEX_INTERNAL_State::id, REGEX_INTERNAL_State::index, REGEX_INTERNAL_State::lowlink, REGEX_INTERNAL_State::marked, REGEX_INTERNAL_State::name, REGEX_INTERNAL_State::scc_id, and REGEX_INTERNAL_Context::state_id.

Referenced by nfa_add_alternation(), nfa_add_label(), nfa_add_question_op(), and nfa_add_star_op().

2461 {
2462  struct REGEX_INTERNAL_State *s;
2463 
2464  s = GNUNET_new(struct REGEX_INTERNAL_State);
2465  s->id = ctx->state_id++;
2466  s->accepting = accepting;
2467  s->marked = GNUNET_NO;
2468  s->contained = 0;
2469  s->index = -1;
2470  s->lowlink = -1;
2471  s->scc_id = 0;
2472  s->name = NULL;
2473  GNUNET_asprintf(&s->name, "s%i", s->id);
2474 
2475  return s;
2476 }
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
int index
Used for SCC detection.
int accepting
If this is an accepting state or not.
unsigned int state_id
Unique state id.
int contained
Marking the state as contained.
#define GNUNET_NO
Definition: gnunet_common.h:78
#define GNUNET_new(type)
Allocate a struct or union of the given type.
int marked
Marking of the state.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
char * name
Human readable name of the state.
int lowlink
Used for SCC detection.
unsigned int id
Unique state id.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_closure_set_create()

static void nfa_closure_set_create ( struct REGEX_INTERNAL_StateSet ret,
struct REGEX_INTERNAL_Automaton nfa,
struct REGEX_INTERNAL_StateSet states,
const char *  label 
)
static

Calculates the closure set for the given set of states.

Parameters
retset to sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
nfathe NFA containing 's'
stateslist of states on which to base the closure on
labeltransitioning label for which to base the closure on, pass NULL for epsilon transition

Definition at line 2489 of file regex_internal.c.

References REGEX_INTERNAL_State::contained, GNUNET_CONTAINER_MDLL_insert, GNUNET_CONTAINER_MDLL_insert_tail, GNUNET_CONTAINER_MDLL_remove, REGEX_INTERNAL_StateSet_MDLL::head, REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_StateSet_MDLL::len, REGEX_INTERNAL_Transition::next, nullstrcmp(), REGEX_INTERNAL_StateSet::off, state_compare(), state_set_append(), REGEX_INTERNAL_StateSet::states, REGEX_INTERNAL_StateSet_MDLL::tail, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by construct_dfa_states(), evaluate_nfa(), and REGEX_INTERNAL_construct_dfa().

2493 {
2494  struct REGEX_INTERNAL_State *s;
2495  unsigned int i;
2496  struct REGEX_INTERNAL_StateSet_MDLL cls_stack;
2497  struct REGEX_INTERNAL_State *clsstate;
2498  struct REGEX_INTERNAL_State *currentstate;
2499  struct REGEX_INTERNAL_Transition *ctran;
2500 
2501  memset(ret, 0, sizeof(struct REGEX_INTERNAL_StateSet));
2502  if (NULL == states)
2503  return;
2504 
2505  for (i = 0; i < states->off; i++)
2506  {
2507  s = states->states[i];
2508 
2509  /* Add start state to closure only for epsilon closure */
2510  if (NULL == label)
2511  state_set_append(ret, s);
2512 
2513  /* initialize work stack */
2514  cls_stack.head = NULL;
2515  cls_stack.tail = NULL;
2516  GNUNET_CONTAINER_MDLL_insert(ST, cls_stack.head, cls_stack.tail, s);
2517  cls_stack.len = 1;
2518 
2519  while (NULL != (currentstate = cls_stack.tail))
2520  {
2522  cls_stack.head,
2523  cls_stack.tail,
2524  currentstate);
2525  cls_stack.len--;
2526  for (ctran = currentstate->transitions_head; NULL != ctran;
2527  ctran = ctran->next)
2528  {
2529  if (NULL == (clsstate = ctran->to_state))
2530  continue;
2531  if (0 != clsstate->contained)
2532  continue;
2533  if (0 != nullstrcmp(label, ctran->label))
2534  continue;
2535  state_set_append(ret, clsstate);
2537  cls_stack.head,
2538  cls_stack.tail,
2539  clsstate);
2540  cls_stack.len++;
2541  clsstate->contained = 1;
2542  }
2543  }
2544  }
2545  for (i = 0; i < ret->off; i++)
2546  ret->states[i]->contained = 0;
2547 
2548  if (ret->off > 1)
2549  qsort(ret->states,
2550  ret->off,
2551  sizeof(struct REGEX_INTERNAL_State *),
2552  &state_compare);
2553 }
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
int contained
Marking the state as contained.
Set of states using MDLL API.
#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 int state_compare(const void *a, const void *b)
Compare two states.
static int nullstrcmp(const char *str1, const char *str2)
Compare two strings for equality.
#define GNUNET_CONTAINER_MDLL_remove(mdll, head, tail, element)
Remove an element from a MDLL.
struct REGEX_INTERNAL_State ** states
Array of states.
Transition between two states.
static void state_set_append(struct REGEX_INTERNAL_StateSet *set, struct REGEX_INTERNAL_State *state)
Append state to the given StateSet.
unsigned int off
Number of entries in use in the &#39;states&#39; array.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_concatenation()

static void nfa_add_concatenation ( struct REGEX_INTERNAL_Context ctx)
static

Pops two NFA fragments (a, b) from the stack and concatenates them (ab)

Parameters
ctxcontext

Definition at line 2562 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_fragment_clear(), REGEX_INTERNAL_Automaton::end, GNUNET_assert, GNUNET_CONTAINER_DLL_insert_tail, GNUNET_CONTAINER_DLL_remove, nfa_add_states(), nfa_fragment_create(), REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, REGEX_INTERNAL_Automaton::start, state_add_transition(), REGEX_INTERNAL_Automaton::state_count, REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by REGEX_INTERNAL_construct_nfa().

2563 {
2564  struct REGEX_INTERNAL_Automaton *a;
2565  struct REGEX_INTERNAL_Automaton *b;
2566  struct REGEX_INTERNAL_Automaton *new_nfa;
2567 
2568  b = ctx->stack_tail;
2569  GNUNET_assert(NULL != b);
2571  a = ctx->stack_tail;
2572  GNUNET_assert(NULL != a);
2574 
2575  state_add_transition(ctx, a->end, NULL, b->start);
2576  a->end->accepting = 0;
2577  b->end->accepting = 1;
2578 
2579  new_nfa = nfa_fragment_create(NULL, NULL);
2580  nfa_add_states(new_nfa, a->states_head, a->states_tail);
2581  nfa_add_states(new_nfa, b->states_head, b->states_tail);
2582  new_nfa->start = a->start;
2583  new_nfa->end = b->end;
2584  new_nfa->state_count += a->state_count + b->state_count;
2587 
2589 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
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.
int accepting
If this is an accepting state or not.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Automaton representation.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
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 &#39;n&#39;.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
static void automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a)
Clears an automaton fragment.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_star_op()

static void nfa_add_star_op ( struct REGEX_INTERNAL_Context ctx)
static

Pops a NFA fragment from the stack (a) and adds a new fragment (a*)

Parameters
ctxcontext

Definition at line 2598 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_fragment_clear(), end, REGEX_INTERNAL_Automaton::end, GNUNET_CONTAINER_DLL_insert_tail, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, nfa_add_states(), nfa_fragment_create(), nfa_state_create(), REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, start, REGEX_INTERNAL_Automaton::start, state_add_transition(), REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by REGEX_INTERNAL_construct_nfa().

2599 {
2600  struct REGEX_INTERNAL_Automaton *a;
2601  struct REGEX_INTERNAL_Automaton *new_nfa;
2602  struct REGEX_INTERNAL_State *start;
2603  struct REGEX_INTERNAL_State *end;
2604 
2605  a = ctx->stack_tail;
2606 
2607  if (NULL == a)
2608  {
2609  GNUNET_log(
2611  "nfa_add_star_op failed, because there was no element on the stack");
2612  return;
2613  }
2614 
2616 
2617  start = nfa_state_create(ctx, 0);
2618  end = nfa_state_create(ctx, 1);
2619 
2620  state_add_transition(ctx, start, NULL, a->start);
2621  state_add_transition(ctx, start, NULL, end);
2622  state_add_transition(ctx, a->end, NULL, a->start);
2623  state_add_transition(ctx, a->end, NULL, end);
2624 
2625  a->end->accepting = 0;
2626  end->accepting = 1;
2627 
2628  new_nfa = nfa_fragment_create(start, end);
2629  nfa_add_states(new_nfa, a->states_head, a->states_tail);
2631 
2633 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
int accepting
If this is an accepting state or not.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Automaton representation.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
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 &#39;n&#39;.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
#define GNUNET_log(kind,...)
static void automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a)
Clears an automaton fragment.
static struct REGEX_INTERNAL_State * nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting)
Creates a new NFA state.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_plus_op()

static void nfa_add_plus_op ( struct REGEX_INTERNAL_Context ctx)
static

Pops an NFA fragment (a) from the stack and adds a new fragment (a+)

Parameters
ctxcontext

Definition at line 2642 of file regex_internal.c.

References REGEX_INTERNAL_Automaton::end, GNUNET_CONTAINER_DLL_insert_tail, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, REGEX_INTERNAL_Automaton::start, and state_add_transition().

Referenced by REGEX_INTERNAL_construct_nfa().

2643 {
2644  struct REGEX_INTERNAL_Automaton *a;
2645 
2646  a = ctx->stack_tail;
2647 
2648  if (NULL == a)
2649  {
2650  GNUNET_log(
2652  "nfa_add_plus_op failed, because there was no element on the stack");
2653  return;
2654  }
2655 
2657 
2658  state_add_transition(ctx, a->end, NULL, a->start);
2659 
2661 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Automaton representation.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
#define GNUNET_log(kind,...)
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_question_op()

static void nfa_add_question_op ( struct REGEX_INTERNAL_Context ctx)
static

Pops an NFA fragment (a) from the stack and adds a new fragment (a?)

Parameters
ctxcontext

Definition at line 2670 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_fragment_clear(), end, REGEX_INTERNAL_Automaton::end, GNUNET_CONTAINER_DLL_insert_tail, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, nfa_add_states(), nfa_fragment_create(), nfa_state_create(), REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, start, REGEX_INTERNAL_Automaton::start, state_add_transition(), REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by REGEX_INTERNAL_construct_nfa().

2671 {
2672  struct REGEX_INTERNAL_Automaton *a;
2673  struct REGEX_INTERNAL_Automaton *new_nfa;
2674  struct REGEX_INTERNAL_State *start;
2675  struct REGEX_INTERNAL_State *end;
2676 
2677  a = ctx->stack_tail;
2678  if (NULL == a)
2679  {
2680  GNUNET_log(
2682  "nfa_add_question_op failed, because there was no element on the stack");
2683  return;
2684  }
2685 
2687 
2688  start = nfa_state_create(ctx, 0);
2689  end = nfa_state_create(ctx, 1);
2690 
2691  state_add_transition(ctx, start, NULL, a->start);
2692  state_add_transition(ctx, start, NULL, end);
2693  state_add_transition(ctx, a->end, NULL, end);
2694 
2695  a->end->accepting = 0;
2696 
2697  new_nfa = nfa_fragment_create(start, end);
2698  nfa_add_states(new_nfa, a->states_head, a->states_tail);
2701 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
int accepting
If this is an accepting state or not.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Automaton representation.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
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 &#39;n&#39;.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
#define GNUNET_log(kind,...)
static void automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a)
Clears an automaton fragment.
static struct REGEX_INTERNAL_State * nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting)
Creates a new NFA state.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_alternation()

static void nfa_add_alternation ( struct REGEX_INTERNAL_Context ctx)
static

Pops two NFA fragments (a, b) from the stack and adds a new NFA fragment that alternates between a and b (a|b)

Parameters
ctxcontext

Definition at line 2711 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_fragment_clear(), end, REGEX_INTERNAL_Automaton::end, GNUNET_assert, GNUNET_CONTAINER_DLL_insert_tail, GNUNET_CONTAINER_DLL_remove, nfa_add_states(), nfa_fragment_create(), nfa_state_create(), REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, start, REGEX_INTERNAL_Automaton::start, state_add_transition(), REGEX_INTERNAL_Automaton::states_head, and REGEX_INTERNAL_Automaton::states_tail.

Referenced by REGEX_INTERNAL_construct_nfa().

2712 {
2713  struct REGEX_INTERNAL_Automaton *a;
2714  struct REGEX_INTERNAL_Automaton *b;
2715  struct REGEX_INTERNAL_Automaton *new_nfa;
2716  struct REGEX_INTERNAL_State *start;
2717  struct REGEX_INTERNAL_State *end;
2718 
2719  b = ctx->stack_tail;
2720  GNUNET_assert(NULL != b);
2722  a = ctx->stack_tail;
2723  GNUNET_assert(NULL != a);
2725 
2726  start = nfa_state_create(ctx, 0);
2727  end = nfa_state_create(ctx, 1);
2728  state_add_transition(ctx, start, NULL, a->start);
2729  state_add_transition(ctx, start, NULL, b->start);
2730 
2731  state_add_transition(ctx, a->end, NULL, end);
2732  state_add_transition(ctx, b->end, NULL, end);
2733 
2734  a->end->accepting = 0;
2735  b->end->accepting = 0;
2736  end->accepting = 1;
2737 
2738  new_nfa = nfa_fragment_create(start, end);
2739  nfa_add_states(new_nfa, a->states_head, a->states_tail);
2740  nfa_add_states(new_nfa, b->states_head, b->states_tail);
2743 
2745 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
int accepting
If this is an accepting state or not.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Automaton representation.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
struct REGEX_INTERNAL_State * start
First state of the automaton.
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.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
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 &#39;n&#39;.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
static void automaton_fragment_clear(struct REGEX_INTERNAL_Automaton *a)
Clears an automaton fragment.
static struct REGEX_INTERNAL_State * nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting)
Creates a new NFA state.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ nfa_add_label()

static void nfa_add_label ( struct REGEX_INTERNAL_Context ctx,
const char *  label 
)
static

Adds a new nfa fragment to the stack.

Parameters
ctxcontext
labellabel for nfa transition

Definition at line 2755 of file regex_internal.c.

References end, GNUNET_assert, GNUNET_CONTAINER_DLL_insert_tail, nfa_fragment_create(), nfa_state_create(), REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, start, and state_add_transition().

Referenced by REGEX_INTERNAL_construct_nfa().

2756 {
2757  struct REGEX_INTERNAL_Automaton *n;
2758  struct REGEX_INTERNAL_State *start;
2759  struct REGEX_INTERNAL_State *end;
2760 
2761  GNUNET_assert(NULL != ctx);
2762 
2763  start = nfa_state_create(ctx, 0);
2764  end = nfa_state_create(ctx, 1);
2765  state_add_transition(ctx, start, label, end);
2766  n = nfa_fragment_create(start, end);
2767  GNUNET_assert(NULL != n);
2769 }
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Automaton representation.
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.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
static struct REGEX_INTERNAL_Automaton * nfa_fragment_create(struct REGEX_INTERNAL_State *start, struct REGEX_INTERNAL_State *end)
Creates a new NFA fragment.
static struct REGEX_INTERNAL_State * nfa_state_create(struct REGEX_INTERNAL_Context *ctx, int accepting)
Creates a new NFA state.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ REGEX_INTERNAL_context_init()

static void REGEX_INTERNAL_context_init ( struct REGEX_INTERNAL_Context ctx)
static

Initialize a new context.

Parameters
ctxcontext

Definition at line 2778 of file regex_internal.c.

References GNUNET_ERROR_TYPE_ERROR, GNUNET_log, REGEX_INTERNAL_Context::stack_head, REGEX_INTERNAL_Context::stack_tail, REGEX_INTERNAL_Context::state_id, and REGEX_INTERNAL_Context::transition_id.

Referenced by REGEX_INTERNAL_construct_dfa(), and REGEX_INTERNAL_construct_nfa().

2779 {
2780  if (NULL == ctx)
2781  {
2782  GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
2783  return;
2784  }
2785  ctx->state_id = 0;
2786  ctx->transition_id = 0;
2787  ctx->stack_head = NULL;
2788  ctx->stack_tail = NULL;
2789 }
unsigned int transition_id
Unique transition id.
unsigned int state_id
Unique state id.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
#define GNUNET_log(kind,...)
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
Here is the caller graph for this function:

◆ REGEX_INTERNAL_construct_nfa()

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'.

Parameters
regexregular expression string
lenlength of the string
Returns
NFA, needs to be freed using REGEX_INTERNAL_destroy_automaton

Definition at line 2801 of file regex_internal.c.

References GNUNET_array_grow, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_ERROR, GNUNET_free_non_null, GNUNET_log, GNUNET_NO, GNUNET_strdup, REGEX_INTERNAL_Automaton::is_multistrided, nfa_add_alternation(), nfa_add_concatenation(), nfa_add_label(), nfa_add_plus_op(), nfa_add_question_op(), nfa_add_star_op(), number_states(), p, REGEX_INTERNAL_Automaton::regex, REGEX_INTERNAL_automaton_destroy(), REGEX_INTERNAL_automaton_traverse(), REGEX_INTERNAL_context_init(), REGEX_INTERNAL_Context::stack_head, and REGEX_INTERNAL_Context::stack_tail.

Referenced by REGEX_INTERNAL_construct_dfa().

2802 {
2803  struct REGEX_INTERNAL_Context ctx;
2804  struct REGEX_INTERNAL_Automaton *nfa;
2805  const char *regexp;
2806  char curlabel[2];
2807  char *error_msg;
2808  unsigned int count;
2809  unsigned int altcount;
2810  unsigned int atomcount;
2811  unsigned int poff;
2812  unsigned int psize;
2813 
2814  struct {
2815  int altcount;
2816  int atomcount;
2817  } * p;
2818 
2819  if (NULL == regex || 0 == strlen(regex) || 0 == len)
2820  {
2822  "Could not parse regex. Empty regex string provided.\n");
2823 
2824  return NULL;
2825  }
2827 
2828  regexp = regex;
2829  curlabel[1] = '\0';
2830  p = NULL;
2831  error_msg = NULL;
2832  altcount = 0;
2833  atomcount = 0;
2834  poff = 0;
2835  psize = 0;
2836 
2837  for (count = 0; count < len && *regexp; count++, regexp++)
2838  {
2839  switch (*regexp)
2840  {
2841  case '(':
2842  if (atomcount > 1)
2843  {
2844  --atomcount;
2846  }
2847  if (poff == psize)
2848  GNUNET_array_grow(p, psize, psize * 2 + 4); /* FIXME why *2 +4? */
2849  p[poff].altcount = altcount;
2850  p[poff].atomcount = atomcount;
2851  poff++;
2852  altcount = 0;
2853  atomcount = 0;
2854  break;
2855 
2856  case '|':
2857  if (0 == atomcount)
2858  {
2859  error_msg = "Cannot append '|' to nothing";
2860  goto error;
2861  }
2862  while (--atomcount > 0)
2864  altcount++;
2865  break;
2866 
2867  case ')':
2868  if (0 == poff)
2869  {
2870  error_msg = "Missing opening '('";
2871  goto error;
2872  }
2873  if (0 == atomcount)
2874  {
2875  /* Ignore this: "()" */
2876  poff--;
2877  altcount = p[poff].altcount;
2878  atomcount = p[poff].atomcount;
2879  break;
2880  }
2881  while (--atomcount > 0)
2883  for (; altcount > 0; altcount--)
2885  poff--;
2886  altcount = p[poff].altcount;
2887  atomcount = p[poff].atomcount;
2888  atomcount++;
2889  break;
2890 
2891  case '*':
2892  if (atomcount == 0)
2893  {
2894  error_msg = "Cannot append '*' to nothing";
2895  goto error;
2896  }
2897  nfa_add_star_op(&ctx);
2898  break;
2899 
2900  case '+':
2901  if (atomcount == 0)
2902  {
2903  error_msg = "Cannot append '+' to nothing";
2904  goto error;
2905  }
2906  nfa_add_plus_op(&ctx);
2907  break;
2908 
2909  case '?':
2910  if (atomcount == 0)
2911  {
2912  error_msg = "Cannot append '?' to nothing";
2913  goto error;
2914  }
2916  break;
2917 
2918  default:
2919  if (atomcount > 1)
2920  {
2921  --atomcount;
2923  }
2924  curlabel[0] = *regexp;
2925  nfa_add_label(&ctx, curlabel);
2926  atomcount++;
2927  break;
2928  }
2929  }
2930  if (0 != poff)
2931  {
2932  error_msg = "Unbalanced parenthesis";
2933  goto error;
2934  }
2935  while (--atomcount > 0)
2937  for (; altcount > 0; altcount--)
2939 
2940  GNUNET_array_grow(p, psize, 0);
2941 
2942  nfa = ctx.stack_tail;
2943  GNUNET_CONTAINER_DLL_remove(ctx.stack_head, ctx.stack_tail, nfa);
2944 
2945  if (NULL != ctx.stack_head)
2946  {
2947  error_msg = "Creating the NFA failed. NFA stack was not empty!";
2948  goto error;
2949  }
2950 
2951  /* Remember the regex that was used to generate this NFA */
2952  nfa->regex = GNUNET_strdup(regex);
2953 
2954  /* create depth-first numbering of the states for pretty printing */
2956  NULL,
2957  NULL,
2958  NULL,
2959  &number_states,
2960  NULL);
2961 
2962  /* No multistriding added so far */
2963  nfa->is_multistrided = GNUNET_NO;
2964 
2965  return nfa;
2966 
2967 error:
2968  GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex);
2969  if (NULL != error_msg)
2970  GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
2971 
2973 
2974  while (NULL != (nfa = ctx.stack_head))
2975  {
2976  GNUNET_CONTAINER_DLL_remove(ctx.stack_head, ctx.stack_tail, nfa);
2978  }
2979 
2980  return NULL;
2981 }
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
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+)
#define GNUNET_NO
Definition: gnunet_common.h:78
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*)
#define GNUNET_free_non_null(ptr)
Free the memory pointed to by ptr if ptr is not NULL.
Automaton representation.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
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...
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&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
Context that contains an id counter for states and transitions as well as a DLL of automatons used as...
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
static void REGEX_INTERNAL_context_init(struct REGEX_INTERNAL_Context *ctx)
Initialize a new context.
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?)
void REGEX_INTERNAL_automaton_destroy(struct REGEX_INTERNAL_Automaton *a)
Free the memory allocated by constructing the REGEX_INTERNAL_Automaton data structure.
int is_multistrided
GNUNET_YES, if multi strides have been added to the Automaton.
#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)
static void number_states(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Helper function used as &#39;action&#39; in &#39;REGEX_INTERNAL_automaton_traverse&#39; function to create the depth-...
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
static void nfa_add_label(struct REGEX_INTERNAL_Context *ctx, const char *label)
Adds a new nfa fragment to the stack.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ construct_dfa_states()

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 
)
static

Create DFA states based on given 'nfa' and starting with 'dfa_state'.

Parameters
ctxcontext.
nfaNFA automaton.
dfaDFA automaton.
dfa_statecurrent dfa state, pass epsilon closure of first nfa state for starting.

Definition at line 2994 of file regex_internal.c.

References automaton_add_state(), dfa_state_create(), REGEX_INTERNAL_Transition::label, REGEX_INTERNAL_Transition::next, REGEX_INTERNAL_State::next, nfa_closure_set_create(), REGEX_INTERNAL_State::nfa_set, state_set_clear(), state_set_compare(), REGEX_INTERNAL_Automaton::states_head, REGEX_INTERNAL_Transition::to_state, and REGEX_INTERNAL_State::transitions_head.

Referenced by REGEX_INTERNAL_construct_dfa().

2998 {
2999  struct REGEX_INTERNAL_Transition *ctran;
3000  struct REGEX_INTERNAL_State *new_dfa_state;
3001  struct REGEX_INTERNAL_State *state_contains;
3002  struct REGEX_INTERNAL_State *state_iter;
3003  struct REGEX_INTERNAL_StateSet tmp;
3004  struct REGEX_INTERNAL_StateSet nfa_set;
3005 
3006  for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
3007  {
3008  if (NULL == ctran->label || NULL != ctran->to_state)
3009  continue;
3010 
3011  nfa_closure_set_create(&tmp, nfa, &dfa_state->nfa_set, ctran->label);
3012  nfa_closure_set_create(&nfa_set, nfa, &tmp, NULL);
3013  state_set_clear(&tmp);
3014 
3015  state_contains = NULL;
3016  for (state_iter = dfa->states_head; NULL != state_iter;
3017  state_iter = state_iter->next)
3018  {
3019  if (0 == state_set_compare(&state_iter->nfa_set, &nfa_set))
3020  {
3021  state_contains = state_iter;
3022  break;
3023  }
3024  }
3025  if (NULL == state_contains)
3026  {
3027  new_dfa_state = dfa_state_create(ctx, &nfa_set);
3028  automaton_add_state(dfa, new_dfa_state);
3029  ctran->to_state = new_dfa_state;
3030  construct_dfa_states(ctx, nfa, dfa, new_dfa_state);
3031  }
3032  else
3033  {
3034  ctran->to_state = state_contains;
3035  state_set_clear(&nfa_set);
3036  }
3037  }
3038 }
struct REGEX_INTERNAL_State * states_head
DLL of states.
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.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
static int state_set_compare(struct REGEX_INTERNAL_StateSet *sset1, struct REGEX_INTERNAL_StateSet *sset2)
Compare to state sets by comparing the id&#39;s of the states that are contained in each set...
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
static void automaton_add_state(struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *s)
Add a state to the automaton &#39;a&#39;, always use this function to alter the states DLL of the automaton...
static void state_set_clear(struct REGEX_INTERNAL_StateSet *set)
Clears the given StateSet &#39;set&#39;.
struct REGEX_INTERNAL_StateSet nfa_set
Set of states on which this state is based on.
Transition between two states.
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 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 &#39;nfa&#39; and starting with &#39;dfa_state&#39;.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * label
Label for this transition.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ REGEX_INTERNAL_construct_dfa()

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'.

Path compression means, that for example a DFA o -> a -> b -> c -> o will be compressed to o -> abc -> o. Note that this parameter influences the non-determinism of states of the resulting NFA in the DHT (number of outgoing edges with the same label). For example for an application that stores IPv4 addresses as bitstrings it could make sense to limit the path compression to 4 or 8.

Parameters
regexregular expression string.
lenlength of the regular expression.
max_path_lenlimit the path compression length to the given value. If set to 1, no path compression is applied. Set to 0 for maximal possible path compression (generally not desireable).
Returns
DFA, needs to be freed using REGEX_INTERNAL_automaton_destroy.

Definition at line 3059 of file regex_internal.c.

References automaton_add_state(), automaton_create_proofs(), construct_dfa_states(), DFA, dfa_compress_paths(), dfa_minimize(), dfa_state_create(), GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_new, GNUNET_OK, GNUNET_strdup, nfa_closure_set_create(), REGEX_INTERNAL_Automaton::regex, REGEX_INTERNAL_automaton_destroy(), REGEX_INTERNAL_construct_nfa(), REGEX_INTERNAL_context_init(), REGEX_INTERNAL_Automaton::start, state_set_append(), state_set_clear(), and REGEX_INTERNAL_Automaton::type.

Referenced by announce_regex(), main(), and REGEX_INTERNAL_announce().

3062 {
3063