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_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. 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_Automaton *	nfa_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_State *	nfa_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_Automaton *	REGEX_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_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'. 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)

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

set	set to be modified
state	state 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().

{
  if (set->off == set->size)
    GNUNET_array_grow (set->states, set->size, set->size * 2 + 4);
  set->states[set->off++] = state;
}

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

str1	first string for comparison.
str2	second 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().

{
  if ((NULL == str1) != (NULL == str2))
    return -1;
  if ((NULL == str1) && (NULL == str2))
    return 0;

  return strcmp (str1, str2);
}

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

ctx	context
from_state	starting state for the transition
label	transition label
to_state	state 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().

{
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_Transition *oth;

  if (NULL == from_state)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not create Transition.\n");
    return;
  }

  /* Do not add duplicate state transitions */
  for (t = from_state->transitions_head; NULL != t; t = t->next)
  {
    if ((t->to_state == to_state) && (0 == nullstrcmp (t->label, label)) &&
        (t->from_state == from_state) )
      return;
  }

  /* sort transitions by label */
  for (oth = from_state->transitions_head; NULL != oth; oth = oth->next)
  {
    if (0 < nullstrcmp (oth->label, label))
      break;
  }

  t = GNUNET_new (struct REGEX_INTERNAL_Transition);
  if (NULL != ctx)
    t->id = ctx->transition_id++;
  if (NULL != label)
    t->label = GNUNET_strdup (label);
  else
    t->label = NULL;
  t->to_state = to_state;
  t->from_state = from_state;

  /* Add outgoing transition to 'from_state' */
  from_state->transition_count++;
  GNUNET_CONTAINER_DLL_insert_before (from_state->transitions_head,
                                      from_state->transitions_tail,
                                      oth,
                                      t);
}

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

state	state from which the to-be-removed transition originates.
transition	transition 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, 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().

{
  if ((NULL == state) || (NULL == transition))
    return;

  if (transition->from_state != state)
    return;

  GNUNET_free (transition->label);

  state->transition_count--;
  GNUNET_CONTAINER_DLL_remove (state->transitions_head,
                               state->transitions_tail,
                               transition);

  GNUNET_free (transition);
}

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

a	first state
b	second 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().

{
  struct REGEX_INTERNAL_State **s1 = (struct REGEX_INTERNAL_State **) a;
  struct REGEX_INTERNAL_State **s2 = (struct REGEX_INTERNAL_State **) b;

  return (*s1)->id - (*s2)->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

s	state.
edges	all 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().

{
  struct REGEX_INTERNAL_Transition *t;
  unsigned int count;

  if (NULL == s)
    return 0;

  count = 0;

  for (t = s->transitions_head; NULL != t; t = t->next)
  {
    if (NULL != t->to_state)
    {
      edges[count].label = t->label;
      edges[count].destination = t->to_state->hash;
      count++;
    }
  }
  return count;
}

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

sset1	first state set
sset2	second 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().

{
  int result;
  unsigned int i;

  if ((NULL == sset1) || (NULL == sset2))
    return 1;

  result = sset1->off - sset2->off;
  if (result < 0)
    return -1;
  if (result > 0)
    return 1;
  for (i = 0; i < sset1->off; i++)
    if (0 != (result = state_compare (&sset1->states[i], &sset2->states[i])))
      break;
  return result;
}

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

set	set 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().

{
  GNUNET_array_grow (set->states, set->size, 0);
  set->off = 0;
}

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

a	automaton 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().

{
  if (NULL == a)
    return;

  a->start = NULL;
  a->end = NULL;
  a->states_head = NULL;
  a->states_tail = NULL;
  a->state_count = 0;
  GNUNET_free (a);
}

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

s	state that should be destroyed

Definition at line 305 of file regex_internal.c.

References GNUNET_free, 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().

{
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_Transition *next_t;

  if (NULL == s)
    return;

  GNUNET_free (s->name);
  GNUNET_free (s->proof);
  state_set_clear (&s->nfa_set);
  for (t = s->transitions_head; NULL != t; t = next_t)
  {
    next_t = t->next;
    state_remove_transition (s, t);
  }

  GNUNET_free (s);
}

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

a	automaton
s	state 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().

{
  struct REGEX_INTERNAL_State *s_check;
  struct REGEX_INTERNAL_Transition *t_check;
  struct REGEX_INTERNAL_Transition *t_check_next;

  if ((NULL == a) || (NULL == s))
    return;

  /* remove all transitions leading to this state */
  for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
  {
    for (t_check = s_check->transitions_head; NULL != t_check;
         t_check = t_check_next)
    {
      t_check_next = t_check->next;
      if (t_check->to_state == s)
        state_remove_transition (s_check, t_check);
    }
  }

  /* remove state */
  GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s);
  a->state_count--;

  automaton_destroy_state (s);
}

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

ctx	context
a	automaton
s1	first state
s2	second 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().

{
  struct REGEX_INTERNAL_State *s_check;
  struct REGEX_INTERNAL_Transition *t_check;
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_Transition *t_next;
  int is_dup;

  if (s1 == s2)
    return;

  /* 1. Make all transitions pointing to s2 point to s1, unless this transition
   * does not already exists, if it already exists remove transition. */
  for (s_check = a->states_head; NULL != s_check; s_check = s_check->next)
  {
    for (t_check = s_check->transitions_head; NULL != t_check; t_check = t_next)
    {
      t_next = t_check->next;

      if (s2 == t_check->to_state)
      {
        is_dup = GNUNET_NO;
        for (t = t_check->from_state->transitions_head; NULL != t; t = t->next)
        {
          if ((t->to_state == s1) && (0 == strcmp (t_check->label, t->label)) )
            is_dup = GNUNET_YES;
        }
        if (GNUNET_NO == is_dup)
          t_check->to_state = s1;
        else
          state_remove_transition (t_check->from_state, t_check);
      }
    }
  }

  /* 2. Add all transitions from s2 to sX to s1 */
  for (t_check = s2->transitions_head; NULL != t_check; t_check = t_check->next)
  {
    if (t_check->to_state != s1)
      state_add_transition (ctx, s1, t_check->label, t_check->to_state);
  }

  /* 3. Rename s1 to {s1,s2} */
#if REGEX_DEBUG_DFA
  char *new_name;

  new_name = s1->name;
  GNUNET_asprintf (&s1->name, "{%s,%s}", new_name, s2->name);
  GNUNET_free (new_name);
#endif

  /* remove state */
  GNUNET_CONTAINER_DLL_remove (a->states_head, a->states_tail, s2);
  a->state_count--;
  automaton_destroy_state (s2);
}

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

a	automaton to add the state to
s	state 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().

{
  GNUNET_CONTAINER_DLL_insert (a->states_head, a->states_tail, s);
  a->state_count++;
}

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

s	start state.
marks	an array of size a->state_count to remember which state was already visited.
count	current count of the state.
check	function that is checked before advancing on each transition in the DFS.
check_cls	closure for check.
action	action to be performed on each state.
action_cls	closure 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().

{
  struct REGEX_INTERNAL_Transition *t;

  if (GNUNET_YES == marks[s->traversal_id])
    return;

  marks[s->traversal_id] = GNUNET_YES;

  if (NULL != action)
    action (action_cls, *count, s);

  (*count)++;

  for (t = s->transitions_head; NULL != t; t = t->next)
  {
    if ((NULL == check) ||
        ((NULL != check) && (GNUNET_YES == check (check_cls, s, t)) ))
    {
      automaton_state_traverse (t->to_state,
                                marks,
                                count,
                                check,
                                check_cls,
                                action,
                                action_cls);
    }
  }
}

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

a	automaton to be traversed.
start	start state, pass a->start or NULL to traverse the whole automaton.
check	function that is checked before advancing on each transition in the DFS.
check_cls	closure for check.
action	action to be performed on each state.
action_cls	closure 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().

{
  unsigned int count;
  struct REGEX_INTERNAL_State *s;

  if ((NULL == a) || (0 == a->state_count))
    return;

  int marks[a->state_count];

  for (count = 0, s = a->states_head; NULL != s && count < a->state_count;
       s = s->next, count++)
  {
    s->traversal_id = count;
    marks[s->traversal_id] = GNUNET_NO;
  }

  count = 0;

  if (NULL == start)
    s = a->start;
  else
    s = start;

  automaton_state_traverse (s,
                            marks,
                            &count,
                            check,
                            check_cls,
                            action,
                            action_cls);
}

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

s1	first string for comparison.
s2	second 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().

{
  if ((GNUNET_YES == s1->null_flag) && (GNUNET_YES == s2->null_flag))
    return 0;
  if ((GNUNET_YES == s1->null_flag) || (GNUNET_YES == s2->null_flag))
    return -1;
  if (s1->slen != s2->slen)
    return -1;
  if (0 == s1->slen)
    return 0;
  return memcmp (s1->sbuf, s2->sbuf, s1->slen);
}

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

