Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 * | |
11 | * or (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #ifndef _DFA_MKPAT_H_ | |
25 | #define _DFA_MKPAT_H_ | |
26 | ||
27 | #include "dfa.h" | |
28 | ||
29 | #include <stdio.h> | |
30 | #include <stdlib.h> | |
31 | #include <errno.h> | |
32 | #include <string.h> | |
33 | ||
34 | /******************************** | |
35 | * Parameters * | |
36 | ********************************/ | |
37 | ||
38 | #define DFA_RESIZE_STEP 20000 | |
39 | #define DFA_INIT_SIZE 250 | |
40 | ||
41 | /******************************** | |
42 | * Data types definition * | |
43 | ********************************/ | |
44 | ||
45 | /* Intersections. */ | |
46 | typedef unsigned short Intersection_t; | |
47 | ||
48 | /* Attribute list. */ | |
49 | typedef struct attrib | |
50 | { | |
51 | int val; | |
52 | int next; | |
53 | } attrib_t; | |
54 | ||
55 | ||
56 | /* DFA state. */ | |
57 | typedef struct state | |
58 | { | |
59 | int att; | |
60 | int next[4]; | |
61 | } state_t; | |
62 | ||
63 | ||
64 | /* DFA. */ | |
65 | typedef struct dfa | |
66 | { | |
67 | /* File header. */ | |
68 | char name[80]; | |
69 | ||
70 | /* Transition graph. */ | |
71 | state_t *states; | |
72 | int max_states; | |
73 | int last_state; | |
74 | ||
75 | /* Attributes sets. */ | |
76 | attrib_t *indexes; | |
77 | int max_indexes; | |
78 | int last_index; | |
79 | } dfa_t; | |
80 | ||
81 | ||
82 | /******************************** | |
83 | * Functions declaration * | |
84 | ********************************/ | |
85 | ||
86 | void dfa_init(void); /* Every call to a DFA function must be done */ | |
87 | void dfa_end(void); /* between calls to these two functions. */ | |
88 | ||
89 | /* Basic DFA manipulation. */ | |
90 | void print_c_dfa(FILE *of, const char *name, dfa_t *pdfa); | |
91 | void new_dfa(dfa_t *pdfa, const char *name); | |
92 | void copy_dfa(dfa_t *p_to, dfa_t *p_from); | |
93 | void kill_dfa(dfa_t *pdfa); | |
94 | int dfa_size(dfa_t *pdfa); /* in kB */ | |
95 | void save_dfa(const char *f_name, dfa_t *pdfa); | |
96 | dfa_t *load_dfa(const char *f_path, const char *f_name, dfa_t **ppdfa); | |
97 | void dfa_finalize(dfa_t *pdfa); | |
98 | void dfa_shuffle(dfa_t *pdfa); | |
99 | int dfa_calculate_max_matched_patterns(dfa_t *pdfa); | |
100 | int dfa_minmax_delta(dfa_t *pdfa, int next_index, int isMin); | |
101 | void dump_dfa(FILE *f, dfa_t *pdfa); | |
102 | ||
103 | struct pattern; | |
104 | ||
105 | /* Conversion between a GNU Go pattern struct into a DFA string. */ | |
106 | void pattern_2_string(struct pattern *pat, struct patval_b *elements, | |
107 | char *str, int ci, int cj); | |
108 | void dfa_rotate_string(char *strrot, const char *str, int ll); | |
109 | ||
110 | /* Add a string with attribute `att_val' into a DFA. */ | |
111 | float dfa_add_string(dfa_t *pdfa, const char *str, int pattern_index, int ll); | |
112 | ||
113 | ||
114 | /******************************** | |
115 | * Global variables * | |
116 | ********************************/ | |
117 | ||
118 | extern int dfa_verbose; /* Verbiage level. */ | |
119 | ||
120 | ||
121 | /************************************** | |
122 | * Experimental DFA builder * | |
123 | **************************************/ | |
124 | ||
125 | #define DFA_ATTRIB_BLOCK_SIZE 150000 | |
126 | #define DFA_NODE_BLOCK_SIZE 50000 | |
127 | ||
128 | typedef struct _dfa_attrib dfa_attrib; | |
129 | typedef struct _dfa_attrib_block dfa_attrib_block; | |
130 | typedef struct _dfa_attrib_array dfa_attrib_array; | |
131 | typedef struct _dfa_node dfa_node; | |
132 | typedef struct _dfa_node_block dfa_node_block; | |
133 | typedef struct _dfa_graph dfa_graph; | |
134 | ||
135 | struct _dfa_attrib { | |
136 | dfa_attrib *next; | |
137 | int string_index; | |
138 | }; | |
139 | ||
140 | struct _dfa_attrib_block { | |
141 | dfa_attrib_block *previous; | |
142 | dfa_attrib attrib[DFA_ATTRIB_BLOCK_SIZE]; | |
143 | }; | |
144 | ||
145 | struct _dfa_attrib_array { | |
146 | dfa_attrib_block *last_block; | |
147 | int allocated; | |
148 | }; | |
149 | ||
150 | struct _dfa_node { | |
151 | dfa_node *branch[4]; | |
152 | dfa_attrib *attributes; | |
153 | dfa_attrib *passing_strings; | |
154 | }; | |
155 | ||
156 | struct _dfa_node_block { | |
157 | dfa_node_block *previous; | |
158 | dfa_node node[DFA_NODE_BLOCK_SIZE]; | |
159 | }; | |
160 | ||
161 | struct _dfa_graph { | |
162 | int num_nodes; | |
163 | dfa_node *root; | |
164 | dfa_node_block *last_block; | |
165 | int allocated; | |
166 | dfa_attrib_array attributes; | |
167 | }; | |
168 | ||
169 | ||
170 | #define DFA_HASH_BLOCK_SIZE 10000 | |
171 | ||
172 | #define DFA_HASH_TABLE_SIZE 4096 | |
173 | #define DFA_HASH_VALUE_1 1 | |
174 | #define DFA_HASH_VALUE_2 79 | |
175 | #define DFA_HASH_VALUE_3 2971 | |
176 | ||
177 | typedef struct _dfa_hash_entry dfa_hash_entry; | |
178 | typedef struct _dfa_hash_block dfa_hash_block; | |
179 | ||
180 | struct _dfa_hash_entry { | |
181 | dfa_hash_entry *next; | |
182 | dfa_attrib *key; | |
183 | dfa_node *value; | |
184 | }; | |
185 | ||
186 | struct _dfa_hash_block { | |
187 | dfa_hash_block *previous; | |
188 | dfa_hash_entry entry[DFA_HASH_BLOCK_SIZE]; | |
189 | }; | |
190 | ||
191 | ||
192 | typedef struct _dfa_pattern dfa_pattern; | |
193 | typedef struct _dfa_patterns dfa_patterns; | |
194 | ||
195 | struct _dfa_pattern { | |
196 | dfa_pattern *next; | |
197 | int num_variations; | |
198 | int current_variation; | |
199 | char *variation[8]; | |
200 | }; | |
201 | ||
202 | struct _dfa_patterns { | |
203 | int num_patterns; | |
204 | dfa_pattern *patterns; | |
205 | dfa_pattern *last_pattern; | |
206 | dfa_graph graph; | |
207 | }; | |
208 | ||
209 | ||
210 | void dfa_graph_reset(dfa_graph *graph); | |
211 | ||
212 | void dfa_patterns_reset(dfa_patterns *patterns); | |
213 | void dfa_patterns_clear(dfa_patterns *patterns); | |
214 | void dfa_patterns_add_pattern(dfa_patterns *patterns, | |
215 | const char *string, int index); | |
216 | void dfa_patterns_set_last_pattern_variation(dfa_patterns *patterns, | |
217 | int variation); | |
218 | void dfa_patterns_select_shortest_variation(dfa_patterns *patterns); | |
219 | void dfa_patterns_build_graph(dfa_patterns *patterns); | |
220 | int *dfa_patterns_optimize_variations(dfa_patterns *patterns, int iterations); | |
221 | ||
222 | ||
223 | #endif /* _DFA_MKPAT_H_ */ | |
224 | ||
225 | ||
226 | /* | |
227 | * Local Variables: | |
228 | * tab-width: 8 | |
229 | * c-basic-offset: 2 | |
230 | * End: | |
231 | */ |