← Back to branch summary

~vadim-tk/percona-server/flushing-algo

« back to all changes in this revision

Viewing changes to sql/gen_lex_hash.cc

  • Committer: root
  • Date: 2011-10-29 01:34:40 UTC
  • Revision ID: root@hppro1.office.percona.com-20111029013440-qhnf4jk8kdjcf4e0
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/gen_lex_hash.cc
 
1
/*
 
2
   Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
 
3
 
 
4
   This program is free software; you can redistribute it and/or modify
 
5
   it under the terms of the GNU General Public License as published by
 
6
   the Free Software Foundation; version 2 of the License.
 
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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */
 
16
 
 
17
/**
 
18
  @file
 
19
 
 
20
  @details
 
21
@verbatim
 
22
The idea of presented algorithm see in 
 
23
"The Art of Computer Programming" by Donald E. Knuth
 
24
Volume 3 "Sorting and searching"
 
25
(chapter 6.3 "Digital searching" - name and number of chapter 
 
26
   is back translation from Russian edition :))
 
27
 
 
28
as illustration of data structures, imagine next table:
 
29
 
 
30
static SYMBOL symbols[] = {
 
31
  { "ADD",              SYM(ADD),0,0},
 
32
  { "AND",              SYM(AND),0,0},
 
33
  { "DAY",              SYM(DAY_SYM),0,0},
 
34
};
 
35
 
 
36
for this structure, presented program generate next searching-structure:
 
37
 
 
38
+-----------+-+-+-+
 
39
|       len |1|2|3|
 
40
+-----------+-+-+-+
 
41
|first_char |0|0|a|
 
42
|last_char  |0|0|d|
 
43
|link       |0|0|+|
 
44
                 |
 
45
                 V
 
46
       +----------+-+-+-+--+
 
47
       |    1 char|a|b|c|d |
 
48
       +----------+-+-+-+--+
 
49
       |first_char|b|0|0|0 |
 
50
       |last_char |n|0|0|-1|
 
51
       |link      |+|0|0|+ |
 
52
                   |     |
 
53
                   |     V
 
54
                   |  symbols[2] ( "DAY" )
 
55
                   V
 
56
+----------+--+-+-+-+-+-+-+-+-+-+--+
 
57
|    2 char|d |e|f|j|h|i|j|k|l|m|n |
 
58
+----------+--+-+-+-+-+-+-+-+-+-+--+
 
59
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
 
60
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
 
61
|link      |+ |0|0|0|0|0|0|0|0|0|+ |
 
62
            |                    |
 
63
            V                    V
 
64
         symbols[0] ( "ADD" )  symbols[1] ( "AND" )
 
65
 
 
66
for optimization, link is the 16-bit index in 'symbols' or 'sql_functions'
 
67
or search-array..
 
68
 
 
69
So, we can read full search-structure as 32-bit word
 
70
@endverbatim
 
71
 
 
72
@todo
 
73
    use instead to_upper_lex, special array 
 
74
    (substitute chars) without skip codes..
 
75
@todo
 
76
    try use reverse order of comparing..
 
77
 
 
78
*/
 
79
 
 
80
#define NO_YACC_SYMBOLS
 
81
#include <my_global.h>
 
82
#include "mysql_version.h"
 
83
#include "lex.h"
 
84
#include <stdlib.h>
 
85
#include <stdio.h>
 
86
#include <string.h>
 
87
 
 
88
#include <welcome_copyright_notice.h> /* ORACLE_WELCOME_COPYRIGHT_NOTICE */
 
89
 
 
90
struct hash_lex_struct
 
91
{
 
92
  int first_char;
 
93
  char last_char;
 
94
  union{
 
95
    hash_lex_struct *char_tails;
 
96
    int iresult;
 
97
  };
 
98
  int ithis;
 
99
};
 
100
 
 
101
hash_lex_struct *get_hash_struct_by_len(hash_lex_struct **root_by_len,
 
102
                                            int len, int *max_len)
 
