← Back to branch summary

~vlad-lesin/percona-server/mysql-5.0.33-original

« back to all changes in this revision

Viewing changes to sql/gen_lex_hash.cc

  • Committer: Vlad Lesin
  • Date: 2012-07-31 09:21:34 UTC
  • Revision ID: vladislav.lesin@percona.com-20120731092134-zfodx022b7992wsi
Virgin 5.0.33

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/gen_lex_hash.cc
 
1
/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; either version 2 of the License, or
 
6
   (at your option) any later version.
 
7
 
 
8
   This program is distributed in the hope that it will be useful,
 
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
   GNU General Public License for more details.
 
12
 
 
13
   You should have received a copy of the GNU General Public License
 
14
   along with this program; if not, write to the Free Software
 
15
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
16
 
 
17
/*
 
18
 
 
19
The idea of presented algorithm see in 
 
20
"The Art of Computer Programming" by Donald E. Knuth
 
21
Volume 3 "Sorting and searching"
 
22
(chapter 6.3 "Digital searching" - name and number of chapter 
 
23
   is back translation from Russian edition :))
 
24
 
 
25
as illustration of data structures, imagine next table:
 
26
 
 
27
static SYMBOL symbols[] = {
 
28
  { "ADD",              SYM(ADD),0,0},
 
29
  { "AND",              SYM(AND),0,0},
 
30
  { "DAY",              SYM(DAY_SYM),0,0},
 
31
};
 
32
 
 
33
for this structure, presented program generate next searching-structure:
 
34
 
 
35
+-----------+-+-+-+
 
36
|       len |1|2|3|
 
37
+-----------+-+-+-+
 
38
|first_char |0|0|a|
 
39
|last_char  |0|0|d|
 
40
|link       |0|0|+|
 
41
                 |
 
42
                 V
 
43
       +----------+-+-+-+--+
 
44
       |    1 char|a|b|c|d |
 
45
       +----------+-+-+-+--+
 
46
       |first_char|b|0|0|0 |
 
47
       |last_char |n|0|0|-1|
 
48
       |link      |+|0|0|+ |
 
49
                   |     |
 
50
                   |     V
 
51
                   |  symbols[2] ( "DAY" )
 
52
                   V
 
53
+----------+--+-+-+-+-+-+-+-+-+-+--+
 
54
|    2 char|d |e|f|j|h|i|j|k|l|m|n |
 
55
+----------+--+-+-+-+-+-+-+-+-+-+--+
 
56
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
 
57
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
 
58
|link      |+ |0|0|0|0|0|0|0|0|0|+ |
 
59
            |                    |
 
60
            V                    V
 
61
         symbols[0] ( "ADD" )  symbols[1] ( "AND" )
 
62
 
 
63
for optimization, link is the 16-bit index in 'symbols' or 'sql_functions'
 
64
or search-array..
 
65
 
 
66
So, we can read full search-structure as 32-bit word
 
67
 
 
68
TODO:
 
69
1. use instead to_upper_lex, special array 
 
70
   (substitute chars) without skip codes..
 
71
2. try use reverse order of comparing..
 
72
       
 
73
*/
 
74
 
 
75
#define NO_YACC_SYMBOLS
 
76
#include "my_global.h"
 
77
#include "my_sys.h"
 
78
#include "m_string.h"
 
79
#ifndef __GNU_LIBRARY__
 
80
#define __GNU_LIBRARY__                         // Skip warnings in getopt.h
 
81
#endif
 
82
#include <my_getopt.h>
 
83
#include "mysql_version.h"
 
84
#include "lex.h"
 
85
 
 
86
const char *default_dbug_option="d:t:o,/tmp/gen_lex_hash.trace";
 
87
 
 
88
struct my_option my_long_options[] =
 
89
{
 
90
#ifdef DBUG_OFF
 
91
  {"debug", '#', "This is a non-debug version. Catch this and exit",
 
92
   0,0, 0, GET_DISABLED, OPT_ARG, 0, 0, 0, 0, 0, 0},
 
93
#else
 
94
  {"debug", '#', "Output debug log", (gptr*) &default_dbug_option,
 
95
   (gptr*) &default_dbug_option, 0, GET_STR, OPT_ARG, 0, 0, 0, 0, 0, 0},
 
96
#endif
 
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) (uchar) 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) (uchar) *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=(uchar) strlen(cur->name);
 
