SolarisからのこのAVLツリーの実装では、32ビットライブラリ用にコンパイルする場合、structavl_nodeは明白な方法で定義されます。
ただし、64ライブラリの場合、ノードの親へのポインタは「avl_pcb」にパックされます。そして、ポンターの61ビットだけが保存されているように見えます。
- なぜこれが機能するのですか？
- 32ビットでも同様のものを作ってみませんか？
1 に答える
9
64ビットマシンでは、ポインタは通常、8バイトの倍数であるワード境界に配置されます。その結果、ポインタの下位3ビットはゼロになります。したがって、データ構造に3ビットの情報が必要な場合は、それらをポインターの下位3ビットにパックできます。そのように：
- ポインタをたどるには、ポインタ値の下位3ビットをクリアしてから、それを逆参照します。
- 3ビットのいずれかを読み取るには、ポインターの残りのビットをマスクして、直接読み取ります。
このアプローチはかなり標準的であり、アドレスを指す機能を失うことはありません。通常、パフォーマンスまたはハードウェア上の理由から、とにかく非整列のポインターを使用したくないためです。
私がよくわからないのは、32ビットの場合にこれを行わなかった理由です。3つのポインターを使用すると、同じトリックを使用して必要なビットを簡単に非表示にできますが、ポインターごとに2ビットです。私の推測では、これはパフォーマンスの問題だと思います。ポインタの下部にビットをパックすると、ビットをクリアするために必要な計算のために、ポインタをたどるコストが増加します。たとえば、64ビットの場合、ビットが親ポインタにパックされていることに注意してください。親ポインタは、順序どおりの後続の計算や、挿入または削除でのローテーションの実行など、一般的でない操作にのみ使用されます。これにより、ルックアップが高速に保たれます。32ビットの場合、3ビットを非表示にするには、実装で2つのポインターの下位ビットを使用する必要があります。そのうちの1つは、左または右のポインターである必要があります。私の推測では、ツリー検索の速度を落とすことによるパフォーマンスへの影響は、スペースを節約する価値がなかったため、メモリの影響を受けて別々に保存することにしました。ただし、必要に応じてポインタの下部にビットを格納できた可能性があるため、これは単なる推測です。
ちなみに、実装でAVLツリーではなく赤/黒ツリーを使用している場合、必要な情報は2ビットだけです。ノードが赤か黒かを判断するビットと、ノードが赤か黒かを判断するビットです。ノードは左または右の子です。その場合、必要な2ビットは常に32ビットポインタにパックできます。これが赤黒木が人気の理由の1つです。
お役に立てれば！
于 2013-01-11T17:03:06.067 に答える