s1	first string for comparison.
s2	second 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().

{
  if (s1->slen != s2->slen)
    return -1;
  if (0 == s1->slen)
    return 0;
  return memcmp (s1->sbuf, s2->sbuf, s1->slen);
}

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

ret	current buffer, to be updated
nlen	target 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, GNUNET_malloc, GNUNET_memcpy, StringBuffer::sbuf, and StringBuffer::slen.

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

{
  char *old;

  GNUNET_assert (nlen >= ret->slen);
  old = ret->abuf;
  ret->abuf = GNUNET_malloc (nlen);
  ret->blen = nlen;
  GNUNET_memcpy (ret->abuf, ret->sbuf, ret->slen);
  ret->sbuf = ret->abuf;
  GNUNET_free (old);
}

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

ret	where to write the result
sarg	string 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().

{
  if (GNUNET_YES == ret->null_flag)
    ret->slen = 0;
  ret->null_flag = GNUNET_NO;
  if (ret->blen < sarg->slen + ret->slen)
    sb_realloc (ret, ret->blen + sarg->slen + 128);
  GNUNET_memcpy (&ret->sbuf[ret->slen], sarg->sbuf, sarg->slen);
  ret->slen += sarg->slen;
}

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

ret	where to write the result
cstr	string 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().

{
  size_t cstr_len = strlen (cstr);

  if (GNUNET_YES == ret->null_flag)
    ret->slen = 0;
  ret->null_flag = GNUNET_NO;
  if (ret->blen < cstr_len + ret->slen)
    sb_realloc (ret, ret->blen + cstr_len + 128);
  GNUNET_memcpy (&ret->sbuf[ret->slen], cstr, cstr_len);
  ret->slen += cstr_len;
}

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

ret	where to write the result and take the input for %.*s from
format	format string, fprintf-style, with exactly one "%.*s"
extra_chars	how 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, GNUNET_malloc, GNUNET_NO, GNUNET_snprintf(), GNUNET_YES, StringBuffer::null_flag, StringBuffer::sbuf, and StringBuffer::slen.

Referenced by automaton_create_proofs().

{
  char *temp;

  if (GNUNET_YES == ret->null_flag)
    ret->slen = 0;
  ret->null_flag = GNUNET_NO;
  temp = GNUNET_malloc (ret->slen + extra_chars + 1);
  GNUNET_snprintf (temp,
                   ret->slen + extra_chars + 1,
                   format,
                   (int) ret->slen,
                   ret->sbuf);
  GNUNET_free (ret->abuf);
  ret->abuf = temp;
  ret->sbuf = temp;
  ret->blen = ret->slen + extra_chars + 1;
  ret->slen = ret->slen + extra_chars;
}

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

ret	where to write the result
format	format string, fprintf-style, with exactly one "%.*s"
extra_chars	how long will the result be, in addition to 'sarg' length
sarg	string 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().

{
  if (ret->blen < sarg->slen + extra_chars + 1)
    sb_realloc (ret, sarg->slen + extra_chars + 1);
  ret->null_flag = GNUNET_NO;
  ret->sbuf = ret->abuf;
  ret->slen = sarg->slen + extra_chars;
  GNUNET_snprintf (ret->sbuf, ret->blen, format, (int) sarg->slen, sarg->sbuf);
}

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

ret	where to write the result
format	format string, fprintf-style, with exactly two "%.*s"
extra_chars	how long will the result be, in addition to 'sarg1/2' length
sarg1	first string to print into the format
sarg2	second 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().

{
  if (ret->blen < sarg1->slen + sarg2->slen + extra_chars + 1)
    sb_realloc (ret, sarg1->slen + sarg2->slen + extra_chars + 1);
  ret->null_flag = GNUNET_NO;
  ret->slen = sarg1->slen + sarg2->slen + extra_chars;
  ret->sbuf = ret->abuf;
  GNUNET_snprintf (ret->sbuf,
                   ret->blen,
                   format,
                   (int) sarg1->slen,
                   sarg1->sbuf,
                   (int) sarg2->slen,
                   sarg2->sbuf);
}

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

ret	where to write the result
format	format string, fprintf-style, with exactly three "%.*s"
extra_chars	how long will the result be, in addition to 'sarg1/2/3' length
sarg1	first string to print into the format
sarg2	second string to print into the format
sarg3	third 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().

{
  if (ret->blen < sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1)
    sb_realloc (ret, sarg1->slen + sarg2->slen + sarg3->slen + extra_chars + 1);
  ret->null_flag = GNUNET_NO;
  ret->slen = sarg1->slen + sarg2->slen + sarg3->slen + extra_chars;
  ret->sbuf = ret->abuf;
  GNUNET_snprintf (ret->sbuf,
                   ret->blen,
                   format,
                   (int) sarg1->slen,
                   sarg1->sbuf,
                   (int) sarg2->slen,
                   sarg2->sbuf,
                   (int) sarg3->slen,
                   sarg3->sbuf);
}

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

sb	buffer 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().

{
  GNUNET_array_grow (sb->abuf, sb->blen, 0);
  sb->slen = 0;
  sb->sbuf = NULL;
  sb->null_flag = GNUNET_YES;
}

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

in	input string
out	output 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().

{
  out->null_flag = in->null_flag;
  if (GNUNET_YES == out->null_flag)
    return;
  if (out->blen < in->slen)
  {
    GNUNET_array_grow (out->abuf, out->blen, in->slen);
  }
  out->sbuf = out->abuf;
  out->slen = in->slen;
  GNUNET_memcpy (out->sbuf, in->sbuf, out->slen);
}

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

cstr	input string
out	output 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().

{
  if (NULL == cstr)
  {
    out->null_flag = GNUNET_YES;
    return;
  }
  out->null_flag = GNUNET_NO;
  out->slen = strlen (cstr);
  if (out->blen < out->slen)
  {
    GNUNET_array_grow (out->abuf, out->blen, out->slen);
  }
  out->sbuf = out->abuf;
  GNUNET_memcpy (out->sbuf, cstr, out->slen);
}

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

str

string

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().

{
  size_t slen;
  const char *op;
  const char *cl;
  const char *pos;
  const char *end;
  unsigned int cnt;

  if ((GNUNET_YES == str->null_flag) || ((slen = str->slen) < 2))
    return GNUNET_NO;
  pos = str->sbuf;
  if ('(' != pos[0])
    return GNUNET_YES;
  end = str->sbuf + slen;
  cnt = 1;
  pos++;
  while (cnt > 0)
  {
    cl = memchr (pos, ')', end - pos);
    if (NULL == cl)
    {
      GNUNET_break (0);
      return GNUNET_YES;
    }
    /* while '(' before ')', count opening parens */
    while ((NULL != (op = memchr (pos, '(', end - pos))) && (op < cl))
    {
      cnt++;
      pos = op + 1;
    }
    /* got ')' first */
    cnt--;
    pos = cl + 1;
  }
  return (*pos == '\0') ? GNUNET_NO : GNUNET_YES;
}

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

str	string, 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().

{
  size_t slen;
  const char *pos;
  const char *end;
  const char *sbuf;
  const char *op;
  const char *cp;
  unsigned int cnt;

  if (0)
    return;
  sbuf = str->sbuf;
  if ((GNUNET_YES == str->null_flag) || (1 >= (slen = str->slen)) ||
      ('(' != str->sbuf[0]) || (')' != str->sbuf[slen - 1]))
    return;
  cnt = 0;
  pos = &sbuf[1];
  end = &sbuf[slen - 1];
  op = memchr (pos, '(', end - pos);
  cp = memchr (pos, ')', end - pos);
  while (NULL != cp)
  {
    while ((NULL != op) && (op < cp))
    {
      cnt++;
      pos = op + 1;
      op = memchr (pos, '(', end - pos);
    }
    while ((NULL != cp) && ((NULL == op) || (cp < op)))
    {
      if (0 == cnt)
        return;     /* can't strip parens */
      cnt--;
      pos = cp + 1;
      cp = memchr (pos, ')', end - pos);
    }
  }
  if (0 != cnt)
  {
    GNUNET_break (0);
    return;
  }
  str->sbuf++;
  str->slen -= 2;
}

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

str	string 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().

{
  return (GNUNET_YES != str->null_flag) && (0 < str->slen) &&
         ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) &&
         (')' == str->sbuf[str->slen - 1]);
}

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

str	original string
ret	where 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().

