ngx_rbtree_insert_timer_value

1 定义

ngx_rbtree_insert_timer_value 函数 定义在 ./nginx-1.24.0/src/core/ngx_rbtree.c

voidngx_rbtree_insert_timer_value(ngx_rbtree_node_t*temp,ngx_rbtree_node_t*node,ngx_rbtree_node_t*sentinel){ngx_rbtree_node_t**p;for(;;){/* * Timer values * 1) are spread in small range, usually several minutes, * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. * The comparison takes into account that overflow. *//* node->key < temp->key */p=((ngx_rbtree_key_int_t)(node->key-temp->key)<0)?&temp->left:&temp->right;if(*p==sentinel){break;}temp=*p;}*p=node;node->parent=temp;node->left=sentinel;node->right=sentinel;ngx_rbt_red(node);}

`ngx_rbtree_insert_timer_value` 函数用于 将新的定时器节点插入 nginx 的红黑树中，该树以毫秒超时值为键排序。 它利用“(节点键 - 当前节点键) < 0”的有符号比较方式， 天然处理了 32 位毫秒值约 49 天回绕溢出问题， 从而在仅几分钟范围的定时器场景下正确找到插入位置，并将新节点染为红色（后续平衡由上层完成）。

2 详解

1 函数签名

voidngx_rbtree_insert_timer_value(ngx_rbtree_node_t*temp,ngx_rbtree_node_t*node,ngx_rbtree_node_t*sentinel)

参数 1 ngx_rbtree_node_t *temp 遍历起始节点，通常为树根，函数会将其沿树移动

参数 2 ngx_rbtree_node_t *node 待插入的新定时器节点，其 key 域存储了以毫秒为单位的超时时间

参数 3 ngx_rbtree_node_t *sentinel 哨兵节点

2 逻辑流程

1 局部变量 2 循环查找 3 链接

1 局部变量

{ngx_rbtree_node_t**p;

声明二级指针变量 p。 p 将保存“父节点的 left 或 right 成员”的地址 通过二级指针，我们可以直接修改父节点中指向子节点的指针， 而无需单独记录父节点，简化了插入链接。

2 循环查找

for(;;){/* * Timer values * 1) are spread in small range, usually several minutes, * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. * The comparison takes into account that overflow. *//* node->key < temp->key */p=((ngx_rbtree_key_int_t)(node->key-temp->key)<0)?&temp->left:&temp->right;if(*p==sentinel){break;}temp=*p;}

#1 开启无限循环，用于从 temp 开始沿树向下遍历， 直到找到正确的插入位置（遇到哨兵）

#2 核心比较与路径选择。 node->key - temp->key： 无符号整数相减，结果为无符号差值（自动模 2³²）。 (ngx_rbtree_key_int_t) (差值)： 将无符号差值强制转换为有符号 32 位整数（ngx_rbtree_key_int_t，即 int32_t）。 按照 C 语言规则，当无符号值小于等于 INT32_MAX 时，解释为正数或零；否则会被解释为负数。 < 0：检查这个有符号差值是否小于零。 若小于零，说明 node->key 在环形时间线上“早于” temp->key（到期更早）， 则 p = &temp->left（插入左子树）； 否则 p = &temp->right（插入右子树）。 溢出处理意义： 假设当前时间为 temp->key = 0xFFFFFFF0（即将回绕）， 新定时器 node->key = 0x00000010（回绕后的一个值）。 无符号差值为 0x00000010 - 0xFFFFFFF0 = 0x00000020， 转换为有符号后为正，表示 node 更大（时间更晚），会放在右子树， 这符合实际时间顺序（因为 node 的实际到期时间确实比 temp 晚）。 如果差值超过 2³¹ 则可能误判，但定时器范围极小便不会触发。 p 的意义：p 现在指向 temp 节点的某一个子指针的地址（left 或 right），便于后续修改。

#2 检查选定的子指针是否指向哨兵（即空位）。 *p 是子指针的内容。 若它为 sentinel，说明已经遍历到叶子位置，可以在此插入新节点，于是跳出循环。 终止条件，结束查找。

#3 若子节点不是哨兵，则将 temp 更新为该子节点，以便下一轮循环继续向下比较

3 链接

*p=node;node->parent=temp;node->left=sentinel;node->right=sentinel;ngx_rbt_red(node);}

#1 将新节点 node 链接到树中。 通过解引用 p 直接修改父节点的子指针，使其指向 node。 完成“父 → 子”方向的连接，无需额外的父节点判断。

#2 设置新节点的 parent 指针，指向 temp（即其父节点）。 建立“子 → 父”的反向链接，使红黑树的双向访问（旋转操作等）成为可能。

#3 将新节点的左右子指针均初始化为 sentinel。

#4 将节点颜色设为红色 红黑树插入默认将新节点染为红色， 这样可以最小化对树黑高度的影响 但可能引入红色父节点的冲突, 需由后续平衡步骤修复