percona-server-5.6.51-91.0/sql/gen_lex_hash.cc

/*
   Copyright (c) 2000, 2016, Oracle and/or its affiliates. All rights reserved.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License, version 2.0,
   as published by the Free Software Foundation.

   This program is also distributed with certain software (including
   but not limited to OpenSSL) that is licensed under separate terms,
   as designated in a particular file or component or in included license
   documentation.  The authors of MySQL hereby grant you an additional
   permission to link the program and your derivative works with the
   separately licensed software that they have included with MySQL.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License, version 2.0, for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software Foundation,
   51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA */

/**
  @file

  @details
@verbatim
The idea of presented algorithm see in
"The Art of Computer Programming" by Donald E. Knuth
Volume 3 "Sorting and searching"
(chapter 6.3 "Digital searching" - name and number of chapter
   is back translation from Russian edition :))

as illustration of data structures, imagine next table:

static SYMBOL symbols[] = {
  { "ADD",              SYM(ADD),0,0},
  { "AND",              SYM(AND),0,0},
  { "DAY",              SYM(DAY_SYM),0,0},
};

for this structure, presented program generate next searching-structure:

+-----------+-+-+-+
|       len |1|2|3|
+-----------+-+-+-+
|first_char |0|0|a|
|last_char  |0|0|d|
|link       |0|0|+|
                 |
                 V
       +----------+-+-+-+--+
       |    1 char|a|b|c|d |
       +----------+-+-+-+--+
       |first_char|d|0|0|0 |
       |last_char |n|0|0|-1|
       |link      |+|0|0|+ |
                   |     |
                   |     V
                   |  symbols[2] ( "DAY" )
                   V
+----------+--+-+-+-+-+-+-+-+-+-+--+
|    2 char|d |e|f|j|h|i|j|k|l|m|n |
+----------+--+-+-+-+-+-+-+-+-+-+--+
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
|link      |+ |0|0|0|0|0|0|0|0|0|+ |
            |                    |
            V                    V
         symbols[0] ( "ADD" )  symbols[1] ( "AND" )

for optimization, link is the 16-bit index in 'symbols' or 'sql_functions'
or search-array..

So, we can read full search-structure as 32-bit word
@endverbatim

@todo
    use instead to_upper_lex, special array
    (substitute chars) without skip codes..
@todo
    try use reverse order of comparing..

*/

#define NO_YACC_SYMBOLS
#include <my_global.h>
#include "mysql_version.h"
#include "lex.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include <welcome_copyright_notice.h> /* ORACLE_WELCOME_COPYRIGHT_NOTICE */

struct hash_lex_struct
{
  int first_char;
  char last_char;
  union{
    hash_lex_struct *char_tails;
    int iresult;
  };
  int ithis;
};

hash_lex_struct *get_hash_struct_by_len(hash_lex_struct **root_by_len,
					    int len, int *max_len)
{
  if (*max_len<len){
    *root_by_len= (hash_lex_struct *)realloc((char*)*root_by_len,
                                             sizeof(hash_lex_struct)*len);
    hash_lex_struct *cur, *end= *root_by_len + len;
    for (cur= *root_by_len + *max_len; cur<end; cur++)
      cur->first_char= 0;
    *max_len= len;
  }
  return (*root_by_len)+(len-1);
}

void insert_into_hash(hash_lex_struct *root, const char *name,
		      int len_from_begin, int index, int function)
{
  hash_lex_struct *end, *cur, *tails;

  if (!root->first_char)
  {
    root->first_char= -1;
    root->iresult= index;
    return;
  }

  if (root->first_char == -1)
  {
    int index2= root->iresult;
    const char *name2= (index2 < 0 ? sql_functions[-index2-1] :
			symbols[index2]).name + len_from_begin;
    root->first_char= (int) (uchar) name2[0];
    root->last_char= (char) root->first_char;
    tails= (hash_lex_struct*)malloc(sizeof(hash_lex_struct));
    root->char_tails= tails;
    tails->first_char= -1;
    tails->iresult= index2;
  }

  size_t real_size= (root->last_char-root->first_char+1);

  if (root->first_char>(*name))
  {
    size_t new_size= root->last_char-(*name)+1;
    if (new_size<real_size) printf("error!!!!\n");
    tails= root->char_tails;
    tails= (hash_lex_struct*)realloc((char*)tails,
				       sizeof(hash_lex_struct)*new_size);
    root->char_tails= tails;
    memmove(tails+(new_size-real_size),tails,real_size*sizeof(hash_lex_struct));
    end= tails + new_size - real_size;
    for (cur= tails; cur<end; cur++)
      cur->first_char= 0;
    root->first_char= (int) (uchar) *name;
  }

  if (root->last_char<(*name))
  {
    size_t new_size= (*name)-root->first_char+1;
    if (new_size<real_size) printf("error!!!!\n");
    tails= root->char_tails;
    tails= (hash_lex_struct*)realloc((char*)tails,
				    sizeof(hash_lex_struct)*new_size);
    root->char_tails= tails;
    end= tails + new_size;
    for (cur= tails+real_size; cur<end; cur++)
      cur->first_char= 0;
    root->last_char= (*name);
  }

  insert_into_hash(root->char_tails+(*name)-root->first_char,
		   name+1,len_from_begin+1,index,function);
}


