ngx_str_rbtree_insert_value
声明 在 src\core\ngx_string.h
void ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_str_node_t *ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *name,
uint32_t hash);
实现在 src\core\ngx_string.c
void
ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
ngx_str_node_t *n, *t;
ngx_rbtree_node_t **p;
for ( ;; ) {
n = (ngx_str_node_t *) node;
t = (ngx_str_node_t *) temp;
if (node->key != temp->key) {
p = (node->key < temp->key) ? &temp->left : &temp->right;
} else if (n->str.len != t->str.len) {
p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
} else {
p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 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_str_rbtree_insert_value 是 Nginx 中用于向红黑树插入字符串节点的函数，其核心作用是根据特定的键值比较逻辑维护红黑树的有序性。
该函数实现了红黑树的节点插入逻辑，将新节点 node 插入到红黑树的正确位置，并初始化其属性（父节点、子节点、颜色）。插入后，红黑树的平衡调整由其他函数（如 ngx_rbtree_insert）处理。
函数签名
void ngx_str_rbtree_insert_value(
ngx_rbtree_node_t *temp,
ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel
);
参数详解
ngx_rbtree_node_t *temp
当前遍历的红黑树节点，作为临时指针用于逐层比较。
初始指向红黑树的根节点（或插入路径上的某个中间节点）。
在循环中，通过比较 temp 和 node 的键值，确定 node 的插入方向（左子树或右子树）。
最终会成为新插入节点的父节点（node->parent = temp）。
若树为空，temp 可能指向哨兵节点（此时 node 成为根节点）。
2 . ngx_rbtree_node_t *node
待插入的红黑树节点。
包含需要插入的字符串数据（ngx_str_node_t 类型，继承自 ngx_rbtree_node_t）。
需要被插入到红黑树的正确位置，并初始化其 parent、left、right 和颜色属性。
ngx_rbtree_node_t *sentinel
红黑树的哨兵节点（NIL 节点）。
标记树的叶子节点或空子节点（代替 NULL）。
作为插入操作的终止条件：当遍历到哨兵时，说明找到插入位置。
所有叶子节点的 left 和 right 均指向哨兵。
函数返回值
void- 无需返回值，所有操作通过指针直接修改红黑树结构。
- 插入结果通过修改
temp、node和sentinel的关联关系体现。
以下是 ngx_str_rbtree_insert_value 函数的逐行详细解释，涵盖代码作用、背景、逻辑、意图及设计思想：
详解
ngx_str_node_t *n, *t;
ngx_rbtree_node_t **p;
n和t用于将通用红黑树节点（ngx_rbtree_node_t）转换为字符串节点（ngx_str_node_t），以便访问字符串数据（str字段）。p是指向红黑树节点指针的指针，用于直接修改父节点的子节点指针（左或右）。通过类型转换扩展通用节点，支持自定义数据（字符串）。
使用二级指针
p简化插入逻辑，避免区分左/右子树。
for ( ;; ) {
循环遍历红黑树，逐层比较键值，直到找到插入位置。
通过迭代而非递归实现，减少函数调用开销，提升性能。
n = (ngx_str_node_t *) node;
t = (ngx_str_node_t *) temp;
将 node（待插入节点）和 temp（当前遍历节点）转换为 ngx_str_node_t 类型，以便访问字符串数据。
ngx_str_node_t 继承自 ngx_rbtree_node_t，添加了 ngx_str_t str 字段存储字符串。
ngx_str_node_t
比较键值（第一优先级：哈希值）
if (node->key != temp->key) {
p = (node->key < temp->key) ? &temp->left : &temp->right;
- 逻辑：
若
node和temp的key（哈希值）不同，根据大小选择左或右子树。p指向temp的左或右子节点指针。优先比较整型
key（哈希值），速度快，减少字符串比较次数。哈希值不同直接决定插入方向，避免后续比较。
比较字符串长度（第二优先级）
} else if (n->str.len != t->str.len) {
p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
逻辑：若
key相同，比较字符串长度，不同则按长度排序。处理哈希冲突（不同字符串哈希值相同），通过长度快速区分。
长度比较为整型操作，仍比逐字节比较高效。
比较字符串内容（第三优先级）
} else {
p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
? &temp->left : &temp->right;
}
- 逻辑：若
key和长度均相同，逐字节比较字符串内容，决定插入方向。
检查是否到达插入位置
if (*p == sentinel) {
break;
}
temp = *p;
- 逻辑：
若
*p指向哨兵（sentinel），说明找到插入位置，终止循环。否则，将
temp更新为子节点，继续向下遍历。哨兵节点标记空子树，简化边界条件处理。
通过迭代逐步深入树的底层。
插入节点并初始化
*p = node; // 将节点插入到树中
node->parent = temp; // 设置父节点
node->left = sentinel; // 子节点初始化为哨兵
node->right = sentinel;
ngx_rbt_red(node); // 标记为红色
- 逻辑：
*p = node：将新节点链接到父节点的左或右子节点。设置父节点、子节点为哨兵，标记颜色为红色。
新节点初始化为红色，简化后续红黑树平衡调整（红黑树性质要求）。
哨兵节点统一表示空子树，避免空指针判断。
ngx_rbt_red
#define ngx_rbt_red(node) ((node)->color = 1)
- 核心逻辑：通过多级比较（哈希值 → 长度 → 内容）确定插入位置，确保树的有序性。
- 性能优化：优先使用整型比较（
key和长度），减少高开销的字符串内容比较。