GNUnet  0.20.0
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 
243 };
244 
245 
250 {
252  DFA
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
344 (*REGEX_INTERNAL_traverse_check) (void *cls,
345  struct REGEX_INTERNAL_State *s,
346  struct REGEX_INTERNAL_Transition *t);
347 
348 
356 typedef void
357 (*REGEX_INTERNAL_traverse_action) (void *cls,
358  const unsigned int count,
359  struct REGEX_INTERNAL_State *s);
360 
361 
375 void
377  struct REGEX_INTERNAL_State *start,
379  void *check_cls,
381  void *action_cls);
382 
394 const char *
396 
397 
405 unsigned int
407 
408 
414 {
418  unsigned int state_id;
419 
423  unsigned int transition_id;
424 
429 
434 };
435 
436 
444 void
446  struct REGEX_INTERNAL_Automaton *dfa,
447  const unsigned int stride_len);
448 
449 
450 #if 0 /* keep Emacsens' auto-indent happy */
451 {
452 #endif
453 #ifdef __cplusplus
454 }
455 #endif
456 
457 #endif
static int start
Set if we are to start default services (including ARM).
Definition: gnunet-arm.c:39
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
static struct GNUNET_SCHEDULER_Task * t
Main task.
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,...
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'.
int(* REGEX_INTERNAL_traverse_check)(void *cls, struct REGEX_INTERNAL_State *s, struct REGEX_INTERNAL_Transition *t)
Function that gets passed to automaton traversal and is called before each next traversal from state ...
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.
const char * REGEX_INTERNAL_get_canonical_regex(struct REGEX_INTERNAL_Automaton *a)
Get the canonical regex of the given automaton.
REGEX_INTERNAL_AutomatonType
Type of an automaton.
@ NFA
@ DFA
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'.
unsigned int REGEX_INTERNAL_get_transition_count(struct REGEX_INTERNAL_Automaton *a)
Get the number of transitions that are contained in the given automaton.
library to parse regular expressions into dfa
A 512-bit hashcode.
Automaton representation.
struct REGEX_INTERNAL_Automaton * next
Linked list of NFAs used for partial NFA creation.
struct REGEX_INTERNAL_State * start
First state of the automaton.
char * canonical_regex
Canonical regex (result of RX->NFA->DFA->RX)
int is_multistrided
GNUNET_YES, if multi strides have been added to the Automaton.
struct REGEX_INTERNAL_State * states_tail
DLL of states.
unsigned int state_count
Number of states in the automaton.
struct REGEX_INTERNAL_Automaton * prev
Linked list of NFAs used for partial NFA creation.
struct REGEX_INTERNAL_State * states_head
DLL of states.
struct REGEX_INTERNAL_State * end
End state of the partial NFA.
enum REGEX_INTERNAL_AutomatonType type
Type of the automaton.
Context that contains an id counter for states and transitions as well as a DLL of automatons used as...
unsigned int transition_id
Unique transition id.
struct REGEX_INTERNAL_Automaton * stack_tail
DLL of REGEX_INTERNAL_Automaton's used as a stack.
struct REGEX_INTERNAL_Automaton * stack_head
DLL of REGEX_INTERNAL_Automaton's used as a stack.
unsigned int state_id
Unique state id.
unsigned int size
Length of the 'states' array.
struct REGEX_INTERNAL_State ** states
Array of states.
unsigned int off
Number of entries in use in the 'states' array.
unsigned int incoming_transition_count
Number of incoming transitions.
struct REGEX_INTERNAL_State * next
This is a linked list to keep states in an automaton.
char * proof
Proof for this 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.
unsigned int traversal_id
Unique state id that is used for traversing the automaton.
struct REGEX_INTERNAL_StateSet nfa_set
Set of states on which this state is based on.
unsigned int dfs_id
Linear state ID acquired by depth-first-search.
char * name
Human readable name of the state.
int marked
Marking of the state.
unsigned int id
Unique state id.
struct REGEX_INTERNAL_Transition * transitions_tail
DLL of transitions.
struct REGEX_INTERNAL_State * next_ST
This is a multi DLL for StateSet_MDLL Stack.
struct REGEX_INTERNAL_State * prev_SS
This is a multi DLL for StateSet_MDLL.
int accepting
If this is an accepting state or not.
int lowlink
Used for SCC detection.
int contained
Marking the state as contained.
struct REGEX_INTERNAL_State * prev_ST
This is a multi DLL for StateSet_MDLL Stack.
struct REGEX_INTERNAL_Transition * transitions_head
DLL of transitions.
struct GNUNET_HashCode hash
Hash of the state.
struct REGEX_INTERNAL_State * next_SS
This is a multi DLL for StateSet_MDLL.
int index
Used for SCC detection.
unsigned int scc_id
Marking the state as part of an SCC (Strongly Connected Component).
Transition between two states.
unsigned int id
Unique id of this transition.
struct REGEX_INTERNAL_State * to_state
State to which this transition leads.
struct REGEX_INTERNAL_Transition * next
This is a linked list.
struct REGEX_INTERNAL_State * from_state
State from which this transition origins.
struct REGEX_INTERNAL_Transition * prev
This is a linked list.
char * label
Label for this transition.