103
{
 
104
  if (*max_len<len){
 
105
    *root_by_len= (hash_lex_struct *)realloc((char*)*root_by_len,
 
106
                                             sizeof(hash_lex_struct)*len);
 
107
    hash_lex_struct *cur, *end= *root_by_len + len;
 
108
    for (cur= *root_by_len + *max_len; cur<end; cur++)
 
109
      cur->first_char= 0;
 
110
    *max_len= len;
 
111
  }
 
112
  return (*root_by_len)+(len-1);
 
113
}
 
114
 
 
115
void insert_into_hash(hash_lex_struct *root, const char *name, 
 
116
                      int len_from_begin, int index, int function)
 
117
{
 
118
  hash_lex_struct *end, *cur, *tails;
 
119
 
 
120
  if (!root->first_char)
 
121
  {
 
122
    root->first_char= -1;
 
123
    root->iresult= index;
 
124
    return;
 
125
  }
 
126
 
 
127
  if (root->first_char == -1)
 
128
  {
 
129
    int index2= root->iresult;
 
130
    const char *name2= (index2 < 0 ? sql_functions[-index2-1] :
 
131
                        symbols[index2]).name + len_from_begin;
 
132
    root->first_char= (int) (uchar) name2[0];
 
133
    root->last_char= (char) root->first_char;
 
134
    tails= (hash_lex_struct*)malloc(sizeof(hash_lex_struct));
 
135
    root->char_tails= tails;
 
136
    tails->first_char= -1;
 
137
    tails->iresult= index2;
 
138
  }
 
139
 
 
140
  size_t real_size= (root->last_char-root->first_char+1);
 
141
 
 
142
  if (root->first_char>(*name))
 
143
  {
 
144
    size_t new_size= root->last_char-(*name)+1;
 
145
    if (new_size<real_size) printf("error!!!!\n");
 
146
    tails= root->char_tails;
 
147
    tails= (hash_lex_struct*)realloc((char*)tails,
 
148
                                       sizeof(hash_lex_struct)*new_size);
 
149
    root->char_tails= tails;
 
150
    memmove(tails+(new_size-real_size),tails,real_size*sizeof(hash_lex_struct));
 
151
    end= tails + new_size - real_size;
 
152
    for (cur= tails; cur<end; cur++)
 
153
      cur->first_char= 0;
 
154
    root->first_char= (int) (uchar) *name;
 
155
  }
 
156
 
 
157
  if (root->last_char<(*name))
 
158
  {
 
159
    size_t new_size= (*name)-root->first_char+1;
 
160
    if (new_size<real_size) printf("error!!!!\n");
 
161
    tails= root->char_tails;
 
162
    tails= (hash_lex_struct*)realloc((char*)tails,
 
163
                                    sizeof(hash_lex_struct)*new_size);
 
164
    root->char_tails= tails;
 
165
    end= tails + new_size;
 
166
    for (cur= tails+real_size; cur<end; cur++)
 
167
      cur->first_char= 0;
 
168
    root->last_char= (*name);
 
169
  }
 
170
 
 
171
  insert_into_hash(root->char_tails+(*name)-root->first_char,
 
172
                   name+1,len_from_begin+1,index,function);
 
173
}
 
174
 
 
175
 
 
176
hash_lex_struct *root_by_len= 0;
 
177
int max_len=0;
 
178
 
 
179
hash_lex_struct *root_by_len2= 0;
 
180
int max_len2=0;
 
181
 
 
182
void insert_symbols()
 
183
{
 
184
  size_t i= 0;
 
185
  SYMBOL *cur;
 
186
  for (cur= symbols; i<array_elements(symbols); cur++, i++){
 
187
    hash_lex_struct *root= 
 
188
      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
 
189
    insert_into_hash(root,cur->name,0,(uint) i,0);
 
190
  }
 
191
}
 
192
 
 
193
void insert_sql_functions()
 
