ToB企服应用市场:ToB评测及商务社交产业平台

标题: Ubuntu 下 nginx-1.24.0 源码分析 - ngx_str_rbtree_insert_value [打印本页]

---

作者: 水军大提督    时间: 11 小时前
标题: Ubuntu 下 nginx-1.24.0 源码分析 - ngx_str_rbtree_insert_value
ngx_str_rbtree_insert_value

---

声明 在 src\core\ngx_string.h

1. void ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
2.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
3. ngx_str_node_t *ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *name,
4.     uint32_t hash);

复制代码

---

实现在 src\core\ngx_string.c

1. void
2. ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
3.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
4. {
5.     ngx_str_node_t      *n, *t;
6.     ngx_rbtree_node_t  **p;
8.     for ( ;; ) {
11.         n = (ngx_str_node_t *) node;
12.         t = (ngx_str_node_t *) temp;
14.         if (node->key != temp->key) {
16.             p = (node->key < temp->key) ? &temp->left : &temp->right;
18.         } else if (n->str.len != t->str.len) {
20.             p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
22.         } else {
23.             p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
24.                  ? &temp->left : &temp->right;
25.         }
27.         if (*p == sentinel) {
28.             break;
29.         }
31.         temp = *p;
32.     }
34.     *p = node;
35.     node->parent = temp;
36.     node->left = sentinel;
37.     node->right = sentinel;
38.     ngx_rbt_red(node);
39. }

复制代码

---

ngx_str_rbtree_insert_value 是 Nginx 中用于向红黑树插入字符串节点的函数，其焦点作用是根据特定的键值比较逻辑维护红黑树的有序性。
该函数实现了红黑树的节点插入逻辑，将新节点 node 插入到红黑树的正确位置，并初始化其属性（父节点、子节点、颜色）。插入后，红黑树的平衡调整由其他函数（如 ngx_rbtree_insert）处置处罚。

---

函数署名

1. void ngx_str_rbtree_insert_value(
2.     ngx_rbtree_node_t *temp,
3.     ngx_rbtree_node_t *node,
4.     ngx_rbtree_node_t *sentinel
5. );

复制代码

---

参数详解

• 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 函数的逐行具体表明，涵盖代码作用、背景、逻辑、意图及设计思想：

---

详解

1. ngx_str_node_t      *n, *t;
2. ngx_rbtree_node_t  **p;

复制代码

• n 和 t 用于将通用红黑树节点（ngx_rbtree_node_t）转换为字符串节点（ngx_str_node_t），以便访问字符串数据（str 字段）。
  
• p 是指向红黑树节点指针的指针，用于直接修改父节点的子节点指针（左或右）。
  
• 通过类型转换扩展通用节点，支持自界说数据（字符串）。
  
• 利用二级指针 p 简化插入逻辑，避免区分左/右子树。
  

---

1. for ( ;; ) {

复制代码

循环遍历红黑树，逐层比较键值，直到找到插入位置。
通过迭代而非递归实现，减少函数调用开销，提升性能。

---

1. n = (ngx_str_node_t *) node;
2. 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

---

比较键值（第一优先级：哈希值）

1. if (node->key != temp->key) {
2.     p = (node->key < temp->key) ? &temp->left : &temp->right;

复制代码

• 逻辑：
  
  
  
  • 若 node 和 temp 的 key（哈希值）差别，根据大小选择左或右子树。
    
  • p 指向 temp 的左或右子节点指针。
    
  • 优先比较整型 key（哈希值），速度快，减少字符串比较次数。
    
  • 哈希值差别直接决定插入方向，避免后续比较。
    
  
  

---

比较字符串长度（第二优先级）

1. } else if (n->str.len != t->str.len) {
2.     p = (n->str.len < t->str.len) ? &temp->left : &temp->right;

复制代码

• 逻辑：若 key 雷同，比较字符串长度，差别则按长度排序。
  
• 处置处罚哈希辩论（差别字符串哈希值雷同），通过长度快速区分。
  
• 长度比较为整型操纵，仍比逐字节比较高效。
  

---

比较字符串内容（第三优先级）

1. } else {
2.     p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
3.          ? &temp->left : &temp->right;
4. }

复制代码

• 逻辑：若 key 和长度均雷同，逐字节比较字符串内容，决定插入方向。
  

---

检查是否到达插入位置

1. if (*p == sentinel) {
2.     break;
3. }
4. temp = *p;

复制代码

• 逻辑：
  
  
  
  • 若 *p 指向哨兵（sentinel），阐明找到插入位置，终止循环。
    
  • 否则，将 temp 更新为子节点，继续向下遍历。
    
  • 哨兵节点标志空子树，简化边界条件处置处罚。
    
  • 通过迭代渐渐深入树的底层。
    
  
  

---

插入节点并初始化

1. *p = node;          // 将节点插入到树中
2. node->parent = temp; // 设置父节点
3. node->left = sentinel; // 子节点初始化为哨兵
4. node->right = sentinel;
5. ngx_rbt_red(node);  // 标记为红色

复制代码

• 逻辑：
  
  
  
  • *p = node：将新节点链接到父节点的左或右子节点。
    
  • 设置父节点、子节点为哨兵，标志颜色为红色。
    
  • 新节点初始化为红色，简化后续红黑树平衡调整（红黑树性子要求）。
    
  • 哨兵节点同一表示空子树，避免空指针判断。
    
  
  

ngx_rbt_red

1. #define ngx_rbt_red(node)               ((node)->color = 1)

复制代码

---

• 焦点逻辑：通过多级比较（哈希值 → 长度 → 内容）确定插入位置，确保树的有序性。
  
• 性能优化：优先利用整型比较（key 和长度），减少高开销的字符串内容比较。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4