GNUnet  0.11.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 1151 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 68 of file regex_internal.c.

References GNUNET_array_grow, and state.

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

70 {
71  if (set->off == set->size)
72  GNUNET_array_grow (set->states, set->size, set->size * 2 + 4);
73  set->states[set->off++] = state;
74 }
#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 86 of file regex_internal.c.

Referenced by nfa_closure_set_create(), and state_add_transition().

87 {
88  if ((NULL == str1) != (NULL == str2))
89  return -1;
90  if ((NULL == str1) && (NULL == str2))
91  return 0;
92 
93  return strcmp (str1, str2);
94 }
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 107 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().

111 {
113  struct REGEX_INTERNAL_Transition *oth;
114 
115  if (NULL == from_state)
116  {
117  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
118  return;
119  }
120 
121  /* Do not add duplicate state transitions */
122  for (t = from_state->transitions_head; NULL != t; t = t->next)
123  {
124  if ((t->to_state == to_state) && (0 == nullstrcmp (t->label, label)) &&
125  (t->from_state == from_state) )
126  return;
127  }
128 
129  /* sort transitions by label */
130  for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
131  {
132  if (0 < nullstrcmp (oth->label, label))
133  break;
134  }
135 
137  if (NULL != ctx)
138  t->id = ctx->transition_id++;
139  if (NULL != label)
140  t->label = GNUNET_strdup (label);
141  else
142  t->label = NULL;
143  t->to_state = to_state;
144  t->from_state = from_state;
145 
146  /* Add outgoing transition to 'from_state' */
147  from_state->transition_count++;
149  from_state->transitions_tail,
150  oth,
151  t);
152 }
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 162 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().

164 {
165  if ((NULL == state) || (NULL == transition))
166  return;
167 
168  if (transition->from_state != state)
169  return;
170 
171  GNUNET_free_non_null (transition->label);
172 
173  state->transition_count--;
175  state->transitions_tail,
176  transition);
177 
178  GNUNET_free (transition);
179 }
#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 193 of file regex_internal.c.

References REGEX_INTERNAL_State::id.

Referenced by nfa_closure_set_create(), and state_set_compare().

194 {
195  struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **) a;
196  struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **) b;
197 
198  return (*s1)->id - (*s2)->id;
199 }
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 212 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().

213 {
215  unsigned int count;
216 
217  if (NULL == s)
218  return 0;
219 
220  count = 0;
221 
222  for (t = s->transitions_head; NULL != t; t = t->next)
223  {
224  if (NULL != t->to_state)
225  {
226  edges[count].label = t->label;
227  edges[count].destination = t->to_state->hash;
228  count++;
229  }
230  }
231  return count;
232 }
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 244 of file regex_internal.c.

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

Referenced by construct_dfa_states().

246 {
247  int result;
248  unsigned int i;
249 
250  if ((NULL == sset1) || (NULL == sset2))
251  return 1;
252 
253  result = sset1->off - sset2->off;
254  if (result < 0)
255  return -1;
256  if (result > 0)
257  return 1;
258  for (i = 0; i < sset1->off; i++)
259  if (0 != (result = state_compare (&sset1->states[i], &sset2->states[i])))
260  break;
261  return result;
262 }
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 271 of file regex_internal.c.

References GNUNET_array_grow.

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

272 {
273  GNUNET_array_grow (set->states, set->size, 0);
274  set->off = 0;
275 }
#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 285 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().

286 {
287  if (NULL == a)
288  return;
289 
290  a->start = NULL;
291  a->end = NULL;
292  a->states_head = NULL;
293  a->states_tail = NULL;
294  a->state_count = 0;
295  GNUNET_free (a);
296 }
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 305 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().

306 {
308  struct REGEX_INTERNAL_Transition *next_t;
309 
310  if (NULL == s)
311  return;
312 
315  state_set_clear (&s->nfa_set);
316  for (t = s->transitions_head; NULL != t; t = next_t)
317  {
318  next_t = t->next;
320  }
321 
322  GNUNET_free (s);
323 }
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 335 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().

337 {
338  struct REGEX_INTERNAL_State *s_check;
339  struct REGEX_INTERNAL_Transition *t_check;
340  struct REGEX_INTERNAL_Transition *t_check_next;
341 
342  if ((NULL == a) || (NULL == s))
343  return;
344 
345  /* remove all transitions leading to this state */
346  for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
347  {
348  for (t_check = s_check->transitions_head; NULL != t_check;
349  t_check = t_check_next)
350  {
351  t_check_next = t_check->next;
352  if (t_check->to_state == s)
353  state_remove_transition (s_check, t_check);
354  }
355  }
356 
357  /* remove state */
359  a->state_count--;
360 
362 }
#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 375 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().

379 {
380  struct REGEX_INTERNAL_State *s_check;
381  struct REGEX_INTERNAL_Transition *t_check;
383  struct REGEX_INTERNAL_Transition *t_next;
384  int is_dup;
385 
386  if (s1 == s2)
387  return;
388 
389  /* 1. Make all transitions pointing to s2 point to s1, unless this transition
390  * does not already exists, if it already exists remove transition. */
391  for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
392  {
393  for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next)
394  {
395  t_next = t_check->next;
396 
397  if (s2 == t_check->to_state)
398  {
399  is_dup = GNUNET_NO;
400  for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
401  {
402  if ((t->to_state == s1) && (0 == strcmp (t_check->label, t->label)) )
403  is_dup = GNUNET_YES;
404  }
405  if (GNUNET_NO == is_dup)
406  t_check->to_state = s1;
407  else
408  state_remove_transition (t_check->from_state, t_check);
409  }
410  }
411  }
412 
413  /* 2. Add all transitions from s2 to sX to s1 */
414  for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next)
415  {
416  if (t_check->to_state != s1)
417  state_add_transition (ctx, s1, t_check->label, t_check->to_state);
418  }
419 
420  /* 3. Rename s1 to {s1,s2} */
421 #if REGEX_DEBUG_DFA
422  char *new_name;
423 
424  new_name = s1->name;
425  GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name);
426  GNUNET_free (new_name);
427 #endif
428 
429  /* remove state */
431  a->state_count--;
433 }
#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 444 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().

446 {
448  a->state_count++;
449 }
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 467 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().

474 {
476 
477  if (GNUNET_YES == marks[s->traversal_id])
478  return;
479 
480  marks[s->traversal_id] = GNUNET_YES;
481 
482  if (NULL != action)
483  action (action_cls, *count, s);
484 
485  (*count)++;
486 
487  for (t = s->transitions_head; NULL != t; t = t->next)
488  {
489  if ((NULL == check) ||
490  ((NULL != check) && (GNUNET_YES == check (check_cls, s, t)) ))
491  {
493  marks,
494  count,
495  check,
496  check_cls,
497  action,
498  action_cls);
499  }
500  }
501 }
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 518 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().

524 {
525  unsigned int count;
526  struct REGEX_INTERNAL_State *s;
527 
528  if ((NULL == a) || (0 == a->state_count))
529  return;
530 
531  int marks[a->state_count];
532 
533  for (count = 0, s = a->states_head; NULL != s && count < a->state_count;
534  s = s->next, count++)
535  {
536  s->traversal_id = count;
537  marks[s->traversal_id] = GNUNET_NO;
538  }
539 
540  count = 0;
541 
542  if (NULL == start)
543  s = a->start;
544  else
545  s = start;
546 
548  marks,
549  &count,
550  check,
551  check_cls,
552  action,
553  action_cls);
554 }
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 610 of file regex_internal.c.

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

Referenced by automaton_create_proofs_simplify().

611 {
612  if ((GNUNET_YES == s1->null_flag) && (GNUNET_YES == s2->null_flag))
613  return 0;
614  if ((GNUNET_YES == s1->null_flag) || (GNUNET_YES == s2->null_flag))
615  return -1;
616  if (s1->slen != s2->slen)
617  return -1;
618  if (0 == s1->slen)
619  return 0;
620  return memcmp (s1->sbuf, s2->sbuf, s1->slen);
621 }
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 633 of file regex_internal.c.

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

Referenced by automaton_create_proofs_simplify().

