GNUnet 0.21.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
31extern "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
170
176
182 unsigned int scc_id;
183
187 int index;
188
193
198 char *name;
199
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
254
255
260{
265
270
276
281
285 unsigned int state_count;
286
291
296
301
305 char *regex;
306
311
316};
317
318
328REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len);
329
330
343typedef int
345 struct REGEX_INTERNAL_State *s,
347
348
356typedef void
358 const unsigned int count,
359 struct REGEX_INTERNAL_State *s);
360
361
375void
379 void *check_cls,
381 void *action_cls);
382
394const char *
396
397
405unsigned int
407
408
414{
418 unsigned int state_id;
419
423 unsigned int transition_id;
424
429
434};
435
436
444void
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
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 ...
const char * REGEX_INTERNAL_get_canonical_regex(struct REGEX_INTERNAL_Automaton *a)
Get the canonical regex of 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.
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.