#include </home/buildbot/bb-worker/worker/gnunet_firefly/build/src/service/regex/regex_internal.h>

Collaboration diagram for REGEX_INTERNAL_State:

Data Fields
struct REGEX_INTERNAL_State *	prev
	This is a linked list to keep states in an automaton. More...

struct REGEX_INTERNAL_State *	next
	This is a linked list to keep states in an automaton. More...

struct REGEX_INTERNAL_State *	prev_SS
	This is a multi DLL for StateSet_MDLL. More...

struct REGEX_INTERNAL_State *	next_SS
	This is a multi DLL for StateSet_MDLL. More...

struct REGEX_INTERNAL_State *	prev_ST
	This is a multi DLL for StateSet_MDLL Stack. More...

struct REGEX_INTERNAL_State *	next_ST
	This is a multi DLL for StateSet_MDLL Stack. More...

unsigned int	id
	Unique state id. More...

unsigned int	traversal_id
	Unique state id that is used for traversing the automaton. More...

int	accepting
	If this is an accepting state or not. More...

int	marked
	Marking of the state. More...

int	contained
	Marking the state as contained. More...

unsigned int	scc_id
	Marking the state as part of an SCC (Strongly Connected Component). More...

int	index
	Used for SCC detection. More...

int	lowlink
	Used for SCC detection. More...

char *	name
	Human readable name of the state. More...

struct GNUNET_HashCode	hash
	Hash of the state. More...

unsigned int	dfs_id
	Linear state ID acquired by depth-first-search. More...

char *	proof
	Proof for this state. More...

unsigned int	transition_count
	Number of transitions from this state to other states. More...

struct REGEX_INTERNAL_Transition *	transitions_head
	DLL of transitions. More...

struct REGEX_INTERNAL_Transition *	transitions_tail
	DLL of transitions. More...

unsigned int	incoming_transition_count
	Number of incoming transitions. More...

struct REGEX_INTERNAL_StateSet	nfa_set
	Set of states on which this state is based on. More...

Detailed Description

A state.

Can be used in DFA and NFA automatons.

Definition at line 116 of file regex_internal.h.

Field Documentation

◆ prev

struct REGEX_INTERNAL_State* REGEX_INTERNAL_State::prev

This is a linked list to keep states in an automaton.

Definition at line 121 of file regex_internal.h.

◆ next

struct REGEX_INTERNAL_State* REGEX_INTERNAL_State::next

This is a linked list to keep states in an automaton.

Definition at line 126 of file regex_internal.h.

Referenced by automaton_merge_states(), automaton_remove_state(), construct_dfa_states(), dfa_compress_paths(), dfa_merge_nondistinguishable_states(), dfa_remove_dead_states(), dfa_remove_unreachable_states(), nfa_add_states(), REGEX_INTERNAL_automaton_destroy(), REGEX_INTERNAL_automaton_traverse(), REGEX_INTERNAL_get_transition_count(), REGEX_INTERNAL_iterate_all_edges(), and scc_tarjan().

◆ prev_SS

struct REGEX_INTERNAL_State* REGEX_INTERNAL_State::prev_SS

This is a multi DLL for StateSet_MDLL.

Definition at line 131 of file regex_internal.h.

◆ next_SS

struct REGEX_INTERNAL_State* REGEX_INTERNAL_State::next_SS

This is a multi DLL for StateSet_MDLL.

Definition at line 136 of file regex_internal.h.

◆ prev_ST

struct REGEX_INTERNAL_State* REGEX_INTERNAL_State::prev_ST

This is a multi DLL for StateSet_MDLL Stack.

Definition at line 141 of file regex_internal.h.

◆ next_ST

struct REGEX_INTERNAL_State* REGEX_INTERNAL_State::next_ST

This is a multi DLL for StateSet_MDLL Stack.

Definition at line 146 of file regex_internal.h.

◆ id

unsigned int REGEX_INTERNAL_State::id

Unique state id.

Definition at line 151 of file regex_internal.h.

Referenced by dfa_state_create(), nfa_state_create(), REGEX_TEST_automaton_save_graph_step(), and state_compare().

◆ traversal_id

unsigned int REGEX_INTERNAL_State::traversal_id

Unique state id that is used for traversing the automaton.

It is guaranteed to be > 0 and < state_count.

Definition at line 157 of file regex_internal.h.

Referenced by automaton_state_traverse(), and REGEX_INTERNAL_automaton_traverse().

◆ accepting

int REGEX_INTERNAL_State::accepting

If this is an accepting state or not.

Definition at line 162 of file regex_internal.h.

Referenced by dfa_compress_paths_helper(), dfa_merge_nondistinguishable_states(), dfa_remove_dead_states(), dfa_state_create(), evaluate_dfa(), evaluate_nfa(), nfa_add_alternation(), nfa_add_concatenation(), nfa_add_question_op(), nfa_add_star_op(), nfa_state_create(), and REGEX_TEST_automaton_save_graph_step().