634 {
635  if (s1->slen != s2->slen)
636  return -1;
637  if (0 == s1->slen)
638  return 0;
639  return memcmp (s1->sbuf, s2->sbuf, s1->slen);
640 }
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 651 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().

652 {
653  char *old;
654 
655  GNUNET_assert (nlen >= ret->slen);
656  old = ret->abuf;
657  ret->abuf = GNUNET_malloc (nlen);
658  ret->blen = nlen;
659  GNUNET_memcpy (ret->abuf, ret->sbuf, ret->slen);
660  ret->sbuf = ret->abuf;
661  GNUNET_free_non_null (old);
662 }
#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 672 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().

673 {
674  if (GNUNET_YES == ret->null_flag)
675  ret->slen = 0;
676  ret->null_flag = GNUNET_NO;
677  if (ret->blen < sarg->slen + ret->slen)
678  sb_realloc (ret, ret->blen + sarg->slen + 128);
679  GNUNET_memcpy (&ret->sbuf[ret->slen], sarg->sbuf, sarg->slen);
680  ret->slen += sarg->slen;
681 }
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 691 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().

692 {
693  size_t cstr_len = strlen (cstr);
694 
695  if (GNUNET_YES == ret->null_flag)
696  ret->slen = 0;
697  ret->null_flag = GNUNET_NO;
698  if (ret->blen < cstr_len + ret->slen)
699  sb_realloc (ret, ret->blen + cstr_len + 128);
700  GNUNET_memcpy (&ret->sbuf[ret->slen], cstr, cstr_len);
701  ret->slen += cstr_len;
702 }
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 716 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().

717 {
718  char *temp;
719 
720  if (GNUNET_YES == ret->null_flag)
721  ret->slen = 0;
722  ret->null_flag = GNUNET_NO;
723  temp = GNUNET_malloc (ret->slen + extra_chars + 1);
724  GNUNET_snprintf (temp,
725  ret->slen + extra_chars + 1,
726  format,
727  (int) ret->slen,
728  ret->sbuf);
729  GNUNET_free_non_null (ret->abuf);
730  ret->abuf = temp;
731  ret->sbuf = temp;
732  ret->blen = ret->slen + extra_chars + 1;
733  ret->slen = ret->slen + extra_chars;
734 }
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 747 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().

751 {
752  if (ret->blen < sarg->slen + extra_chars + 1)
753  sb_realloc (ret, sarg->slen + extra_chars + 1);
754  ret->null_flag = GNUNET_NO;
755  ret->sbuf = ret->abuf;
756  ret->slen = sarg->slen + extra_chars;
757  GNUNET_snprintf (ret->sbuf, ret->blen, format, (int) sarg->slen, sarg->sbuf);
758 }
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 771 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().

776 {
777  if (ret->blen < sarg1->slen + sarg2->slen + extra_chars + 1)
778  sb_realloc (ret, sarg1->slen + sarg2->slen + extra_chars + 1);
779  ret->null_flag = GNUNET_NO;
780  ret->slen = sarg1->slen + sarg2->slen + extra_chars;
781  ret->sbuf = ret->abuf;
782  GNUNET_snprintf (ret->sbuf,
783  ret->blen,
784  format,
785  (int) sarg1->slen,
786  sarg1->sbuf,
787  (int) sarg2->slen,
788  sarg2->sbuf);
789 }
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 804 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().

810 {
811  if (ret->blen < sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1)
812  sb_realloc (ret, sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1);
813  ret->null_flag = GNUNET_NO;
814  ret->slen = sarg1->slen + sarg2->slen + sarg3->slen + extra_chars;
815  ret->sbuf = ret->abuf;
816  GNUNET_snprintf (ret->sbuf,
817  ret->blen,
818  format,
819  (int) sarg1->slen,
820  sarg1->sbuf,
821  (int) sarg2->slen,
822  sarg2->sbuf,
823  (int) sarg3->slen,
824  sarg3->sbuf);
825 }
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 835 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().

836 {
837  GNUNET_array_grow (sb->abuf, sb->blen, 0);
838  sb->slen = 0;
839  sb->sbuf = NULL;
840  sb->null_flag = GNUNET_YES;
841 }
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 851 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().

853 {
854  out->null_flag = in->null_flag;
855  if (GNUNET_YES == out->null_flag)
856  return;
857  if (out->blen < in->slen)
858  {
859  GNUNET_array_grow (out->abuf, out->blen, in->slen);
860  }
861  out->sbuf = out->abuf;
862  out->slen = in->slen;
863  GNUNET_memcpy (out->sbuf, in->sbuf, out->slen);
864 }
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 874 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().

875 {
876  if (NULL == cstr)
877  {
878  out->null_flag = GNUNET_YES;
879  return;
880  }
881  out->null_flag = GNUNET_NO;
882  out->slen = strlen (cstr);
883  if (out->blen < out->slen)
884  {
885  GNUNET_array_grow (out->abuf, out->blen, out->slen);
886  }
887  out->sbuf = out->abuf;
888  GNUNET_memcpy (out->sbuf, cstr, out->slen);
889 }
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 901 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().

902 {
903  size_t slen;
904  const char *op;
905  const char *cl;
906  const char *pos;
907  const char *end;
908  unsigned int cnt;
909 
910  if ((GNUNET_YES == str->null_flag) || ((slen = str->slen) < 2))
911  return GNUNET_NO;
912  pos = str->sbuf;
913  if ('(' != pos[0])
914  return GNUNET_YES;
915  end = str->sbuf + slen;
916  cnt = 1;
917  pos++;
918  while (cnt > 0)
919  {
920  cl = memchr (pos, ')', end - pos);
921  if (NULL == cl)
922  {
923  GNUNET_break (0);
924  return GNUNET_YES;
925  }
926  /* while '(' before ')', count opening parens */
927  while ((NULL != (op = memchr (pos, '(', end - pos))) && (op < cl))
928  {
929  cnt++;
930  pos = op + 1;
931  }
932  /* got ')' first */
933  cnt--;
934  pos = cl + 1;
935  }
936  return (*pos == '\0') ? GNUNET_NO : GNUNET_YES;
937 }
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:144
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 950 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().

951 {
952  size_t slen;
953  const char *pos;
954  const char *end;
955  const char *sbuf;
956  const char *op;
957  const char *cp;
958  unsigned int cnt;
959 
960  if (0)
961  return;
962  sbuf = str->sbuf;
963  if ((GNUNET_YES == str->null_flag) || (1 >= (slen = str->slen)) ||
964  ('(' != str->sbuf[0]) || (')' != str->sbuf[slen - 1]))
965  return;
966  cnt = 0;
967  pos = &sbuf[1];
968  end = &sbuf[slen - 1];
969  op = memchr (pos, '(', end - pos);
970  cp = memchr (pos, ')', end - pos);
971  while (NULL != cp)
972  {
973  while ((NULL != op) && (op < cp))
974  {
975  cnt++;
976  pos = op + 1;
977  op = memchr (pos, '(', end - pos);
978  }
979  while ((NULL != cp) && ((NULL == op) || (cp < op)))
980  {
981  if (0 == cnt)
982  return; /* can't strip parens */
983  cnt--;
984  pos = cp + 1;
985  cp = memchr (pos, ')', end - pos);
986  }
987  }
988  if (0 != cnt)
989  {
990  GNUNET_break (0);
991  return;
992  }
993  str->sbuf++;
994  str->slen -= 2;
995 }
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:144
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 1007 of file regex_internal.c.

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

Referenced by automaton_create_proofs_simplify().

1008 {
1009  return (GNUNET_YES != str->null_flag) && (0 < str->slen) &&
1010  ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) &&
1011  (')' == str->sbuf[str->slen - 1]);
1012 }
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 1025 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().

