1 定义ngx_rbtree_insert_value 函数 定义在 ./nginx-1.24.0/src/core/ngx_rbtree.cvoidngx_rbtree_insert_value(ngx_rbtree_node_t*temp,ngx_rbtree_node_t*node,ngx_rbtree_node_t*sentinel){ngx_rbtree_node_t**p;for(;;){p(node-keytemp-key)?temp-left:temp-right;if(*psentinel){break;}temp*p;}*pnode;node-parenttemp;node-leftsentinel;node-rightsentinel;ngx_rbt_red(node);}ngx_rbtree_insert_value 函数的作用是 按节点 key 值进行二叉搜索树插入 将新节点挂载到树中正确的位置并初始化为红色叶子节点不进行任何红黑树自平衡修复。2 详解1 函数签名voidngx_rbtree_insert_value(ngx_rbtree_node_t*temp,ngx_rbtree_node_t*node,ngx_rbtree_node_t*sentinel)该函数不向调用者返回任何值它的职责是纯副作用修改树的结构将 node 挂入树中。参数1 ngx_rbtree_node_t *temp temp 表示“临时指针”它将在函数内部作为循环游标 从根节点逐步向下移动直至找到插入位置的父节点。 调用者传入的是树的 根节点tree-root。 函数执行过程中temp 会被不断更新为当前比较节点的左/右孩子。 最终状态函数结束时temp 指向新节点 node 的父节点参数2 ngx_rbtree_node_t *node 指向待插入节点的指针参数3 ngx_rbtree_node_t *sentinel 指向全局唯一的哨兵节点2 逻辑流程1 局部变量 2 循环查找 3 挂载1 局部变量{ngx_rbtree_node_t**p;p 将用于存放新节点要挂载的“目标位置”的地址即父节点 left 或 right 指针的地址2 循环查找for(;;){p(node-keytemp-key)?temp-left:temp-right;if(*psentinel){break;}temp*p;}#1 开始一个无限循环用于沿树向下查找插入点。 循环会在遇到空子树哨兵时通过 break 退出否则不断下行#2 比较新节点与当前节点 temp 的 key 值 若 node-key temp-key则新节点应插入左子树p 指向 temp-left 的地址temp-left。 否则插入右子树p 指向 temp-right。#3 解引用 p即检查当前节点的相应孩子是否就是哨兵节点 哨兵节点代表“空位”。如果成立说明已经到达了叶子下一层的空位置找到了插入点 立即退出 for 循环。 此时 temp 停留在将成为新节点父节点的真实节点上 p 仍保存着 temp 的某侧孩子指针当前指向哨兵的地址。#4 若未遇到哨兵即 *p 是真实节点 则将 temp 更新为该孩子节点继续向树的深层探索。3 挂载*pnode;node-parenttemp;node-leftsentinel;node-rightsentinel;ngx_rbt_red(node);}*p node; 挂载新节点将新节点 node 的地址写入 *p。 由于 p 指向父节点 temp 的 left 或 right 指针原指向哨兵 这条语句相当于让父节点正确地指向了新节点完成了物理连接。 node-parent temp; 设置新节点的父节点指针指向 temp即循环结束时的当前节点。双向链接建立。 node-left sentinel; 新节点的左孩子设为哨兵节点表示它是叶子没有左子树。 node-right sentinel; 右孩子同样设为哨兵节点确保新节点是干净的叶子左右皆空。 ngx_rbt_red(node); 将新节点的颜色设为红色。 红黑树插入规则要求新节点总是红色 这样可以尽可能地避免违反“从根到叶子的所有路径黑高相同”的性质 只有当父节点也是红色时才会破坏“不连续红”规则而这种情况由后续旋转修复。整体逻辑总结 函数通过 for 循环遍历树 利用二级指针 p 同时完成“选择方向”和“定位插入点”的操作。 循环结束时temp 是父节点p 存放其子指针的地址然后将新节点接入并完成叶子初始化和颜色设定。 将“查找”与“挂载”无缝结合并且完全依赖哨兵节点避免了 NULL 检查