Algorithm implemented from a description in
"The Art of Computer Programming" by Donald E. Knuth
Volume 3 "Sorting and searching",
chapter 6.3 "Digital searching"
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..
So, we can read full search-structure as 32-bit word