gen_lex_hash.cc File Reference

#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>

Classes
struct	hash_lex_struct
Functions
hash_lex_struct *	get_hash_struct_by_len (hash_lex_struct **root_by_len, int len, int *max_len)
void	insert_into_hash (hash_lex_struct *root, const char *name, int len_from_begin, int index, int function)
void	insert_symbols ()
void	insert_sql_functions ()
void	calc_length ()
void	generate_find_structs ()
void	add_struct_to_map (hash_lex_struct *st)
void	add_structs_to_map (hash_lex_struct *st, int len)
void	set_links (hash_lex_struct *st, int len)
void	print_hash_map (const char *name)
void	print_find_structs ()
int	check_dup_symbols (SYMBOL *s1, SYMBOL *s2)
int	check_duplicates ()
int	main (int argc, char **argv)
Variables
hash_lex_struct *	root_by_len = 0
int	max_len = 0
hash_lex_struct *	root_by_len2 = 0
int	max_len2 = 0
char *	hash_map = 0
int	size_hash_map = 0

---

Detailed Description

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

Todo:

use instead to_upper_lex, special array (substitute chars) without skip codes..

try use reverse order of comparing..