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 */ 232