← 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: 2008-10-06 06:47:29 UTC
  • Revision ID: brian@tangent.org-20081006064729-2i9mhjkzyvow9xsm
Remove uint.

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