hash_lex_struct *root_by_len= 0;
int max_len=0;

hash_lex_struct *root_by_len2= 0;
int max_len2=0;

void insert_symbols()
{
  size_t i= 0;
  SYMBOL *cur;
  for (cur= symbols; i<array_elements(symbols); cur++, i++){
    hash_lex_struct *root=
      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
    insert_into_hash(root,cur->name,0,(uint) i,0);
  }
}

void insert_sql_functions()
{
  int i= 0;
  SYMBOL *cur;
  for (cur= sql_functions; i < (int) array_elements(sql_functions); cur++, i++)
  {
    hash_lex_struct *root=
      get_hash_struct_by_len(&root_by_len,cur->length,&max_len);
    insert_into_hash(root,cur->name,0,-i-1,1);
  }
}

void calc_length()
{
  SYMBOL *cur, *end= symbols + array_elements(symbols);
  for (cur= symbols; cur < end; cur++)
    cur->length=(uchar) strlen(cur->name);
  end= sql_functions + array_elements(sql_functions);
  for (cur= sql_functions; cur<end; cur++)
    cur->length=(uchar) strlen(cur->name);
}

void generate_find_structs()
{
  root_by_len= 0;
  max_len=0;

  insert_symbols();

  root_by_len2= root_by_len;
  max_len2= max_len;

  root_by_len= 0;
  max_len= 0;

  insert_symbols();
  insert_sql_functions();
}

struct hash_map_cleanup
{
  hash_map_cleanup(char **buffer, int *sz)
    : m_buffer(buffer), m_sz(sz)
  {}
  ~hash_map_cleanup()
  {
    free(*m_buffer);
    *m_buffer= NULL;
    *m_sz= 0;
  }
  char **m_buffer;
  int   *m_sz;
};

char *hash_map= 0;
int size_hash_map= 0;

void add_struct_to_map(hash_lex_struct *st)
{
  st->ithis= size_hash_map/4;
  size_hash_map+= 4;
  hash_map= (char*)realloc((char*)hash_map,size_hash_map);
  hash_map[size_hash_map-4]= (char) (st->first_char == -1 ? 0 :
				     st->first_char);
  hash_map[size_hash_map-3]= (char) (st->first_char == -1 ||
				     st->first_char == 0 ? 0 : st->last_char);
  if (st->first_char == -1)
  {
    hash_map[size_hash_map-2]= ((unsigned int)(int16)st->iresult)&255;
    hash_map[size_hash_map-1]= ((unsigned int)(int16)st->iresult)>>8;
  }
  else if (st->first_char == 0)
  {
    hash_map[size_hash_map-2]= ((unsigned int)(int16)array_elements(symbols))&255;
    hash_map[size_hash_map-1]= ((unsigned int)(int16)array_elements(symbols))>>8;
  }
}


void add_structs_to_map(hash_lex_struct *st, int len)
{
  hash_lex_struct *cur, *end= st+len;
  for (cur= st; cur<end; cur++)
    add_struct_to_map(cur);
  for (cur= st; cur<end; cur++)
  {
    if (cur->first_char && cur->first_char != -1)
      add_structs_to_map(cur->char_tails,cur->last_char-cur->first_char+1);
  }
}

void set_links(hash_lex_struct *st, int len)
{
  hash_lex_struct *cur, *end= st+len;
  for (cur= st; cur<end; cur++)
  {
    if (cur->first_char != 0 && cur->first_char != -1)
    {
      int ilink= cur->char_tails->ithis;
      hash_map[cur->ithis*4+2]= ilink%256;
      hash_map[cur->ithis*4+3]= ilink/256;
      set_links(cur->char_tails,cur->last_char-cur->first_char+1);
    }
  }
}


void print_hash_map(const char *name)
{
  char *cur;
  int i;

  printf("static uchar %s[%d]= {\n",name,size_hash_map);
  for (i=0, cur= hash_map; i<size_hash_map; i++, cur++)
  {
    switch(i%4){
    case 0: case 1:
      if (!*cur)
	printf("0,   ");
      else
	printf("\'%c\', ",*cur);
      break;
    case 2: printf("%u, ",(uint)(uchar)*cur); break;
    case 3: printf("%u,\n",(uint)(uchar)*cur); break;
    }
  }
  printf("};\n");
}


void print_find_structs()
{
  {
    hash_map_cleanup cleanup(&hash_map, &size_hash_map);
    add_structs_to_map(root_by_len,max_len);
    set_links(root_by_len,max_len);
    print_hash_map("sql_functions_map");
  }

  printf("\n");

  {
    hash_map_cleanup cleanup(&hash_map, &size_hash_map);
    add_structs_to_map(root_by_len2,max_len2);
    set_links(root_by_len2,max_len2);
    print_hash_map("symbols_map");
  }
}