{
  if (GNUNET_YES == str->null_flag)
  {
    ret->null_flag = GNUNET_YES;
    return;
  }
  if ((str->slen > 1) && ('(' == str->sbuf[0]) && ('|' == str->sbuf[1]) &&
      (')' == str->sbuf[str->slen - 1]))
  {
    /* remove epsilon */
    if (ret->blen < str->slen - 3)
    {
      GNUNET_array_grow (ret->abuf, ret->blen, str->slen - 3);
    }
    ret->sbuf = ret->abuf;
    ret->slen = str->slen - 3;
    GNUNET_memcpy (ret->sbuf, &str->sbuf[2], ret->slen);
    return;
  }
  sb_strdup (ret, str);
}

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

str1	first string to compare
str2	second string for comparison
n	number 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().

{
  size_t max;

  if ((str1->slen != str2->slen) && ((str1->slen < n) || (str2->slen < n)))
    return -1;
  max = GNUNET_MAX (str1->slen, str2->slen);
  if (max > n)
    max = n;
  return memcmp (str1->sbuf, str2->sbuf, max);
}

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

str1	first string to compare
str2	second C string for comparison
n	number 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().

{
  if (str1->slen < n)
    return -1;
  return memcmp (str1->sbuf, str2, n);
}

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

sb	buffer to initialize
n	desired 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().

{
  sb->null_flag = GNUNET_NO;
  sb->abuf = sb->sbuf = (0 == n) ? NULL : GNUNET_malloc (n);
  sb->blen = n;
  sb->slen = 0;
}

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

str1	first string to compare, starting from position 'k'
str2	second string for comparison
k	starting 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().

{
  if ((GNUNET_YES == str1->null_flag) || (GNUNET_YES == str2->null_flag) ||
      (k > str1->slen) || (str1->slen - k != str2->slen))
    return -1;
  return memcmp (&str1->sbuf[k], str2->sbuf, str2->slen);
}

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

cls	states array.
count	current state counter.
s	current 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().

