GNUnet  0.11.x
Data Fields
REGEX_INTERNAL_State Struct Reference

A state. More...

#include </home/handbook/gnunet/src/regex/regex_internal.h>

Collaboration diagram for REGEX_INTERNAL_State:
[legend]

Data Fields

struct REGEX_INTERNAL_Stateprev
 This is a linked list to keep states in an automaton. More...
 
struct REGEX_INTERNAL_Statenext
 This is a linked list to keep states in an automaton. More...
 
struct REGEX_INTERNAL_Stateprev_SS
 This is a multi DLL for StateSet_MDLL. More...
 
struct REGEX_INTERNAL_Statenext_SS
 This is a multi DLL for StateSet_MDLL. More...
 
struct REGEX_INTERNAL_Stateprev_ST
 This is a multi DLL for StateSet_MDLL Stack. More...
 
struct REGEX_INTERNAL_Statenext_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 accquired 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_Transitiontransitions_head
 DLL of transitions. More...
 
struct REGEX_INTERNAL_Transitiontransitions_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

◆ 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

◆ 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 iterate_initial_edge(), REGEX_TEST_automaton_save_graph_step(), and state_get_edges().

◆ dfs_id

unsigned int REGEX_INTERNAL_State::dfs_id

Linear state ID accquired 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

◆ 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(), iterate_initial_edge(), REGEX_INTERNAL_get_transition_count(), state_add_transition(), and state_remove_transition().

◆ transitions_head

struct REGEX_INTERNAL_Transition* REGEX_INTERNAL_State::transitions_head

◆ 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(), and state_remove_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(), and 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: