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
- );
参数详解
当前遍历的红黑树节点，作为临时指针用于逐层比较。
初始指向红黑树的根节点（或插入路径上的某个中间节点）。
在循环中，通过比较 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 简化插入逻辑，避免区分左/右子树。
循环遍历红黑树，逐层比较键值，直到找到插入位置。
通过迭代而非递归实现，减少函数调用开销，提升性能。
- n = (ngx_str_node_t *) node;
- t = (ngx_str_node_t *) temp;
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 和长度），减少高开销的字符串内容比较。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