{
  struct REGEX_INTERNAL_State **states = cls;

  s->dfs_id = count;
  if (NULL != states)
    states[count] = s;
}

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_ij	value of $R^{(k-1)_{ij}.
R_last_ik	value of $R^{(k-1)_{ik}.
R_last_kk	value of $R^{(k-1)_{kk}.
R_last_kj	value of $R^{(k-1)_{kj}.
R_cur_ij	result for this inductive step is saved in R_cur_ij, R_cur_ij is expected to be NULL when called!
R_cur_l	optimization – kept between iterations to avoid realloc
R_cur_r	optimization – 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().

{
  struct StringBuffer R_temp_ij;
  struct StringBuffer R_temp_ik;
  struct StringBuffer R_temp_kj;
  struct StringBuffer R_temp_kk;
  int eps_check;
  int ij_ik_cmp;
  int ij_kj_cmp;
  int ik_kk_cmp;
  int kk_kj_cmp;
  int clean_ik_kk_cmp;
  int clean_kk_kj_cmp;
  size_t length;
  size_t length_l;
  size_t length_r;

  /*
   * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
   * R_last == R^{(k-1)}, R_cur == R^{(k)}
   * R_cur_ij = R_cur_l | R_cur_r
   * R_cur_l == R^{(k-1)}_{ij}
   * R_cur_r == R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
   */if ((GNUNET_YES == R_last_ij->null_flag) &&
      ((GNUNET_YES == R_last_ik->null_flag) ||
       (GNUNET_YES == R_last_kj->null_flag)))
  {
    /* R^{(k)}_{ij} = N | N */
    R_cur_ij->null_flag = GNUNET_YES;
    R_cur_ij->synced = GNUNET_NO;
    return;
  }

  if ((GNUNET_YES == R_last_ik->null_flag) ||
      (GNUNET_YES == R_last_kj->null_flag))
  {
    /*  R^{(k)}_{ij} = R^{(k-1)}_{ij} | N */
    if (GNUNET_YES == R_last_ij->synced)
    {
      R_cur_ij->synced = GNUNET_YES;
      R_cur_ij->null_flag = GNUNET_NO;
      return;
    }
    R_cur_ij->synced = GNUNET_YES;
    sb_strdup (R_cur_ij, R_last_ij);
    return;
  }
  R_cur_ij->synced = GNUNET_NO;

  /* $R^{(k)}_{ij} = N | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} OR
   * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj} */

  R_cur_r->null_flag = GNUNET_YES;
  R_cur_r->slen = 0;
  R_cur_l->null_flag = GNUNET_YES;
  R_cur_l->slen = 0;

  /* cache results from strcmp, we might need these many times */
  ij_kj_cmp = sb_nullstrcmp (R_last_ij, R_last_kj);
  ij_ik_cmp = sb_nullstrcmp (R_last_ij, R_last_ik);
  ik_kk_cmp = sb_nullstrcmp (R_last_ik, R_last_kk);
  kk_kj_cmp = sb_nullstrcmp (R_last_kk, R_last_kj);

  /* Assign R_temp_(ik|kk|kj) to R_last[][] and remove epsilon as well
   * as parentheses, so we can better compare the contents */

  memset (&R_temp_ij, 0, sizeof(struct StringBuffer));
  memset (&R_temp_ik, 0, sizeof(struct StringBuffer));
  memset (&R_temp_kk, 0, sizeof(struct StringBuffer));
  memset (&R_temp_kj, 0, sizeof(struct StringBuffer));
  remove_epsilon (R_last_ik, &R_temp_ik);
  remove_epsilon (R_last_kk, &R_temp_kk);
  remove_epsilon (R_last_kj, &R_temp_kj);
  remove_parentheses (&R_temp_ik);
  remove_parentheses (&R_temp_kk);
  remove_parentheses (&R_temp_kj);
  clean_ik_kk_cmp = sb_nullstrcmp (R_last_ik, &R_temp_kk);
  clean_kk_kj_cmp = sb_nullstrcmp (&R_temp_kk, R_last_kj);

  /* construct R_cur_l (and, if necessary R_cur_r) */
  if (GNUNET_YES != R_last_ij->null_flag)
  {
    /* Assign R_temp_ij to R_last_ij and remove epsilon as well
     * as parentheses, so we can better compare the contents */
    remove_epsilon (R_last_ij, &R_temp_ij);
    remove_parentheses (&R_temp_ij);

    if ((0 == sb_strcmp (&R_temp_ij, &R_temp_ik)) &&
        (0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
        (0 == sb_strcmp (&R_temp_kk, &R_temp_kj)))
    {
      if (0 == R_temp_ij.slen)
      {
        R_cur_r->null_flag = GNUNET_NO;
      }
      else if ((0 == sb_strncmp_cstr (R_last_ij, "(|", 2)) ||
               ((0 == sb_strncmp_cstr (R_last_ik, "(|", 2)) &&
                (0 == sb_strncmp_cstr (R_last_kj, "(|", 2)) ))
      {
        /*
         * a|(e|a)a*(e|a) = a*
         * a|(e|a)(e|a)*(e|a) = a*
         * (e|a)|aa*a = a*
         * (e|a)|aa*(e|a) = a*
         * (e|a)|(e|a)a*a = a*
         * (e|a)|(e|a)a*(e|a) = a*
         * (e|a)|(e|a)(e|a)*(e|a) = a*
         */if (GNUNET_YES == needs_parentheses (&R_temp_ij))
          sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_ij);
        else
          sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_ij);
      }
      else
      {
        /*
         * a|aa*a = a+
         * a|(e|a)a*a = a+
         * a|aa*(e|a) = a+
         * a|(e|a)(e|a)*a = a+
         * a|a(e|a)*(e|a) = a+
         */if (GNUNET_YES == needs_parentheses (&R_temp_ij))
          sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_ij);
        else
          sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_ij);
      }
    }
    else if ((0 == ij_ik_cmp) && (0 == clean_kk_kj_cmp) &&
             (0 != clean_ik_kk_cmp))
    {
      /* a|ab*b = ab* */
      if (0 == R_last_kk->slen)
        sb_strdup (R_cur_r, R_last_ij);
      else if (GNUNET_YES == needs_parentheses (&R_temp_kk))
        sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
      else
        sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, R_last_kk);
      R_cur_l->null_flag = GNUNET_YES;
    }
    else if ((0 == ij_kj_cmp) && (0 == clean_ik_kk_cmp) &&
             (0 != clean_kk_kj_cmp))
    {
      /* a|bb*a = b*a */
      if (R_last_kk->slen < 1)
      {
        sb_strdup (R_cur_r, R_last_kj);
      }
      else if (GNUNET_YES == needs_parentheses (&R_temp_kk))
        sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
      else
        sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);

      R_cur_l->null_flag = GNUNET_YES;
    }
    else if ((0 == ij_ik_cmp) && (0 == kk_kj_cmp) &&
             (! has_epsilon (R_last_ij)) && has_epsilon (R_last_kk))
    {
      /* a|a(e|b)*(e|b) = a|ab* = a|a|ab|abb|abbb|... = ab* */
      if (needs_parentheses (&R_temp_kk))
        sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ij, &R_temp_kk);
      else
        sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ij, &R_temp_kk);
      R_cur_l->null_flag = GNUNET_YES;
    }
    else if ((0 == ij_kj_cmp) && (0 == ik_kk_cmp) &&
             (! has_epsilon (R_last_ij)) && has_epsilon (R_last_kk))
    {
      /* a|(e|b)(e|b)*a = a|b*a = a|a|ba|bba|bbba|...  = b*a */
      if (needs_parentheses (&R_temp_kk))
        sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_ij);
      else
        sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_ij);
      R_cur_l->null_flag = GNUNET_YES;
    }
    else
    {
      sb_strdup (R_cur_l, R_last_ij);
      remove_parentheses (R_cur_l);
    }
  }
  else
  {
    /* we have no left side */
    R_cur_l->null_flag = GNUNET_YES;
  }

  /* construct R_cur_r, if not already constructed */
  if (GNUNET_YES == R_cur_r->null_flag)
  {
    length = R_temp_kk.slen - R_last_ik->slen;

    /* a(ba)*bx = (ab)+x */
    if ((length > 0) && (GNUNET_YES != R_last_kk->null_flag) &&
        (0 < R_last_kk->slen) && (GNUNET_YES != R_last_kj->null_flag) &&
        (0 < R_last_kj->slen) && (GNUNET_YES != R_last_ik->null_flag) &&
        (0 < R_last_ik->slen) &&
        (0 == sb_strkcmp (&R_temp_kk, R_last_ik, length)) &&
        (0 == sb_strncmp (&R_temp_kk, R_last_kj, length)))
    {
      struct StringBuffer temp_a;
      struct StringBuffer temp_b;

      sb_init (&temp_a, length);
      sb_init (&temp_b, R_last_kj->slen - length);

      length_l = length;
      temp_a.sbuf = temp_a.abuf;
      GNUNET_memcpy (temp_a.sbuf, R_last_kj->sbuf, length_l);
      temp_a.slen = length_l;

      length_r = R_last_kj->slen - length;
      temp_b.sbuf = temp_b.abuf;
      GNUNET_memcpy (temp_b.sbuf, &R_last_kj->sbuf[length], length_r);
      temp_b.slen = length_r;

      /* e|(ab)+ = (ab)* */
      if ((GNUNET_YES != R_cur_l->null_flag) && (0 == R_cur_l->slen) &&
          (0 == temp_b.slen))
      {
        sb_printf2 (R_cur_r, "(%.*s%.*s)*", 3, R_last_ik, &temp_a);
        sb_free (R_cur_l);
        R_cur_l->null_flag = GNUNET_YES;
      }
      else
      {
        sb_printf3 (R_cur_r, "(%.*s%.*s)+%.*s", 3, R_last_ik, &temp_a, &temp_b);
      }
      sb_free (&temp_a);
      sb_free (&temp_b);
    }
    else if ((0 == sb_strcmp (&R_temp_ik, &R_temp_kk)) &&
             (0 == sb_strcmp (&R_temp_kk, &R_temp_kj)) )
    {
      /*
       * (e|a)a*(e|a) = a*
       * (e|a)(e|a)*(e|a) = a*
       */
      if (has_epsilon (R_last_ik) && has_epsilon (R_last_kj))
      {
        if (needs_parentheses (&R_temp_kk))
          sb_printf1 (R_cur_r, "(%.*s)*", 3, &R_temp_kk);
        else
          sb_printf1 (R_cur_r, "%.*s*", 1, &R_temp_kk);
      }
      /* aa*a = a+a */
      else if ((0 == clean_ik_kk_cmp) && (0 == clean_kk_kj_cmp) &&
               (! has_epsilon (R_last_ik)))
      {
        if (needs_parentheses (&R_temp_kk))
          sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, &R_temp_kk);
        else
          sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, &R_temp_kk);
      }
      /*
       * (e|a)a*a = a+
       * aa*(e|a) = a+
       * a(e|a)*(e|a) = a+
       * (e|a)a*a = a+
       */else
      {
        eps_check = (has_epsilon (R_last_ik) + has_epsilon (R_last_kk)
                     + has_epsilon (R_last_kj));

        if (1 == eps_check)
        {
          if (needs_parentheses (&R_temp_kk))
            sb_printf1 (R_cur_r, "(%.*s)+", 3, &R_temp_kk);
          else
            sb_printf1 (R_cur_r, "%.*s+", 1, &R_temp_kk);
        }
      }
    }
    /*
     * aa*b = a+b
     * (e|a)(e|a)*b = a*b
     */
    else if (0 == sb_strcmp (&R_temp_ik, &R_temp_kk))
    {
      if (has_epsilon (R_last_ik))
      {
        if (needs_parentheses (&R_temp_kk))
          sb_printf2 (R_cur_r, "(%.*s)*%.*s", 3, &R_temp_kk, R_last_kj);
        else
          sb_printf2 (R_cur_r, "%.*s*%.*s", 1, &R_temp_kk, R_last_kj);
      }
      else
      {
        if (needs_parentheses (&R_temp_kk))
          sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, &R_temp_kk, R_last_kj);
        else
          sb_printf2 (R_cur_r, "%.*s+%.*s", 1, &R_temp_kk, R_last_kj);
      }
    }
    /*
     * ba*a = ba+
     * b(e|a)*(e|a) = ba*
     */
    else if (0 == sb_strcmp (&R_temp_kk, &R_temp_kj))
    {
      if (has_epsilon (R_last_kj))
      {
        if (needs_parentheses (&R_temp_kk))
          sb_printf2 (R_cur_r, "%.*s(%.*s)*", 3, R_last_ik, &R_temp_kk);
        else
          sb_printf2 (R_cur_r, "%.*s%.*s*", 1, R_last_ik, &R_temp_kk);
      }
      else
      {
        if (needs_parentheses (&R_temp_kk))
          sb_printf2 (R_cur_r, "(%.*s)+%.*s", 3, R_last_ik, &R_temp_kk);
        else
          sb_printf2 (R_cur_r, "%.*s+%.*s", 1, R_last_ik, &R_temp_kk);
      }
    }
    else
    {
      if (0 < R_temp_kk.slen)
      {
        if (needs_parentheses (&R_temp_kk))
        {
          sb_printf3 (R_cur_r,
                      "%.*s(%.*s)*%.*s",
                      3,
                      R_last_ik,
                      &R_temp_kk,
                      R_last_kj);
        }
        else
        {
          sb_printf3 (R_cur_r,
                      "%.*s%.*s*%.*s",
                      1,
                      R_last_ik,
                      &R_temp_kk,
                      R_last_kj);
        }
      }
      else
      {
        sb_printf2 (R_cur_r, "%.*s%.*s", 0, R_last_ik, R_last_kj);
      }
    }
  }
  sb_free (&R_temp_ij);
  sb_free (&R_temp_ik);
  sb_free (&R_temp_kk);
  sb_free (&R_temp_kj);

  if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag))
  {
    R_cur_ij->null_flag = GNUNET_YES;
    return;
  }

  if ((GNUNET_YES != R_cur_l->null_flag) && (GNUNET_YES == R_cur_r->null_flag))
  {
    struct StringBuffer tmp;

    tmp = *R_cur_ij;
    *R_cur_ij = *R_cur_l;
    *R_cur_l = tmp;
    return;
  }

  if ((GNUNET_YES == R_cur_l->null_flag) && (GNUNET_YES != R_cur_r->null_flag))
  {
    struct StringBuffer tmp;

    tmp = *R_cur_ij;
    *R_cur_ij = *R_cur_r;
    *R_cur_r = tmp;
    return;
  }

  if (0 == sb_nullstrcmp (R_cur_l, R_cur_r))
  {
    struct StringBuffer tmp;

    tmp = *R_cur_ij;
    *R_cur_ij = *R_cur_l;
    *R_cur_l = tmp;
    return;
  }
  sb_printf2 (R_cur_ij, "(%.*s|%.*s)", 3, R_cur_l, R_cur_r);
}

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

a	automaton 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_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().