1026 {
1027  if (GNUNET_YES == str->null_flag)
1028  {
1029  ret->null_flag = GNUNET_YES;
1030  return;
1031  }
1032  if ((str->slen > 1) && ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) &&
1033  (')' == str->sbuf[str->slen - 1]))
1034  {
1035  /* remove epsilon */
1036  if (ret->blen < str->slen - 3)
1037  {
1038  GNUNET_array_grow (ret->abuf, ret->blen, str->slen - 3);
1039  }
1040  ret->sbuf = ret->abuf;
1041  ret->slen = str->slen - 3;
1042  GNUNET_memcpy (ret->sbuf, &str->sbuf[2], ret->slen);
1043  return;
1044  }
1045  sb_strdup (ret, str);
1046 }
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 1059 of file regex_internal.c.

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

Referenced by automaton_create_proofs_simplify().

1062 {
1063  size_t max;
1064 
1065  if ((str1->slen != str2->slen) && ((str1->slen < n) || (str2->slen < n)))
1066  return -1;
1067  max = GNUNET_MAX (str1->slen, str2->slen);
1068  if (max > n)
1069  max = n;
1070  return memcmp (str1->sbuf, str2->sbuf, max);
1071 }
#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 1084 of file regex_internal.c.

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

Referenced by automaton_create_proofs_simplify().

1085 {
1086  if (str1->slen < n)
1087  return -1;
1088  return memcmp (str1->sbuf, str2, n);
1089 }
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 1100 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().

1101 {
1102  sb->null_flag = GNUNET_NO;
1103  sb->abuf = sb->sbuf = (0 == n) ? NULL : GNUNET_malloc (n);
1104  sb->blen = n;
1105  sb->slen = 0;
1106 }
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 1119 of file regex_internal.c.

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

Referenced by automaton_create_proofs_simplify().

1122 {
1123  if ((GNUNET_YES == str1->null_flag) || (GNUNET_YES == str2->null_flag) ||
1124  (k > str1->slen) || (str1->slen - k != str2->slen))
1125  return -1;
1126  return memcmp (&str1->sbuf[k], str2->sbuf, str2->slen);
1127 }
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 1139 of file regex_internal.c.

References REGEX_INTERNAL_State::dfs_id.

Referenced by automaton_create_proofs(), and REGEX_INTERNAL_construct_nfa().

1142 {
1143  struct REGEX_INTERNAL_State **states = cls;
1144 
1145  s->dfs_id = count;
1146  if (NULL != states)
1147  states[count] = s;
1148 }
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 1171 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().

1178 {
1179  struct StringBuffer R_temp_ij;
1180  struct StringBuffer R_temp_ik;
1181  struct StringBuffer R_temp_kj;
1182  struct StringBuffer R_temp_kk;
1183  int eps_check;
1184  int ij_ik_cmp;
1185  int ij_kj_cmp;
1186  int ik_kk_cmp;
1187  int kk_kj_cmp;
1188  int clean_ik_kk_cmp;
1189  int clean_kk_kj_cmp;
1190  size_t length;
1191  size_t length_l;
1192  size_t length_r;
1193 
1194  /*
1195  * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1196  * R_last == R^{(k-1)}, R_cur == R^{(k)}
1197  * R_cur_ij = R_cur_l | R_cur_r
1198  * R_cur_l == R^{(k-1)}_{ij}
1199  * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
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  */if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1285  sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_ij);
1286  else
1287  sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_ij);
1288  }
1289  else
1290  {
1291  /*
1292  * a|aa*a = a+
1293  * a|(e|a)a*a = a+
1294  * a|aa*(e|a) = a+
1295  * a|(e|a)(e|a)*a = a+
1296  * a|a(e|a)*(e|a) = a+
1297  */if (GNUNET_YES == needs_parentheses (&R_temp_ij))
1298  sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_ij);
1299  else
1300  sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_ij);
1301  }
1302  }
1303  else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) &&
1304  (0 != clean_ik_kk_cmp))
1305  {
1306  /* a|ab*b = ab* */
1307  if (0 == R_last_kk->slen)
1308  sb_strdup (R_cur_r, R_last_ij);
1309  else if (GNUNET_YES == needs_parentheses (&R_temp_kk))
1310  sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1311  else
1312  sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, R_last_kk);
1313  R_cur_l->null_flag = GNUNET_YES;
1314  }
1315  else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) &&
1316  (0 != clean_kk_kj_cmp))
1317  {
1318  /* a|bb*a = b*a */
1319  if (R_last_kk->slen < 1)
1320  {
1321  sb_strdup (R_cur_r, R_last_kj);
1322  }
1323  else if (GNUNET_YES == needs_parentheses (&R_temp_kk))
1324  sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1325  else
1326  sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1327 
1328  R_cur_l->null_flag = GNUNET_YES;
1329  }
1330  else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) &&
1331  (! has_epsilon (R_last_ij)) && has_epsilon (R_last_kk))
1332  {
1333  /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */
1334  if (needs_parentheses (&R_temp_kk))
1335  sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
1336  else
1337  sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
1338  R_cur_l->null_flag = GNUNET_YES;
1339  }
1340  else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) &&
1341  (! has_epsilon (R_last_ij)) && has_epsilon (R_last_kk))
1342  {
1343  /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|... = b*a */
1344  if (needs_parentheses (&R_temp_kk))
1345  sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
1346  else
1347  sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
1348  R_cur_l->null_flag = GNUNET_YES;
1349  }
1350  else
1351  {
1352  sb_strdup (R_cur_l, R_last_ij);
1353  remove_parentheses (R_cur_l);
1354  }
1355  }
1356  else
1357  {
1358  /* we have no left side */
1359  R_cur_l->null_flag = GNUNET_YES;
1360  }
1361 
1362  /* construct R_cur_r, if not already constructed */
1363  if (GNUNET_YES == R_cur_r->null_flag)
1364  {
1365  length = R_temp_kk.slen - R_last_ik->slen;
1366 
1367  /* a(ba)*bx = (ab)+x */
1368  if ((length > 0) && (GNUNET_YES != R_last_kk->null_flag) &&
1369  (0 < R_last_kk->slen) && (GNUNET_YES != R_last_kj->null_flag) &&
1370  (0 < R_last_kj->slen) && (GNUNET_YES != R_last_ik->null_flag) &&
1371  (0 < R_last_ik->slen) &&
1372  (0 == sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
1373  (0 == sb_strncmp (&R_temp_kk, R_last_kj, length)))
1374  {
1375  struct StringBuffer temp_a;
1376  struct StringBuffer temp_b;
1377 
1378  sb_init (&temp_a, length);
1379  sb_init (&temp_b, R_last_kj->slen - length);
1380 
1381  length_l = length;
1382  temp_a.sbuf = temp_a.abuf;
1383  GNUNET_memcpy (temp_a.sbuf, R_last_kj->sbuf, length_l);
1384  temp_a.slen = length_l;
1385 
1386  length_r = R_last_kj->slen - length;
1387  temp_b.sbuf = temp_b.abuf;
1388  GNUNET_memcpy (temp_b.sbuf, &R_last_kj->sbuf[length], length_r);
1389  temp_b.slen = length_r;
1390 
1391  /* e|(ab)+ = (ab)* */
1392  if ((GNUNET_YES != R_cur_l->null_flag) && (0 == R_cur_l->slen) &&
1393  (0 == temp_b.slen))
1394  {
1395  sb_printf2 (R_cur_r, "(%.*s%.*s)*", 3, R_last_ik, &temp_a);
1396  sb_free (R_cur_l);
1397  R_cur_l->null_flag = GNUNET_YES;
1398  }
1399  else
1400  {
1401  sb_printf3 (R_cur_r, "(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
1402  }
1403  sb_free (&temp_a);
1404  sb_free (&temp_b);
1405  }
1406  else if ((0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
1407  (0 == sb_strcmp (&R_temp_kk, &R_temp_kj)) )
1408  {
1409  /*
1410  * (e|a)a*(e|a) = a*
1411  * (e|a)(e|a)*(e|a) = a*
1412  */
1413  if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj))
1414  {
1415  if (needs_parentheses (&R_temp_kk))
1416  sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_kk);
1417  else
1418  sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_kk);
1419  }
1420  /* aa*a = a+a */
1421  else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) &&
1422  (! has_epsilon (R_last_ik)))
1423  {
1424  if (needs_parentheses (&R_temp_kk))
1425  sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
1426  else
1427  sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
1428  }
1429  /*
1430  * (e|a)a*a = a+
1431  * aa*(e|a) = a+
1432  * a(e|a)*(e|a) = a+
1433  * (e|a)a*a = a+
1434  */else
1435  {
1436  eps_check = (has_epsilon (R_last_ik) + has_epsilon (R_last_kk)
1437  + has_epsilon (R_last_kj));
1438 
1439  if (1 == eps_check)
1440  {
1441  if (needs_parentheses (&R_temp_kk))
1442  sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_kk);
1443  else
1444  sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_kk);
1445  }
1446  }
1447  }
1448  /*
1449  * aa*b = a+b
1450  * (e|a)(e|a)*b = a*b
1451  */
1452  else if (0 == sb_strcmp (&R_temp_ik, &R_temp_kk))
1453  {
1454  if (has_epsilon (R_last_ik))
1455  {
1456  if (needs_parentheses (&R_temp_kk))
1457  sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
1458  else
1459  sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
1460  }
1461  else
1462  {
1463  if (needs_parentheses (&R_temp_kk))
1464  sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
1465  else
1466  sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
1467  }
1468  }
1469  /*
1470  * ba*a = ba+
1471  * b(e|a)*(e|a) = ba*
1472  */
1473  else if (0 == sb_strcmp (&R_temp_kk, &R_temp_kj))
1474  {
1475  if (has_epsilon (R_last_kj))
1476  {
1477  if (needs_parentheses (&R_temp_kk))
1478  sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
1479  else
1480  sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
1481  }
1482  else
1483  {
1484  if (needs_parentheses (&R_temp_kk))
1485  sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
1486  else
1487  sb_printf2 (R_cur_r, "%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
1488  }
1489  }
1490  else
1491  {
1492  if (0 < R_temp_kk.slen)
1493  {
1494  if (needs_parentheses (&R_temp_kk))
1495  {
1496  sb_printf3 (R_cur_r,
1497  "%.*s(%.*s)*%.*s",
1498  3,
1499  R_last_ik,
1500  &R_temp_kk,
1501  R_last_kj);
1502  }
1503  else
1504  {
1505  sb_printf3 (R_cur_r,
1506  "%.*s%.*s*%.*s",
1507  1,
1508  R_last_ik,
1509  &R_temp_kk,
1510  R_last_kj);
1511  }
1512  }
1513  else
1514  {
1515  sb_printf2 (R_cur_r, "%.*s%.*s", 0, R_last_ik, R_last_kj);
1516  }
1517  }
1518  }
1519  sb_free (&R_temp_ij);
1520  sb_free (&R_temp_ik);
1521  sb_free (&R_temp_kk);
1522  sb_free (&R_temp_kj);
1523 
1524  if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag))
1525  {
1526  R_cur_ij->null_flag = GNUNET_YES;
1527  return;
1528  }
1529 
1530  if ((GNUNET_YES != R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag))
1531  {
1532  struct StringBuffer tmp;
1533 
1534  tmp = *R_cur_ij;
1535  *R_cur_ij = *R_cur_l;
1536  *R_cur_l = tmp;
1537  return;
1538  }
1539 
1540  if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES != R_cur_r->null_flag))
1541  {
1542  struct StringBuffer tmp;
1543 
1544  tmp = *R_cur_ij;
1545  *R_cur_ij = *R_cur_r;
1546  *R_cur_r = tmp;
1547  return;
1548  }
1549 
1550  if (0 == sb_nullstrcmp (R_cur_l, R_cur_r))
1551  {
1552  struct StringBuffer tmp;
1553 
1554  tmp = *R_cur_ij;
1555  *R_cur_ij = *R_cur_l;
1556  *R_cur_l = tmp;
1557  return;
1558  }
1559  sb_printf2 (R_cur_ij, "(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
1560 }
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 1575 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().

