GNUnet  0.11.x
regex_internal.h
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2012 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
25 #ifndef REGEX_INTERNAL_H
26 #define REGEX_INTERNAL_H
27 
28 #include "regex_internal_lib.h"
29 
30 #ifdef __cplusplus
31 extern "C"
32 {
33 #if 0 /* keep Emacsens' auto-indent happy */
34 }
35 #endif
36 #endif
37 
42 #define ALLOWED_LITERALS \
43  "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
44 
45 
52 {
57 
62 
66  unsigned int id;
67 
71  char *label;
72 
77 
82 };
83 
84 
89 
90 
95 {
100 
104  unsigned int off;
105 
109  unsigned int size;
110 };
111 
112 
117 {
122 
127 
132 
137 
142 
147 
151  unsigned int id;
152 
157  unsigned int traversal_id;
158 
163 
169  int marked;
170 
176 
182  unsigned int scc_id;
183 
187  int index;
188 
192  int lowlink;
193 
198  char *name;
199 
203  struct GNUNET_HashCode hash;
204 
211  unsigned int dfs_id;
212 
216  char *proof;
217 
221  unsigned int transition_count;
222 
227 
232 
237 
242  struct REGEX_INTERNAL_StateSet nfa_set;
243 };
244 
245 
250 {
253 };
254 
255 
260 {
265 
270 
276 
281 
285  unsigned int state_count;
286 
291 
296 
301 
305  char *regex;
306 
311 
316 };
317 
318 
328 REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len);
329 
330 
343 typedef int (*REGEX_INTERNAL_traverse_check) (void *cls,
344  struct REGEX_INTERNAL_State *s,
346  t);
347 
348 
356 typedef void (*REGEX_INTERNAL_traverse_action) (void *cls,
357  const unsigned int count,
358  struct REGEX_INTERNAL_State *s);
359 
360 
374 void
376  struct REGEX_INTERNAL_State *start,
378  void *check_cls,
380  void *action_cls);
381 
393 const char *
395 
396 
404 unsigned int
406 
407 
413 {
417  unsigned int state_id;
418 
422  unsigned int transition_id;
423 
428 
433 };
434 
435 
443 void
445  struct REGEX_INTERNAL_Automaton *dfa,
446  const unsigned int stride_len);
447 
448 
449 #if 0 /* keep Emacsens' auto-indent happy */
450 {
451 #endif
452 #ifdef __cplusplus
453 }
454 #endif
455 
456 #endif
unsigned int state_count
Number of states in the automaton.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
unsigned int incoming_transition_count
Number of incoming transitions.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
int index
Used for SCC detection.
unsigned int traversal_id
Unique state id that is used for traversing the automaton.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
unsigned int transition_id
Unique transition id.
int accepting
If this is an accepting state or not.
struct REGEX_INTERNAL_Automaton * next
Linked list of NFAs used for partial NFA creation.
unsigned int state_id
Unique state id.
void REGEX_INTERNAL_automaton_traverse(const struct REGEX_INTERNAL_Automaton *a, struct REGEX_INTERNAL_State *start, REGEX_INTERNAL_traverse_check check, void *check_cls, REGEX_INTERNAL_traverse_action action, void *action_cls)
Traverses the given automaton using depth-first-search (DFS) from it&#39;s start state, visiting all reachable states and calling &#39;action&#39; on each one of them.
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
int contained
Marking the state as contained.
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 &#39;len&#39;.
struct REGEX_INTERNAL_State * prev_SS
This is a multi DLL for StateSet_MDLL.
Automaton representation.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
static struct GNUNET_SCHEDULER_Task * t
Main task.
char * proof
Proof for this state.
int marked
Marking of the state.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
Context that contains an id counter for states and transitions as well as a DLL of automatons used as...
library to parse regular expressions into dfa
char * name
Human readable name of the state.
struct REGEX_INTERNAL_State * prev
This is a linked list to keep states in an automaton.
unsigned int transition_count
Number of transitions from this state to other states.
struct REGEX_INTERNAL_State * next_ST
This is a multi DLL for StateSet_MDLL Stack.
const char * REGEX_INTERNAL_get_canonical_regex(struct REGEX_INTERNAL_Automaton *a)
Get the canonical regex of the given automaton.
struct REGEX_INTERNAL_State ** states
Array of states.
Transition between two states.
A 512-bit hashcode.
struct REGEX_INTERNAL_State * start
First state of the automaton.
struct REGEX_INTERNAL_Automaton * prev
Linked list of NFAs used for partial NFA creation.
unsigned int off
Number of entries in use in the &#39;states&#39; array.
struct REGEX_INTERNAL_State * prev_ST
This is a multi DLL for StateSet_MDLL Stack.
unsigned int REGEX_INTERNAL_get_transition_count(struct REGEX_INTERNAL_Automaton *a)
Get the number of transitions that are contained in the given automaton.
void(* REGEX_INTERNAL_traverse_action)(void *cls, const unsigned int count, struct REGEX_INTERNAL_State *s)
Function that is called with each state, when traversing an automaton.
unsigned int id
Unique id of this transition.
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 &#39;dfa&#39;.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
int is_multistrided
GNUNET_YES, if multi strides have been added to the Automaton.
unsigned int dfs_id
Linear state ID accquired by depth-first-search.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
char * canonical_regex
Canonical regex (result of RX->NFA->DFA->RX)
struct REGEX_INTERNAL_State * next_SS
This is a multi DLL for StateSet_MDLL.
char * label
Label for this transition.
REGEX_INTERNAL_AutomatonType
Type of an automaton.
int(* REGEX_INTERNAL_traverse_check)(void *cls, struct REGEX_INTERNAL_State *s, struct REGEX_INTERNAL_Transition *t)
Function that get&#39;s passed to automaton traversal and is called before each next traversal from state...
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model
int lowlink
Used for SCC detection.
unsigned int id
Unique state id.
struct REGEX_INTERNAL_Transition * prev
This is a linked list.
struct REGEX_INTERNAL_Transition * transitions_tail
DLL of transitions.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton&#39;s used as a stack.
unsigned int size
Length of the &#39;states&#39; array.