线索二叉搜索树字节对齐实现代码逻辑解析

核心设计思路 #

传统线索二叉树需要为每个节点额外配置两个布尔标记位，用来区分left/right指针存储的是子节点地址还是前驱/后继线索，会带来额外的内存开销。这套实现用了典型的*标签指针（Tagged Pointer）*优化思路：靠2字节对齐带来的指针低位冗余，把指针本身空出的最低位当标记位使用，完全省掉了额外的标记字段，同时用无分支位运算做存取，性能更高。

__attribute__((aligned(2)))的作用 #

这个GCC扩展属性是整个逻辑能成立的基础：

• 它强制所有bstree_node_t类型实例的起始内存地址为2的整数倍，换算成二进制表示，这类地址的最低位永远是0，不承载有效地址信息，刚好可以空出来存1比特的标记
• 当bstree_node_t被嵌入用户自定义结构体（比如示例里的struct leaf）时，编译器会自动调整结构体布局、插入必要的填充字节，保证node字段的地址始终满足2字节对齐要求，不会破坏指针最低位为0的前提。

整套实现的标记规则非常简单：存在left/right字段里的uintptr_t值，最低位为0代表是指向子节点的正常链接，最低位为1代表是指向前驱/后继的线索指针。

内联函数运行逻辑拆解 #

四个函数都是纯位运算实现，没有if分支，避免了分支预测失败的性能损耗：

线索设置：_bstree_set_thread #

static inline void _bstree_set_thread(bstree_node_t *t, uintptr_t *p)
{
    *p = (uintptr_t) t | 1;
}

逻辑非常直接：因为传入的节点指针t本身满足2字节对齐，最低位为0，和1做或运算只会把最低位置为1，不会破坏原始地址信息，同时标记这个值是线索而非正常链接，最后写入left/right对应的存储位置p。

线索读取：_bstree_get_thread #

static inline bstree_node_t *_bstree_get_thread(uintptr_t u)
{
    return (bstree_node_t *) ((u & -(int)(u & 1)) & ~1UL);
}

分步拆解运算逻辑：

• u & 1：取出最低位的标记位，如果是线索则值为1，是正常链接则值为0
• -(int)(u & 1)：对标记位取补码负值，如果标记为1（线索），-1的补码是全1；如果标记为0（正常链接），-0的结果是全0
• u & 上述结果：如果是正常链接，和全0做与运算结果为0，直接返回空；如果是线索，和全1做与运算保留u的全部原始位
• 最后和~1UL（除最低位外全1的掩码）做与运算，清掉最低位的标记1，还原出原始的节点指针返回。

简单说，这个函数只有当输入值确实是线索时，才会返回对应的节点地址，否则返回空。

正常链接设置：_bstree_set_link #

static inline void _bstree_set_link(bstree_node_t *n, uintptr_t *p)
{
    *p = (uintptr_t) n;
}

没有额外运算：子节点指针n本身满足2字节对齐，最低位天然为0，直接存入存储位置p即可，最低位的0自然标记这是正常链接。

正常链接读取：_bstree_get_link #

static inline bstree_node_t *_bstree_get_link(uintptr_t u)
{
    return (bstree_node_t *) (u & ((int)(u & 1) - 1));
}

同样是无分支逻辑：

• u & 1取出标记位，正常链接为0，线索为1
• (标记位) - 1：如果是正常链接（标记0），0-1=-1补码为全1；如果是线索（标记1），1-1=0
• 和u做与运算：如果是线索，和0做与结果为0返回空；如果是正常链接，和全1做与保留全部地址位（最低位本来就是0，不需要额外清理），直接返回子节点指针。

设计的优缺点 #

• 优势：每个节点省掉了两个标记位的内存开销，所有存取操作都是纯位运算，无分支，性能比传统带标记位的实现更高，这种优化在操作系统内核、高性能基础库里非常常见
• 局限性：强依赖编译器的对齐属性和指针的二进制表示规则，属于平台相关优化，移植到不支持该对齐属性、或者指针低位有特殊含义的平台上会直接出错。

内容的提问来源于stack exchange，提问作者user17232631