Hash Table Section
A hash table consists of Elf32_Word
or
Elf64_Word
objects that provide for symbol table access. The
SHT_HASH
section provides this hash table. The symbol table to which the
hashing is associated is specified in the sh_link
entry of the hash
table's section header. Labels are used in the following figure to help explain the hash table
organization, but these labels are not part of the specification.
Symbol Hash Table
The bucket
array contains nbucket
entries, and the
chain
array contains nchain
entries. Indexes start at
0
. Both bucket
and chain
hold
symbol table indexes. Chain table entries parallel the symbol table. The number of symbol
table entries should equal nchain
, so symbol table indexes also select
chain table entries.
A hashing function that accepts a symbol name, returns a value to compute a
bucket
index. Consequently, if the hashing function returns the value
x for some name, bucket
[x% nbucket
] gives an index
y. This index is an index into both the symbol table and the
chain table. If the symbol table entry is not the name desired,
chain
[y] gives the next symbol table entry
with the same hash value.
The chain
links can be followed until the selected symbol table entry
holds the desired name, or the chain
entry contains the value
STN_UNDEF
.
The hash function is as follows.
unsigned long elf_Hash(const unsigned char *name) { unsigned int h = 0, g; while (*name) { h = (h << 4) + *name++; if (g = h & 0xf0000000) h ^= g >> 24; h &= ~g; } return h; }