{
  unsigned int n = a->state_count;
  struct REGEX_INTERNAL_State *states[n];
  struct StringBuffer *R_last;
  struct StringBuffer *R_cur;
  struct StringBuffer R_cur_r;
  struct StringBuffer R_cur_l;
  struct StringBuffer *R_swap;
  struct REGEX_INTERNAL_Transition *t;
  struct StringBuffer complete_regex;
  unsigned int i;
  unsigned int j;
  unsigned int k;

  R_last = GNUNET_malloc_large (sizeof(struct StringBuffer) * n * n);
  R_cur = GNUNET_malloc_large (sizeof(struct StringBuffer) * n * n);
  if ((NULL == R_last) || (NULL == R_cur))
  {
    GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc");
    GNUNET_free (R_cur);
    GNUNET_free (R_last);
    return GNUNET_SYSERR;
  }

  /* create depth-first numbering of the states, initializes 'state' */
  REGEX_INTERNAL_automaton_traverse (a,
                                     a->start,
                                     NULL,
                                     NULL,
                                     &number_states,
                                     states);

  for (i = 0; i < n; i++)
    GNUNET_assert (NULL != states[i]);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      R_last[i * n + j].null_flag = GNUNET_YES;

  /* Compute regular expressions of length "1" between each pair of states */
  for (i = 0; i < n; i++)
  {
    for (t = states[i]->transitions_head; NULL != t; t = t->next)
    {
      j = t->to_state->dfs_id;
      if (GNUNET_YES == R_last[i * n + j].null_flag)
      {
        sb_strdup_cstr (&R_last[i * n + j], t->label);
      }
      else
      {
        sb_append_cstr (&R_last[i * n + j], "|");
        sb_append_cstr (&R_last[i * n + j], t->label);
      }
    }
    /* add self-loop: i is reachable from i via epsilon-transition */
    if (GNUNET_YES == R_last[i * n + i].null_flag)
    {
      R_last[i * n + i].slen = 0;
      R_last[i * n + i].null_flag = GNUNET_NO;
    }
    else
    {
      sb_wrap (&R_last[i * n + i], "(|%.*s)", 3);
    }
  }
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (needs_parentheses (&R_last[i * n + j]))
        sb_wrap (&R_last[i * n + j], "(%.*s)", 2);
  /* Compute regular expressions of length "k" between each pair of states per
   * induction */
  memset (&R_cur_l, 0, sizeof(struct StringBuffer));
  memset (&R_cur_r, 0, sizeof(struct StringBuffer));
  for (k = 0; k < n; k++)
  {
    for (i = 0; i < n; i++)
    {
      for (j = 0; j < n; j++)
      {
        /* Basis for the recursion:
         * $R^{(k)}_{ij} = R^{(k-1)}_{ij} | R^{(k-1)}_{ik} ( R^{(k-1)}_{kk} )^* R^{(k-1)}_{kj}
         * R_last == R^{(k-1)}, R_cur == R^{(k)}
         */

        /* Create R_cur[i][j] and simplify the expression */
        automaton_create_proofs_simplify (&R_last[i * n + j],
                                          &R_last[i * n + k],
                                          &R_last[k * n + k],
                                          &R_last[k * n + j],
                                          &R_cur[i * n + j],
                                          &R_cur_l,
                                          &R_cur_r);
      }
    }
    /* set R_last = R_cur */
    R_swap = R_last;
    R_last = R_cur;
    R_cur = R_swap;
    /* clear 'R_cur' for next iteration */
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        R_cur[i * n + j].null_flag = GNUNET_YES;
  }
  sb_free (&R_cur_l);
  sb_free (&R_cur_r);
  /* assign proofs and hashes */
  for (i = 0; i < n; i++)
  {
    if (GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag)
    {
      states[i]->proof = GNUNET_strndup (R_last[a->start->dfs_id * n + i].sbuf,
                                         R_last[a->start->dfs_id * n + i].slen);
      GNUNET_CRYPTO_hash (states[i]->proof,
                          strlen (states[i]->proof),
                          &states[i]->hash);
    }
  }

  /* complete regex for whole DFA: union of all pairs (start state/accepting
   * state(s)). */
  sb_init (&complete_regex, 16 * n);
  for (i = 0; i < n; i++)
  {
    if (states[i]->accepting)
    {
      if ((0 == complete_regex.slen) &&
          (0 < R_last[a->start->dfs_id * n + i].slen))
      {
        sb_append (&complete_regex, &R_last[a->start->dfs_id * n + i]);
      }
      else if ((GNUNET_YES != R_last[a->start->dfs_id * n + i].null_flag) &&
               (0 < R_last[a->start->dfs_id * n + i].slen))
      {
        sb_append_cstr (&complete_regex, "|");
        sb_append (&complete_regex, &R_last[a->start->dfs_id * n + i]);
      }
    }
  }
  a->canonical_regex =
    GNUNET_strndup (complete_regex.sbuf, complete_regex.slen);

  /* cleanup */
  sb_free (&complete_regex);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
    {
      sb_free (&R_cur[i * n + j]);
      sb_free (&R_last[i * n + j]);
    }
  GNUNET_free (R_cur);
  GNUNET_free (R_last);
  return GNUNET_OK;
}

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

ctx	context
nfa_states	set 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().

{
  struct REGEX_INTERNAL_State *s;
  char *pos;
  size_t len;
  struct REGEX_INTERNAL_State *cstate;
  struct REGEX_INTERNAL_Transition *ctran;
  unsigned int i;

  s = GNUNET_new (struct REGEX_INTERNAL_State);
  s->id = ctx->state_id++;
  s->index = -1;
  s->lowlink = -1;

  if (NULL == nfa_states)
  {
    GNUNET_asprintf (&s->name, "s%i", s->id);
    return s;
  }

  s->nfa_set = *nfa_states;

  if (nfa_states->off < 1)
    return s;

  /* Create a name based on 'nfa_states' */
  len = nfa_states->off * 14 + 4;
  s->name = GNUNET_malloc (len);
  strcat (s->name, "{");
  pos = s->name + 1;

  for (i = 0; i < nfa_states->off; i++)
  {
    cstate = nfa_states->states[i];
    GNUNET_snprintf (pos, pos - s->name + len, "%i,", cstate->id);
    pos += strlen (pos);

    /* Add a transition for each distinct label to NULL state */
    for (ctran = cstate->transitions_head; NULL != ctran; ctran = ctran->next)
      if (NULL != ctran->label)
        state_add_transition (ctx, s, ctran->label, NULL);

    /* If the nfa_states contain an accepting state, the new dfa state is also
     * accepting. */
    if (cstate->accepting)
      s->accepting = 1;
  }
  pos[-1] = '}';
  s->name = GNUNET_realloc (s->name, strlen (s->name) + 1);

  memset (nfa_states, 0, sizeof(struct REGEX_INTERNAL_StateSet));
  return s;
}

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

s	starting state, will point to the next state or NULL (if no transition possible)
str	edge 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().

{
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_State *new_s;
  unsigned int len;
  unsigned int max_len;

  if (NULL == s)
    return 0;

  new_s = NULL;
  max_len = 0;
  for (t = (*s)->transitions_head; NULL != t; t = t->next)
  {
    len = strlen (t->label);

    if (0 == strncmp (t->label, str, len))
    {
      if (len >= max_len)
      {
        max_len = len;
        new_s = t->to_state;
      }
    }
  }

  *s = new_s;
  return max_len;
}

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

cls	closure, not used.
count	count, not used.
s	state 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().

{
  s->marked = GNUNET_YES;
}

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

a	DFA 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().

{
  struct REGEX_INTERNAL_State *s;
  struct REGEX_INTERNAL_State *s_next;

  /* 1. unmark all states */
  for (s = a->states_head; NULL != s; s = s->next)
    s->marked = GNUNET_NO;

  /* 2. traverse dfa from start state and mark all visited states */
  REGEX_INTERNAL_automaton_traverse (a,
                                     a->start,
                                     NULL,
                                     NULL,
                                     &mark_states,
                                     NULL);

  /* 3. delete all states that were not visited */
  for (s = a->states_head; NULL != s; s = s_next)
  {
    s_next = s->next;
    if (GNUNET_NO == s->marked)
      automaton_remove_state (a, s);
  }
}

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

a	DFA 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().

{
  struct REGEX_INTERNAL_State *s;
  struct REGEX_INTERNAL_State *s_next;
  struct REGEX_INTERNAL_Transition *t;
  int dead;

  GNUNET_assert (DFA == a->type);

  for (s = a->states_head; NULL != s; s = s_next)
  {
    s_next = s->next;

    if (s->accepting)
      continue;

    dead = 1;
    for (t = s->transitions_head; NULL != t; t = t->next)
    {
      if ((NULL != t->to_state) && (t->to_state != s) )
      {
        dead = 0;
        break;
      }
    }

    if (0 == dead)
      continue;

    /* state s is dead, remove it */
    automaton_remove_state (a, s);
  }
}

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

ctx	context
a	DFA 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().