◆ marked

int REGEX_INTERNAL_State::marked

Marking of the state.

This is used for marking all visited states when traversing all states of an automaton and for cases where the state id cannot be used (dfa minimization).

Definition at line 169 of file regex_internal.h.

Referenced by dfa_compress_paths(), dfa_compress_paths_helper(), dfa_merge_nondistinguishable_states(), dfa_remove_unreachable_states(), mark_states(), and nfa_state_create().

◆ contained

int REGEX_INTERNAL_State::contained

Marking the state as contained.

This is used for checking, if the state is contained in a set in constant time.

Definition at line 175 of file regex_internal.h.

Referenced by dfa_compress_paths(), dfa_compress_paths_helper(), nfa_closure_set_create(), nfa_state_create(), scc_tarjan(), and scc_tarjan_strongconnect().

◆ scc_id

unsigned int REGEX_INTERNAL_State::scc_id

Marking the state as part of an SCC (Strongly Connected Component).

All states with the same scc_id are part of the same SCC. scc_id is 0, if state is not a part of any SCC.

Definition at line 182 of file regex_internal.h.

Referenced by nfa_state_create(), REGEX_TEST_automaton_save_graph_step(), and scc_tarjan_strongconnect().

◆ index

int REGEX_INTERNAL_State::index

Used for SCC detection.

Definition at line 187 of file regex_internal.h.

Referenced by dfa_state_create(), nfa_state_create(), scc_tarjan(), and scc_tarjan_strongconnect().

◆ lowlink

int REGEX_INTERNAL_State::lowlink

Used for SCC detection.

Definition at line 192 of file regex_internal.h.

Referenced by dfa_state_create(), nfa_state_create(), scc_tarjan(), and scc_tarjan_strongconnect().

◆ name

char* REGEX_INTERNAL_State::name

Human readable name of the state.

Used for debugging and graph creation.

Definition at line 198 of file regex_internal.h.

Referenced by automaton_destroy_state(), automaton_merge_states(), dfa_state_create(), nfa_state_create(), and REGEX_TEST_automaton_save_graph_step().

◆ hash

struct GNUNET_HashCode REGEX_INTERNAL_State::hash

Hash of the state.

Definition at line 203 of file regex_internal.h.

Referenced by REGEX_TEST_automaton_save_graph_step().

◆ dfs_id

unsigned int REGEX_INTERNAL_State::dfs_id

Linear state ID acquired by depth-first-search.

This ID should be used for storing information about the state in an array, because the 'id' of the state is not guaranteed to be linear. The 'dfs_id' is guaranteed to be > 0 and < 'state_count'.

Definition at line 211 of file regex_internal.h.

Referenced by automaton_create_proofs(), number_states(), and REGEX_TEST_automaton_save_graph_step().

◆ proof

char* REGEX_INTERNAL_State::proof

Proof for this state.

Definition at line 216 of file regex_internal.h.

Referenced by automaton_create_proofs(), automaton_destroy_state(), and REGEX_TEST_automaton_save_graph_step().

◆ transition_count

unsigned int REGEX_INTERNAL_State::transition_count

Number of transitions from this state to other states.

Definition at line 221 of file regex_internal.h.

Referenced by dfa_merge_nondistinguishable_states(), REGEX_INTERNAL_get_transition_count(), and state_add_transition().

◆ transitions_head

struct REGEX_INTERNAL_Transition* REGEX_INTERNAL_State::transitions_head

DLL of transitions.

Definition at line 226 of file regex_internal.h.

Referenced by automaton_destroy_state(), automaton_merge_states(), automaton_remove_state(), automaton_state_traverse(), construct_dfa_states(), dfa_add_multi_strides_helper(), dfa_compress_paths(), dfa_compress_paths_helper(), dfa_merge_nondistinguishable_states(), dfa_remove_dead_states(), dfa_state_create(), nfa_closure_set_create(), REGEX_TEST_automaton_save_graph_step(), scc_tarjan_strongconnect(), state_add_transition(), and state_get_edges().

◆ transitions_tail

struct REGEX_INTERNAL_Transition* REGEX_INTERNAL_State::transitions_tail

DLL of transitions.

Definition at line 231 of file regex_internal.h.

Referenced by state_add_transition().

◆ incoming_transition_count

unsigned int REGEX_INTERNAL_State::incoming_transition_count

Number of incoming transitions.

Used for compressing DFA paths.

Definition at line 236 of file regex_internal.h.

Referenced by dfa_compress_paths_helper().

◆ nfa_set

struct REGEX_INTERNAL_StateSet REGEX_INTERNAL_State::nfa_set

Set of states on which this state is based on.

Used when creating a DFA out of several NFA states.

Definition at line 242 of file regex_internal.h.

Referenced by automaton_destroy_state(), construct_dfa_states(), and dfa_state_create().

The documentation for this struct was generated from the following file:

src/service/regex/regex_internal.h

Data Fields