home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / sql / gen_lex_hash.cpp < prev    next >
C/C++ Source or Header  |  2000-09-07  |  16KB  |  568 lines
  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. #define NO_YACC_SYMBOLS
  19. #include <global.h>
  20. #include <my_sys.h>
  21. #include <m_string.h>
  22. #ifndef __GNU_LIBRARY__
  23. #define __GNU_LIBRARY__                // Skipp warnings in getopt.h
  24. #endif
  25. #include <getopt.h>
  26. #include "mysql_version.h"
  27. #include "lex.h"
  28.  
  29. bool opt_search=0,opt_verbose=0;
  30. ulong opt_count=100000;
  31.  
  32. #define max_allowed_array  8000    // Don't generate bigger arrays than this
  33. #define max_symbol      32767    // Use this for 'not found'
  34. #define how_much_for_plus  8    // 2-8
  35. #define type_count       1    // 1-5
  36. #define char_table_count   5
  37. #define total_symbols  (sizeof(symbols)/sizeof(SYMBOL) +\
  38.             sizeof(sql_functions)/sizeof(SYMBOL))
  39.  
  40. #define how_much_and INT_MAX24
  41.  
  42. /*
  43.   The following only have to work with characters in the set
  44.   used by SQL commands
  45. */
  46.  
  47. #undef tolower
  48. #define tolower(a) ((a) >= 'A' && (a) <= 'Z') ? ((a)- 'A' + 'a') : (a)
  49.  
  50. static uint how_long_symbols,function_plus,function_mod,function_type;
  51. static uint char_table[256];
  52. static uchar unique_length[256];
  53. static uchar bits[how_much_and/8+1];
  54. static uint primes[max_allowed_array+1];
  55. static ulong hash_results[type_count][how_much_for_plus+1][total_symbols];
  56. static ulong start_value=0;
  57.  
  58. struct rand_struct {
  59.   unsigned long seed1,seed2,max_value;
  60.   double max_value_dbl;
  61. };
  62.  
  63. void randominit(struct rand_struct *rand_st,ulong seed1, ulong seed2)
  64. {                        /* For mysql 3.21.# */
  65.   rand_st->max_value= 0x3FFFFFFFL;
  66.   rand_st->max_value_dbl=(double) rand_st->max_value;
  67.   rand_st->seed1=seed1%rand_st->max_value ;
  68.   rand_st->seed2=seed2%rand_st->max_value;
  69. }
  70.  
  71. double rnd(struct rand_struct *rand_st)
  72. {
  73.   rand_st->seed1=(rand_st->seed1*3+rand_st->seed2) % rand_st->max_value;
  74.   rand_st->seed2=(rand_st->seed1+rand_st->seed2+33) % rand_st->max_value;
  75.   return (((double) rand_st->seed1)/rand_st->max_value_dbl);
  76. }
  77.  
  78.  
  79. static void make_char_table(ulong t1,ulong t2,int type)
  80. {
  81.   uint i;
  82.   struct rand_struct rand_st;
  83.   randominit(&rand_st,t1,t2);
  84.  
  85.   for (i=0 ; i < 256 ; i++)
  86.   {
  87.     switch (type) {
  88.     case 0: char_table[i]= i + (i << 8);        break;
  89.     case 1: char_table[i]= i + ((i ^255 ) << 8);    break;
  90.     case 2: char_table[i]= i;                break;
  91.     case 3: char_table[i]= i + ((uint) (rnd(&rand_st)*255) << 8); break;
  92.     case 4: char_table[i]= (uint) (rnd(&rand_st)*255) + (i << 8); break;
  93.     }
  94.   }
  95.   char_table[0]|=1+257;                // Avoid problems with 0
  96.   for (i=0 ; i < 256 ; i++)
  97.   {
  98.     uint tmp=(uint) (rnd(&rand_st)*255);
  99.     swap(uint,char_table[i],char_table[tmp]);
  100.   }
  101.   /* lower characters should be mapped to upper */
  102.   for (i= 'a' ; i <= 'z' ; i++)
  103.   {
  104.     /* This loop is coded with extra variables to avoid a bug in gcc 2.96 */
  105.     uchar tmp= (uchar) (i - 'a');    // Assume ascii
  106.     tmp+='A';
  107.     char_table[i]=char_table[tmp];
  108.   }
  109. }
  110.  
  111. /* Fill array primes with primes between start and 'max_allowed_array' */
  112.  
  113. static void make_prime_array(uint start)
  114. {
  115.   uint i,j,*to;
  116.   uint max_index=(uint) sqrt((double) max_allowed_array);
  117.  
  118.   bzero((char*) primes,sizeof(primes[0])*max_allowed_array);
  119.  
  120.   i=2;
  121.   while (i < max_index)
  122.   {
  123.     for (j=i+i ; j <= max_allowed_array ; j+=i)
  124.       primes[j]=1;
  125.     while (primes[++i]) ;
  126.   }
  127.  
  128.   to=primes;
  129.   for (i=start ; i <= max_allowed_array ; i++)
  130.     if (!primes[i])
  131.       *to++=i;
  132.   *to=0;                    // end marker
  133. }
  134.  
  135. #define USE_char_table
  136.  
  137. static ulong tab_index_function(const char *s,uint add, uint type)
  138. {
  139.   register ulong nr=start_value+char_table[(uchar) *s]; // Nice value
  140.   ulong pos=3;
  141.   uint tmp_length=unique_length[(uchar) *s]-1;
  142.   while (*++s && tmp_length-- > 0)
  143.   {
  144.     switch (type) {
  145.     case 0:
  146.       nr= (nr ^ (char_table[(uchar) *s] + (nr << add)));
  147.       break;
  148.     case 1:
  149.       nr= (nr + (char_table[(uchar) *s] + (nr << add)));
  150.       break;
  151.     case 2:
  152.       nr= (nr ^ (char_table[(uchar) *s] ^ (nr << add)));
  153.       break;
  154.     case 3:
  155.       nr= (char_table[(uchar) *s] ^ (nr << add));
  156.       break;
  157.     case 4:
  158.       nr+= nr+nr+((nr & 63)+pos)*((ulong) char_table[(uchar) *s]);
  159.       pos+=add;
  160.       break;
  161.     }
  162.   }
  163.   return nr & INT_MAX24;
  164. }
  165.  
  166. static int search(bool write_warning)
  167. {
  168.   uint size_symbols = sizeof(symbols)/sizeof(SYMBOL);
  169.   uint size_functions = sizeof(sql_functions)/sizeof(SYMBOL);
  170.   uint size=size_symbols + size_functions;
  171.   uint i=0,found,*prime,type;
  172.   int igra[max_allowed_array],test_count=INT_MAX;
  173.   uint possible_plus[how_much_for_plus*type_count+type_count];
  174.  
  175.   how_long_symbols = sizeof(symbols)/sizeof(SYMBOL);
  176.  
  177.   bzero((char*) possible_plus,sizeof(possible_plus));
  178.   found=0;
  179.  
  180.   /* Check first which function_plus are possible */
  181.   for (type=0 ; type < type_count ; type ++)
  182.   {
  183.     for (function_plus = 1;
  184.      function_plus <= how_much_for_plus;
  185.      function_plus++)
  186.     {
  187.       bzero((char*) bits,sizeof(bits));
  188.       for (i=0; i < size; i++)
  189.       {
  190.     ulong order= tab_index_function ((i < how_long_symbols) ?
  191.                      symbols[i].name :
  192.                      sql_functions[i-how_long_symbols].name,
  193.                      function_plus, type);
  194.     hash_results[type][function_plus][i]=order;
  195.     uint pos=order/8;
  196.     uint bit=order & 7;
  197.     if (bits[pos] & (1 << bit))
  198.       break;
  199.     bits[pos]|=1 << bit;
  200.       }
  201.       if (i == size)
  202.       {
  203.     possible_plus[found++]=function_plus;
  204.       }
  205.     }
  206.     possible_plus[found++]=0;            // End marker
  207.   }
  208.   if (found == type_count)
  209.   {
  210.     if (write_warning)
  211.       fprintf(stderr,"\
  212. The hash function didn't return a unique value for any parameter\n\
  213. You have to change gen_lex_code.cc, function 'tab_index_function' to\n\
  214. generate unique values for some parameter.  When you have succeeded in this,\n\
  215. you have to change 'main' to print out the new function\n");
  216.     return(1);
  217.   }
  218.  
  219.   if (opt_verbose)
  220.     fprintf (stderr,"Info: Possible add values: %d\n",found-type_count);
  221.  
  222.   for (prime=primes; (function_mod=*prime) ; prime++)
  223.   {
  224.     uint *plus_ptr=possible_plus;
  225.     for (type=0 ; type < type_count ; type++ )
  226.     {
  227.       while ((function_plus= *plus_ptr++))
  228.       {
  229.     ulong *order_pos= &hash_results[type][function_plus][0];
  230.     if (test_count++ == INT_MAX)
  231.     {
  232.       test_count=1;
  233.       bzero((char*) igra,sizeof(igra));
  234.     }
  235.     for (i=0; i<size ;i++)
  236.     {
  237.       ulong order;
  238.       order = *order_pos++ % function_mod;
  239.       if (igra[order] == test_count)
  240.         break;
  241.       igra[order] = test_count;
  242.     }
  243.     if (i == size)
  244.     {
  245.       *prime=0;                // Mark this used
  246.       function_type=type;
  247.       return 0;                // Found ok value
  248.     }
  249.       }
  250.     }
  251.   }
  252.  
  253.   function_mod=max_allowed_array;
  254.   if (write_warning)
  255.     fprintf (stderr,"Fatal error when generating hash for symbols\n\
  256. Didn't find suitable values for perfect hashing:\n\
  257. You have to edit gen_lex_hase.cc to generate a new hashing function.\n\
  258. You can try running gen_lex_hash with --search to find a suitable value\n\
  259. Symbol array size = %d\n",function_mod);
  260.   return -1;
  261. }
  262.  
  263.  
  264. void print_arrays()
  265. {
  266.   uint size_symbols = sizeof(symbols)/sizeof(SYMBOL);
  267.   uint size_functions = sizeof(sql_functions)/sizeof(SYMBOL);
  268.   uint size=size_symbols + size_functions;
  269.   uint i;
  270.  
  271.   fprintf(stderr,"Symbols: %d  Functions: %d;  Total: %d\nShifts per char: %d,  Array size: %d\n",
  272.       size_symbols,size_functions,size_symbols+size_functions,
  273.       function_plus,function_mod);
  274.  
  275.   int *prva= (int*) my_alloca(sizeof(int)*function_mod);
  276.   for (i=0 ; i <= function_mod; i++)
  277.     prva[i]= max_symbol;
  278.  
  279.   for (i=0;i<size;i++)
  280.   {
  281.     ulong order = tab_index_function ((i < how_long_symbols) ? symbols[i].name : sql_functions[i - how_long_symbols].name,function_plus,function_type);
  282.     order %= function_mod;
  283.     prva [order] = i;
  284.   }
  285.  
  286. #ifdef USE_char_table
  287.   printf("static uint16 char_table[] = {\n");
  288.   for (i=0; i < 255 ;i++)            // < 255 is correct
  289.   {
  290.     printf("%u,",char_table[i]);
  291.     if (((i+1) & 15) == 0)
  292.       puts("");
  293.   }
  294.   printf("%d\n};\n\n\n",char_table[i]);
  295. #endif
  296.  
  297.   printf("static uchar unique_length[] = {\n");
  298.   for (i=0; i < 255 ;i++)            // < 255 is correct
  299.   {
  300.     printf("%u,",unique_length[i]);
  301.     if (((i+1) & 15) == 0)
  302.       puts("");
  303.   }
  304.   printf("%d\n};\n\n\n",unique_length[i]);
  305.  
  306.   printf("static uint16 my_function_table[] = {\n");
  307.   for (i=0; i < function_mod-1 ;i++)
  308.   {
  309.     printf("%d,",prva[i]);
  310.     if (((i+1) % 12) == 0)
  311.       puts("");
  312.   }
  313.   printf("%d\n};\n\n\n",prva[i]);
  314.   my_afree((gptr) prva);
  315. }
  316.  
  317.  
  318. static struct option long_options[] =
  319. {
  320.   {"count",        required_argument,       0, 'c'},
  321.   {"search",        no_argument,       0, 'S'},
  322.   {"verbose",        no_argument,       0, 'v'},
  323.   {"version",        no_argument,       0, 'V'},
  324.   {"rnd1",        required_argument,       0, 'r'},
  325.   {"rnd2",        required_argument,       0, 'R'},
  326.   {"type",        required_argument,       0, 't'},
  327.   {0, 0, 0, 0}
  328. };
  329.  
  330.  
  331. static void usage(int version)
  332. {
  333.   printf("%s  Ver 3.1 Distrib %s, for %s (%s)\n",
  334.      my_progname, MYSQL_SERVER_VERSION, SYSTEM_TYPE, MACHINE_TYPE);
  335.   if (version)
  336.     return;
  337.   puts("Copyright (C) 2000 MySQL AB & MySQL Finland AB, by Sinisa and Monty");
  338.   puts("This software comes with ABSOLUTELY NO WARRANTY. This is free software,\nand you are welcome to modify and redistribute it under the GPL license\n");
  339.   puts("This program generates a perfect hashing function for the sql_lex.cc");
  340.   printf("Usage: %s [OPTIONS]\n", my_progname);
  341.   printf("\n\
  342. -c, --count=#        Try count times to find a optimal hash table\n\
  343. -r, --rnd1=#        Set 1 part of rnd value for hash generator\n\
  344. -R, --rnd2=#        Set 2 part of rnd value for hash generator\n\
  345. -t, --type=#        Set type of char table to generate\n\
  346. -S, --search        Search after good rnd1 and rnd2 values\n\
  347. -v, --verbose        Write some information while the program executes\n\
  348. -V, --version        Output version information and exit\n");
  349.  
  350. }
  351.  
  352. static uint best_type;
  353. static ulong best_t1,best_t2;
  354.  
  355. static int get_options(int argc, char **argv)
  356. {
  357.   int c,option_index=0;
  358.  
  359.   while ((c=getopt_long(argc,argv,"?SvVc:r:R:t:",
  360.             long_options, &option_index)) != EOF)
  361.   {
  362.     switch(c) {
  363.     case 'c':
  364.       opt_count=atol(optarg);
  365.       break;
  366.     case 'r':
  367.       best_t1=atol(optarg);
  368.       break;
  369.     case 'R':
  370.       best_t2=atol(optarg);
  371.       break;
  372.     case 't':
  373.       best_type=atoi(optarg);
  374.       break;
  375.     case 'S':
  376.       opt_search=1;
  377.       break;
  378.     case 'v':
  379.       opt_verbose=1;
  380.       break;
  381.     case 'V': usage(1); exit(0);
  382.     case 'I':
  383.     case '?':
  384.       usage(0);
  385.       exit(0);
  386.     default:
  387.       fprintf(stderr,"illegal option: -%c\n",opterr);
  388.       usage(0);
  389.       exit(1);
  390.     }
  391.   }
  392.   argc-=optind;
  393.   argv+=optind;
  394.   if (argc >= 1)
  395.   {
  396.     usage(0);
  397.      exit(1);
  398.   }
  399.   return(0);
  400. }
  401.  
  402. static uint max_prefix(const char *name)
  403. {
  404.   uint i;
  405.   uint max_length=1;
  406.   for (i=0 ; i < sizeof(symbols)/sizeof(SYMBOL) ; i++)
  407.   {
  408.     const char *str=symbols[i].name;
  409.     if (str != name)
  410.     {
  411.       const char *str2=name;
  412.       uint length;
  413.       while (*str && *str == *str2)
  414.       {
  415.     str++;
  416.     str2++;
  417.       }
  418.       length=(uint) (str2 - name)+1;
  419.       if (length > max_length)
  420.     max_length=length;
  421.     }
  422.   }
  423.   for (i=0 ; i < sizeof(sql_functions)/sizeof(SYMBOL) ; i++)
  424.   {
  425.     const char *str=sql_functions[i].name;
  426.     if (str != name)
  427.     {
  428.       const char *str2=name;
  429.       uint length;
  430.       while (*str && *str == *str2)
  431.       {
  432.     str++;
  433.     str2++;
  434.       }
  435.       length=(uint) (str2 - name)+1;
  436.       if (length > max_length)
  437.     max_length=length;
  438.     }
  439.   }
  440.   return max_length;
  441. }
  442.  
  443.  
  444. static void make_max_length_table(void)
  445. {
  446.   uint i;
  447.   for (i=0 ; i < sizeof(symbols)/sizeof(SYMBOL) ; i++)
  448.   {
  449.     uint length=max_prefix(symbols[i].name);
  450.     if (length > unique_length[(uchar) symbols[i].name[0]])
  451.     {
  452.       unique_length[(uchar) symbols[i].name[0]]=length;
  453.       unique_length[(uchar) tolower(symbols[i].name[0])]=length;
  454.     }
  455.   }
  456.   for (i=0 ; i < sizeof(sql_functions)/sizeof(SYMBOL) ; i++)
  457.   {
  458.     uint length=max_prefix(sql_functions[i].name);
  459.     if (length > unique_length[(uchar) sql_functions[i].name[0]])
  460.     {
  461.       unique_length[(uchar) sql_functions[i].name[0]]=length;
  462.       unique_length[(uchar) tolower(sql_functions[i].name[0])]=length;
  463.     }
  464.   }
  465. }
  466.  
  467.  
  468. int main(int argc,char **argv)
  469. {
  470.   struct rand_struct rand_st;
  471.   static uint best_mod,best_add,best_functype;
  472.   int error;
  473.  
  474.   MY_INIT(argv[0]);
  475.   start_value=2610463L; best_t1=8358376L;  best_t2=860646L;  best_type=2; /* mode=4111  add=8  func_type: 0 */
  476.   if (get_options(argc,(char **) argv))
  477.     exit(1);
  478.  
  479.   make_max_length_table();
  480.   make_char_table(best_t1,best_t2,best_type);
  481.   make_prime_array(sizeof(symbols)/sizeof(SYMBOL) +
  482.            sizeof(sql_functions)/sizeof(SYMBOL));
  483.  
  484.   if ((error=search(1)) > 0 || error && !opt_search)
  485.     exit(1);                    // This should work
  486.   best_mod=function_mod; best_add=function_plus; best_functype=function_type;
  487.  
  488.   if (opt_search)
  489.   {
  490.     time_t start_time=time((time_t*) 0);
  491.     randominit(&rand_st,start_time,start_time/2); // Some random values
  492.     printf("start_value=%ldL;  best_t1=%ldL;  best_t2=%ldL;  best_type=%d; /* mode=%d  add=%d type: %d */\n",
  493.        start_value, best_t1,best_t2,best_type,best_mod,best_add,
  494.        best_functype);
  495.  
  496.     for (uint i=1 ; i <= opt_count ; i++)
  497.     {
  498.       if (i % 10 == 0)
  499.       {
  500.     putchar('.');
  501.     fflush(stdout);
  502.       }
  503.       ulong t1=(ulong) (rnd(&rand_st)*INT_MAX24);
  504.       ulong t2=(ulong) (rnd(&rand_st)*INT_MAX24);
  505.       uint type=(int) (rnd(&rand_st)*char_table_count);
  506.       start_value=(ulong) (rnd(&rand_st)*INT_MAX24);
  507.       make_char_table(t1,t2,type);
  508.       if (!search(0))
  509.       {
  510.     best_mod=function_mod; best_add=function_plus;
  511.     best_functype=function_type;
  512.     best_t1=t1; best_t2=t2; best_type=type;
  513.     printf("\nstart_value=%ldL; best_t1=%ldL;  best_t2=%ldL;  best_type=%d; /* mode=%d  add=%d  func_type: %d */\n",
  514.            start_value,best_t1,best_t2,best_type,best_mod,best_add,best_functype);
  515.       }
  516.     }
  517.   }
  518.  
  519.   function_mod=best_mod; function_plus=best_add;
  520.   make_char_table(best_t1,best_t2,best_type);
  521.  
  522.   printf("/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB\n\
  523.    This program is free software; you can redistribute it and/or modify\n\
  524.    it under the terms of the GNU General Public License as published by\n\
  525.    the Free Software Foundation; either version 2 of the License, or\n\
  526.    (at your option) any later version.\n\n\
  527.    This program is distributed in the hope that it will be useful,\n\
  528.    but WITHOUT ANY WARRANTY; without even the implied warranty of\n\
  529.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\n\
  530.    GNU General Public License for more details.\n\n\
  531.    You should have received a copy of the GNU General Public License\n\
  532.    along with this program; if not, write to the Free Software\n\
  533.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */\n\n");
  534.  
  535. printf("/* This code is generated by gen_lex_hash.cc that seeks for a perfect\nhash function */\n\n");
  536.   printf("#include \"lex.h\"\n\n");
  537.  
  538.   print_arrays();
  539.  
  540.   printf("/* start_value=%ldL;  best_t1=%ldL;  best_t2=%ldL;  best_type=%d; */ /* mode=%d  add=%d type: %d */\n\n",
  541.      start_value, best_t1, best_t2,best_type,
  542.      best_mod, best_add, best_functype);
  543.  
  544.   printf("inline SYMBOL *get_hash_symbol(const char *s,unsigned int length,bool function)\n\
  545. {\n\
  546.   ulong idx = %lu+char_table[(uchar) *s];\n\
  547.   SYMBOL *sim;\n\
  548.   const char *start=s;\n\
  549.   int i=unique_length[(uchar) *s++];\n\
  550.   if (i > (int) length) i=(int) length;\n\
  551.   while (--i > 0)\n\
  552.     idx= (idx ^ (char_table[(uchar) *s++] + (idx << %d)));\n\
  553.   idx=my_function_table[(idx & %d) %% %d];\n\
  554.   if (idx >= %d)\n\
  555.   {\n\
  556.     if (!function || idx >= %d) return (SYMBOL*) 0;\n\
  557.     sim=sql_functions + (idx - %d);\n\
  558.   }\n\
  559.   else\n\
  560.     sim=symbols + idx;\n\
  561.   if ((length != sim->length) || lex_casecmp(start,sim->name,length))\n\
  562.     return  (SYMBOL *)0;\n\
  563.   return sim;\n\
  564. }\n",(ulong) start_value,(int) function_plus,(int) how_much_and,function_mod,how_long_symbols,max_symbol,how_long_symbols);
  565.   exit(0);
  566.   return 0;
  567. }
  568.