{
  uint32_t *table;
  struct REGEX_INTERNAL_State *s1;
  struct REGEX_INTERNAL_State *s2;
  struct REGEX_INTERNAL_Transition *t1;
  struct REGEX_INTERNAL_Transition *t2;
  struct REGEX_INTERNAL_State *s1_next;
  struct REGEX_INTERNAL_State *s2_next;
  int change;
  unsigned int num_equal_edges;
  unsigned int i;
  unsigned int state_cnt;
  unsigned long long idx;
  unsigned long long idx1;

  if ((NULL == a) || (0 == a->state_count))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Could not merge nondistinguishable states, automaton was NULL.\n");
    return GNUNET_SYSERR;
  }

  state_cnt = a->state_count;
  table = GNUNET_malloc_large (
    (sizeof(uint32_t) * state_cnt * state_cnt / 32) + sizeof(uint32_t));
  if (NULL == table)
  {
    GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc");
    return GNUNET_SYSERR;
  }

  for (i = 0, s1 = a->states_head; NULL != s1; s1 = s1->next)
    s1->marked = i++;

  /* Mark all pairs of accepting/!accepting states */
  for (s1 = a->states_head; NULL != s1; s1 = s1->next)
    for (s2 = a->states_head; NULL != s2; s2 = s2->next)
      if ((s1->accepting && ! s2->accepting) ||
          (! s1->accepting && s2->accepting))
      {
        idx = (unsigned long long) s1->marked * state_cnt + s2->marked;
        table[idx / 32] |= (1U << (idx % 32));
      }

  /* Find all equal states */
  change = 1;
  while (0 != change)
  {
    change = 0;
    for (s1 = a->states_head; NULL != s1; s1 = s1->next)
    {
      for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2->next)
      {
        idx = (unsigned long long) s1->marked * state_cnt + s2->marked;
        if (0 != (table[idx / 32] & (1U << (idx % 32))))
          continue;
        num_equal_edges = 0;
        for (t1 = s1->transitions_head; NULL != t1; t1 = t1->next)
        {
          for (t2 = s2->transitions_head; NULL != t2; t2 = t2->next)
          {
            if (0 == strcmp (t1->label, t2->label))
            {
              num_equal_edges++;
              /* same edge, but targets definitively different, so we're different
                 as well */
              if (t1->to_state->marked > t2->to_state->marked)
                idx1 = (unsigned long long) t1->to_state->marked * state_cnt
                       + t2->to_state->marked;
              else
                idx1 = (unsigned long long) t2->to_state->marked * state_cnt
                       + t1->to_state->marked;
              if (0 != (table[idx1 / 32] & (1U << (idx1 % 32))))
              {
                table[idx / 32] |= (1U << (idx % 32));
                change = 1;               /* changed a marker, need to run again */
              }
            }
          }
        }
        if ((num_equal_edges != s1->transition_count) ||
            (num_equal_edges != s2->transition_count))
        {
          /* Make sure ALL edges of possible equal states are the same */
          table[idx / 32] |= (1U << (idx % 32));
          change = 1;         /* changed a marker, need to run again */
        }
      }
    }
  }

  /* Merge states that are equal */
  for (s1 = a->states_head; NULL != s1; s1 = s1_next)
  {
    s1_next = s1->next;
    for (s2 = a->states_head; NULL != s2 && s1 != s2; s2 = s2_next)
    {
      s2_next = s2->next;
      idx = (unsigned long long) s1->marked * state_cnt + s2->marked;
      if (0 == (table[idx / 32] & (1U << (idx % 32))))
        automaton_merge_states (ctx, a, s1, s2);
    }
  }

  GNUNET_free (table);
  return GNUNET_OK;
}

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

ctx	context
a	DFA 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().

{
  if (NULL == a)
    return GNUNET_SYSERR;

  GNUNET_assert (DFA == a->type);

  /* 1. remove unreachable states */
  dfa_remove_unreachable_states (a);

  /* 2. remove dead states */
  dfa_remove_dead_states (a);

  /* 3. Merge nondistinguishable states */
  if (GNUNET_OK != dfa_merge_nondistinguishable_states (ctx, a))
    return GNUNET_SYSERR;
  return GNUNET_OK;
}

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

cls	context, contains stride length and strided transitions DLL.
depth	current depth of the depth-first traversal of the graph.
label	current label, string that contains all labels on the path from 'start' to 's'.
start	start state for the depth-first traversal of the graph.
s	current 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, 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().

{
  struct REGEX_INTERNAL_Strided_Context *ctx = cls;
  struct REGEX_INTERNAL_Transition *t;
  char *new_label;

  if (depth == ctx->stride)
  {
    t = GNUNET_new (struct REGEX_INTERNAL_Transition);
    t->label = GNUNET_strdup (label);
    t->to_state = s;
    t->from_state = start;
    GNUNET_CONTAINER_DLL_insert (ctx->transitions_head,
                                 ctx->transitions_tail,
                                 t);
  }
  else
  {
    for (t = s->transitions_head; NULL != t; t = t->next)
    {
      /* Do not consider self-loops, because it end's up in too many
       * transitions */
      if (t->to_state == t->from_state)
        continue;

      if (NULL != label)
      {
        GNUNET_asprintf (&new_label, "%s%s", label, t->label);
      }
      else
        new_label = GNUNET_strdup (t->label);

      dfa_add_multi_strides_helper (cls,
                                    (depth + 1),
                                    new_label,
                                    start,
                                    t->to_state);
    }
  }
  GNUNET_free (label);
}

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

cls	context.
count	not used.
s	current state.

Definition at line 2175 of file regex_internal.c.

References dfa_add_multi_strides_helper().

Referenced by REGEX_INTERNAL_dfa_add_multi_strides().

{
  dfa_add_multi_strides_helper (cls, 0, NULL, s, s);
}

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_ctx	regex context needed to add transitions to the automaton.
dfa	DFA to which the multi strided transitions should be added.
stride_len	length 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_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.

{
  struct REGEX_INTERNAL_Strided_Context ctx = { stride_len, NULL, NULL };
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_Transition *t_next;

  if ((1 > stride_len) || (GNUNET_YES == dfa->is_multistrided))
    return;

  /* Compute the new transitions of given stride_len */
  REGEX_INTERNAL_automaton_traverse (dfa,
                                     dfa->start,
                                     NULL,
                                     NULL,
                                     &dfa_add_multi_strides,
                                     &ctx);

  /* Add all the new transitions to the automaton. */
  for (t = ctx.transitions_head; NULL != t; t = t_next)
  {
    t_next = t->next;
    state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
    GNUNET_CONTAINER_DLL_remove (ctx.transitions_head, ctx.transitions_tail, t);
    GNUNET_free (t->label);
    GNUNET_free (t);
  }

  /* Mark this automaton as multistrided */
  dfa->is_multistrided = GNUNET_YES;
}

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

dfa	DFA for which the paths should be compressed.
start	starting state for linear path search.
cur	current state in the recursive DFS.
label	current label (string of traversed labels).
max_len	maximal path compression length.
transitions_head	transitions DLL.
transitions_tail	transitions 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().

{
  struct REGEX_INTERNAL_Transition *t;
  char *new_label;


  if ((NULL != label) &&
      (((cur->incoming_transition_count > 1) || (GNUNET_YES ==
                                                 cur->accepting) ||
        (GNUNET_YES == cur->marked) ) ||
       ((start != dfa->start) && (max_len > 0) && (max_len == strlen (
                                                     label))) ||
       ((start == dfa->start) && (GNUNET_REGEX_INITIAL_BYTES == strlen (
                                    label)))))
  {
    t = GNUNET_new (struct REGEX_INTERNAL_Transition);
    t->label = GNUNET_strdup (label);
    t->to_state = cur;
    t->from_state = start;
    GNUNET_CONTAINER_DLL_insert (*transitions_head, *transitions_tail, t);

    if (GNUNET_NO == cur->marked)
    {
      dfa_compress_paths_helper (dfa,
                                 cur,
                                 cur,
                                 NULL,
                                 max_len,
                                 transitions_head,
                                 transitions_tail);
    }
    return;
  }
  else if (cur != start)
    cur->contained = GNUNET_YES;

  if ((GNUNET_YES == cur->marked) && (cur != start))
    return;

  cur->marked = GNUNET_YES;


  for (t = cur->transitions_head; NULL != t; t = t->next)
  {
    if (NULL != label)
      GNUNET_asprintf (&new_label, "%s%s", label, t->label);
    else
      new_label = GNUNET_strdup (t->label);

    if (t->to_state != cur)
    {
      dfa_compress_paths_helper (dfa,
                                 start,
                                 t->to_state,
                                 new_label,
                                 max_len,
                                 transitions_head,
                                 transitions_tail);
    }
    GNUNET_free (new_label);
  }
}

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_ctx	context for adding new transitions.
dfa	DFA representation, will directly modify the given DFA.
max_len	maximal 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_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().

