ハッシュテーブル

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 エントリに値 STN_UNDEF が含まれるまで、chain リンクをたどることができます。

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

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