• Nginx源码解析 --红黑树

    预读知识

    红黑树是一种自平衡二叉树，不仅可以使用二分法快速查找，而且插入和删除操作的效率也很高，常用于构造关联数组（例如C++标准库里的set和 map)。

    在Nginx里红黑树主要用在事件机制里的定时器，检查连接超时，此外还在reslover、cache里用于快速查找。

     红黑树概要_编程界的谢菲尔德的博客-CSDN博客

    1. 节点不是黑色，就是红色（非黑即红）
    2. 根节点为黑色
    3. 叶节点为黑色（叶节点是指末梢的空节点 Nil或Null）
    4. 一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）
    5. 每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）

    基本数据结构

    1. typedef ngx_uint_t  ngx_rbtree_key_t;
    2. typedef ngx_int_t   ngx_rbtree_key_int_t;
    3.  
    4.  
    5. typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;
    6.  
    7. struct ngx_rbtree_node_s {
    8.     ngx_rbtree_key_t       key;
    9.     ngx_rbtree_node_t     *left;
    10.     ngx_rbtree_node_t     *right;
    11.     ngx_rbtree_node_t     *parent;
    12.     u_char                 color;
    13.     u_char                 data;
    14. };
    15.  
    16.  
    17. typedef struct ngx_rbtree_s  ngx_rbtree_t;
    18.  
    19. typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    20.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
    21.  
    22. struct ngx_rbtree_s {
    23.     ngx_rbtree_node_t     *root;
    24.     ngx_rbtree_node_t     *sentinel;
    25.     ngx_rbtree_insert_pt   insert;
    26. };
    27.

    结构定义

    1.

    typedef ngx_uint_t  ngx_rbtree_key_t;                 //无符号
    typedef ngx_int_t   ngx_rbtree_key_int_t;           //有符号

    2结点                                           //侵入容器

    ngx_rbtree_key_t         key;       //红黑树的键 用于排序比较

     ngx_rbtree_node_t     *left;      //左指针
     ngx_rbtree_node_t     *right;    //右指针
     ngx_rbtree_node_t     *parent; //父结点
     u_char                          color;    // 1代表 0代表 黑色
     u_char                          data;     // 无意义

    3 树                                            

     ngx_rbtree_node_t     *root;           //红黑树的根节点：           
     ngx_rbtree_node_t     *sentinel;     //红黑树的哨兵节点，用于简化实现，它总是黑色的；
     ngx_rbtree_insert_pt   insert;         //节点的插入方法，允许对特殊节点定制特殊插入方法

    4. 内存布局

     

    2.操作函数

    1.初始化（红为一  黑为0 同时也代表 正负）

    1.  
    2. #define ngx_rbt_red(node)               ((node)->color = 1)
    3. #define ngx_rbt_black(node)             ((node)->color = 0)
    4. #define ngx_rbt_is_red(node)            ((node)->color)
    5. #define ngx_rbt_is_black(node)          (!ngx_rbt_is_red(node))
    6. #define ngx_rbt_copy_color(n1, n2)      (n1->color = n2->color)
    7.  
    8.  
    9. #define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)
    10.  
    11.  
    12. #define ngx_rbtree_init(tree, s, i)                                           \
    13.     ngx_rbtree_sentinel_init(s);                                              \
    14.     (tree)->root = s;                                                         \
    15.     (tree)->sentinel = s;                                                     \
    16.     (tree)->insert = i
    ngx_rbtree_init实际上是一个宏，初始化后红黑树里仅有一个哨兵节点s，它同时也是根节点。

    2.辅助函数 （旋转函数）（个人建议 直接看红黑树概要_编程界的谢菲尔德的博客-CSDN博客）

    1.左旋

    1. static ngx_inline void
    2. ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    3.     ngx_rbtree_node_t *node)
    4. {
    5.     ngx_rbtree_node_t  *temp;
    6.  
    7.     temp = node->right;
    8.     node->right = temp->left;
    9.  
    10.     if (temp->left != sentinel) {
    11.         temp->left->parent = node;
    12.     }
    13.  
    14.     temp->parent = node->parent;
    15.  
    16.     if (node == *root) {
    17.         *root = temp;
    18.  
    19.     } else if (node == node->parent->left) {
    20.         node->parent->left = temp;
    21.  
    22.     } else {
    23.         node->parent->right = temp;
    24.     }
    25.  
    26.     temp->left = node;
    27.     node->parent = temp;
    28. }

    2.右旋

    1. static ngx_inline void
    2. ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
    3.     ngx_rbtree_node_t *node)
    4. {
    5.     ngx_rbtree_node_t  *temp;
    6.  
    7.     temp = node->left;
    8.     node->left = temp->right;
    9.  
    10.     if (temp->right != sentinel) {
    11.         temp->right->parent = node;
    12.     }
    13.  
    14.     temp->parent = node->parent;
    15.  
    16.     if (node == *root) {
    17.         *root = temp;
    18.  
    19.     } else if (node == node->parent->right) {
    20.         node->parent->right = temp;
    21.  
    22.     } else {
    23.         node->parent->left = temp;
    24.     }
    25.  
    26.     temp->right = node;
    27.     node->parent = temp;
    28. }

    3.删除

    1. void
    2. ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
    3. {
    4.     ngx_uint_t           red;
    5.     ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
    6.  
    7.     /* a binary tree delete */
    8.  
    9.     root = &tree->root;
    10.     sentinel = tree->sentinel;
    11.  
    12.     if (node->left == sentinel) {
    13.         temp = node->right;
    14.         subst = node;
    15.  
    16.     } else if (node->right == sentinel) {
    17.         temp = node->left;
    18.         subst = node;
    19.  
    20.     } else {
    21.         subst = ngx_rbtree_min(node->right, sentinel);
    22.  
    23.         if (subst->left != sentinel) {
    24.             temp = subst->left;
    25.         } else {
    26.             temp = subst->right;
    27.         }
    28.     }
    29. if (subst == *root) {
    30.         *root = temp;
    31.         ngx_rbt_black(temp);
    32.  
    33.         /* DEBUG stuff */
    34.         node->left = NULL;
    35.         node->right = NULL;
    36.         node->parent = NULL;
    37.         node->key = 0;
    38.  
    39.         return;
    40.     }
    41.  
    42.     red = ngx_rbt_is_red(subst);
    43.  
    44.     if (subst == subst->parent->left) {
    45.         subst->parent->left = temp;
    46.  
    47.     } else {
    48.         subst->parent->right = temp;
    49.     }
    50.  
    51.     if (subst == node) {
    52.  
    53.         temp->parent = subst->parent;
    54.  
    55.     } else {
    56.  
    57.         if (subst->parent == node) {
    58.             temp->parent = subst;
    59.  
    60.         } else {
    61.             temp->parent = subst->parent;
    62.         }
    63.   subst->left = node->left;
    64.         subst->right = node->right;
    65.         subst->parent = node->parent;
    66.         ngx_rbt_copy_color(subst, node);
    67.  
    68.         if (node == *root) {
    69.             *root = subst;
    70.  
    71.         } else {
    72.             if (node == node->parent->left) {
    73.                 node->parent->left = subst;
    74.             } else {
    75.                 node->parent->right = subst;
    76.             }
    77.         }
    78.  
    79.         if (subst->left != sentinel) {
    80.             subst->left->parent = subst;
    81.         }
    82.  
    83.         if (subst->right != sentinel) {
    84.             subst->right->parent = subst;
    85.         }
    86.     }
    87.  
    88.     /* DEBUG stuff */
    89.     node->left = NULL;
    90.     node->right = NULL;
    91. node->parent = NULL;
    92.     node->key = 0;
    93.  
    94.     if (red) {
    95.         return;
    96.     }
    97.  
    98.     /* a delete fixup */
    99.  
    100.     while (temp != *root && ngx_rbt_is_black(temp)) {
    101.  
    102.         if (temp == temp->parent->left) {
    103.             w = temp->parent->right;
    104.  
    105.             if (ngx_rbt_is_red(w)) {
    106.                 ngx_rbt_black(w);
    107.                 ngx_rbt_red(temp->parent);
    108.                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
    109.                 w = temp->parent->right;
    110.             }
    111.  
    112.             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
    113.                 ngx_rbt_red(w);
    114.                 temp = temp->parent;
    115.  
    116.             } else {
    117.                 if (ngx_rbt_is_black(w->right)) {
    118.                     ngx_rbt_black(w->left);
    119.                     ngx_rbt_red(w);
    120.                     ngx_rbtree_right_rotate(root, sentinel, w);
    121.                     w = temp->parent->right;
    122.                 }
    123. .....
    124.                                                   
    125.  
    126.

    4.插入

    1.首先包装一个整的

    ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)

    2.分类

    2.1void  ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
        ngx_rbtree_node_t *sentinel)    //这个是一个数值插入

    2.2 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
        ngx_rbtree_node_t *sentinel)    定时器红黑树的专用插入函数，键值是毫秒值

    2.3 (字符串头文件里)

    void ngx str_rbtree_insert_value ngx_rbtree_node_t *temp ,

    ngx_rbtree_node_t *node , ngx_rbtree_node_t *sentinel);
    //字符串红黑树的专用插入函数，键值是字符串的hash值



     

  • 相关阅读:
    [SystemC]SystemC Hierarchical Channels
    MySQL：日志系统介绍 | 错误日志 | 查询日志 | 二进制日志：bin-log数据恢复实践 | 慢日志查询
    AUTOCAD——LEN命令
    Jmeter集成到jenkins
    【抓包分析】通过ChatGPT解密还原某软件登录算法实现绕过手机验证码登录
    单元测试框架-Pytest（简单学习）
    Redis介绍、安装与初体验
    unity 骨骼物理 头发 布料模拟
    SpringBoot
    前后端分离Vue+nodejs酒店公寓客房预订管理系统udr7l-java-php-django-springboot
  • 原文地址：https://blog.csdn.net/qq_62309585/article/details/128055303