1576 {
1577  unsigned int n = a->state_count;
1578  struct REGEX_INTERNAL_State *states[n];
1579  struct StringBuffer *R_last;
1580  struct StringBuffer *R_cur;
1581  struct StringBuffer R_cur_r;
1582  struct StringBuffer R_cur_l;
1583  struct StringBuffer *R_swap;
1584  struct REGEX_INTERNAL_Transition *t;
1585  struct StringBuffer complete_regex;
1586  unsigned int i;
1587  unsigned int j;
1588  unsigned int k;
1589 
1590  R_last = GNUNET_malloc_large (sizeof(struct StringBuffer) * n * n);
1591  R_cur = GNUNET_malloc_large (sizeof(struct StringBuffer) * n * n);
1592  if ((NULL == R_last) || (NULL == R_cur))
1593  {
1595  GNUNET_free_non_null (R_cur);
1596  GNUNET_free_non_null (R_last);
1597  return GNUNET_SYSERR;
1598  }
1599 
1600  /* create depth-first numbering of the states, initializes 'state' */
1602  a->start,
1603  NULL,
1604  NULL,
1605  &number_states,
1606  states);
1607 
1608  for (i = 0; i < n; i++)
1609  GNUNET_assert (NULL != states[i]);
1610  for (i = 0; i < n; i++)
1611  for (j = 0; j < n; j++)
1612  R_last[i * n + j].null_flag = GNUNET_YES;
1613 
1614  /* Compute regular expressions of length "1" between each pair of states */
1615  for (i = 0; i < n; i++)
1616  {
1617  for (t = states[i]->transitions_head; NULL != t; t = t->next)
1618  {
1619  j = t->to_state->dfs_id;
1620  if (GNUNET_YES == R_last[i * n + j].null_flag)
1621  {
1622  sb_strdup_cstr (&R_last[i * n + j], t->label);
1623  }
1624  else
1625  {
1626  sb_append_cstr (&R_last[i * n + j], "|");
1627  sb_append_cstr (&R_last[i * n + j], t->label);
1628  }
1629  }
1630  /* add self-loop: i is reachable from i via epsilon-transition */
1631  if (GNUNET_YES == R_last[i * n + i].null_flag)
1632  {
1633  R_last[i * n + i].slen = 0;
1634  R_last[i * n + i].null_flag = GNUNET_NO;
1635  }
1636  else
1637  {
1638  sb_wrap (&R_last[i * n + i], "(|%.*s)", 3);
1639  }
1640  }
1641  for (i = 0; i < n; i++)
1642  for (j = 0; j < n; j++)
1643  if (needs_parentheses (&R_last[i * n + j]))
1644  sb_wrap (&R_last[i * n + j], "(%.*s)", 2);
1645  /* Compute regular expressions of length "k" between each pair of states per
1646  * induction */
1647  memset (&R_cur_l, 0, sizeof(struct StringBuffer));
1648  memset (&R_cur_r, 0, sizeof(struct StringBuffer));
1649  for (k = 0; k < n; k++)
1650  {
1651  for (i = 0; i < n; i++)
1652  {
1653  for (j = 0; j < n; j++)
1654  {
1655  /* Basis for the recursion:
1656  * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
1657  * R_last == R^{(k-1)}, R_cur == R^{(k)}
1658  */
1659 
1660  /* Create R_cur[i][j] and simplify the expression */
1661  automaton_create_proofs_simplify (&R_last[i * n + j],
1662  &R_last[i * n + k],
1663  &R_last[k * n + k],
1664  &R_last[k * n + j],
1665  &R_cur[i * n + j],
1666  &R_cur_l,
1667  &R_cur_r);
1668  }
1669  }
1670  /* set R_last = R_cur */
1671  R_swap = R_last;
1672  R_last = R_cur;
1673  R_cur = R_swap;
1674  /* clear 'R_cur' for next iteration */
1675  for (i = 0; i < n; i++)
1676  for (j = 0; j < n; j++)
1677  R_cur[i * n + j].null_flag = GNUNET_YES;
1678  }
1679  sb_free (&R_cur_l);
1680  sb_free (&R_cur_r);
1681  /* assign proofs and hashes */
1682  for (i = 0; i < n; i++)
1683  {
1684  if (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag)
1685  {
1686  states[i]->proof = GNUNET_strndup (R_last[a->start->dfs_id * n + i].sbuf,
1687  R_last[a->start->dfs_id * n + i].slen);
1688  GNUNET_CRYPTO_hash (states[i]->proof,
1689  strlen (states[i]->proof),
1690  &states[i]->hash);
1691  }
1692  }
1693 
1694  /* complete regex for whole DFA: union of all pairs (start state/accepting
1695  * state(s)). */
1696  sb_init (&complete_regex, 16 * n);
1697  for (i = 0; i < n; i++)
1698  {
1699  if (states[i]->accepting)
1700  {
1701  if ((0 == complete_regex.slen) &&
1702  (0 < R_last[a->start->dfs_id * n + i].slen))
1703  {
1704  sb_append (&complete_regex, &R_last[a->start->dfs_id * n + i]);
1705  }
1706  else if ((GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) &&
1707  (0 < R_last[a->start->dfs_id * n + i].slen))
1708  {
1709  sb_append_cstr (&complete_regex, "|");
1710  sb_append (&complete_regex, &R_last[a->start->dfs_id * n + i]);
1711  }
1712  }
1713  }
1714  a->canonical_regex =
1715  GNUNET_strndup (complete_regex.sbuf, complete_regex.slen);
1716 
1717  /* cleanup */
1718  sb_free (&complete_regex);
1719  for (i = 0; i < n; i++)
1720  for (j = 0; j < n; j++)
1721  {
1722  sb_free (&R_cur[i * n + j]);
1723  sb_free (&R_last[i * n + j]);
1724  }
1725  GNUNET_free (R_cur);
1726  GNUNET_free (R_last);
1727  return GNUNET_OK;
1728 }
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:48
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 1741 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().

