爲什麼此AVL樹實現在64位而不是32位實現中將指針裝入指針？

Question

在this AVL tree implementation from Solaris，結構avl_node以一種明顯的方式，如果在編譯爲32位庫中定義。

但對於64庫的指針，節點的父被包裝成「avl_pcb」。而且看起來只有61位的ponter被存儲。

1. 爲什麼這樣做的工作？
2. 爲什麼不爲32位做類似的事情？

Answer 1

在一個64位的機器上，指針通常對齊在字邊界，字邊界是8個字節的倍數。結果，指針的最低三位將爲零。因此，如果數據結構需要三位信息，則它可以將它們打包到指針的最低三位中。那樣：

• 要跟隨指針，清除指針值的最低三位，然後解除引用它。
• 讀取任何三個比特的，屏蔽掉在指針的位的其餘部分，並直接讀取它們。

這種方法非常標準，不會失去指向地址的能力，因爲通常出於性能或硬件方面的原因，您不希望有非對齊的指針。

我不知道是什麼原因，他們沒有這樣做在32位情況下，由於有三個三分球，他們可以很容易地隱藏使用同樣的伎倆必需的位，但每個指針兩位。我的猜測是這是一個性能問題：如果你在指針的底部打包位，由於需要清除位的計算，你會增加跟隨指針的開銷。請注意，例如，在64位的情況下，這些位被打包到父指針中，這隻用於非常見的操作，如計算中間繼承者或者在插入或刪除時進行旋轉。這可以快速查找。在32位的情況下，要隱藏3位，實現需要使用兩個指針的低位，其中一個指針必須是左指針或右指針。我的猜測是，減緩樹搜索的性能降低不值得節省空間，所以他們決定只是將內存命中並分別存儲。但這只是推測，因爲如果他們願意，他們絕對可以將這些位存儲在指針的底部。

附註：如果實現使用的是紅/黑樹而不是AVL樹，那麼只需要兩位信息：一個位來告訴節點是紅色還是黑色，一位告訴節點是左邊還是右邊的孩子。在這種情況下，所需的兩位總是可以打包成一個32位的指針。這是爲什麼紅黑樹受歡迎的原因之一。

希望這會有所幫助！