← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/gen_lex_hash.cc

  • Committer: Stewart Smith
  • Date: 2008-11-21 16:06:07 UTC
  • mto: This revision was merged to the branch mainline in revision 593.
  • Revision ID: stewart@flamingspork.com-20081121160607-n6gdlt013spuo54r
remove mysql_frm_type
and fix engines to return correct value from delete_table when table doesn't exist.
(it should be ENOENT).

Also fix up some tests that manipulated frm files by hand. These tests are no longer valid and will need to be rewritten in the not too distant future.

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 * symbols) {
 
253
  return sizeof(symbols)/sizeof(symbols[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 *opt __attribute__((unused)),
 
363
               char *argument __attribute__((unused)))
 
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 \"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