1743 {
1744  struct REGEX_INTERNAL_State *s;
1745  char *pos;
1746  size_t len;
1747  struct REGEX_INTERNAL_State *cstate;
1748  struct REGEX_INTERNAL_Transition *ctran;
1749  unsigned int i;
1750 
1751  s = GNUNET_new (struct REGEX_INTERNAL_State);
1752  s->id = ctx->state_id++;
1753  s->index = -1;
1754  s->lowlink = -1;
1755 
1756  if (NULL == nfa_states)
1757  {
1758  GNUNET_asprintf (&s->name, "s%i", s->id);
1759  return s;
1760  }
1761 
1762  s->nfa_set = *nfa_states;
1763 
1764  if (nfa_states->off < 1)
1765  return s;
1766 
1767  /* Create a name based on 'nfa_states' */
1768  len = nfa_states->off * 14 + 4;
1769  s->name = GNUNET_malloc (len);
1770  strcat (s->name, "{");
1771  pos = s->name + 1;
1772 
1773  for (i = 0; i < nfa_states->off; i++)
1774  {
1775  cstate = nfa_states->states[i];
1776  GNUNET_snprintf (pos, pos - s->name + len, "%i,", cstate->id);
1777  pos += strlen (pos);
1778 
1779  /* Add a transition for each distinct label to NULL state */
1780  for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
1781  if (NULL != ctran->label)
1782  state_add_transition (ctx, s, ctran->label, NULL);
1783 
1784  /* If the nfa_states contain an accepting state, the new dfa state is also
1785  * accepting. */
1786  if (cstate->accepting)
1787  s->accepting = 1;
1788  }
1789  pos[-1] = '}';
1790  s->name = GNUNET_realloc (s->name, strlen (s->name) + 1);
1791 
1792  memset (nfa_states, 0, sizeof(struct REGEX_INTERNAL_StateSet));
1793  return s;
1794 }
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 1811 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().

1812 {
1813  struct REGEX_INTERNAL_Transition *t;
1814  struct REGEX_INTERNAL_State *new_s;
1815  unsigned int len;
1816  unsigned int max_len;
1817 
1818  if (NULL == s)
1819  return 0;
1820 
1821  new_s = NULL;
1822  max_len = 0;
1823  for (t = (*s)->transitions_head; NULL != t; t = t->next)
1824  {
1825  len = strlen (t->label);
1826 
1827  if (0 == strncmp (t->label, str, len))
1828  {
1829  if (len >= max_len)
1830  {
1831  max_len = len;
1832  new_s = t->to_state;
1833  }
1834  }
1835  }
1836 
1837  *s = new_s;
1838  return max_len;
1839 }
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 1852 of file regex_internal.c.

References GNUNET_YES, and REGEX_INTERNAL_State::marked.

Referenced by dfa_remove_unreachable_states().

1855 {
1856  s->marked = GNUNET_YES;
1857 }
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 1867 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().

1868 {
1869  struct REGEX_INTERNAL_State *s;
1870  struct REGEX_INTERNAL_State *s_next;
1871 
1872  /* 1. unmark all states */
1873  for (s = a->states_head; NULL != s; s = s->next)
1874  s->marked = GNUNET_NO;
1875 
1876  /* 2. traverse dfa from start state and mark all visited states */
1878  a->start,
1879  NULL,
1880  NULL,
1881  &mark_states,
1882  NULL);
1883 
1884  /* 3. delete all states that were not visited */
1885  for (s = a->states_head; NULL != s; s = s_next)
1886  {
1887  s_next = s->next;
1888  if (GNUNET_NO == s->marked)
1889  automaton_remove_state (a, s);
1890  }
1891 }
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 1901 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().

1902 {
1903  struct REGEX_INTERNAL_State *s;
1904  struct REGEX_INTERNAL_State *s_next;
1905  struct REGEX_INTERNAL_Transition *t;
1906  int dead;
1907 
1908  GNUNET_assert (DFA == a->type);
1909 
1910  for (s = a->states_head; NULL != s; s = s_next)
1911  {
1912  s_next = s->next;
1913 
1914  if (s->accepting)
1915  continue;
1916 
1917  dead = 1;
1918  for (t = s->transitions_head; NULL != t; t = t->next)
1919  {
1920  if ((NULL != t->to_state) && (t->to_state != s) )
1921  {
1922  dead = 0;
1923  break;
1924  }
1925  }
1926 
1927  if (0 == dead)
1928  continue;
1929 
1930  /* state s is dead, remove it */
1931  automaton_remove_state (a, s);
1932  }
1933 }
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 1944 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().