224
  end= sql_functions + array_elements(sql_functions);
 
225
  for (cur= sql_functions; cur<end; cur++)
 
226
    cur->length=(uchar) 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
void add_struct_to_map(hash_lex_struct *st)
 
250
{
 
251
  st->ithis= size_hash_map/4;
 
252
  size_hash_map+= 4;
 
253
  hash_map= (char*)realloc((char*)hash_map,size_hash_map);
 
254
  hash_map[size_hash_map-4]= (char) (st->first_char == -1 ? 0 :
 
255
                                     st->first_char);
 
256
  hash_map[size_hash_map-3]= (char) (st->first_char == -1 ||
 
257
                                     st->first_char == 0 ? 0 : st->last_char);
 
258
  if (st->first_char == -1)
 
259
  {
 
260
    hash_map[size_hash_map-2]= ((unsigned int)(int16)st->iresult)&255;
 
261
    hash_map[size_hash_map-1]= ((unsigned int)(int16)st->iresult)>>8;
 
262
  }
 
263
  else if (st->first_char == 0)
 
264
  {
 
265
    hash_map[size_hash_map-2]= ((unsigned int)(int16)array_elements(symbols))&255;
 
266
    hash_map[size_hash_map-1]= ((unsigned int)(int16)array_elements(symbols))>>8;
 
267
  }
 
268
}
 
269
 
 
270
 
 
271
void add_structs_to_map(hash_lex_struct *st, int len)
 
272
{
 
273
  hash_lex_struct *cur, *end= st+len;
 
274
  for (cur= st; cur<end; cur++)
 
275
    add_struct_to_map(cur);
 
276
  for (cur= st; cur<end; cur++)
 
277
  {
 
278
    if (cur->first_char && cur->first_char != -1)
 
279
      add_structs_to_map(cur->char_tails,cur->last_char-cur->first_char+1);
 
280
  }
 
281
}
 
282
 
 
283
void set_links(hash_lex_struct *st, int len)
 
284
{
 
285
  hash_lex_struct *cur, *end= st+len;
 
286
  for (cur= st; cur<end; cur++)
 
287
  {
 
288
    if (cur->first_char != 0 && cur->first_char != -1)
 
289
    {
 
290
      int ilink= cur->char_tails->ithis;
 
291
      hash_map[cur->ithis*4+2]= ilink%256;
 
292
      hash_map[cur->ithis*4+3]= ilink/256;
 
293
      set_links(cur->char_tails,cur->last_char-cur->first_char+1);
 
294
    }
 
295
  }
 
296
}
 
297
 
 
298
 
 
299
void print_hash_map(const char *name)
 
300
{
 
301
  char *cur;
 
302
  int i;
 
303
 
 
304
  printf("static uchar %s[%d]= {\n",name,size_hash_map);
 
305
  for (i=0, cur= hash_map; i<size_hash_map; i++, cur++)
 
306
  {
 
307
    switch(i%4){
 
308
    case 0: case 1:
 
309
      if (!*cur)
 
310
        printf("0,   ");
 
311
      else
 
312
        printf("\'%c\', ",*cur);
 
313
      break;
 
314
    case 2: printf("%u, ",(uint)(uchar)*cur); break;
 
315
    case 3: printf("%u,\n",(uint)(uchar)*cur); break;
 
316
    }
 
317
  }
 
318
  printf("};\n");
 
319
}
 
320
 
 
321
 
 
322
void print_find_structs()
 
323
{
 
324
  add_structs_to_map(root_by_len,max_len);
 
325
  set_links(root_by_len,max_len);
 
326
  print_hash_map("sql_functions_map");
 
327
 
 
328
  hash_map= 0;
 
329
  size_hash_map= 0;
 
330
 
 
331
  printf("\n");
 
332
 
 
333
  add_structs_to_map(root_by_len2,max_len2);
 
334
  set_links(root_by_len2,max_len2);
 
335
  print_hash_map("symbols_map");
 
336
}
 
337
 
 
338
 
 
339
static void usage(int version)
 
