Adding upstream version 1:10.5.12.upstream/1%10.5.12upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 482 insertions, 0 deletions

diff --git a/sql/gen_lex_hash.cc b/sql/gen_lex_hash.cc
new file mode 100644
index 00000000..98e6205e
--- /dev/null
+++ b/sql/gen_lex_hash.cc
@@ -0,0 +1,482 @@
+/*
+   Copyright (c) 2000, 2012, Oracle and/or its affiliates.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   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 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, Inc., 51 Franklin St, Fifth Floor, 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|b|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
+#undef CHECK_UNLIKELY
+#include "mariadb.h"
+#include "mysql_version.h"
+#include "lex.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 (unlikely(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 (unlikely(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();
+}
+
+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()
+{
+  add_structs_to_map(root_by_len,max_len);
+  set_links(root_by_len,max_len);
+  print_hash_map("sql_functions_map");
+  free(hash_map);
+
+  hash_map= 0;
+  size_hash_map= 0;
+
+  printf("\n");
+
+  add_structs_to_map(root_by_len2,max_len2);
+  set_links(root_by_len2,max_len2);
+  print_hash_map("symbols_map");
+  free(hash_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);
+}
+