1946 {
1947  uint32_t *table;
1948  struct REGEX_INTERNAL_State *s1;
1949  struct REGEX_INTERNAL_State *s2;
1950  struct REGEX_INTERNAL_Transition *t1;
1951  struct REGEX_INTERNAL_Transition *t2;
1952  struct REGEX_INTERNAL_State *s1_next;
1953  struct REGEX_INTERNAL_State *s2_next;
1954  int change;
1955  unsigned int num_equal_edges;
1956  unsigned int i;
1957  unsigned int state_cnt;
1958  unsigned long long idx;
1959  unsigned long long idx1;
1960 
1961  if ((NULL == a) || (0 == a->state_count))
1962  {
1964  "Could not merge nondistinguishable states, automaton was NULL.\n");
1965  return GNUNET_SYSERR;
1966  }
1967 
1968  state_cnt = a->state_count;
1969  table = GNUNET_malloc_large (
1970  (sizeof(uint32_t) * state_cnt * state_cnt / 32) + sizeof(uint32_t));
1971  if (NULL == table)
1972  {
1974  return GNUNET_SYSERR;
1975  }
1976 
1977  for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next)
1978  s1->marked = i++;
1979 
1980  /* Mark all pairs of accepting/!accepting states */
1981  for (s1 = a->states_head; NULL != s1; s1 = s1->next)
1982  for (s2 = a->states_head; NULL != s2; s2 = s2->next)
1983  if ((s1->accepting && ! s2->accepting) ||
1984  (! s1->accepting && s2->accepting))
1985  {
1986  idx = (unsigned long long) s1->marked * state_cnt + s2->marked;
1987  table[idx / 32] |= (1U << (idx % 32));
1988  }
1989 
1990  /* Find all equal states */
1991  change = 1;
1992  while (0 != change)
1993  {
1994  change = 0;
1995  for (s1 = a->states_head; NULL != s1; s1 = s1->next)
1996  {
1997  for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
1998  {
1999  idx = (unsigned long long) s1->marked * state_cnt + s2->marked;
2000  if (0 != (table[idx / 32] & (1U << (idx % 32))))
2001  continue;
2002  num_equal_edges = 0;
2003  for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
2004  {
2005  for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
2006  {
2007  if (0 == strcmp (t1->label, t2->label))
2008  {
2009  num_equal_edges++;
2010  /* same edge, but targets definitively different, so we're different
2011  as well */
2012  if (t1->to_state->marked > t2->to_state->marked)
2013  idx1 = (unsigned long long) t1->to_state->marked * state_cnt
2014  + t2->to_state->marked;
2015  else
2016  idx1 = (unsigned long long) t2->to_state->marked * state_cnt
2017  + t1->to_state->marked;
2018  if (0 != (table[idx1 / 32] & (1U << (idx1 % 32))))
2019  {
2020  table[idx / 32] |= (1U << (idx % 32));
2021  change = 1; /* changed a marker, need to run again */
2022  }
2023  }
2024  }
2025  }
2026  if ((num_equal_edges != s1->transition_count) ||
2027  (num_equal_edges != s2->transition_count))
2028  {
2029  /* Make sure ALL edges of possible equal states are the same */
2030  table[idx / 32] |= (1U << (idx % 32));
2031  change = 1; /* changed a marker, need to run again */
2032  }
2033  }
2034  }
2035  }
2036 
2037  /* Merge states that are equal */
2038  for (s1 = a->states_head; NULL != s1; s1 = s1_next)
2039  {
2040  s1_next = s1->next;
2041  for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
2042  {
2043  s2_next = s2->next;
2044  idx = (unsigned long long) s1->marked * state_cnt + s2->marked;
2045  if (0 == (table[idx / 32] & (1U << (idx % 32))))
2046  automaton_merge_states (ctx, a, s1, s2);
2047  }
2048  }
2049 
2050  GNUNET_free (table);
2051  return GNUNET_OK;
2052 }
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:55
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 2064 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().

2066 {
2067  if (NULL == a)
2068  return GNUNET_SYSERR;
2069 
2070  GNUNET_assert (DFA == a->type);
2071 
2072  /* 1. remove unreachable states */
2074 
2075  /* 2. remove dead states */
2077 
2078  /* 3. Merge nondistinguishable states */
2080  return GNUNET_SYSERR;
2081  return GNUNET_OK;
2082 }
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 2119 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().

2124 {
2125  struct REGEX_INTERNAL_Strided_Context *ctx = cls;
2126  struct REGEX_INTERNAL_Transition *t;
2127  char *new_label;
2128 
2129  if (depth == ctx->stride)
2130  {
2132  t->label = GNUNET_strdup (label);
2133  t->to_state = s;
2134  t->from_state = start;
2136  ctx->transitions_tail,
2137  t);
2138  }
2139  else
2140  {
2141  for (t = s->transitions_head; NULL != t; t = t->next)
2142  {
2143  /* Do not consider self-loops, because it end's up in too many
2144  * transitions */
2145  if (t->to_state == t->from_state)
2146  continue;
2147 
2148  if (NULL != label)
2149  {
2150  GNUNET_asprintf (&new_label, "%s%s", label, t->label);
2151  }
2152  else
2153  new_label = GNUNET_strdup (t->label);
2154 
2156  (depth + 1),
2157  new_label,
2158  start,
2159  t->to_state);
2160  }
2161  }
2163 }
#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 2175 of file regex_internal.c.

References dfa_add_multi_strides_helper().

Referenced by REGEX_INTERNAL_dfa_add_multi_strides().

2178 {
2179  dfa_add_multi_strides_helper (cls, 0, NULL, s, s);
2180 }
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 2191 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.

2194 {
2195  struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
2196  struct REGEX_INTERNAL_Transition *t;
2197  struct REGEX_INTERNAL_Transition *t_next;
2198 
2199  if ((1 > stride_len) || (GNUNET_YES == dfa->is_multistrided))
2200  return;
2201 
2202  /* Compute the new transitions of given stride_len */
2204  dfa->start,
2205  NULL,
2206  NULL,
2208  &ctx);
2209 
2210  /* Add all the new transitions to the automaton. */
2211  for (t = ctx.transitions_head; NULL != t; t = t_next)
2212  {
2213  t_next = t->next;
2214  state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
2217  GNUNET_free (t);
2218  }
2219 
2220  /* Mark this automaton as multistrided */
2221  dfa->is_multistrided = GNUNET_YES;
2222 }
#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 2239 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().

2246 {
2247  struct REGEX_INTERNAL_Transition *t;
2248  char *new_label;
2249 
2250 
2251  if ((NULL != label) &&
2252  (((cur->incoming_transition_count > 1) || (GNUNET_YES ==
2253  cur->accepting) ||
2254  (GNUNET_YES == cur->marked) ) ||
2255  ((start != dfa->start) && (max_len > 0) && (max_len == strlen (
2256  label))) ||
2257  ((start == dfa->start) && (GNUNET_REGEX_INITIAL_BYTES == strlen (
2258  label)))))
2259  {
2261  t->label = GNUNET_strdup (label);
2262  t->to_state = cur;
2263  t->from_state = start;
2264  GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t);
2265 
2266  if (GNUNET_NO == cur->marked)
2267  {
2269  cur,
2270  cur,
2271  NULL,
2272  max_len,
2273  transitions_head,
2274  transitions_tail);
2275  }
2276  return;
2277  }
2278  else if (cur != start)
2279  cur->contained = GNUNET_YES;
2280 
2281  if ((GNUNET_YES == cur->marked) && (cur != start))
2282  return;
2283 
2284  cur->marked = GNUNET_YES;
2285 
2286 
2287  for (t = cur->transitions_head; NULL != t; t = t->next)
2288  {
2289  if (NULL != label)
2290  GNUNET_asprintf (&new_label, "%s%s", label, t->label);
2291  else
2292  new_label = GNUNET_strdup (t->label);
2293 
2294  if (t->to_state != cur)
2295  {
2297  start,
2298  t->to_state,
2299  new_label,
2300  max_len,
2301  transitions_head,
2302  transitions_tail);
2303  }
2304  GNUNET_free (new_label);
2305  }
2306 }
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 2318 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().

2321 {
2322  struct REGEX_INTERNAL_State *s;
2323  struct REGEX_INTERNAL_State *s_next;
2324  struct REGEX_INTERNAL_Transition *t;
2325  struct REGEX_INTERNAL_Transition *t_next;
2326  struct REGEX_INTERNAL_Transition *transitions_head = NULL;
2327  struct REGEX_INTERNAL_Transition *transitions_tail = NULL;
2328 
2329  if (NULL == dfa)
2330  return;
2331 
2332  /* Count the incoming transitions on each state. */
2333  for (s = dfa->states_head; NULL != s; s = s->next)
2334  {
2335  for (t = s->transitions_head; NULL != t; t = t->next)
2336  {
2337  if (NULL != t->to_state)
2339  }
2340  }
2341 
2342  /* Unmark all states. */
2343  for (s = dfa->states_head; NULL != s; s = s->next)
2344  {
2345  s->marked = GNUNET_NO;
2346  s->contained = GNUNET_NO;
2347  }
2348 
2349  /* Add strides and mark states that can be deleted. */
2351  dfa->start,
2352  dfa->start,
2353  NULL,
2354  max_len,
2355  &transitions_head,
2356  &transitions_tail);
2357 
2358  /* Add all the new transitions to the automaton. */
2359  for (t = transitions_head; NULL != t; t = t_next)
2360  {
2361  t_next = t->next;
2362  state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
2363  GNUNET_CONTAINER_DLL_remove (transitions_head, transitions_tail, t);
2365  GNUNET_free (t);
2366  }
2367 
2368  /* Remove marked states (including their incoming and outgoing transitions). */
2369  for (s = dfa->states_head; NULL != s; s = s_next)
2370  {
2371  s_next = s->next;
2372  if (GNUNET_YES == s->contained)
2373  automaton_remove_state (dfa, s);
2374  }
2375 }
#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 2388 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().