{
  struct REGEX_INTERNAL_State *s;
  struct REGEX_INTERNAL_State *s_next;
  struct REGEX_INTERNAL_Transition *t;
  struct REGEX_INTERNAL_Transition *t_next;
  struct REGEX_INTERNAL_Transition *transitions_head = NULL;
  struct REGEX_INTERNAL_Transition *transitions_tail = NULL;

  if (NULL == dfa)
    return;

  /* Count the incoming transitions on each state. */
  for (s = dfa->states_head; NULL != s; s = s->next)
  {
    for (t = s->transitions_head; NULL != t; t = t->next)
    {
      if (NULL != t->to_state)
        t->to_state->incoming_transition_count++;
    }
  }

  /* Unmark all states. */
  for (s = dfa->states_head; NULL != s; s = s->next)
  {
    s->marked = GNUNET_NO;
    s->contained = GNUNET_NO;
  }

  /* Add strides and mark states that can be deleted. */
  dfa_compress_paths_helper (dfa,
                             dfa->start,
                             dfa->start,
                             NULL,
                             max_len,
                             &transitions_head,
                             &transitions_tail);

  /* Add all the new transitions to the automaton. */
  for (t = transitions_head; NULL != t; t = t_next)
  {
    t_next = t->next;
    state_add_transition (regex_ctx, t->from_state, t->label, t->to_state);
    GNUNET_CONTAINER_DLL_remove (transitions_head, transitions_tail, t);
    GNUNET_free (t->label);
    GNUNET_free (t);
  }

  /* Remove marked states (including their incoming and outgoing transitions). */
  for (s = dfa->states_head; NULL != s; s = s_next)
  {
    s_next = s->next;
    if (GNUNET_YES == s->contained)
      automaton_remove_state (dfa, s);
  }
}

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

start	starting state
end	end 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().

{
  struct REGEX_INTERNAL_Automaton *n;

  n = GNUNET_new (struct REGEX_INTERNAL_Automaton);

  n->type = NFA;
  n->start = NULL;
  n->end = NULL;
  n->state_count = 0;

  if ((NULL == start) || (NULL == end))
    return n;

  automaton_add_state (n, end);
  automaton_add_state (n, start);

  n->state_count = 2;

  n->start = start;
  n->end = end;

  return n;
}

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

n	automaton to which the states should be added
states_head	head of the DLL of states
states_tail	tail 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().

{
  struct REGEX_INTERNAL_State *s;

  if ((NULL == n) || (NULL == states_head))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not add states\n");
    return;
  }

  if (NULL == n->states_head)
  {
    n->states_head = states_head;
    n->states_tail = states_tail;
    return;
  }

  if (NULL != states_head)
  {
    n->states_tail->next = states_head;
    n->states_tail = states_tail;
  }

  for (s = states_head; NULL != s; s = s->next)
    n->state_count++;
}

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

ctx	context
accepting	is 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().

{
  struct REGEX_INTERNAL_State *s;

  s = GNUNET_new (struct REGEX_INTERNAL_State);
  s->id = ctx->state_id++;
  s->accepting = accepting;
  s->marked = GNUNET_NO;
  s->contained = 0;
  s->index = -1;
  s->lowlink = -1;
  s->scc_id = 0;
  s->name = NULL;
  GNUNET_asprintf (&s->name, "s%i", s->id);

  return s;
}

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

ret	set to sorted nfa closure on 'label' (epsilon closure if 'label' is NULL)
nfa	the NFA containing 's'
states	list of states on which to base the closure on
label	transitioning 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().

{
  struct REGEX_INTERNAL_State *s;
  unsigned int i;
  struct REGEX_INTERNAL_StateSet_MDLL cls_stack;
  struct REGEX_INTERNAL_State *clsstate;
  struct REGEX_INTERNAL_State *currentstate;
  struct REGEX_INTERNAL_Transition *ctran;

  memset (ret, 0, sizeof(struct REGEX_INTERNAL_StateSet));
  if (NULL == states)
    return;

  for (i = 0; i < states->off; i++)
  {
    s = states->states[i];

    /* Add start state to closure only for epsilon closure */
    if (NULL == label)
      state_set_append (ret, s);

    /* initialize work stack */
    cls_stack.head = NULL;
    cls_stack.tail = NULL;
    GNUNET_CONTAINER_MDLL_insert (ST, cls_stack.head, cls_stack.tail, s);
    cls_stack.len = 1;

    while (NULL != (currentstate = cls_stack.tail))
    {
      GNUNET_CONTAINER_MDLL_remove (ST,
                                    cls_stack.head,
                                    cls_stack.tail,
                                    currentstate);
      cls_stack.len--;
      for (ctran = currentstate->transitions_head; NULL != ctran;
           ctran = ctran->next)
      {
        if (NULL == (clsstate = ctran->to_state))
          continue;
        if (0 != clsstate->contained)
          continue;
        if (0 != nullstrcmp (label, ctran->label))
          continue;
        state_set_append (ret, clsstate);
        GNUNET_CONTAINER_MDLL_insert_tail (ST,
                                           cls_stack.head,
                                           cls_stack.tail,
                                           clsstate);
        cls_stack.len++;
        clsstate->contained = 1;
      }
    }
  }
  for (i = 0; i < ret->off; i++)
    ret->states[i]->contained = 0;

  if (ret->off > 1)
    qsort (ret->states,
           ret->off,
           sizeof(struct REGEX_INTERNAL_State *),
           &state_compare);
}

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

ctx

context

Definition at line 2564 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_fragment_clear(), testconfigure::b, 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().

{
  struct REGEX_INTERNAL_Automaton *a;
  struct REGEX_INTERNAL_Automaton *b;
  struct REGEX_INTERNAL_Automaton *new_nfa;

  b = ctx->stack_tail;
  GNUNET_assert (NULL != b);
  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
  a = ctx->stack_tail;
  GNUNET_assert (NULL != a);
  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);

  state_add_transition (ctx, a->end, NULL, b->start);
  a->end->accepting = 0;
  b->end->accepting = 1;

  new_nfa = nfa_fragment_create (NULL, NULL);
  nfa_add_states (new_nfa, a->states_head, a->states_tail);
  nfa_add_states (new_nfa, b->states_head, b->states_tail);
  new_nfa->start = a->start;
  new_nfa->end = b->end;
  new_nfa->state_count += a->state_count + b->state_count;
  automaton_fragment_clear (a);
  automaton_fragment_clear (b);

  GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}

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

ctx

context

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().

{
  struct REGEX_INTERNAL_Automaton *a;
  struct REGEX_INTERNAL_Automaton *new_nfa;
  struct REGEX_INTERNAL_State *start;
  struct REGEX_INTERNAL_State *end;

  a = ctx->stack_tail;

  if (NULL == a)
  {
    GNUNET_log (
      GNUNET_ERROR_TYPE_ERROR,
      "nfa_add_star_op failed, because there was no element on the stack");
    return;
  }

  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);

  start = nfa_state_create (ctx, 0);
  end = nfa_state_create (ctx, 1);

  state_add_transition (ctx, start, NULL, a->start);
  state_add_transition (ctx, start, NULL, end);
  state_add_transition (ctx, a->end, NULL, a->start);
  state_add_transition (ctx, a->end, NULL, end);

  a->end->accepting = 0;
  end->accepting = 1;

  new_nfa = nfa_fragment_create (start, end);
  nfa_add_states (new_nfa, a->states_head, a->states_tail);
  automaton_fragment_clear (a);

  GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}

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

ctx

context

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().

{
  struct REGEX_INTERNAL_Automaton *a;

  a = ctx->stack_tail;

  if (NULL == a)
  {
    GNUNET_log (
      GNUNET_ERROR_TYPE_ERROR,
      "nfa_add_plus_op failed, because there was no element on the stack");
    return;
  }

  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);

  state_add_transition (ctx, a->end, NULL, a->start);

  GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, a);
}

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

ctx

context

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().

{
  struct REGEX_INTERNAL_Automaton *a;
  struct REGEX_INTERNAL_Automaton *new_nfa;
  struct REGEX_INTERNAL_State *start;
  struct REGEX_INTERNAL_State *end;

  a = ctx->stack_tail;
  if (NULL == a)
  {
    GNUNET_log (
      GNUNET_ERROR_TYPE_ERROR,
      "nfa_add_question_op failed, because there was no element on the stack");
    return;
  }

  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);

  start = nfa_state_create (ctx, 0);
  end = nfa_state_create (ctx, 1);

  state_add_transition (ctx, start, NULL, a->start);
  state_add_transition (ctx, start, NULL, end);
  state_add_transition (ctx, a->end, NULL, end);

  a->end->accepting = 0;

  new_nfa = nfa_fragment_create (start, end);
  nfa_add_states (new_nfa, a->states_head, a->states_tail);
  GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
  automaton_fragment_clear (a);
}

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

