Я читаю gen_lex_hash.cc mysql, но не знаю объяснения:
Идею представленного алгоритма см. "Искусство компьютерного программирования" Дональда Э. Кнута Том 3 "Сортировка и поиск" (глава 6.3 "Цифровой поиск" - название и номер главы это обратный перевод с русского издания :))
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 search-array..
Из приведенного выше потока я не могу понять детали и не могу найти подробного объяснения.
Для понимания этого я отлаживал программу gen_lex_hash
, но ничего не помогает, например:
0,-1
что означает?
Любой совет будет оценен!