GNUnet  0.10.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 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
43 
44 
51 {
56 
61 
65  unsigned int id;
66 
70  char *label;
71 
76 
81 };
82 
83 
88 
89 
94 {
99 
103  unsigned int off;
104 
108  unsigned int size;
109 };
110 
111 
116 {
121 
126 
131 
136 
141 
146 
150  unsigned int id;
151 
156  unsigned int traversal_id;
157 
162 
168  int marked;
169 
175 
181  unsigned int scc_id;
182 
186  int index;
187 
191  int lowlink;
192 
197  char *name;
198 
202  struct GNUNET_HashCode hash;
203 
210  unsigned int dfs_id;
211 
215  char *proof;
216 
220  unsigned int transition_count;
221 
226 
231 
236 
241  struct REGEX_INTERNAL_StateSet nfa_set;
242 };
243 
244 
249 {
252 };
253 
254 
259 {
264 
269 
275 
280 
284  unsigned int state_count;
285 
290 
295 
300 
304  char *regex;
305 
310 
315 };
316 
317 
327 REGEX_INTERNAL_construct_nfa (const char *regex, const size_t len);
328 
329 
342 typedef int (*REGEX_INTERNAL_traverse_check) (void *cls,
343  struct REGEX_INTERNAL_State * s,
344  struct REGEX_INTERNAL_Transition * t);
345 
346 
354 typedef void (*REGEX_INTERNAL_traverse_action) (void *cls,
355  const unsigned int count,
356  struct REGEX_INTERNAL_State * s);
357 
358 
372 void
374  struct REGEX_INTERNAL_State *start,
376  void *check_cls,
378  void *action_cls);
379 
391 const char *
393 
394 
402 unsigned int
404 
405 
411 {
415  unsigned int state_id;
416 
420  unsigned int transition_id;
421 
426 
431 };
432 
433 
441 void
443  struct REGEX_INTERNAL_Automaton *dfa,
444  const unsigned int stride_len);
445 
446 
447 
448 #if 0 /* keep Emacsens' auto-indent happy */
449 {
450 #endif
451 #ifdef __cplusplus
452 }
453 #endif
454 
455 #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.