ctx

context

Definition at line 2713 of file regex_internal.c.

References REGEX_INTERNAL_State::accepting, automaton_fragment_clear(), testconfigure::b, 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().

{
  struct REGEX_INTERNAL_Automaton *a;
  struct REGEX_INTERNAL_Automaton *b;
  struct REGEX_INTERNAL_Automaton *new_nfa;
  struct REGEX_INTERNAL_State *start;
  struct REGEX_INTERNAL_State *end;

  b = ctx->stack_tail;
  GNUNET_assert (NULL != b);
  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, b);
  a = ctx->stack_tail;
  GNUNET_assert (NULL != a);
  GNUNET_CONTAINER_DLL_remove (ctx->stack_head, ctx->stack_tail, a);

  start = nfa_state_create (ctx, 0);
  end = nfa_state_create (ctx, 1);
  state_add_transition (ctx, start, NULL, a->start);
  state_add_transition (ctx, start, NULL, b->start);

  state_add_transition (ctx, a->end, NULL, end);
  state_add_transition (ctx, b->end, NULL, end);

  a->end->accepting = 0;
  b->end->accepting = 0;
  end->accepting = 1;

  new_nfa = nfa_fragment_create (start, end);
  nfa_add_states (new_nfa, a->states_head, a->states_tail);
  nfa_add_states (new_nfa, b->states_head, b->states_tail);
  automaton_fragment_clear (a);
  automaton_fragment_clear (b);

  GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, new_nfa);
}

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

ctx	context
label	label 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().

{
  struct REGEX_INTERNAL_Automaton *n;
  struct REGEX_INTERNAL_State *start;
  struct REGEX_INTERNAL_State *end;

  GNUNET_assert (NULL != ctx);

  start = nfa_state_create (ctx, 0);
  end = nfa_state_create (ctx, 1);
  state_add_transition (ctx, start, label, end);
  n = nfa_fragment_create (start, end);
  GNUNET_assert (NULL != n);
  GNUNET_CONTAINER_DLL_insert_tail (ctx->stack_head, ctx->stack_tail, n);
}

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

ctx

context

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().

{
  if (NULL == ctx)
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Context was NULL!");
    return;
  }
  ctx->state_id = 0;
  ctx->transition_id = 0;
  ctx->stack_head = NULL;
  ctx->stack_tail = NULL;
}

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

regex	regular expression string
len	length 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, 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().

{
  struct REGEX_INTERNAL_Context ctx;
  struct REGEX_INTERNAL_Automaton *nfa;
  const char *regexp;
  char curlabel[2];
  char *error_msg;
  unsigned int count;
  unsigned int altcount;
  unsigned int atomcount;
  unsigned int poff;
  unsigned int psize;

  struct
  {
    int altcount;
    int atomcount;
  } *p;

  if ((NULL == regex) || (0 == strlen (regex)) || (0 == len))
  {
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
                "Could not parse regex. Empty regex string provided.\n");

    return NULL;
  }
  REGEX_INTERNAL_context_init (&ctx);

  regexp = regex;
  curlabel[1] = '\0';
  p = NULL;
  error_msg = NULL;
  altcount = 0;
  atomcount = 0;
  poff = 0;
  psize = 0;

  for (count = 0; count < len && *regexp; count++, regexp++)
  {
    switch (*regexp)
    {
    case '(':
      if (atomcount > 1)
      {
        --atomcount;
        nfa_add_concatenation (&ctx);
      }
      if (poff == psize)
        GNUNET_array_grow (p, psize, psize * 2 + 4);    /* FIXME why *2 +4? */
      p[poff].altcount = altcount;
      p[poff].atomcount = atomcount;
      poff++;
      altcount = 0;
      atomcount = 0;
      break;

    case '|':
      if (0 == atomcount)
      {
        error_msg = "Cannot append '|' to nothing";
        goto error;
      }
      while (--atomcount > 0)
        nfa_add_concatenation (&ctx);
      altcount++;
      break;

    case ')':
      if (0 == poff)
      {
        error_msg = "Missing opening '('";
        goto error;
      }
      if (0 == atomcount)
      {
        /* Ignore this: "()" */
        poff--;
        altcount = p[poff].altcount;
        atomcount = p[poff].atomcount;
        break;
      }
      while (--atomcount > 0)
        nfa_add_concatenation (&ctx);
      for (; altcount > 0; altcount--)
        nfa_add_alternation (&ctx);
      poff--;
      altcount = p[poff].altcount;
      atomcount = p[poff].atomcount;
      atomcount++;
      break;

    case '*':
      if (atomcount == 0)
      {
        error_msg = "Cannot append '*' to nothing";
        goto error;
      }
      nfa_add_star_op (&ctx);
      break;

    case '+':
      if (atomcount == 0)
      {
        error_msg = "Cannot append '+' to nothing";
        goto error;
      }
      nfa_add_plus_op (&ctx);
      break;

    case '?':
      if (atomcount == 0)
      {
        error_msg = "Cannot append '?' to nothing";
        goto error;
      }
      nfa_add_question_op (&ctx);
      break;

    default:
      if (atomcount > 1)
      {
        --atomcount;
        nfa_add_concatenation (&ctx);
      }
      curlabel[0] = *regexp;
      nfa_add_label (&ctx, curlabel);
      atomcount++;
      break;
    }
  }
  if (0 != poff)
  {
    error_msg = "Unbalanced parenthesis";
    goto error;
  }
  while (--atomcount > 0)
    nfa_add_concatenation (&ctx);
  for (; altcount > 0; altcount--)
    nfa_add_alternation (&ctx);

  GNUNET_array_grow (p, psize, 0);

  nfa = ctx.stack_tail;
  GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);

  if (NULL != ctx.stack_head)
  {
    error_msg = "Creating the NFA failed. NFA stack was not empty!";
    goto error;
  }

  /* Remember the regex that was used to generate this NFA */
  nfa->regex = GNUNET_strdup (regex);

  /* create depth-first numbering of the states for pretty printing */
  REGEX_INTERNAL_automaton_traverse (nfa,
                                     NULL,
                                     NULL,
                                     NULL,
                                     &number_states,
                                     NULL);

  /* No multistriding added so far */
  nfa->is_multistrided = GNUNET_NO;

  return nfa;

error:
  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Could not parse regex: `%s'\n", regex);
  if (NULL != error_msg)
    GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "%s\n", error_msg);

  GNUNET_free (p);

  while (NULL != (nfa = ctx.stack_head))
  {
    GNUNET_CONTAINER_DLL_remove (ctx.stack_head, ctx.stack_tail, nfa);
    REGEX_INTERNAL_automaton_destroy (nfa);
  }

  return NULL;
}

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

ctx	context.
nfa	NFA automaton.
dfa	DFA automaton.
dfa_state	current 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().

{
  struct REGEX_INTERNAL_Transition *ctran;
  struct REGEX_INTERNAL_State *new_dfa_state;
  struct REGEX_INTERNAL_State *state_contains;
  struct REGEX_INTERNAL_State *state_iter;
  struct REGEX_INTERNAL_StateSet tmp;
  struct REGEX_INTERNAL_StateSet nfa_set;

  for (ctran = dfa_state->transitions_head; NULL != ctran; ctran = ctran->next)
  {
    if ((NULL == ctran->label) || (NULL != ctran->to_state) )
      continue;

    nfa_closure_set_create (&tmp, nfa, &dfa_state->nfa_set, ctran->label);
    nfa_closure_set_create (&nfa_set, nfa, &tmp, NULL);
    state_set_clear (&tmp);

    state_contains = NULL;
    for (state_iter = dfa->states_head; NULL != state_iter;
         state_iter = state_iter->next)
    {
      if (0 == state_set_compare (&state_iter->nfa_set, &nfa_set))
      {
        state_contains = state_iter;
        break;
      }
    }
    if (NULL == state_contains)
    {
      new_dfa_state = dfa_state_create (ctx, &nfa_set);
      automaton_add_state (dfa, new_dfa_state);
      ctran->to_state = new_dfa_state;
      construct_dfa_states (ctx, nfa, dfa, new_dfa_state);
    }
    else
    {
      ctran->to_state = state_contains;
      state_set_clear (&nfa_set);
    }
  }
}

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

regex	regular expression string.
len	length of the regular expression.
max_path_len	limit 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().

{
  struct REGEX_INTERNAL_Context ctx;
  struct REGEX_INTERNAL_Automaton *dfa;
  struct REGEX_INTERNAL_Automaton *nfa;
  struct REGEX_INTERNAL_StateSet nfa_start_eps_cls;