340
{
 
341
  printf("%s  Ver 3.6 Distrib %s, for %s (%s)\n",
 
342
         my_progname, MYSQL_SERVER_VERSION, SYSTEM_TYPE, MACHINE_TYPE);
 
343
  if (version)
 
344
    return;
 
345
  puts("Copyright (C) 2001 MySQL AB, by VVA and Monty");
 
346
  puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,\n\
 
347
and you are welcome to modify and redistribute it under the GPL license\n");
 
348
  puts("This program generates a perfect hashing function for the sql_lex.cc");
 
349
  printf("Usage: %s [OPTIONS]\n\n", my_progname);
 
350
  my_print_help(my_long_options);
 
351
}
 
352
 
 
353
 
 
354
extern "C" my_bool
 
355
get_one_option(int optid, const struct my_option *opt __attribute__((unused)),
 
356
               char *argument __attribute__((unused)))
 
357
{
 
358
  switch(optid) {
 
359
  case 'V':
 
360
    usage(1);
 
361
    exit(0);
 
362
  case 'I':
 
363
  case '?':
 
364
    usage(0);
 
365
    exit(0);
 
366
  case '#':
 
367
    DBUG_PUSH(argument ? argument : default_dbug_option);
 
368
    break;
 
369
  }
 
370
  return 0;
 
371
}
 
372
 
 
373
 
 
374
static int get_options(int argc, char **argv)
 
375
{
 
376
  int ho_error;
 
377
 
 
378
  if ((ho_error= handle_options(&argc, &argv, my_long_options, get_one_option)))
 
379
    exit(ho_error);
 
380
 
 
381
  if (argc >= 1)
 
382
  {
 
383
    usage(0);
 
384
     exit(1);
 
385
  }
 
386
  return(0);
 
387
}
 
388
 
 
389
 
 
390
int check_dup_symbols(SYMBOL *s1, SYMBOL *s2)
 
391
{
 
392
  if (s1->length!=s2->length || strncmp(s1->name,s2->name,s1->length))
 
393
    return 0;
 
394
 
 
395
  const char *err_tmpl= "\ngen_lex_hash fatal error : \
 
396
Unfortunately gen_lex_hash can not generate a hash,\n since \
 
397
your lex.h has duplicate definition for a symbol \"%s\"\n\n";
 
398
  printf (err_tmpl,s1->name);
 
399
  fprintf (stderr,err_tmpl,s1->name);
 
400
 
 
401
  return 1;
 
402
}
 
403
 
 
404
 
 
405
int check_duplicates()
 
406
{
 
407
  SYMBOL *cur1, *cur2, *s_end, *f_end;
 
408
 
 
409
  s_end= symbols + array_elements(symbols);
 
410
  f_end= sql_functions + array_elements(sql_functions);
 
411
 
 
412
  for (cur1= symbols; cur1<s_end; cur1++)
 
413
  {
 
414
    for (cur2= cur1+1; cur2<s_end; cur2++)
 
415
    {
 
416
      if (check_dup_symbols(cur1,cur2))
 
417
        return 1;
 
418
    }
 
419
    for (cur2= sql_functions; cur2<f_end; cur2++)
 
420
    {
 
421
      if (check_dup_symbols(cur1,cur2))
 
422
        return 1;
 
423
    }
 
424
  }
 
425
 
 
426
  for (cur1= sql_functions; cur1<f_end; cur1++)
 
427
  {
 
428
    for (cur2= cur1+1; cur2< f_end; cur2++)
 
429
    {
 
430
      if (check_dup_symbols(cur1,cur2))
 
431
        return 1;
 
432
    }
 
433
  }
 
434
  return 0;
 
435
}
 
436
 
 
437
 
 
438
int main(int argc,char **argv)
 