int check_dup_symbols(SYMBOL *s1, SYMBOL *s2)
{
  if (s1->length!=s2->length || strncmp(s1->name,s2->name,s1->length))
    return 0;

  const char *err_tmpl= "\ngen_lex_hash fatal error : \
Unfortunately gen_lex_hash can not generate a hash,\n since \
your lex.h has duplicate definition for a symbol \"%s\"\n\n";
  printf (err_tmpl,s1->name);
  fprintf (stderr,err_tmpl,s1->name);

  return 1;
}


int check_duplicates()
{
  SYMBOL *cur1, *cur2, *s_end, *f_end;

  s_end= symbols + array_elements(symbols);
  f_end= sql_functions + array_elements(sql_functions);

  for (cur1= symbols; cur1<s_end; cur1++)
  {
    for (cur2= cur1+1; cur2<s_end; cur2++)
    {
      if (check_dup_symbols(cur1,cur2))
	return 1;
    }
    for (cur2= sql_functions; cur2<f_end; cur2++)
    {
      if (check_dup_symbols(cur1,cur2))
	return 1;
    }
  }

  for (cur1= sql_functions; cur1<f_end; cur1++)
  {
    for (cur2= cur1+1; cur2< f_end; cur2++)
    {
      if (check_dup_symbols(cur1,cur2))
	return 1;
    }
  }
  return 0;
}


int main(int argc,char **argv)
{


  /* Broken up to indicate that it's not advice to you, gentle reader. */
  printf("/*\n\n  Do " "not " "edit " "this " "file " "directly!\n\n*/\n");

  puts("/*");
  puts(ORACLE_WELCOME_COPYRIGHT_NOTICE("2000"));
  puts("*/");

  /* Broken up to indicate that it's not advice to you, gentle reader. */
  printf("/* Do " "not " "edit " "this " "file!  This is generated by "
         "gen_lex_hash.cc\nthat seeks for a perfect hash function */\n\n");
  printf("#include \"lex.h\"\n\n");

  calc_length();

  if (check_duplicates())
    exit(1);

  generate_find_structs();
  print_find_structs();

  printf("\nstatic unsigned int sql_functions_max_len=%d;\n", max_len);
  printf("\nstatic unsigned int symbols_max_len=%d;\n\n", max_len2);

  printf("\
static SYMBOL *get_hash_symbol(const char *s,\n\
                               unsigned int len,bool function)\n\
{\n\
  uchar *hash_map;\n\
  const char *cur_str= s;\n\
\n\
  if (len == 0) {\n\
    DBUG_PRINT(\"warning\", (\"get_hash_symbol() received a request for a zero-length symbol, which is probably a mistake.\"));\
    return(NULL);\n\
  }\n"
);

  printf("\
  if (function){\n\
    if (len>sql_functions_max_len) return 0;\n\
    hash_map= sql_functions_map;\n\
    uint32 cur_struct= uint4korr(hash_map+((len-1)*4));\n\
\n\
    for (;;){\n\
      uchar first_char= (uchar)cur_struct;\n\
\n\
      if (first_char == 0)\n\
      {\n\
        int16 ires= (int16)(cur_struct>>16);\n\
        if (ires==array_elements(symbols)) return 0;\n\
        SYMBOL *res;\n\
        if (ires>=0) \n\
          res= symbols+ires;\n\
        else\n\
          res= sql_functions-ires-1;\n\
		  uint count= (uint) (cur_str - s);\n\
        return lex_casecmp(cur_str,res->name+count,len-count) ? 0 : res;\n\
      }\n\
\n\
      uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];\n\
      if (cur_char<first_char) return 0;\n\
      cur_struct>>=8;\n\
      if (cur_char>(uchar)cur_struct) return 0;\n\
\n\
      cur_struct>>=8;\n\
      cur_struct= uint4korr(hash_map+\n\
                        (((uint16)cur_struct + cur_char - first_char)*4));\n\
      cur_str++;\n\
    }\n"
);

  printf("\
  }else{\n\
    if (len>symbols_max_len) return 0;\n\
    hash_map= symbols_map;\n\
    uint32 cur_struct= uint4korr(hash_map+((len-1)*4));\n\
\n\
    for (;;){\n\
      uchar first_char= (uchar)cur_struct;\n\
\n\
      if (first_char==0){\n\
        int16 ires= (int16)(cur_struct>>16);\n\
        if (ires==array_elements(symbols)) return 0;\n\
        SYMBOL *res= symbols+ires;\n\
		uint count= (uint) (cur_str - s);\n\
        return lex_casecmp(cur_str,res->name+count,len-count)!=0 ? 0 : res;\n\
      }\n\
\n\
      uchar cur_char= (uchar)to_upper_lex[(uchar)*cur_str];\n\
      if (cur_char<first_char) return 0;\n\
      cur_struct>>=8;\n\
      if (cur_char>(uchar)cur_struct) return 0;\n\
\n\
      cur_struct>>=8;\n\
      cur_struct= uint4korr(hash_map+\n\
                        (((uint16)cur_struct + cur_char - first_char)*4));\n\
      cur_str++;\n\
    }\n\
  }\n\
}\n"
);
  exit(0);
}