ハッシュテーブルセクション

ハッシュテーブルは、シンボルテーブルへのアクセスを提供する Elf32_Word または Elf64_Word オブジェクトから構成されます。SHT_HASH セクションは、このハッシュテーブルを提供します。ハッシュが関連付けられているシンボルテーブルは、ハッシュテーブルのセクションヘッダーの sh_link エントリに指定されます。ハッシュテーブルの構造についての説明をわかりやすくするために次の図ではラベルを表示しますが、ラベルは仕様の一部ではありません。

図 10  シンボルハッシュテーブル

bucket 配列には nbucket 個のエントリが存在し、chain 配列には nchain 個のエントリが存在します。インデックスは 0 から始まります。bucket と chain には、シンボルテーブルインデックスを保持します。連鎖テーブルエントリは、シンボルテーブルに対応しています。シンボルテーブルエントリ数は、nchain に等しくなければなりません。したがって、シンボルテーブルインデックスにより、連鎖テーブルエントリも選択されます。

ハッシュ関数はシンボル名を受け取り、bucket インデックスの計算に使用できる値を返します。つまり、ハッシュ関数がある名前に対して値 x を返した場合、bucket [ x% nbucket ] はインデックス y を返します。このインデックスは、シンボルテーブルと連鎖テーブルの両方へのインデックスです。シンボルテーブルエントリが目的の名前でなかった場合、chain[y] は、同じハッシュ値が存在する次のシンボルテーブルエントリを返します。

目的の名前を持つシンボルテーブルエントリが選択されるか、chain エントリの値が STN_UNDEF になるまで、chain リンクをたどることができます。

ハッシュ関数を次に示します。

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