----------------------------------------------------------------------------

Hash table

A hash table of Elf32_Word objects supports symbol table access. Labels
appear in Figure 8-16, ``Symbol hash table'' to help explain the hash table
organization, but they are not part of the specification. 

 -------------------
|      nbucket     |
|------------------|
|      nchain      |
|------------------|
|     bucket[0]    |
|       . . .      |
| bucket[nbucket-1]|
|------------------|
|     chain[0]     |
|       . . .      |
|  chain[nchain-1] |
|------------------|

Figure 8-16 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 accepts a symbol name and returns a value
that may be used to compute a bucket index. Consequently, if the hashing
function returns the value ``x'' for some name, bucket[x%nbucket] gives an
index, ``y'', into both the symbol table and the chain table. If the symbol
table entry is not the one desired, chain[y] gives the next symbol table
entry with the same hash value. One can follow the chain links until either
the selected symbol table entry holds the desired name or the chain entry
contains the value STN_UNDEF.

   unsigned long elf_hash(const unsigned char *name) {
        unsigned long     h = 0, g;


        while (∗name)
        {
             h = (h << 4) + *name++;
             if (g = h & 0xf0000000)
                  h ^= g >> 24;
             h &= ~g;
        }
        return h;
   }

Figure 8-17 Hashing function