data-structures - 为什么这个 AVL 树实现将位打包成 64 位而不是 32 位实现的指针？

Question

在 this AVL tree implementation from Solaris , 如果为 32 位库编译，则 struct avl_node 以明显的方式定义。

但是对于 64-library，指向节点父级的指针被打包到“avl_pcb”中。看起来只存储了 61 位的 ponter。

为什么这有效？

为什么不为 32 位做类似的事情？

Answer 1

在 64 位机器上，指针通常在字边界对齐，字边界是 8 字节的倍数。结果，指针的最低三位将为零。因此，如果数据结构需要三位信息，它可以将它们打包到指针的最低三位。那样:

要跟随指针，清除指针值的最低三位，然后取消引用它。

要读取这三个位中的任何一个，请屏蔽指针中的其余位并直接读取它们。

这种方法非常标准，并且不会失去任何指向地址的能力，因为通常出于性能或硬件原因，您无论如何都不想拥有未对齐的指针。

我不确定的是为什么他们没有在 32 位情况下这样做，因为使用三个指针，他们可以使用相同的技巧轻松隐藏必要的位，但每个指针有两个位。我的猜测是这是一个性能问题:如果你确实将位打包到指针的底部，你会增加跟随指针的成本，因为清除位所需的计算。请注意，例如，在 64 位情况下，位被打包到父指针中，它仅用于不常见的操作，例如计算中序后继或对插入或删除进行旋转。这样可以保持快速查找。在 32 位情况下，要隐藏 3 位，实现将需要使用两个指针的低位，其中之一必须是左指针或右指针。我的猜测是减慢树搜索的性能损失不值得节省空间，所以他们决定只接受内存损失并将它们分开存储。不过，这只是推测，因为如果他们愿意，他们绝对可以将这些位存储在指针的底部。

附带说明:如果实现使用的是红/黑树而不是 AVL 树，那么只需要两位信息:一位用于判断节点是红色还是黑色，另一位用于判断节点是红色还是黑色节点是左 child 或右 child 。在这种情况下，所需的两位总是可以打包成一个 32 位的指针。这就是红黑树受欢迎的原因之一。

希望这可以帮助!