← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/gen_lex_hash.cc

  • Committer: Brian Aker
  • Date: 2009-03-27 22:55:28 UTC
  • mto: This revision was merged to the branch mainline in revision 968.
  • Revision ID: brian@tangent.org-20090327225528-8y76cfx8a4oemqv9
Remove ref_count

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 "global.h"
85
 
#include <mysys/my_sys.h>
86
 
#include <mystrings/m_string.h>
87
 
#ifndef __GNU_LIBRARY__
88
 
#define __GNU_LIBRARY__                         // Skip warnings in getopt.h
89
 
#endif
90
 
#include <mysys/my_getopt.h>
91
 
#include <drizzled/version.h>
92
 
#include "lex.h"
93
 
 
94
 
const char *default_dbug_option="d:t:o,/tmp/gen_lex_hash.trace";
95
 
 
96
 
struct my_option my_long_options[] =
97
 
{
98
 
  {"help", '?', "Display help and exit",
99
 
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
100
 
  {"version", 'V', "Output version information and exit",
101
 
   0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0},
102
 
  {0, 0, 0, 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}
103
 
};
104
 
 
105
 
struct hash_lex_struct
106
 
{
107
 
  int first_char;
108
 
  char last_char;
109
 
  union{
110
 
    hash_lex_struct *char_tails;
111
 
    int iresult;
112
 
  };
113
 
  int ithis;
114
 
};
115
 
 
116
 
hash_lex_struct *get_hash_struct_by_len(hash_lex_struct **root_by_len,
117
 
                                            int len, int *max_len)
118
 
{
119
 
  if (*max_len<len){
120
 
    *root_by_len= (hash_lex_struct *)realloc((char*)*root_by_len,
121
 
                                             sizeof(hash_lex_struct)*len);
122
 
    hash_lex_struct *cur, *end= *root_by_len + len;
123
 
    for (cur= *root_by_len + *max_len; cur<end; cur++)
124
 
      cur->first_char= 0;
125
 
    *max_len= len;
126
 
  }
127
 
  return (*root_by_len)+(len-1);
128
 
}
129
 
 
130
 
void insert_into_hash(hash_lex_struct *root, const char *name, 
131
 
                      int len_from_begin, int index, int function)
132
 
{
133
 
  hash_lex_struct *end, *cur, *tails;
134
 
 
135
 
  if (!root->first_char)
136
 
  {
137
 
    root->first_char= -1;
138
 
    root->iresult= index;
139
 
    return;
140
 
  }
141
 
 
142
 
  if (root->first_char == -1)
143
 
  {
144
 
    int index2= root->iresult;
145
 
    const char *name2= (index2 < 0 ? sql_functions[-index2-1] :
146
 
                        symbols[index2]).name + len_from_begin;
147
 
    root->first_char= (int) (unsigned char) name2[0];
148
 
    root->last_char= (char) root->first_char;
149
 
    tails= (hash_lex_struct*)malloc(sizeof(hash_lex_struct));
150
 
    root->char_tails= tails;
151
 
    tails->first_char= -1;
152
 
    tails->iresult= index2;
153
 
  }
154
 
 
155
 
  size_t real_size= (root->last_char-root->first_char+1);
156
 
 
157
 
  if (root->first_char>(*name))
158
 
  {
159
 
    size_t new_size= root->last_char-(*name)+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
 
    memmove(tails+(new_size-real_size),tails,real_size*sizeof(hash_lex_struct));
166
 
    end= tails + new_size - real_size;
167
 
    for (cur= tails; cur<end; cur++)
168
 
      cur->first_char= 0;
169
 
    root->first_char= (int) (unsigned char) *name;
170
 
  }
171
 
 
172
 
  if (root->last_char<(*name))
173
 
  {
174
 
    size_t new_size= (*name)-root->first_char+1;
175
 
    if (new_size<real_size) printf("error!!!!\n");
176
 
    tails= root->char_tails;
177
 
    tails= (hash_lex_struct*)realloc((char*)tails,
178
 
                                    sizeof(hash_lex_struct)*new_size);
179
 
    root->char_tails= tails;
180
 
    end= tails + new_size;
181
 
    for (cur= tails+real_size; cur<end; cur++)
182
 
      cur->first_char= 0;
183
 
    root->last_char= (*name);
184
 
  }
185
 
 
186
 
  insert_into_hash(root->char_tails+(*name)-root->first_char,
187
 
                   name+1,len_from_begin+1,index,function);
188
 
}
189
 
 
190
 
 
191
 
hash_lex_struct *root_by_len= 0;
192
 
int max_len=0;
193
 
 
194
 
hash_lex_struct *root_by_len2= 0;
195
 
int max_len2=0;
196
 
 
197
 
void insert_symbols()
198
 
{
199
 
  size_t i= 0;
200
 
  SYMBOL *cur;
201
 
  for (cur= symbols; i<array_elements(symbols); cur++, i++){
202
 
    hash_lex_struct *root= 
203
 
      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
204
 
    insert_into_hash(root,cur->name,0,i,0);
205
 
  }
206
 
}
207
 
 
208
 
void insert_sql_functions()
209
 
{
210
 
  int i= 0;
211
 
  SYMBOL *cur;
212
 
  for (cur= sql_functions; i < (int) array_elements(sql_functions); cur++, i++)
213
 
  {
214
 
    hash_lex_struct *root= 
215
 
      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
216
 
    insert_into_hash(root,cur->name,0,-i-1,1);
217
 
  }
218
 
}
219
 
 
220
 
void calc_length()
221
 
{
222
 
  SYMBOL *cur, *end= symbols + array_elements(symbols);
223
 
  for (cur= symbols; cur < end; cur++)
224
 
    cur->length=(unsigned char) strlen(cur->name);
225
 
  end= sql_functions + array_elements(sql_functions);
226
 
  for (cur= sql_functions; cur<end; cur++)
227
 
    cur->length=(unsigned char) strlen(cur->name);
228
 
}
229
 
 
230
 
void generate_find_structs()
231
 
{
232
 
  root_by_len= 0;
233
 
  max_len=0;
234
 
 
235
 
  insert_symbols();
236
 
 
237
 
  root_by_len2= root_by_len;
238
 
  max_len2= max_len;
239
 
 
240
 
  root_by_len= 0;
241
 
  max_len= 0;
242
 
 
243
 
  insert_symbols();
244
 
  insert_sql_functions();
245
 
}
246
 
 
247
 
char *hash_map= 0;
248
 
int size_hash_map= 0;
249
 
 
250
 
/* Ok. I honestly don't know why this has no problem and
251
 
 * array_elements macro doesn't. But it works.
252
 
 */
253
 
static inline uint32_t array_elements_func(SYMBOL * symbols) {
254
 
  return sizeof(symbols)/sizeof(symbols[0]);
255
 
}
256
 
 
257
 
void add_struct_to_map(hash_lex_struct *st)
258
 
{
259
 
  st->ithis= size_hash_map/4;
260
 
  size_hash_map+= 4;
261
 
  hash_map= (char*)realloc((char*)hash_map,size_hash_map);
262
 
  hash_map[size_hash_map-4]= (char) (st->first_char == -1 ? 0 :
263
 
                                     st->first_char);
264
 
  hash_map[size_hash_map-3]= (char) (st->first_char == -1 ||
265
 
                                     st->first_char == 0 ? 0 : st->last_char);
266
 
  if (st->first_char == -1)
267
 
  {
268
 
    hash_map[size_hash_map-2]= ((unsigned int)(int16_t)st->iresult)&255;
269
 
    hash_map[size_hash_map-1]= ((unsigned int)(int16_t)st->iresult)>>8;
270
 
  }
271
 
  else if (st->first_char == 0)
272
 
  {
273
 
    hash_map[size_hash_map-2]= ((unsigned int)(int16_t)array_elements_func(symbols))&255;
274
 
    hash_map[size_hash_map-1]= ((unsigned int)(int16_t)array_elements(symbols))>>8;
275
 
  }
276
 
}
277
 
 
278
 
 
279
 
void add_structs_to_map(hash_lex_struct *st, int len)
280
 
{
281
 
  hash_lex_struct *cur, *end= st+len;
282
 
  for (cur= st; cur<end; cur++)
283
 
    add_struct_to_map(cur);
284
 
  for (cur= st; cur<end; cur++)
285
 
  {
286
 
    if (cur->first_char && cur->first_char != -1)
287
 
      add_structs_to_map(cur->char_tails,cur->last_char-cur->first_char+1);
288
 
  }
289
 
}
290
 
 
291
 
void set_links(hash_lex_struct *st, int len)
292
 
{
293
 
  hash_lex_struct *cur, *end= st+len;
294
 
  for (cur= st; cur<end; cur++)
295
 
  {
296
 
    if (cur->first_char != 0 && cur->first_char != -1)
297
 
    {
298
 
      int ilink= cur->char_tails->ithis;
299
 
      hash_map[cur->ithis*4+2]= ilink%256;
300
 
      hash_map[cur->ithis*4+3]= ilink/256;
301
 
      set_links(cur->char_tails,cur->last_char-cur->first_char+1);
302
 
    }
303
 
  }
304
 
}
305
 
 
306
 
 
307
 
void print_hash_map(const char *name)
308
 
{
309
 
  char *cur;
310
 
  int i;
311
 
 
312
 
  printf("static unsigned char %s[%d]= {\n",name,size_hash_map);
313
 
  for (i=0, cur= hash_map; i<size_hash_map; i++, cur++)
314
 
  {
315
 
    switch(i%4){
316
 
    case 0: case 1:
317
 
      if (!*cur)
318
 
        printf("0,   ");
319
 
      else
320
 
        printf("\'%c\', ",*cur);
321
 
      break;
322
 
    case 2: printf("%u, ",(uint)(unsigned char)*cur); break;
323
 
    case 3: printf("%u,\n",(uint)(unsigned char)*cur); break;
324
 
    }
325
 
  }
326
 
  printf("};\n");
327
 
}
328
 
 
329
 
 
330
 
void print_find_structs()
331
 
{
332
 
  add_structs_to_map(root_by_len,max_len);
333
 
  set_links(root_by_len,max_len);
334
 
  print_hash_map("sql_functions_map");
335
 
 
336
 
  hash_map= 0;
337
 
  size_hash_map= 0;
338
 
 
339
 
  printf("\n");
340
 
 
341
 
  add_structs_to_map(root_by_len2,max_len2);
342
 
  set_links(root_by_len2,max_len2);
343
 
  print_hash_map("symbols_map");
344
 
}
345
 
 
346
 
 
347
 
static void usage(int version)
348
 
{
349
 
  printf("%s  Ver 3.6 Distrib %s, for %s (%s)\n",
350
 
         my_progname, DRIZZLE_SERVER_VERSION, SYSTEM_TYPE, MACHINE_TYPE);
351
 
  if (version)
352
 
    return;
353
 
  puts("Copyright (C) 2008 Sun Microsystems, Inc.");
354
 
  puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,\n\
355
 
and you are welcome to modify and redistribute it under the GPL license\n");
356
 
  puts("This program generates a perfect hashing function for the sql_lex.cc");
357
 
  printf("Usage: %s [OPTIONS]\n\n", my_progname);
358
 
  my_print_help(my_long_options);
359
 
}
360
 
 
361
 
 
362
 
extern "C" bool
363
 
get_one_option(int optid, const struct my_option *opt __attribute__((unused)),
364
 
               char *argument __attribute__((unused)))
365
 
{
366
 
  switch(optid) {
367
 
  case 'V':
368
 
    usage(1);
369
 
    exit(0);
370
 
  case 'I':
371
 
  case '?':
372
 
    usage(0);
373
 
    exit(0);
374
 
  }
375
 
  return 0;
376
 
}
377
 
 
378
 
 
379
 
static int get_options(int argc, char **argv)
380
 
{
381
 
  int ho_error;
382
 
 
383
 
  if ((ho_error= handle_options(&argc, &argv, my_long_options, get_one_option)))
384
 
    exit(ho_error);
385
 
 
386
 
  if (argc >= 1)
387
 
  {
388
 
    usage(0);
389
 
     exit(1);
390
 
  }
391
 
  return(0);
392
 
}
393
 
 
394
 
 
395
 
int check_dup_symbols(SYMBOL *s1, SYMBOL *s2)
396
 
{
397
 
  if (s1->length!=s2->length || strncmp(s1->name,s2->name,s1->length))
398
 
    return 0;
399
 
 
400
 
  const char *err_tmpl= "\ngen_lex_hash fatal error : \
401
 
Unfortunately gen_lex_hash can not generate a hash,\n since \
402
 
your lex.h has duplicate definition for a symbol \"%s\"\n\n";
403
 
  printf (err_tmpl,s1->name);
404
 
  fprintf (stderr,err_tmpl,s1->name);
405
 
 
406
 
  return 1;
407
 
}
408
 
 
409
 
 
410
 
int check_duplicates()
411
 
{
412
 
  SYMBOL *cur1, *cur2, *s_end, *f_end;
413
 
 
414
 
  s_end= symbols + array_elements(symbols);
415
 
  f_end= sql_functions + array_elements(sql_functions);
416
 
 
417
 
  for (cur1= symbols; cur1<s_end; cur1++)
418
 
  {
419
 
    for (cur2= cur1+1; cur2<s_end; cur2++)
420
 
    {
421
 
      if (check_dup_symbols(cur1,cur2))
422
 
        return 1;
423
 
    }
424
 
    for (cur2= sql_functions; cur2<f_end; cur2++)
425
 
    {
426
 
      if (check_dup_symbols(cur1,cur2))
427
 
        return 1;
428
 
    }
429
 
  }
430
 
 
431
 
  for (cur1= sql_functions; cur1<f_end; cur1++)
432
 
  {
433
 
    for (cur2= cur1+1; cur2< f_end; cur2++)
434
 
    {
435
 
      if (check_dup_symbols(cur1,cur2))
436
 
        return 1;
437
 
    }
438
 
  }
439
 
  return 0;
440
 
}
441
 
 
442
 
 
443
 
int main(int argc,char **argv)
444
 
{
445
 
  MY_INIT(argv[0]);
446
 
 
447
 
  if (get_options(argc,(char **) argv))
448
 
    exit(1);
449
 
 
450
 
  /* Broken up to indicate that it's not advice to you, gentle reader. */
451
 
  printf("/*\n\n  Do " "not " "edit " "this " "file " "directly!\n\n*/\n");
452
 
 
453
 
  printf("/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*- \n"
454
 
         " *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab: \n"
455
 
         " * \n"
456
 
         " *  Copyright (C) 2008 Sun Microsystems \n"
457
 
         " * \n"
458
 
         " *  This program is free software; you can redistribute it and/or modify \n"
459
 
         " *  it under the terms of the GNU General Public License as published by \n"
460
 
         " *  the Free Software Foundation; version 2 of the License. \n"
461
 
         " * \n"
462
 
         " *  This program is distributed in the hope that it will be useful, \n"
463
 
         " *  but WITHOUT ANY WARRANTY; without even the implied warranty of \n"
464
 
         " *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the \n"
465
 
         " *  GNU General Public License for more details. \n"
466
 
         " * \n"
467
 
         " *  You should have received a copy of the GNU General Public License \n"
468
 
         " *  along with this program; if not, write to the Free Software \n"
469
 
         " *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA \n"
470
 
         " */\n");
471
 
 
472
 
  /* Broken up to indicate that it's not advice to you, gentle reader. */
473
 
  printf("/* Do " "not " "edit " "this " "file!  This is generated by "
474
 
         "gen_lex_hash.cc\nthat seeks for a perfect hash function */\n\n");
475
 
  printf("#include \"lex.h\"\n\n");
476
 
 
477
 
  calc_length();
478
 
 
479
 
  if (check_duplicates())
480
 
    exit(1);
481
 
 
482
 
  generate_find_structs();
483
 
  print_find_structs();
484
 
 
485
 
  printf("\nstatic unsigned int sql_functions_max_len=%d;\n", max_len);
486
 
  printf("\nstatic unsigned int symbols_max_len=%d;\n\n", max_len2);
487
 
 
488
 
  printf("\
489
 
static SYMBOL *get_hash_symbol(const char *s,\n\
490
 
                               unsigned int len,bool function)\n\
491
 
{\n\
492
 
  register unsigned char *hash_map;\n\
493
 
  register const char *cur_str= s;\n\
494
 
\n\
495
 
  if (len == 0) {\n\
496
 
    return(NULL);\n\
497
 
  }\n"
498
 
);
499
 
 
500
 
  printf("\
501
 
  if (function){\n\
502
 
    if (len>sql_functions_max_len) return 0;\n\
503
 
    hash_map= sql_functions_map;\n\
504
 
    register uint32_t cur_struct= uint4korr(hash_map+((len-1)*4));\n\
505
 
\n\
506
 
    for (;;){\n\
507
 
      register unsigned char first_char= (unsigned char)cur_struct;\n\
508
 
\n\
509
 
      if (first_char == 0)\n\
510
 
      {\n\
511
 
        register int16_t ires= (int16_t)(cur_struct>>16);\n\
512
 
        if (ires==array_elements(symbols)) return 0;\n\
513
 
        register SYMBOL *res;\n\
514
 
        if (ires>=0) \n\
515
 
          res= symbols+ires;\n\
516
 
        else\n\
517
 
          res= sql_functions-ires-1;\n\
518
 
        register uint32_t count= cur_str-s;\n\
519
 
        return lex_casecmp(cur_str,res->name+count,len-count) ? 0 : res;\n\
520
 
      }\n\
521
 
\n\
522
 
      register unsigned char cur_char= (unsigned char)to_upper_lex[(unsigned char)*cur_str];\n\
523
 
      if (cur_char<first_char) return 0;\n\
524
 
      cur_struct>>=8;\n\
525
 
      if (cur_char>(unsigned char)cur_struct) return 0;\n\
526
 
\n\
527
 
      cur_struct>>=8;\n\
528
 
      cur_struct= uint4korr(hash_map+\n\
529
 
                        (((uint16_t)cur_struct + cur_char - first_char)*4));\n\
530
 
      cur_str++;\n\
531
 
    }\n"
532
 
);
533
 
 
534
 
  printf("\
535
 
  }else{\n\
536
 
    if (len>symbols_max_len) return 0;\n\
537
 
    hash_map= symbols_map;\n\
538
 
    register uint32_t cur_struct= uint4korr(hash_map+((len-1)*4));\n\
539
 
\n\
540
 
    for (;;){\n\
541
 
      register unsigned char first_char= (unsigned char)cur_struct;\n\
542
 
\n\
543
 
      if (first_char==0){\n\
544
 
        register int16_t ires= (int16_t)(cur_struct>>16);\n\
545
 
        if (ires==array_elements(symbols)) return 0;\n\
546
 
        register SYMBOL *res= symbols+ires;\n\
547
 
        register uint32_t count= cur_str-s;\n\
548
 
        return lex_casecmp(cur_str,res->name+count,len-count)!=0 ? 0 : res;\n\
549
 
      }\n\
550
 
\n\
551
 
      register unsigned char cur_char= (unsigned char)to_upper_lex[(unsigned char)*cur_str];\n\
552
 
      if (cur_char<first_char) return 0;\n\
553
 
      cur_struct>>=8;\n\
554
 
      if (cur_char>(unsigned char)cur_struct) return 0;\n\
555
 
\n\
556
 
      cur_struct>>=8;\n\
557
 
      cur_struct= uint4korr(hash_map+\n\
558
 
                        (((uint16_t)cur_struct + cur_char - first_char)*4));\n\
559
 
      cur_str++;\n\
560
 
    }\n\
561
 
  }\n\
562
 
}\n"
563
 
);
564
 
  my_end(0);
565
 
  exit(0);
566
 
}
567