2390 {
2391  struct REGEX_INTERNAL_Automaton *n;
2392 
2393  n = GNUNET_new (struct REGEX_INTERNAL_Automaton);
2394 
2395  n->type = NFA;
2396  n->start = NULL;
2397  n->end = NULL;
2398  n->state_count = 0;
2399 
2400  if ((NULL == start) || (NULL == end))
2401  return n;
2402 
2403  automaton_add_state (n, end);
2404  automaton_add_state (n, start);
2405 
2406  n->state_count = 2;
2407 
2408  n->start = start;
2409  n->end = end;
2410 
2411  return n;
2412 }
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 2423 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().

2426 {
2427  struct REGEX_INTERNAL_State *s;
2428 
2429  if ((NULL == n) || (NULL == states_head))
2430  {
2431  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
2432  return;
2433  }
2434 
2435  if (NULL == n->states_head)
2436  {
2437  n->states_head = states_head;
2438  n->states_tail = states_tail;
2439  return;
2440  }
2441 
2442  if (NULL != states_head)
2443  {
2444  n->states_tail->next = states_head;
2445  n->states_tail = states_tail;
2446  }
2447 
2448  for (s = states_head; NULL != s; s = s->next)
2449  n->state_count++;
2450 }
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 2462 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().

2463 {
2464  struct REGEX_INTERNAL_State *s;
2465 
2466  s = GNUNET_new (struct REGEX_INTERNAL_State);
2467  s->id = ctx->state_id++;
2468  s->accepting = accepting;
2469  s->marked = GNUNET_NO;
2470  s->contained = 0;
2471  s->index = -1;
2472  s->lowlink = -1;
2473  s->scc_id = 0;
2474  s->name = NULL;
2475  GNUNET_asprintf (&s->name, "s%i", s->id);
2476 
2477  return s;
2478 }
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 2491 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().

2495 {
2496  struct REGEX_INTERNAL_State *s;
2497  unsigned int i;
2498  struct REGEX_INTERNAL_StateSet_MDLL cls_stack;
2499  struct REGEX_INTERNAL_State *clsstate;
2500  struct REGEX_INTERNAL_State *currentstate;
2501  struct REGEX_INTERNAL_Transition *ctran;
2502 
2503  memset (ret, 0, sizeof(struct REGEX_INTERNAL_StateSet));
2504  if (NULL == states)
2505  return;
2506 
2507  for (i = 0; i < states->off; i++)
2508  {
2509  s = states->states[i];
2510 
2511  /* Add start state to closure only for epsilon closure */
2512  if (NULL == label)
2513  state_set_append (ret, s);
2514 
2515  /* initialize work stack */
2516  cls_stack.head = NULL;
2517  cls_stack.tail = NULL;
2518  GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s);
2519  cls_stack.len = 1;
2520 
2521  while (NULL != (currentstate = cls_stack.tail))
2522  {
2524  cls_stack.head,
2525  cls_stack.tail,
2526  currentstate);
2527  cls_stack.len--;
2528  for (ctran = currentstate->transitions_head; NULL != ctran;
2529  ctran = ctran->next)
2530  {
2531  if (NULL == (clsstate = ctran->to_state))
2532  continue;
2533  if (0 != clsstate->contained)
2534  continue;
2535  if (0 != nullstrcmp (label, ctran->label))
2536  continue;
2537  state_set_append (ret, clsstate);
2539  cls_stack.head,
2540  cls_stack.tail,
2541  clsstate);
2542  cls_stack.len++;
2543  clsstate->contained = 1;
2544  }
2545  }
2546  }
2547  for (i = 0; i < ret->off; i++)
2548  ret->states[i]->contained = 0;
2549 
2550  if (ret->off > 1)
2551  qsort (ret->states,
2552  ret->off,
2553  sizeof(struct REGEX_INTERNAL_State *),
2554  &state_compare);
2555 }
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 2564 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().

2565 {
2566  struct REGEX_INTERNAL_Automaton *a;
2567  struct REGEX_INTERNAL_Automaton *b;
2568  struct REGEX_INTERNAL_Automaton *new_nfa;
2569 
2570  b = ctx->stack_tail;
2571  GNUNET_assert (NULL != b);
2573  a = ctx->stack_tail;
2574  GNUNET_assert (NULL != a);
2576 
2577  state_add_transition (ctx, a->end, NULL, b->start);
2578  a->end->accepting = 0;
2579  b->end->accepting = 1;
2580 
2581  new_nfa = nfa_fragment_create (NULL, NULL);
2582  nfa_add_states (new_nfa, a->states_head, a->states_tail);
2583  nfa_add_states (new_nfa, b->states_head, b->states_tail);
2584  new_nfa->start = a->start;
2585  new_nfa->end = b->end;
2586  new_nfa->state_count += a->state_count + b->state_count;
2589 
2591 }
#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 2600 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().

2601 {
2602  struct REGEX_INTERNAL_Automaton *a;
2603  struct REGEX_INTERNAL_Automaton *new_nfa;
2604  struct REGEX_INTERNAL_State *start;
2605  struct REGEX_INTERNAL_State *end;
2606 
2607  a = ctx->stack_tail;
2608 
2609  if (NULL == a)
2610  {
2611  GNUNET_log (
2613  "nfa_add_star_op failed, because there was no element on the stack");
2614  return;
2615  }
2616 
2618 
2619  start = nfa_state_create (ctx, 0);
2620  end = nfa_state_create (ctx, 1);
2621 
2622  state_add_transition (ctx, start, NULL, a->start);
2623  state_add_transition (ctx, start, NULL, end);
2624  state_add_transition (ctx, a->end, NULL, a->start);
2625  state_add_transition (ctx, a->end, NULL, end);
2626 
2627  a->end->accepting = 0;
2628  end->accepting = 1;
2629 
2630  new_nfa = nfa_fragment_create (start, end);
2631  nfa_add_states (new_nfa, a->states_head, a->states_tail);
2633 
2635 }
#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 2644 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().

2645 {
2646  struct REGEX_INTERNAL_Automaton *a;
2647 
2648  a = ctx->stack_tail;
2649 
2650  if (NULL == a)
2651  {
2652  GNUNET_log (
2654  "nfa_add_plus_op failed, because there was no element on the stack");
2655  return;
2656  }
2657 
2659 
2660  state_add_transition (ctx, a->end, NULL, a->start);
2661 
2663 }
#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 2672 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().

2673 {
2674  struct REGEX_INTERNAL_Automaton *a;
2675  struct REGEX_INTERNAL_Automaton *new_nfa;
2676  struct REGEX_INTERNAL_State *start;
2677  struct REGEX_INTERNAL_State *end;
2678 
2679  a = ctx->stack_tail;
2680  if (NULL == a)
2681  {
2682  GNUNET_log (
2684  "nfa_add_question_op failed, because there was no element on the stack");
2685  return;
2686  }
2687 
2689 
2690  start = nfa_state_create (ctx, 0);
2691  end = nfa_state_create (ctx, 1);
2692 
2693  state_add_transition (ctx, start, NULL, a->start);
2694  state_add_transition (ctx, start, NULL, end);
2695  state_add_transition (ctx, a->end, NULL, end);
2696 
2697  a->end->accepting = 0;
2698 
2699  new_nfa = nfa_fragment_create (start, end);
2700  nfa_add_states (new_nfa, a->states_head, a->states_tail);
2703 }
#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 2713 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().

2714 {
2715  struct REGEX_INTERNAL_Automaton *a;
2716  struct REGEX_INTERNAL_Automaton *b;
2717  struct REGEX_INTERNAL_Automaton *new_nfa;
2718  struct REGEX_INTERNAL_State *start;
2719  struct REGEX_INTERNAL_State *end;
2720 
2721  b = ctx->stack_tail;
2722  GNUNET_assert (NULL != b);
2724  a = ctx->stack_tail;
2725  GNUNET_assert (NULL != a);
2727 
2728  start = nfa_state_create (ctx, 0);
2729  end = nfa_state_create (ctx, 1);
2730  state_add_transition (ctx, start, NULL, a->start);
2731  state_add_transition (ctx, start, NULL, b->start);
2732 
2733  state_add_transition (ctx, a->end, NULL, end);
2734  state_add_transition (ctx, b->end, NULL, end);
2735 
2736  a->end->accepting = 0;
2737  b->end->accepting = 0;
2738  end->accepting = 1;
2739 
2740  new_nfa = nfa_fragment_create (start, end);
2741  nfa_add_states (new_nfa, a->states_head, a->states_tail);
2742  nfa_add_states (new_nfa, b->states_head, b->states_tail);
2745 
2747 }
#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 2757 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().