194
{
 
195
  int i= 0;
 
196
  SYMBOL *cur;
 
197
  for (cur= sql_functions; i < (int) array_elements(sql_functions); cur++, i++)
 
198
  {
 
199
    hash_lex_struct *root= 
 
200
      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
 
201
    insert_into_hash(root,cur->name,0,-i-1,1);
 
202
  }
 
203
}
 
204
 
 
205
void calc_length()
 
206
{
 
207
  SYMBOL *cur, *end= symbols + array_elements(symbols);
 
208
  for (cur= symbols; cur < end; cur++)
 
209
    cur->length=(uchar) strlen(cur->name);
 
210
  end= sql_functions + array_elements(sql_functions);
 
211
  for (cur= sql_functions; cur<end; cur++)
 
212
    cur->length=(uchar) strlen(cur->name);
 
213
}
 
214
 
 
215
void generate_find_structs()
 
216
{
 
217
  root_by_len= 0;
 
218
  max_len=0;
 
219
 
 
220
  insert_symbols();
 
221
 
 
222
  root_by_len2= root_by_len;
 
223
  max_len2= max_len;
 
224
 
 
225
  root_by_len= 0;
 
226
  max_len= 0;
 
227
 
 
228
  insert_symbols();
 
229
  insert_sql_functions();
 
230
}
 
231
 
 
232
char *hash_map= 0;
 
233
int size_hash_map= 0;
 
234
 
 
235
void add_struct_to_map(hash_lex_struct *st)
 
236
{
 
237
  st->ithis= size_hash_map/4;
 
238
  size_hash_map+= 4;
 
239
  hash_map= (char*)realloc((char*)hash_map,size_hash_map);
 
240
  hash_map[size_hash_map-4]= (char) (st->first_char == -1 ? 0 :
 
241
                                     st->first_char);
 
242
  hash_map[size_hash_map-3]= (char) (st->first_char == -1 ||
 
243
                                     st->first_char == 0 ? 0 : st->last_char);
 
244
  if (st->first_char == -1)
 
245
  {
 
246
    hash_map[size_hash_map-2]= ((unsigned int)(int16)st->iresult)&255;
 
247
    hash_map[size_hash_map-1]= ((unsigned int)(int16)st->iresult)>>8;
 
248
  }
 
249
  else if (st->first_char == 0)
 
250
  {
 
251
    hash_map[size_hash_map-2]= ((unsigned int)(int16)array_elements(symbols))&255;
 
252
    hash_map[size_hash_map-1]= ((unsigned int)(int16)array_elements(symbols))>>8;
 
253
  }
 
254
}
 
255
 
 
256
 
 
257
void add_structs_to_map(hash_lex_struct *st, int len)
 
258
{
 
259
  hash_lex_struct *cur, *end= st+len;
 
260
  for (cur= st; cur<end; cur++)
 
261
    add_struct_to_map(cur);
 
262
  for (cur= st; cur<end; cur++)
 
263
  {
 
264
    if (cur->first_char && cur->first_char != -1)
 
265
      add_structs_to_map(cur->char_tails,cur->last_char-cur->first_char+1);
 
266
  }
 
267
}
 
268
 
 
269
void set_links(hash_lex_struct *st, int len)
 
270
{
 
271
  hash_lex_struct *cur, *end= st+len;
 
272
  for (cur= st; cur<end; cur++)
 
273
  {
 
274
    if (cur->first_char != 0 && cur->first_char != -1)
 
275
    {
 
276
      int ilink= cur->char_tails->ithis;
 
277
      hash_map[cur->ithis*4+2]= ilink%256;
 
278
      hash_map[cur->ithis*4+3]= ilink/256;
 
279
      set_links(cur->char_tails,cur->last_char-cur->first_char+1);
 
280
    }
 
281
  }
 
282
}
 
283
 
 
284
 
 
285
void print_hash_map(const char *name)
 
