ハッシュテーブル

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

図 7-11 シンボルハッシュテーブル

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

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

chain リンクから、求める名前のシンボルテーブルエントリを探すことができます。 chain リンクの最後には 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;
}