« back to all changes in this revision
Viewing changes to drizzled/gen_lex_hash.cc
- browse files at revision 779.4.5
- compare with another revision
- compare with revision 48
- download diff
- download tarball
- view history from revision 779.4.5
- Committer: Monty Taylor
- Date: 2009-01-30 00:53:14 UTC
- mto: (779.3.19 devel)
- mto: This revision was merged to the branch mainline in revision 823.
- Revision ID: mordred@inaugust.com-20090130005314-3ufwrbqxnxu2aevi
Replaced gen_lex_hash with gperf. Yay for no more building tools to build source!!!
- files added:
- drizzled/function_hash.gperf
- files removed:
- drizzled/gen_lex_hash.cc
- files renamed:
- drizzled/lex.h => drizzled/symbol_hash.gperf
- files modified:
- configure.ac
added
removed
drizzled/gen_lex_hash.cc
1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
*
4
* Copyright (C) 2008 Sun Microsystems
5
*
6
* This program is free software; you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation; version 2 of the License.
9
*
10
* This program is distributed in the hope that it will be useful,
11
* but WITHOUT ANY WARRANTY; without even the implied warranty of
12
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
* GNU General Public License for more details.
14
*
15
* You should have received a copy of the GNU General Public License
16
* along with this program; if not, write to the Free Software
17
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18
*/
19
20
/**
21
@file
22
23
@details
24
@verbatim
25
The idea of presented algorithm see in
26
"The Art of Computer Programming" by Donald E. Knuth
27
Volume 3 "Sorting and searching"
28
(chapter 6.3 "Digital searching" - name and number of chapter
29
is back translation from Russian edition :))
30
31
as illustration of data structures, imagine next table:
32
33
static SYMBOL symbols[] = {
34
{ "ADD", SYM(ADD),0,0},
35
{ "AND", SYM(AND),0,0},
36
{ "DAY", SYM(DAY_SYM),0,0},
37
};
38
39
for this structure, presented program generate next searching-structure:
40
41
+-----------+-+-+-+
42
| len |1|2|3|
43
+-----------+-+-+-+
44
|first_char |0|0|a|
45
|last_char |0|0|d|
46
|link |0|0|+|
47
|
48
V
49
+----------+-+-+-+--+
50
| 1 char|a|b|c|d |
51
+----------+-+-+-+--+
52
|first_char|b|0|0|0 |
53
|last_char |n|0|0|-1|
54
|link |+|0|0|+ |
55
| |
56
| V
57
| symbols[2] ( "DAY" )
58
V
59
+----------+--+-+-+-+-+-+-+-+-+-+--+
60
| 2 char|d |e|f|j|h|i|j|k|l|m|n |
61
+----------+--+-+-+-+-+-+-+-+-+-+--+
62
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
63
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
64
|link |+ |0|0|0|0|0|0|0|0|0|+ |
65
| |
66
V V
67
symbols[0] ( "ADD" ) symbols[1] ( "AND" )
68
69
for optimization, link is the 16-bit index in 'symbols' or 'sql_functions'
70
or search-array..
71
72
So, we can read full search-structure as 32-bit word
73
@endverbatim
74
75
@todo
76
use instead to_upper_lex, special array
77
(substitute chars) without skip codes..
78
@todo
79
try use reverse order of comparing..
80
81
*/
82
83
#define NO_YACC_SYMBOLS
84
#include <drizzled/global.h>
85
#include <mysys/my_sys.h>
86
#include <mystrings/m_string.h>
87
#include <mysys/my_getopt.h>
88
89
#include <drizzled/lex.h>
90
91
using namespace std;
92
93
const char *default_dbug_option="d:t:o,/tmp/gen_lex_hash.trace";
94
95
struct my_option my_long_options[] =
96
{
97
{"help", '?', "Display help and exit",
98
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
99
{"version", 'V', "Output version information and exit",
100
0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
101
{0, 0, 0, 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}
102
};
103
104
struct hash_lex_struct
105
{
106
int first_char;
107
char last_char;
108
union{
109
hash_lex_struct *char_tails;
110
int iresult;
111
};
112
int ithis;
113
};
114
115
hash_lex_struct *get_hash_struct_by_len(hash_lex_struct **root_by_len,
116
int len, int *max_len)
117
{
118
if (*max_len<len){
119
*root_by_len= (hash_lex_struct *)realloc((char*)*root_by_len,
120
sizeof(hash_lex_struct)*len);
121
hash_lex_struct *cur, *end= *root_by_len + len;
122
for (cur= *root_by_len + *max_len; cur<end; cur++)
123
cur->first_char= 0;
124
*max_len= len;
125
}
126
return (*root_by_len)+(len-1);
127
}
128
129
void insert_into_hash(hash_lex_struct *root, const char *name,
130
int len_from_begin, int index, int function)
131
{
132
hash_lex_struct *end, *cur, *tails;
133
134
if (!root->first_char)
135
{
136
root->first_char= -1;
137
root->iresult= index;
138
return;
139
}
140
141
if (root->first_char == -1)
142
{
143
int index2= root->iresult;
144
const char *name2= (index2 < 0 ? sql_functions[-index2-1] :
145
symbols[index2]).name + len_from_begin;
146
root->first_char= (int) (unsigned char) name2[0];
147
root->last_char= (char) root->first_char;
148
tails= (hash_lex_struct*)malloc(sizeof(hash_lex_struct));
149
root->char_tails= tails;
150
tails->first_char= -1;
151
tails->iresult= index2;
152
}
153
154
size_t real_size= (root->last_char-root->first_char+1);
155
156
if (root->first_char>(*name))
157
{
158
size_t new_size= root->last_char-(*name)+1;
159
if (new_size<real_size) printf("error!!!!\n");
160
tails= root->char_tails;
161
tails= (hash_lex_struct*)realloc((char*)tails,
162
sizeof(hash_lex_struct)*new_size);
163
root->char_tails= tails;
164
memmove(tails+(new_size-real_size),tails,real_size*sizeof(hash_lex_struct));
165
end= tails + new_size - real_size;
166
for (cur= tails; cur<end; cur++)
167
cur->first_char= 0;
168
root->first_char= (int) (unsigned char) *name;
169
}
170
171
if (root->last_char<(*name))
172
{
173
size_t new_size= (*name)-root->first_char+1;
174
if (new_size<real_size) printf("error!!!!\n");
175
tails= root->char_tails;
176
tails= (hash_lex_struct*)realloc((char*)tails,
177
sizeof(hash_lex_struct)*new_size);
178
root->char_tails= tails;
179
end= tails + new_size;
180
for (cur= tails+real_size; cur<end; cur++)
181
cur->first_char= 0;
182
root->last_char= (*name);
183
}
184
185
insert_into_hash(root->char_tails+(*name)-root->first_char,
186
name+1,len_from_begin+1,index,function);
187
}
188
189
190
hash_lex_struct *root_by_len= 0;
191
int max_len=0;
192
193
hash_lex_struct *root_by_len2= 0;
194
int max_len2=0;
195
196
void insert_symbols()
197
{
198
size_t i= 0;
199
SYMBOL *cur;
200
for (cur= symbols; i<array_elements(symbols); cur++, i++){
201
hash_lex_struct *root=
202
get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
203
insert_into_hash(root,cur->name,0,i,0);
204
}
205
}
206
207
void insert_sql_functions()
208
{
209
int i= 0;
210
SYMBOL *cur;
211
for (cur= sql_functions; i < (int) array_elements(sql_functions); cur++, i++)
212
{
213
hash_lex_struct *root=
214
get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
215
insert_into_hash(root,cur->name,0,-i-1,1);
216
}
217
}
218
219
void calc_length()
220
{
221
SYMBOL *cur, *end= symbols + array_elements(symbols);
222
for (cur= symbols; cur < end; cur++)
223
cur->length=(unsigned char) strlen(cur->name);
224
end= sql_functions + array_elements(sql_functions);
225
for (cur= sql_functions; cur<end; cur++)
226
cur->length=(unsigned char) strlen(cur->name);
227
}
228
229
void generate_find_structs()
230
{
231
root_by_len= 0;
232
max_len=0;
233
234
insert_symbols();
235
236
root_by_len2= root_by_len;
237
max_len2= max_len;
238
239
root_by_len= 0;
240
max_len= 0;
241
242
insert_symbols();
243
insert_sql_functions();
244
}
245
246
char *hash_map= 0;
247
int size_hash_map= 0;
248
249
/* Ok. I honestly don't know why this has no problem and
250
* array_elements macro doesn't. But it works.
251
*/
252
static inline uint32_t array_elements_func(SYMBOL *symbol_arr) {
253
return sizeof(symbol_arr)/sizeof(symbol_arr[0]);
254
}
255
256
void add_struct_to_map(hash_lex_struct *st)
257
{
258
st->ithis= size_hash_map/4;
259
size_hash_map+= 4;
260
hash_map= (char*)realloc((char*)hash_map,size_hash_map);
261
hash_map[size_hash_map-4]= (char) (st->first_char == -1 ? 0 :
262
st->first_char);
263
hash_map[size_hash_map-3]= (char) (st->first_char == -1 ||
264
st->first_char == 0 ? 0 : st->last_char);
265
if (st->first_char == -1)
266
{
267
hash_map[size_hash_map-2]= ((unsigned int)(int16_t)st->iresult)&255;
268
hash_map[size_hash_map-1]= ((unsigned int)(int16_t)st->iresult)>>8;
269
}
270
else if (st->first_char == 0)
271
{
272
hash_map[size_hash_map-2]= ((unsigned int)(int16_t)array_elements_func(symbols))&255;
273
hash_map[size_hash_map-1]= ((unsigned int)(int16_t)array_elements(symbols))>>8;
274
}
275
}
276
277
278
void add_structs_to_map(hash_lex_struct *st, int len)
279
{
280
hash_lex_struct *cur, *end= st+len;
281
for (cur= st; cur<end; cur++)
282
add_struct_to_map(cur);
283
for (cur= st; cur<end; cur++)
284
{
285
if (cur->first_char && cur->first_char != -1)
286
add_structs_to_map(cur->char_tails,cur->last_char-cur->first_char+1);
287
}
288
}
289
290
void set_links(hash_lex_struct *st, int len)
291
{
292
hash_lex_struct *cur, *end= st+len;
293
for (cur= st; cur<end; cur++)
294
{
295
if (cur->first_char != 0 && cur->first_char != -1)
296
{
297
int ilink= cur->char_tails->ithis;
298
hash_map[cur->ithis*4+2]= ilink%256;
299
hash_map[cur->ithis*4+3]= ilink/256;
300
set_links(cur->char_tails,cur->last_char-cur->first_char+1);
301
}
302
}
303
}
304
305
306
void print_hash_map(const char *name)
307
{
308
char *cur;
309
int i;
310
311
printf("static unsigned char %s[%d]= {\n",name,size_hash_map);
312
for (i=0, cur= hash_map; i<size_hash_map; i++, cur++)
313
{
314
switch(i%4){
315
case 0: case 1:
316
if (!*cur)
317
printf("0, ");
318
else
319
printf("\'%c\', ",*cur);
320
break;
321
case 2: printf("%u, ",(uint)(unsigned char)*cur); break;
322
case 3: printf("%u,\n",(uint)(unsigned char)*cur); break;
323
}
324
}
325
printf("};\n");
326
}
327
328
329
void print_find_structs()
330
{
331
add_structs_to_map(root_by_len,max_len);
332
set_links(root_by_len,max_len);
333
print_hash_map("sql_functions_map");
334
335
hash_map= 0;
336
size_hash_map= 0;
337
338
printf("\n");
339
340
add_structs_to_map(root_by_len2,max_len2);
341
set_links(root_by_len2,max_len2);
342
print_hash_map("symbols_map");
343
}
344
345
346
static void usage(int version)
347
{
348
printf("%s Ver 3.6 Distrib %s, for %s (%s)\n",
349
my_progname, VERSION, SYSTEM_TYPE, MACHINE_TYPE);
350
if (version)
351
return;
352
puts("Copyright (C) 2008 Sun Microsystems, Inc.");
353
puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,\n\
354
and you are welcome to modify and redistribute it under the GPL license\n");
355
puts("This program generates a perfect hashing function for the sql_lex.cc");
356
printf("Usage: %s [OPTIONS]\n\n", my_progname);
357
my_print_help(my_long_options);
358
}
359
360
361
extern "C" bool
362
get_one_option(int optid, const struct my_option *,
363
char *)
364
{
365
switch(optid) {
366
case 'V':
367
usage(1);
368
exit(0);
369
case 'I':
370
case '?':
371
usage(0);
372
exit(0);
373
}
374
return 0;
375
}
376
377
378
static int get_options(int argc, char **argv)
379
{
380
int ho_error;
381
382
if ((ho_error= handle_options(&argc, &argv, my_long_options, get_one_option)))
383
exit(ho_error);
384
385
if (argc >= 1)
386
{
387
usage(0);
388
exit(1);
389
}
390
return(0);
391
}
392
393
394
int check_dup_symbols(SYMBOL *s1, SYMBOL *s2)
395
{
396
if (s1->length!=s2->length || strncmp(s1->name,s2->name,s1->length))
397
return 0;
398
399
const char *err_tmpl= "\ngen_lex_hash fatal error : \
400
Unfortunately gen_lex_hash can not generate a hash,\n since \
401
your lex.h has duplicate definition for a symbol \"%s\"\n\n";
402
printf (err_tmpl,s1->name);
403
fprintf (stderr,err_tmpl,s1->name);
404
405
return 1;
406
}
407
408
409
int check_duplicates()
410
{
411
SYMBOL *cur1, *cur2, *s_end, *f_end;
412
413
s_end= symbols + array_elements(symbols);
414
f_end= sql_functions + array_elements(sql_functions);
415
416
for (cur1= symbols; cur1<s_end; cur1++)
417
{
418
for (cur2= cur1+1; cur2<s_end; cur2++)
419
{
420
if (check_dup_symbols(cur1,cur2))
421
return 1;
422
}
423
for (cur2= sql_functions; cur2<f_end; cur2++)
424
{
425
if (check_dup_symbols(cur1,cur2))
426
return 1;
427
}
428
}
429
430
for (cur1= sql_functions; cur1<f_end; cur1++)
431
{
432
for (cur2= cur1+1; cur2< f_end; cur2++)
433
{
434
if (check_dup_symbols(cur1,cur2))
435
return 1;
436
}
437
}
438
return 0;
439
}
440
441
442
int main(int argc,char **argv)
443
{
444
MY_INIT(argv[0]);
445
446
if (get_options(argc,(char **) argv))
447
exit(1);
448
449
/* Broken up to indicate that it's not advice to you, gentle reader. */
450
printf("/*\n\n Do " "not " "edit " "this " "file " "directly!\n\n*/\n");
451
452
printf("/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*- \n"
453
" * vim:expandtab:shiftwidth=2:tabstop=2:smarttab: \n"
454
" * \n"
455
" * Copyright (C) 2008 Sun Microsystems \n"
456
" * \n"
457
" * This program is free software; you can redistribute it and/or modify \n"
458
" * it under the terms of the GNU General Public License as published by \n"
459
" * the Free Software Foundation; version 2 of the License. \n"
460
" * \n"
461
" * This program is distributed in the hope that it will be useful, \n"
462
" * but WITHOUT ANY WARRANTY; without even the implied warranty of \n"
463
" * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the \n"
464
" * GNU General Public License for more details. \n"
465
" * \n"
466
" * You should have received a copy of the GNU General Public License \n"
467
" * along with this program; if not, write to the Free Software \n"
468
" * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA \n"
469
" */\n");
470
471
/* Broken up to indicate that it's not advice to you, gentle reader. */
472
printf("/* Do " "not " "edit " "this " "file! This is generated by "
473
"gen_lex_hash.cc\nthat seeks for a perfect hash function */\n\n");
474
printf("#include <drizzled/lex.h>\n\n");
475
476
calc_length();
477
478
if (check_duplicates())
479
exit(1);
480
481
generate_find_structs();
482
print_find_structs();
483
484
printf("\nstatic unsigned int sql_functions_max_len=%d;\n", max_len);
485
printf("\nstatic unsigned int symbols_max_len=%d;\n\n", max_len2);
486
487
printf("\
488
static SYMBOL *get_hash_symbol(const char *s,\n\
489
unsigned int len,bool function)\n\
490
{\n\
491
register unsigned char *hash_map;\n\
492
register const char *cur_str= s;\n\
493
\n\
494
if (len == 0) {\n\
495
return(NULL);\n\
496
}\n"
497
);
498
499
printf("\
500
if (function){\n\
501
if (len>sql_functions_max_len) return 0;\n\
502
hash_map= sql_functions_map;\n\
503
register uint32_t cur_struct= uint4korr(hash_map+((len-1)*4));\n\
504
\n\
505
for (;;){\n\
506
register unsigned char first_char= (unsigned char)cur_struct;\n\
507
\n\
508
if (first_char == 0)\n\
509
{\n\
510
register int16_t ires= (int16_t)(cur_struct>>16);\n\
511
if (ires==array_elements(symbols)) return 0;\n\
512
register SYMBOL *res;\n\
513
if (ires>=0) \n\
514
res= symbols+ires;\n\
515
else\n\
516
res= sql_functions-ires-1;\n\
517
register uint32_t count= cur_str-s;\n\
518
return lex_casecmp(cur_str,res->name+count,len-count) ? 0 : res;\n\
519
}\n\
520
\n\
521
register unsigned char cur_char= (unsigned char)to_upper_lex[(unsigned char)*cur_str];\n\
522
if (cur_char<first_char) return 0;\n\
523
cur_struct>>=8;\n\
524
if (cur_char>(unsigned char)cur_struct) return 0;\n\
525
\n\
526
cur_struct>>=8;\n\
527
cur_struct= uint4korr(hash_map+\n\
528
(((uint16_t)cur_struct + cur_char - first_char)*4));\n\
529
cur_str++;\n\
530
}\n"
531
);
532
533
printf("\
534
}else{\n\
535
if (len>symbols_max_len) return 0;\n\
536
hash_map= symbols_map;\n\
537
register uint32_t cur_struct= uint4korr(hash_map+((len-1)*4));\n\
538
\n\
539
for (;;){\n\
540
register unsigned char first_char= (unsigned char)cur_struct;\n\
541
\n\
542
if (first_char==0){\n\
543
register int16_t ires= (int16_t)(cur_struct>>16);\n\
544
if (ires==array_elements(symbols)) return 0;\n\
545
register SYMBOL *res= symbols+ires;\n\
546
register uint32_t count= cur_str-s;\n\
547
return lex_casecmp(cur_str,res->name+count,len-count)!=0 ? 0 : res;\n\
548
}\n\
549
\n\
550
register unsigned char cur_char= (unsigned char)to_upper_lex[(unsigned char)*cur_str];\n\
551
if (cur_char<first_char) return 0;\n\
552
cur_struct>>=8;\n\
553
if (cur_char>(unsigned char)cur_struct) return 0;\n\
554
\n\
555
cur_struct>>=8;\n\
556
cur_struct= uint4korr(hash_map+\n\
557
(((uint16_t)cur_struct + cur_char - first_char)*4));\n\
558
cur_str++;\n\
559
}\n\
560
}\n\
561
}\n"
562
);
563
my_end(0);
564
exit(0);
565
}
566
Loggerhead is a web-based interface for Breezy
Version: 2.0.1