286
{
 
287
  char *cur;
 
288
  int i;
 
289
 
 
290
  printf("static uchar %s[%d]= {\n",name,size_hash_map);
 
291
  for (i=0, cur= hash_map; i<size_hash_map; i++, cur++)
 
292
  {
 
293
    switch(i%4){
 
294
    case 0: case 1:
 
295
      if (!*cur)
 
296
        printf("0,   ");
 
297
      else
 
298
        printf("\'%c\', ",*cur);
 
299
      break;
 
300
    case 2: printf("%u, ",(uint)(uchar)*cur); break;
 
301
    case 3: printf("%u,\n",(uint)(uchar)*cur); break;
 
302
    }
 
303
  }
 
304
  printf("};\n");
 
305
}
 
306
 
 
307
 
 
308
void print_find_structs()
 
309
{
 
310
  add_structs_to_map(root_by_len,max_len);
 
311
  set_links(root_by_len,max_len);
 
312
  print_hash_map("sql_functions_map");
 
313
 
 
314
  hash_map= 0;
 
315
  size_hash_map= 0;
 
316
 
 
317
  printf("\n");
 
318
 
 
319
  add_structs_to_map(root_by_len2,max_len2);
 
320
  set_links(root_by_len2,max_len2);
 
321
  print_hash_map("symbols_map");
 
322
}
 
323
 
 
324
 
 
325
int check_dup_symbols(SYMBOL *s1, SYMBOL *s2)
 
326
{
 
327
  if (s1->length!=s2->length || strncmp(s1->name,s2->name,s1->length))
 
328
    return 0;
 
329
 
 
330
  const char *err_tmpl= "\ngen_lex_hash fatal error : \
 
331
Unfortunately gen_lex_hash can not generate a hash,\n since \
 
332
your lex.h has duplicate definition for a symbol \"%s\"\n\n";
 
333
  printf (err_tmpl,s1->name);
 
334
  fprintf (stderr,err_tmpl,s1->name);
 
335
 
 
336
  return 1;
 
337
}
 
338
 
 
339
 
 
340
int check_duplicates()
 
341
{
 
342
  SYMBOL *cur1, *cur2, *s_end, *f_end;
 
343
 
 
344
  s_end= symbols + array_elements(symbols);
 
345
  f_end= sql_functions + array_elements(sql_functions);
 
346
 
 
347
  for (cur1= symbols; cur1<s_end; cur1++)
 
348
  {
 
349
    for (cur2= cur1+1; cur2<s_end; cur2++)
 
350
    {
 
351
      if (check_dup_symbols(cur1,cur2))
 
352
        return 1;
 
353
    }
 
354
    for (cur2= sql_functions; cur2<f_end; cur2++)
 
355
    {
 
356
      if (check_dup_symbols(cur1,cur2))
 
357
        return 1;
 
358
    }
 
359
  }
 
360
 
 
361
  for (cur1= sql_functions; cur1<f_end; cur1++)
 
362
  {
 
363
    for (cur2= cur1+1; cur2< f_end; cur2++)
 
364
    {
 
365
      if (check_dup_symbols(cur1,cur2))
 
366
        return 1;
 
367
    }
 
368
  }
 
369
  return 0;
 
370
}
 
371
 
 
372
 
 
373
int main(int argc,char **argv)
 
