菜鸟nginx源码剖析数据结构篇(四)红黑树ngx_rbtree_t

  • Author:Echo Chen(陈斌)
  • Email:[email protected]
  • Blog:Blog.csdn.net/chen19870707
  • Date:October 27h, 2014

    1.ngx_rbtree优势和特点

    ngx_rbtree是一种使用红黑树实现的关联容器,关于红黑树的特性,在《手把手实现红黑树》已经详细介绍,这里就只探讨ngx_rbtree与众不同的地方;ngx_rbtree红黑树容器中的元素都是有序的,支持快速索引,插入,删除操作,也支持范围查询,遍历操作,应用非常广泛。

    2.源代码位置

    头文件:http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_rbtree.h

    源文件:http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_rbtree.c

    3.数据结构定义

    可以看到ngx_rbtree的结点ngx_rbtree_node_t结构跟一般的红黑树差不多,都是由键值key、左孩子left、右孩子right、父亲结点parent、颜色值color,不同的是ngx_rbtree_node_t这里多了一个data,但根据官方文档记在,由于data只有一个字节,表示太少,很少使用到

       1: typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;
       2:  
       3: struct ngx_rbtree_node_s {
       4:     ngx_rbtree_key_t       key;
       5:     ngx_rbtree_node_t     *left;
       6:     ngx_rbtree_node_t     *right;
       7:     ngx_rbtree_node_t     *parent;
       8:     u_char                 color;
       9:     u_char                 data;
      10: };

    ngx_rbtree_t的结构也与一般红黑树相同,右root结点和哨兵叶子结点(sentinel)组成,不同的是这里多了一个 函数指针inserter,它决定了在添加结点是新加还是替换。

       1: typedef struct ngx_rbtree_s  ngx_rbtree_t;
       2:  
       3: typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
       4:     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
       5:  
       6: struct ngx_rbtree_s {
       7:     ngx_rbtree_node_t     *root;
       8:     ngx_rbtree_node_t     *sentinel;
       9:     ngx_rbtree_insert_pt   insert;
      10: };

    4.ngx_rbtree初始化 ngx_rbtree_init

    其中tree为ngx_rbtree_t类型,即为红黑树,s为ngx_rbtree_node_t,是rbtree的根节点,i即为上节提到的决定插入是新结点还是替换的函数指针。首先将根节点涂成 黑色(红黑树基本性质),然后把 红黑树的 根节点和 哨兵结点 都指向这个结点。

       1: #define ngx_rbtree_init(tree, s, i)                                           \
       2:     ngx_rbtree_sentinel_init(s);                                              \
       3:     (tree)->root = s;                                                         \
       4:     (tree)->sentinel = s;                                                     \
       5:     (tree)->insert = i
       6:  
       7: #define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)

    5.ngx_rbtree 左旋 ngx_rbtree_left_rotate 和 右旋 ngx_rbtree_right_rotate

    可以看到,经典代码总是永恒的,ngx_rbtree的左旋右旋也是参考《算法导论》导论中的步骤和伪代码,对照我自己的实现的《手把手实现红黑树》,与我自己实现的左旋右旋代码基本一致,我图解了详细的过程,有不清楚的可以参考《手把手实现红黑树》。

       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: }
       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: }

    6.ngx_rbtree插入 ngx_rbtree_insert

    ngx_rbtree_insert也是分为两步,插入和调整,由于这两项都在《手把手实现红黑树》中做了详细解释,这里就不在啰嗦,这里值得一提的是,还记得node_rbtree_t
    结构中的insert指针吗?这里就是通过这个函数指针来实现的插入。一个小小的技巧就实现了多态;并且它给出了 唯一值和时间类型的key 插入方法,可以满足一般需求,用户也可以实现自己的插入方法。

    void
    ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
        ngx_rbtree_node_t *node)
    {
        ngx_rbtree_node_t  **root, *temp, *sentinel;
    
        /* a binary tree insert */
    
        root = (ngx_rbtree_node_t **) &tree->root;
        sentinel = tree->sentinel;
    
        if (*root == sentinel) {
            node->parent = NULL;
            node->left = sentinel;
            node->right = sentinel;
            ngx_rbt_black(node);
            *root = node;
    
            return;
        }
    
        tree->insert(*root, node, sentinel);
    
        /* re-balance tree */
    
        while (node != *root && ngx_rbt_is_red(node->parent)) {
    
            if (node->parent == node->parent->parent->left) {
                temp = node->parent->parent->right;
    
                if (ngx_rbt_is_red(temp)) {
                    ngx_rbt_black(node->parent);
                    ngx_rbt_black(temp);
                    ngx_rbt_red(node->parent->parent);
                    node = node->parent->parent;
    
                } else {
                    if (node == node->parent->right) {
                        node = node->parent;
                        ngx_rbtree_left_rotate(root, sentinel, node);
                    }
    
                    ngx_rbt_black(node->parent);
                    ngx_rbt_red(node->parent->parent);
                    ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
                }
    
            } else {
                temp = node->parent->parent->left;
    
                if (ngx_rbt_is_red(temp)) {
                    ngx_rbt_black(node->parent);
                    ngx_rbt_black(temp);
                    ngx_rbt_red(node->parent->parent);
                    node = node->parent->parent;
    
                } else {
                    if (node == node->parent->left) {
                        node = node->parent;
                        ngx_rbtree_right_rotate(root, sentinel, node);
                    }
    
                    ngx_rbt_black(node->parent);
                    ngx_rbt_red(node->parent->parent);
                    ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
                }
            }
        }
    
        ngx_rbt_black(*root);
    }
    

    6.1 唯一值类型插入

    这个即为一般红黑树的插入方法,循环,如果插入的值比当前节点小,就进入左子树,否则进入右子树,直至遇到叶子结点,叶子节点就是要链入红黑树的位置。

       1: void
       2: ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
       3:     ngx_rbtree_node_t *sentinel)
       4: {
       5:     ngx_rbtree_node_t  **p;
       6:  
       7:     for ( ;; ) {
       8:  
       9:         p = (node->key < temp->key) ? &temp->left : &temp->right;
      10:  
      11:         if (*p == sentinel) {
      12:             break;
      13:         }
      14:  
      15:         temp = *p;
      16:     }
      17:  
      18:     *p = node;
      19:     node->parent = temp;
      20:     node->left = sentinel;
      21:     node->right = sentinel;
      22:     ngx_rbt_red(node);
      23: }

    如果有相等的结点,会直接被覆盖,如上图插入key为2的结点,则当tmp 为2的结点时,p为叶子遍历结束,这样p就会被覆盖为新的值。

    6.2 唯一时间类型插入

    唯一区别就是判断大小时,采用了两个值相减,避免溢出。

       1: typedef ngx_int_t   ngx_rbtree_key_int_t;
       2: void
       3: ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
       4:     ngx_rbtree_node_t *sentinel)
       5: {
       6:     ngx_rbtree_node_t  **p;
       7:  
       8:     for ( ;; ) {
       9:  
      10:         /*
      11:          * Timer values
      12:          * 1) are spread in small range, usually several minutes,
      13:          * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
      14:          * The comparison takes into account that overflow.
      15:          */
      16:  
      17:         /*  node->key < temp->key */
      18:  
      19:         p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
      20:             ? &temp->left : &temp->right;
      21:  
      22:         if (*p == sentinel) {
      23:             break;
      24:         }
      25:  
      26:         temp = *p;
      27:     }
      28:  
      29:     *p = node;
      30:     node->parent = temp;
      31:     node->left = sentinel;
      32:     node->right = sentinel;
      33:     ngx_rbt_red(node);
      34: }

    7.ngx_rbtree删除ngx_rbtree_delete

    也是按照《算法导论》上的步骤,先删除后调整,在《手把手实现红黑树》已介绍,请参考

       1: void
       2: ngx_rbtree_delete_delete(ngx_thread_volatile ngx_rbtree_t *tree,
       3:     ngx_rbtree_node_t *node)
       4: {
       5:     ngx_uint_t           red;
       6:     ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
       7:  
       8:     /* a binary tree delete */
       9:  
      10:     root = (ngx_rbtree_node_t **) &tree->root;
      11:     sentinel = tree->sentinel;
      12:  
      13:     if (node->left == sentinel) {
      14:         temp = node->right;
      15:         subst = node;
      16:  
      17:     } else if (node->right == sentinel) {
      18:         temp = node->left;
      19:         subst = node;
      20:  
      21:     } else {
      22:         subst = ngx_rbtree_min(node->right, sentinel);
      23:  
      24:         if (subst->left != sentinel) {
      25:             temp = subst->left;
      26:         } else {
      27:             temp = subst->right;
      28:         }
      29:     }
      30:  
      31:     if (subst == *root) {
      32:         *root = temp;
      33:         ngx_rbt_black(temp);
      34:  
      35:         /* DEBUG stuff */
      36:         node->left = NULL;
      37:         node->right = NULL;
      38:         node->parent = NULL;
      39:         node->key = 0;
      40:  
      41:         return;
      42:     }
      43:  
      44:     red = ngx_rbt_is_red(subst);
      45:  
      46:     if (subst == subst->parent->left) {
      47:         subst->parent->left = temp;
      48:  
      49:     } else {
      50:         subst->parent->right = temp;
      51:     }
      52:  
      53:     if (subst == node) {
      54:  
      55:         temp->parent = subst->parent;
      56:  
      57:     } else {
      58:  
      59:         if (subst->parent == node) {
      60:             temp->parent = subst;
      61:  
      62:         } else {
      63:             temp->parent = subst->parent;
      64:         }
      65:  
      66:         subst->left = node->left;
      67:         subst->right = node->right;
      68:         subst->parent = node->parent;
      69:         ngx_rbt_copy_color(subst, node);
      70:  
      71:         if (node == *root) {
      72:             *root = subst;
      73:  
      74:         } else {
      75:             if (node == node->parent->left) {
      76:                 node->parent->left = subst;
      77:             } else {
      78:                 node->parent->right = subst;
      79:             }
      80:         }
      81:  
      82:         if (subst->left != sentinel) {
      83:             subst->left->parent = subst;
      84:         }
      85:  
      86:         if (subst->right != sentinel) {
      87:             subst->right->parent = subst;
      88:         }
      89:     }
      90:  
      91:     /* DEBUG stuff */
      92:     node->left = NULL;
      93:     node->right = NULL;
      94:     node->parent = NULL;
      95:     node->key = 0;
      96:  
      97:     if (red) {
      98:         return;
      99:     }
     100:  
     101:     /* a delete fixup */
     102:  
     103:     while (temp != *root && ngx_rbt_is_black(temp)) {
     104:  
     105:         if (temp == temp->parent->left) {
     106:             w = temp->parent->right;
     107:  
     108:             if (ngx_rbt_is_red(w)) {
     109:                 ngx_rbt_black(w);
     110:                 ngx_rbt_red(temp->parent);
     111:                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
     112:                 w = temp->parent->right;
     113:             }
     114:  
     115:             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
     116:                 ngx_rbt_red(w);
     117:                 temp = temp->parent;
     118:  
     119:             } else {
     120:                 if (ngx_rbt_is_black(w->right)) {
     121:                     ngx_rbt_black(w->left);
     122:                     ngx_rbt_red(w);
     123:                     ngx_rbtree_right_rotate(root, sentinel, w);
     124:                     w = temp->parent->right;
     125:                 }
     126:  
     127:                 ngx_rbt_copy_color(w, temp->parent);
     128:                 ngx_rbt_black(temp->parent);
     129:                 ngx_rbt_black(w->right);
     130:                 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
     131:                 temp = *root;
     132:             }
     133:  
     134:         } else {
     135:             w = temp->parent->left;
     136:  
     137:             if (ngx_rbt_is_red(w)) {
     138:                 ngx_rbt_black(w);
     139:                 ngx_rbt_red(temp->parent);
     140:                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
     141:                 w = temp->parent->left;
     142:             }
     143:  
     144:             if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
     145:                 ngx_rbt_red(w);
     146:                 temp = temp->parent;
     147:  
     148:             } else {
     149:                 if (ngx_rbt_is_black(w->left)) {
     150:                     ngx_rbt_black(w->right);
     151:                     ngx_rbt_red(w);
     152:                     ngx_rbtree_left_rotate(root, sentinel, w);
     153:                     w = temp->parent->left;
     154:                 }
     155:  
     156:                 ngx_rbt_copy_color(w, temp->parent);
     157:                 ngx_rbt_black(temp->parent);
     158:                 ngx_rbt_black(w->left);
     159:                 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
     160:                 temp = *root;
     161:             }
     162:         }
     163:     }
     164:  
     165:     ngx_rbt_black(temp);
     166: }

    8.实战

    由于ngx_rbtree_t未牵涉到内存池,所以非常容易抽出来使用,如下为实现了插入、打印最小值、删除的例子

       1: #include <iostream>
       2: #include <algorithm>
       3: #include <pthread.h>
       4: #include <time.h>
       5: #include <stdio.h>
       6: #include <errno.h>
       7: #include <string.h>
       8: #include "ngx_queue.h"
       9: #include "ngx_rbtree.h"
      10:  
      11:  
      12: int main()
      13: {
      14:  
      15:     ngx_rbtree_t tree;
      16:     ngx_rbtree_node_t sentinel;
      17:  
      18:     ngx_rbtree_init(&tree,&sentinel,ngx_rbtree_insert_value);
      19:  
      20:     ngx_rbtree_node_t *rbnode = new ngx_rbtree_node_t[100];
      21:     for(int i = 99; i >= 0 ;i--)
      22:     {
      23:         rbnode[i].key = i;
      24:         rbnode[i].parent = NULL;
      25:         rbnode[i].left = NULL;
      26:         rbnode[i].right = NULL;
      27:         ngx_rbtree_insert(&tree,&rbnode[i]);
      28:     }
      29:  
      30:     for(int i = 0; i < 100;i++)
      31:     {
      32:          ngx_rbtree_node_t *p = ngx_rbtree_min(tree.root,&sentinel);
      33:          std::cout << p->key << "  ";
      34:          ngx_rbtree_delete(&tree,p);
      35:      }
      36:  
      37:  
      38:     delete[] rbnode;
      39:  
      40:     return 0;
      41: }

    运行结果:

    -

    Echo Chen:Blog.csdn.net/chen19870707

    -

  • 时间: 10-26

    菜鸟nginx源码剖析数据结构篇(四)红黑树ngx_rbtree_t的相关文章

    菜鸟nginx源码剖析数据结构篇(六) 哈希表 ngx_hash_t(上)

    Author:Echo Chen(陈斌) Email:[email protected] Blog:Blog.csdn.net/chen19870707 Date:October 31h, 2014 1.哈希表ngx_hash_t的优势和特点 哈希表是一种典型的以空间换取时间的数据结构,在没有冲突的情况下,对任意元素的插入.索引.删除的时间复杂度都是O(1).这样优秀的时间复杂度是通过将元素的key值以hash方法f映射到哈希表中的某一个位置来访问记录来实现的,即键值为key的元素必定存储在哈希

    菜鸟nginx源码剖析数据结构篇(九) 内存池ngx_pool_t[转]

    菜鸟nginx源码剖析数据结构篇(九) 内存池ngx_pool_t Author:Echo Chen(陈斌) Email:[email protected] Blog:Blog.csdn.net/chen19870707 Date:Nov 11th, 2014 今天是一年一度的光棍节,还没有女朋友的程序猿童鞋不妨new一个出来,内存管理一直是C/C++中最棘手的部分,远不止new/delete.malloc/free这么简单.随着代码量的递增,程序结构复杂度的提高.今天我们就一起研究一下以精巧著

    菜鸟nginx源码剖析数据结构篇(十一) 共享内存ngx_shm_t[转]

    菜鸟nginx源码剖析数据结构篇(十一) 共享内存ngx_shm_t Author:Echo Chen(陈斌) Email:[email protected] Blog:Blog.csdn.net/chen19870707 Date:Nov 14th, 2014 1.共享内存 共享内存是Linux下提供的最基本的进程通信方法,它通过mmap或者shmget系统调用在内存中创建了一块连续的线性地址空间,而通过munmap或者shmdt系统调用释放这块内存,使用共享内存的好处是多个进程使用同一块内存

    菜鸟nginx源码剖析数据结构篇(八) 缓冲区链表ngx_chain_t[转]

    菜鸟nginx源码剖析数据结构篇(八) 缓冲区链表 ngx_chain_t Author:Echo Chen(陈斌) Email:[email protected] Blog:Blog.csdn.net/chen19870707 Date:Nov 6th, 2014 1.缓冲区链表结构ngx_chain_t和ngx_buf_t nginx的缓冲区链表如下图所示,ngx_chain_t为链表,ngx_buf_t为缓冲区结点: 2.源代码位置 头文件:http://trac.nginx.org/ng

    菜鸟nginx源码剖析数据结构篇(九) 内存池ngx_pool_t

    1.源代码位置 头文件:http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_palloc.h 源文件:http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_palloc.c 2.数据结构定义 先来学习一下nginx内存池的几个主要数据结构:     ngx_pool_data_t(内存池数据块结构) 1: typedef struct { 2:     u_char         

    菜鸟nginx源码剖析数据结构篇(十) 自旋锁ngx_spinlock

    Author:Echo Chen(陈斌) Email:[email protected] Blog:Blog.csdn.net/chen19870707 Date:Nov 11th, 2014 自旋锁(Spinlock)是一种 Linux 内核中广泛运用的底层同步机制.自旋锁是一种工作于多处理器环境的特殊的锁,在单处理环境中自旋锁的操作被替换为空操作.当某个处理器上的内核执行线程申请自旋锁时,如果锁可用,则获得锁,然后执行临界区操作,最后释放锁:如果锁已被占用,线程并不会转入睡眠状态,而是忙等待

    菜鸟nginx源码剖析 框架篇(一) 从main函数看nginx启动流程(转)

    俗话说的好,牵牛要牵牛鼻子 驾车顶牛,处理复杂的东西,只要抓住重点,才能理清脉络,不至于深陷其中,不能自拔.对复杂的nginx而言,main函数就是“牛之鼻”,只要能理清main函数,就一定能理解其中的奥秘,下面我们就一起来研究一下nginx的main函数. 1.nginx的main函数解读 nginx启动显然是由main函数驱动的,main函数在在core/nginx.c文件中,其源代码解析如下,涉及到的数据结构在本节仅指出其作用,将在第二节中详细解释. nginx main函数的流程图如下:

    菜鸟nginx源代码剖析数据结构篇(八) 缓冲区链表ngx_chain_t

    菜鸟nginx源代码剖析数据结构篇(八) 缓冲区链表 ngx_chain_t Author:Echo Chen(陈斌) Email:[email protected]mail.com Blog:Blog.csdn.net/chen19870707 Date:Nov 6th, 2014 1.缓冲区链表结构ngx_chain_t和ngx_buf_t nginx的缓冲区链表例如以下图所看到的.ngx_chain_t为链表.ngx_buf_t为缓冲区结点: 2.源码位置 头文件:http://trac.

    SpringMVC源码剖析(四)- DispatcherServlet请求转发的实现

    SpringMVC完成初始化流程之后,就进入Servlet标准生命周期的第二个阶段,即“service”阶段.在“service”阶段中,每一次Http请求到来,容器都会启动一个请求线程,通过service()方法,委派到doGet()或者doPost()这些方法,完成Http请求的处理. 在初始化流程中,SpringMVC巧妙的运用依赖注入读取参数,并最终建立一个与容器上下文相关联的spring子上下文.这个子上下文,就像Struts2中xwork容器一样,为接下来的Http处理流程中各种编程