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 
55 
60 
64  unsigned int id;
65 
69  char *label;
70 
75 
80 };
81 
82 
87 
88 
97 
101  unsigned int off;
102 
106  unsigned int size;
107 };
108 
109 
118 
123 
128 
133 
138 
143 
147  unsigned int id;
148 
153  unsigned int traversal_id;
154 
159 
165  int marked;
166 
172 
178  unsigned int scc_id;
179 
183  int index;
184 
188  int lowlink;
189 
194  char *name;
195 
199  struct GNUNET_HashCode hash;
200 
207  unsigned int dfs_id;
208 
212  char *proof;
213 
217  unsigned int transition_count;
218 
223 
228 
233 
238  struct REGEX_INTERNAL_StateSet nfa_set;
239 };
240 
241 
248 };
249 
250 
259 
264 
270 
275 
279  unsigned int state_count;
280 
285 
290 
295 
299  char *regex;
300 
305 
310 };
311 
312 
322 REGEX_INTERNAL_construct_nfa(const char *regex, const size_t len);
323 
324 
337 typedef int (*REGEX_INTERNAL_traverse_check) (void *cls,
338  struct REGEX_INTERNAL_State * s,
339  struct REGEX_INTERNAL_Transition * t);
340 
341 
349 typedef void (*REGEX_INTERNAL_traverse_action) (void *cls,
350  const unsigned int count,
351  struct REGEX_INTERNAL_State * s);
352 
353 
367 void
369  struct REGEX_INTERNAL_State *start,
371  void *check_cls,
373  void *action_cls);
374 
386 const char *
388 
389 
397 unsigned int
399 
400 
409  unsigned int state_id;
410 
414  unsigned int transition_id;
415 
420 
425 };
426 
427 
435 void
437  struct REGEX_INTERNAL_Automaton *dfa,
438  const unsigned int stride_len);
439 
440 
441 
442 #if 0 /* keep Emacsens' auto-indent happy */
443 {
444 #endif
445 #ifdef __cplusplus
446 }
447 #endif
448 
449 #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.