374
{
 
375
 
 
376
 
 
377
  /* Broken up to indicate that it's not advice to you, gentle reader. */
 
378
  printf("/*\n\n  Do " "not " "edit " "this " "file " "directly!\n\n*/\n");
 
379
 
 
380
  puts("/*");
 
381
  puts(ORACLE_WELCOME_COPYRIGHT_NOTICE("2000, 2011"));
 
382
  puts("*/");
 
383
 
 
384
  /* Broken up to indicate that it's not advice to you, gentle reader. */
 
385
  printf("/* Do " "not " "edit " "this " "file!  This is generated by "
 
386
         "gen_lex_hash.cc\nthat seeks for a perfect hash function */\n\n");
 
387
  printf("#include \"lex.h\"\n\n");
 
388
 
 
389
  calc_length();
 
390
 
 
391
  if (check_duplicates())
 
392
    exit(1);
 
393
 
 
394
  generate_find_structs();
 
395
  print_find_structs();
 
396
 
 
397
  printf("\nstatic unsigned int sql_functions_max_len=%d;\n", max_len);
 
398
  printf("\nstatic unsigned int symbols_max_len=%d;\n\n", max_len2);
 
399
 
 
400
  printf("\
 
401
static SYMBOL *get_hash_symbol(const char *s,\n\
 
402
                               unsigned int len,bool function)\n\
 
403
{\n\
 
404
  register uchar *hash_map;\n\
 
405
  register const char *cur_str= s;\n\
 
406
\n\
 
407
  if (len == 0) {\n\
 
408
    DBUG_PRINT(\"warning\", (\"get_hash_symbol() received a request for a zero-length symbol, which is probably a mistake.\"));\
 
409
    return(NULL);\n\
 
410
  }\n"
 
411
);
 
412
 
 
413
  printf("\
 
414
  if (function){\n\
 
415
    if (len>sql_functions_max_len) return 0;\n\
 
416
    hash_map= sql_functions_map;\n\
 
417
    register uint32 cur_struct= uint4korr(hash_map+((len-1)*4));\n\
 
418
\n\
 
419
    for (;;){\n\
 
420
      register uchar first_char= (uchar)cur_struct;\n\
 
421
\n\
 
422
      if (first_char == 0)\n\
 
423
      {\n\
 
424
        register int16 ires= (int16)(cur_struct>>16);\n\
 
425
        if (ires==array_elements(symbols)) return 0;\n\
 
426
        register SYMBOL *res;\n\
 
427
        if (ires>=0) \n\
 
428
          res= symbols+ires;\n\
 
429
        else\n\
 
430
          res= sql_functions-ires-1;\n\
 
431
                  register uint count= (uint) (cur_str - s);\n\
 
432
        return lex_casecmp(cur_str,res->name+count,len-count) ? 0 : res;\n\
 
433
      }\n\
 
434
\n\
 
435
      register uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];\n\
 
436
      if (cur_char<first_char) return 0;\n\
 
437
      cur_struct>>=8;\n\
 
438
      if (cur_char>(uchar)cur_struct) return 0;\n\
 
439
\n\
 
440
      cur_struct>>=8;\n\
 
441
      cur_struct= uint4korr(hash_map+\n\
 
442
                        (((uint16)cur_struct + cur_char - first_char)*4));\n\
 
443
      cur_str++;\n\
 
444
    }\n"
 
445
);
 
446
 
 
447
  printf("\
 
448
  }else{\n\
 
449
    if (len>symbols_max_len) return 0;\n\
 
450
    hash_map= symbols_map;\n\
 
451
    register uint32 cur_struct= uint4korr(hash_map+((len-1)*4));\n\
 
452
\n\
 
453
    for (;;){\n\
 
454
      register uchar first_char= (uchar)cur_struct;\n\
 
455
\n\
 
456
      if (first_char==0){\n\
 
457
        register int16 ires= (int16)(cur_struct>>16);\n\
 
458
        if (ires==array_elements(symbols)) return 0;\n\
 
459
        register SYMBOL *res= symbols+ires;\n\
 
460
                register uint count= (uint) (cur_str - s);\n\
 
461
        return lex_casecmp(cur_str,res->name+count,len-count)!=0 ? 0 : res;\n\
 
462
      }\n\
 
463
\n\
 
464
      register uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];\n\
 
465
      if (cur_char<first_char) return 0;\n\
 
466
      cur_struct>>=8;\n\
 
467
      if (cur_char>(uchar)cur_struct) return 0;\n\
 
468
\n\
 
469
      cur_struct>>=8;\n\
 
470
      cur_struct= uint4korr(hash_map+\n\
 
471
                        (((uint16)cur_struct + cur_char - first_char)*4));\n\
 
472
      cur_str++;\n\
 
473
    }\n\
 
474
  }\n\
 
475
}\n"
 
476
);
 
477
  exit(0);
 
478
}
 
479