PDB シリアライズされたハッシュテーブル形式¶
はじめに¶
PDB 形式の設計目標の 1 つは、デバッグ情報への迅速なアクセスを提供することです。このため、値のリストを読み取ってその場でハッシュテーブルを再構築する必要があるのではなく、いくつかのハッシュテーブルはシリアライズされて直接ファイルに埋め込まれます。
シリアライズ形式は、恣意的な大きさや容量のハッシュテーブル、値の型、ハッシュ関数をサポートします。サポートされているキー値の型は uint32 のみです。唯一の要件は、作成者と消費者がハッシュ関数に同意することです。そのため、ハッシュ関数はこのドキュメントではさらに説明されません。特定のインスタンスの PDB ファイルハッシュテーブルでは、適切なハッシュ関数を使用されていると想定されています。
ディスク上の形式¶
.--------------------.-- +0
| Size |
.--------------------.-- +4
| Capacity |
.--------------------.-- +8
| Present Bit Vector |
.--------------------.-- +N
| Deleted Bit Vector |
.--------------------.-- +M ─╮
| Key | │
.--------------------.-- +M+4 │
| Value | │
.--------------------.-- +M+4+sizeof(Value) │
... ├─ |Capacity| Bucket entries
.--------------------. │
| Key | │
.--------------------. │
| Value | │
.--------------------. ─╯
サイズ - ハッシュテーブルに格納されている値の数。
容量 - ハッシュテーブル内のバケットの数。作成者は、
2/3*容量+1以下の負荷係数を維持する必要があります。現在のビットベクトル - どのバケットに有効な値があるかについての情報を格納するシリアライズされたビットベクトル。バケットに値がある場合、対応するビットが設定され、バケットに値がない場合（バケットが空であるか、値が削除された値であるかのどちらかである場合）、ビットは設定されません。
削除されたビットベクトル - どのバケットに削除された値があるかについての情報を格納するシリアライズされたビットベクトル。このバケット内のエントリが削除されている場合、ビットが設定され、それ以外の場合は設定されません。
キーと値 -
容量個のハッシュバケットのリスト。ここで最初のエントリはキー（常に uint32）、2 番目のエントリは値です。各バケットの状態（有効、空、削除）は、現在と削除ビットベクトルを調べることで確認できます。
現在と削除ビットベクトル¶
各バケットのステータスを示すビットベクトルは次のようにシリアライズされます。
.--------------------.-- +0
| Word Count |
.--------------------.-- +4
| Word_0 | ─╮
.--------------------.-- +8 │
| Word_1 | │
.--------------------.-- +12 ├─ |Word Count| values
... │
.--------------------. │
| Word_N | │
.--------------------. ─╯
単語は、連続したバイトブロックとして見た場合、次のレイアウトのビットベクトルを表します。
.------------. .------------.------------.
| Word_N | ... | Word_1 | Word_0 |
.------------. .------------.------------.
| | | | |
+N*32 +(N-1)*32 +64 +32 +0
このビットベクトルの k 番目のビットは、ハッシュテーブル内の k 番目のバケットのステータスを表します。