Hash table

A hash table of Elf32_Word objects supports symbol table access. Labels appear in ``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]

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;
   }

Hashing function