439
{
 
440
  MY_INIT(argv[0]);
 
441
  DBUG_PROCESS(argv[0]);
 
442
 
 
443
  if (get_options(argc,(char **) argv))
 
444
    exit(1);
 
445
 
 
446
  /* Broken up to indicate that it's not advice to you, gentle reader. */
 
447
  printf("/*\n\n  Do " "not " "edit " "this " "file " "directly!\n\n*/\n");
 
448
 
 
449
  printf("/* Copyright (C) 2001-2004 MySQL AB\n\
 
450
   This software comes with ABSOLUTELY NO WARRANTY. This is free software,\n\
 
451
   and you are welcome to modify and redistribute it under the GPL license\n\
 
452
   \n*/\n\n");
 
453
 
 
454
  /* Broken up to indicate that it's not advice to you, gentle reader. */
 
455
  printf("/* Do " "not " "edit " "this " "file!  This is generated by "
 
456
         "gen_lex_hash.cc\nthat seeks for a perfect hash function */\n\n");
 
457
  printf("#include \"lex.h\"\n\n");
 
458
 
 
459
  calc_length();
 
460
 
 
461
  if (check_duplicates())
 
462
    exit(1);
 
463
 
 
464
  generate_find_structs();
 
465
  print_find_structs();
 
466
 
 
467
  printf("\nstatic unsigned int sql_functions_max_len=%d;\n", max_len);
 
468
  printf("\nstatic unsigned int symbols_max_len=%d;\n\n", max_len2);
 
469
 
 
470
  printf("\
 
471
static inline SYMBOL *get_hash_symbol(const char *s,\n\
 
472
                                    unsigned int len,bool function)\n\
 
473
{\n\
 
474
  register uchar *hash_map;\n\
 
475
  register const char *cur_str= s;\n\
 
476
\n\
 
477
  if (len == 0) {\n\
 
478
    DBUG_PRINT(\"warning\", (\"get_hash_symbol() received a request for a zero-length symbol, which is probably a mistake.\"));\
 
479
    return(NULL);\n\
 
480
  }\n"
 
481
);
 
482
 
 
483
  printf("\
 
484
  if (function){\n\
 
485
    if (len>sql_functions_max_len) return 0;\n\
 
486
    hash_map= sql_functions_map;\n\
 
487
    register uint32 cur_struct= uint4korr(hash_map+((len-1)*4));\n\
 
488
\n\
 
489
    for (;;){\n\
 
490
      register uchar first_char= (uchar)cur_struct;\n\
 
491
\n\
 
492
      if (first_char == 0)\n\
 
493
      {\n\
 
494
        register int16 ires= (int16)(cur_struct>>16);\n\
 
495
        if (ires==array_elements(symbols)) return 0;\n\
 
496
        register SYMBOL *res;\n\
 
497
        if (ires>=0) \n\
 
498
          res= symbols+ires;\n\
 
499
        else\n\
 
500
          res= sql_functions-ires-1;\n\
 
501
        register uint count= cur_str-s;\n\
 
502
        return lex_casecmp(cur_str,res->name+count,len-count) ? 0 : res;\n\
 
503
      }\n\
 
504
\n\
 
505
      register uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];\n\
 
506
      if (cur_char<first_char) return 0;\n\
 
507
      cur_struct>>=8;\n\
 
508
      if (cur_char>(uchar)cur_struct) return 0;\n\
 
509
\n\
 
510
      cur_struct>>=8;\n\
 
511
      cur_struct= uint4korr(hash_map+\n\
 
512
                        (((uint16)cur_struct + cur_char - first_char)*4));\n\
 
513
      cur_str++;\n\
 
514
    }\n"
 
515
);
 
516
 
 
517
  printf("\
 
518
  }else{\n\
 
519
    if (len>symbols_max_len) return 0;\n\
 
520
    hash_map= symbols_map;\n\
 
521
    register uint32 cur_struct= uint4korr(hash_map+((len-1)*4));\n\
 
522
\n\
 
523
    for (;;){\n\
 
524
      register uchar first_char= (uchar)cur_struct;\n\
 
525
\n\
 
526
      if (first_char==0){\n\
 
527
        register int16 ires= (int16)(cur_struct>>16);\n\
 
528
        if (ires==array_elements(symbols)) return 0;\n\
 
529
        register SYMBOL *res= symbols+ires;\n\
 
530
        register uint count= cur_str-s;\n\
 
531
        return lex_casecmp(cur_str,res->name+count,len-count)!=0 ? 0 : res;\n\
 
532
      }\n\
 
533
\n\
 
534
      register uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];\n\
 
535
      if (cur_char<first_char) return 0;\n\
 
536
      cur_struct>>=8;\n\
 
537
      if (cur_char>(uchar)cur_struct) return 0;\n\
 
538
\n\
 
539
      cur_struct>>=8;\n\
 
540
      cur_struct= uint4korr(hash_map+\n\
 
541
                        (((uint16)cur_struct + cur_char - first_char)*4));\n\
 
542
      cur_str++;\n\
 
543
    }\n\
 
544
  }\n\
 
545
}\n"
 
546
);
 
547
  my_end(0);
 
548
  exit(0);
 
549
}
 
550