*/
/**
* @file src/regex/regex_internal.h
- * @brief common internal definitions for regex library
+ * @brief common internal definitions for regex library.
* @author Maximilian Szengel
*/
#ifndef REGEX_INTERNAL_H
/**
- * Transition between two states. Each state can have 0-n transitions. If label
- * is 0, this is considered to be an epsilon transition.
+ * Transition between two states. Transitions are stored at the states from
+ * which they origin ('from_state'). Each state can have 0-n transitions.
+ * If label is NULL, this is considered to be an epsilon transition.
*/
struct GNUNET_REGEX_Transition
{
};
+/**
+ * A state. Can be used in DFA and NFA automatons.
+ */
+struct GNUNET_REGEX_State;
+
+
+/**
+ * Set of states.
+ */
+struct GNUNET_REGEX_StateSet
+{
+ /**
+ * Array of states.
+ */
+ struct GNUNET_REGEX_State **states;
+
+ /**
+ * Number of entries in *use* in the 'states' array.
+ */
+ unsigned int off;
+
+ /**
+ * Length of the 'states' array.
+ */
+ unsigned int size;
+};
+
+
/**
* A state. Can be used in DFA and NFA automatons.
*/
struct GNUNET_REGEX_State
{
/**
- * This is a linked list.
+ * This is a linked list to keep states in an automaton.
*/
struct GNUNET_REGEX_State *prev;
/**
- * This is a linked list.
+ * This is a linked list to keep states in an automaton.
*/
struct GNUNET_REGEX_State *next;
+ /**
+ * This is a multi DLL for StateSet_MDLL.
+ */
+ struct GNUNET_REGEX_State *prev_SS;
+
+ /**
+ * This is a multi DLL for StateSet_MDLL.
+ */
+ struct GNUNET_REGEX_State *next_SS;
+
+ /**
+ * This is a multi DLL for StateSet_MDLL Stack.
+ */
+ struct GNUNET_REGEX_State *prev_ST;
+
+ /**
+ * This is a multi DLL for StateSet_MDLL Stack.
+ */
+ struct GNUNET_REGEX_State *next_ST;
+
/**
* Unique state id.
*/
/**
* Marking the state as contained. This is used for checking, if the state is
- * contained in a set in constant time
+ * contained in a set in constant time.
*/
int contained;
int lowlink;
/**
- * Human readable name of the automaton. Used for debugging and graph
+ * Human readable name of the state. Used for debugging and graph
* creation.
*/
char *name;
*/
struct GNUNET_REGEX_Transition *transitions_tail;
+ /**
+ * Number of incoming transitions. Used for compressing DFA paths.
+ */
+ unsigned int incoming_transition_count;
+
/**
* Set of states on which this state is based on. Used when creating a DFA out
* of several NFA states.
*/
- struct GNUNET_REGEX_StateSet *nfa_set;
+ struct GNUNET_REGEX_StateSet nfa_set;
};
};
+/**
+ * Construct an NFA by parsing the regex string of length 'len'.
+ *
+ * @param regex regular expression string.
+ * @param len length of the string.
+ *
+ * @return NFA, needs to be freed using GNUNET_REGEX_automaton_destroy.
+ */
+struct GNUNET_REGEX_Automaton *
+GNUNET_REGEX_construct_nfa (const char *regex, const size_t len);
+
+
/**
* Function that get's passed to automaton traversal and is called before each
* next traversal from state 's' using transition 't' to check if traversal
* @param stride_len length of the strides.
*/
void
-GNUNET_REGEX_add_multi_strides_to_dfa (struct GNUNET_REGEX_Context *regex_ctx,
- struct GNUNET_REGEX_Automaton *dfa,
- const unsigned int stride_len);
+GNUNET_REGEX_dfa_add_multi_strides (struct GNUNET_REGEX_Context *regex_ctx,
+ struct GNUNET_REGEX_Automaton *dfa,
+ const unsigned int stride_len);
/**