1 /* dfa.h - decls for manipulating regexps as DFAs
2  *
3  ****************************************************************
4  * Copyright (C) 1998, 2000 Thomas Lord
5  *
6  * See the file "COPYING" for further information about
7  * the copyright and warranty status of this work.
8  */
9 
10 
11 #ifndef INCLUDE__RX__DFA_H
12 #define INCLUDE__RX__DFA_H
13 
14 /************************************************************************
15  *(h1 "DFA Data Structures")
16  *
17  */
18 
19 #include "hackerlab/mem/alloc-limits.h"
20 #include "hackerlab/rx/nfa.h"
21 #include "hackerlab/rx/dfa-cache.h"
22 #include "hackerlab/rx/super.h"
23 
24 /*(c #s"struct rx_dfa" :category type)
25  *
26  * This structure type holds pointers to an NFA and one state of the
27  * DFA built from that NFA.  In addition, it contains a copy of the
28  * state label from that DFA state.
29  *
30  * In effect, this structure represents a virtual machine whose
31  * semantics are defined by the NFA, whose internal state is
32  * represented by the DFA state, and whose output is represented by
33  * the state label and by a flag that says whether or not the machine
34  * is able to accept additional characters from its current state.
35  *
36  * Rx provides functions which can advance these machines through
37  * successive states by following transitions indicated by the
38  * characters of an input string.
39  *
40  insert*/
41 struct rx_dfa
42 {
43   struct rx_nfa * rx;			/* The NFA */
44   struct rx_superstate * state;		/* The DFA state */
45   long final_tag;			/* The DFA state label */
46 
47   /* When a `struct rx_dfa' is first allocated, all of those fields
48    * are 0.  When the `state' field is not 0, it holds a lock on the
49    * superstate it points to.
50    */
51 };
52 /*end-insert
53  */
54 
55 
56 
57 /* automatically generated __STDC__ prototypes */
58 extern struct rx_dfa * rx_dfa_alloc (alloc_limits limits);
59 extern void rx_dfa_free (alloc_limits limits, struct rx_dfa * dfa);
60 extern void rx_init_dfa_from_nfa (struct rx_dfa * frame, struct rx_nfa * rx);
61 extern void rx_init_dfa_from_dfa (struct rx_dfa * dest, struct rx_dfa * src);
62 extern void rx_clear_dfa_state (struct rx_dfa * frame);
63 extern int rx_dfa_goto_start_superstate (struct rx_dfa * frame,
64 					 int storage_unit_size);
65 extern int rx_dfa_can_continue (struct rx_dfa * frame);
66 extern int rx_dfa_tag (struct rx_dfa * frame);
67 extern int rx_dfa_fits (int * label,
68 			struct rx_dfa * frame,
69 			const t_uchar * burst,
70 			size_t len);
71 extern int rx_dfa_advance (struct rx_dfa * frame,
72 			   const t_uchar * burst,
73 			   size_t len);
74 extern int rx_dfa_advance_to_final (size_t * amt,
75 				    struct rx_dfa * frame,
76 				    const t_uchar * burst,
77 				    size_t len);
78 #endif  /* INCLUDE__RX__DFA_H */
79