2758 {
2759  struct REGEX_INTERNAL_Automaton *n;
2760  struct REGEX_INTERNAL_State *start;
2761  struct REGEX_INTERNAL_State *end;
2762 
2763  GNUNET_assert (NULL != ctx);
2764 
2765  start = nfa_state_create (ctx, 0);
2766  end = nfa_state_create (ctx, 1);
2767  state_add_transition (ctx, start, label, end);
2768  n = nfa_fragment_create (start, end);
2769  GNUNET_assert (NULL != n);
2771 }
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 2780 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().

2781 {
2782  if (NULL == ctx)
2783  {
2784  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
2785  return;
2786  }
2787  ctx->state_id = 0;
2788  ctx->transition_id = 0;
2789  ctx->stack_head = NULL;
2790  ctx->stack_tail = NULL;
2791 }
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 2803 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().

2804 {
2805  struct REGEX_INTERNAL_Context ctx;
2806  struct REGEX_INTERNAL_Automaton *nfa;
2807  const char *regexp;
2808  char curlabel[2];
2809  char *error_msg;
2810  unsigned int count;
2811  unsigned int altcount;
2812  unsigned int atomcount;
2813  unsigned int poff;
2814  unsigned int psize;
2815 
2816  struct
2817  {
2818  int altcount;
2819  int atomcount;
2820  } *p;
2821 
2822  if ((NULL == regex) || (0 == strlen (regex)) || (0 == len))
2823  {
2825  "Could not parse regex. Empty regex string provided.\n");
2826 
2827  return NULL;
2828  }
2830 
2831  regexp = regex;
2832  curlabel[1] = '\0';
2833  p = NULL;
2834  error_msg = NULL;
2835  altcount = 0;
2836  atomcount = 0;
2837  poff = 0;
2838  psize = 0;
2839 
2840  for (count = 0; count < len && *regexp; count++, regexp++)
2841  {
2842  switch (*regexp)
2843  {
2844  case '(':
2845  if (atomcount > 1)
2846  {
2847  --atomcount;
2849  }
2850  if (poff == psize)
2851  GNUNET_array_grow (p, psize, psize * 2 + 4); /* FIXME why *2 +4? */
2852  p[poff].altcount = altcount;
2853  p[poff].atomcount = atomcount;
2854  poff++;
2855  altcount = 0;
2856  atomcount = 0;
2857  break;
2858 
2859  case '|':
2860  if (0 == atomcount)
2861  {
2862  error_msg = "Cannot append '|' to nothing";
2863  goto error;
2864  }
2865  while (--atomcount > 0)
2867  altcount++;
2868  break;
2869 
2870  case ')':
2871  if (0 == poff)
2872  {
2873  error_msg = "Missing opening '('";
2874  goto error;
2875  }
2876  if (0 == atomcount)
2877  {
2878  /* Ignore this: "()" */
2879  poff--;
2880  altcount = p[poff].altcount;
2881  atomcount = p[poff].atomcount;
2882  break;
2883  }
2884  while (--atomcount > 0)
2886  for (; altcount > 0; altcount--)
2888  poff--;
2889  altcount = p[poff].altcount;
2890  atomcount = p[poff].atomcount;
2891  atomcount++;
2892  break;
2893 
2894  case '*':
2895  if (atomcount == 0)
2896  {
2897  error_msg = "Cannot append '*' to nothing";
2898  goto error;
2899  }
2900  nfa_add_star_op (&ctx);
2901  break;
2902 
2903  case '+':
2904  if (atomcount == 0)
2905  {
2906  error_msg = "Cannot append '+' to nothing";
2907  goto error;
2908  }
2909  nfa_add_plus_op (&ctx);
2910  break;
2911 
2912  case '?':
2913  if (atomcount == 0)
2914  {
2915  error_msg = "Cannot append '?' to nothing";
2916  goto error;
2917  }
2919  break;
2920 
2921  default:
2922  if (atomcount > 1)
2923  {
2924  --atomcount;
2926  }
2927  curlabel[0] = *regexp;
2928  nfa_add_label (&ctx, curlabel);
2929  atomcount++;
2930  break;
2931  }
2932  }
2933  if (0 != poff)
2934  {
2935  error_msg = "Unbalanced parenthesis";
2936  goto error;
2937  }
2938  while (--atomcount > 0)
2940  for (; altcount > 0; altcount--)
2942 
2943  GNUNET_array_grow (p, psize, 0);
2944 
2945  nfa = ctx.stack_tail;
2946  GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2947 
2948  if (NULL != ctx.stack_head)
2949  {
2950  error_msg = "Creating the NFA failed. NFA stack was not empty!";
2951  goto error;
2952  }
2953 
2954  /* Remember the regex that was used to generate this NFA */
2955  nfa->regex = GNUNET_strdup (regex);
2956 
2957  /* create depth-first numbering of the states for pretty printing */
2959  NULL,
2960  NULL,
2961  NULL,
2962  &number_states,
2963  NULL);
2964 
2965  /* No multistriding added so far */
2966  nfa->is_multistrided = GNUNET_NO;
2967 
2968  return nfa;
2969 
2970 error:
2971  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex);
2972  if (NULL != error_msg)
2973  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);
2974 
2976 
2977  while (NULL != (nfa = ctx.stack_head))
2978  {
2979  GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
2981  }
2982 
2983  return NULL;
2984 }
#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 2997 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().

3001 {
3002  struct REGEX_INTERNAL_Transition *ctran;
3003  struct REGEX_INTERNAL_State *new_dfa_state;
3004  struct REGEX_INTERNAL_State *state_contains;
3005  struct REGEX_INTERNAL_State *state_iter;
3006  struct REGEX_INTERNAL_StateSet tmp;
3007  struct REGEX_INTERNAL_StateSet nfa_set;
3008 
3009  for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
3010  {
3011  if ((NULL == ctran->label) || (NULL != ctran->to_state) )
3012  continue;
3013 
3014  nfa_closure_set_create (&tmp, nfa, &dfa_state->nfa_set, ctran->label);
3015  nfa_closure_set_create (&nfa_set, nfa, &tmp, NULL);
3016  state_set_clear (&tmp);
3017 
3018  state_contains = NULL;
3019  for (state_iter = dfa->states_head; NULL != state_iter;
3020  state_iter = state_iter->next)
3021  {
3022  if (0 == state_set_compare (&state_iter->nfa_set, &nfa_set))
3023  {
3024  state_contains = state_iter;
3025  break;
3026  }
3027  }
3028  if (NULL == state_contains)
3029  {
3030  new_dfa_state = dfa_state_create (ctx, &nfa_set);
3031  automaton_add_state (dfa, new_dfa_state);
3032  ctran->to_state = new_dfa_state;
3033  construct_dfa_states (ctx, nfa, dfa, new_dfa_state);
3034  }
3035  else
3036  {
3037  ctran->to_state = state_contains;
3038  state_set_clear (&nfa_set);
3039  }
3040  }
3041 }
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 3062 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().

3065 {
3066  struct REGEX_INTERNAL_Context ctx;
3067  struct REGEX_INTERNAL_Automaton *dfa;
3068  struct REGEX_INTERNAL_Automaton *nfa;
3069  struct REGEX_INTERNAL_StateSet nfa_start_eps_cls;
3070  struct REGEX_INTERNAL_StateSet singleton_set;
3071 
3073 
3074  /* Create NFA */
3075  nfa = REGEX_INTERNAL_construct_nfa (regex, len);
3076 
3077  if (NULL == nfa)
3078  {
3080  "Could not create DFA, because NFA creation failed\n"