Chinaunix首页 | 论坛 | 博客
  • 博客访问: 805264
  • 博文数量: 77
  • 博客积分: 821
  • 博客等级: 军士长
  • 技术积分: 1904
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-23 16:17
个人简介

学校:上海交通大学软件工程 学历:硕士 行业:从事流媒体移动开发 QQ: 412595942 邮箱:yiikai1987910@gmail.com

文章分类

全部博文(77)

文章存档

2016年(4)

2015年(15)

2014年(16)

2013年(12)

2012年(21)

2011年(9)

分类: C/C++

2016-11-10 10:56:13

 红黑数的性质这里就不多说了网上很多,主要看看nginx是如何定义的rbtree和怎么使用它

      

[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. rbtree = ngx_slab_alloc(shpool, sizeof(ngx_rbtree_t));   //从共享内存中创建一颗红黑树  
  2.   
  3. sentinel = ngx_slab_alloc(shpool, sizeof(ngx_rbtree_node_t));   //创建了一个红黑树的节点作为哨兵节点  
  4.   
  5. ngx_rbtree_init(ctx->rbtree, ctx->sentinel, ngx_http_srs_hook_rbtree_insert_value); //初始化这颗红黑树  


主要看下ngx_rbtree_init的实现:


[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  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  

关键的就是参数i,这个是个函数指针,作为红黑树的插入节点时候的算法,这个需要用户自己实现



[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,  
  2.     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);  

第二个参数就是需要插入的节点数据,第三个参数是哨兵节点


接下去看下怎么实现这个插入函数(ps: nginx很多模块中已经有了rbtree插入的实现,我也是参考写的)


[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. static void   
  2. ngx_http_srs_hook_rbtree_insert_value(ngx_rbtree_node_t *temp,   ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) {  
  3.   
  4.     ngx_rbtree_node_t           **p;  
  5.     p = NULL;  
  6.     if(node == NULL) {  
  7.         return;  
  8.     }  
  9.     for ( ;; ) {  
  10.   
  11.         if (node->key < temp->key) {  
  12.   
  13.             p = &temp->left;  
  14.   
  15.         } else if (node->key > temp->key) {  
  16.   
  17.             p = &temp->right;  
  18.   
  19.         } else { /* node->key == temp->key */  
  20.   
  21.             break;  //目前的实现不支持相同的key的节点  
  22.         }  
  23.   
  24.         if (*p == sentinel) {  
  25.             break;  
  26.         }  
  27.   
  28.         temp = *p;  
  29.     }  
  30.   
  31.     *p = node;  
  32.     node->parent = temp;  
  33.     node->left = sentinel;  
  34.     node->right = sentinel;  
  35.     ngx_rbt_red(node);      //最后就是要让插入的节点是红色的(这是红黑树的性质)  
  36.        
  37. }  

对于使用者只需要负责插入的算法, 对于红黑数的反转等问题nginx都为大家做了



现在看看怎么进行节点的插入的


[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. typedef struct{                
  2.     ngx_rbtree_node_t node;  
  3.     void *data;  
  4. }channel;     //定义的红黑树节点  
  5.   
  6. channel findchannel;  
  7. ngx_rbtree_insert(srshookctx->rbtree,&(findchannel->node));  

看下ngx_rbtree_insert的实现:



[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)  
  2. {  
  3.     ngx_rbtree_node_t  **root, *temp, *sentinel;  
  4.   
  5.     /* a binary tree insert */  
  6.   
  7.     root = (ngx_rbtree_node_t **) &tree->root;  
  8.     sentinel = tree->sentinel;  
  9.   
  10.     if (*root == sentinel) {  
  11.         node->parent = NULL;  
  12.         node->left = sentinel;  
  13.         node->right = sentinel;  
  14.         ngx_rbt_black(node);  
  15.         *root = node;  
  16.   
  17.         return;  
  18.     }  
  19.   
  20.     tree->insert(*root, node, sentinel);     //这里就调用了我们之前设定的插入算法的函数  
  21.   
  22.     /* re-balance tree */                    //数据插入之后, nginx就为我们做了很复杂的红黑树的翻转来保持树的平衡  
  23.   
  24.     while (node != *root && ngx_rbt_is_red(node->parent)) {  
  25.   
  26.         if (node->parent == node->parent->parent->left) {  
  27.             temp = node->parent->parent->right;  
  28.   
  29.             if (ngx_rbt_is_red(temp)) {  
  30.                 ngx_rbt_black(node->parent);  
  31.                 ngx_rbt_black(temp);  
  32.                 ngx_rbt_red(node->parent->parent);  
  33.                 node = node->parent->parent;  
  34.   
  35.             } else {  
  36.                 if (node == node->parent->right) {  
  37.                     node = node->parent;  
  38.                     ngx_rbtree_left_rotate(root, sentinel, node);  
  39.                 }  
  40.   
  41.                 ngx_rbt_black(node->parent);  
  42.                 ngx_rbt_red(node->parent->parent);  
  43.                 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);  
  44.             }  
  45.   
  46.         } else {  
  47.             temp = node->parent->parent->left;  
  48.   
  49.             if (ngx_rbt_is_red(temp)) {  
  50.                 ngx_rbt_black(node->parent);  
  51.                 ngx_rbt_black(temp);  
  52.                 ngx_rbt_red(node->parent->parent);  
  53.                 node = node->parent->parent;  
  54.   
  55.             } else {  
  56.                 if (node == node->parent->left) {  
  57.                     node = node->parent;  
  58.                     ngx_rbtree_right_rotate(root, sentinel, node);  
  59.                 }  
  60.   
  61.                 ngx_rbt_black(node->parent);  
  62.                 ngx_rbt_red(node->parent->parent);  
  63.                 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);  
  64.             }  
  65.         }  
  66.     }  
  67.   
  68.     ngx_rbt_black(*root);  
  69. }  

这样红黑数的插入就完成了,那如何来查找树里的节点呢?这里我实现了一个查找节点的函数



[cpp] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. static requestchannel_st*  
  2. ngx_http_channel_tree_lookup(ngx_http_srs_hook_ctx_t *srsctx, uint64_t key)  
  3. {  
  4.     ngx_rbtree_key_t             node_key;  
  5.     ngx_rbtree_node_t           *node;  
  6.     ngx_rbtree_node_t           *sentinel;  
  7.     requestchannel_st                  *fcn;  
  8.   
  9.     node_key = key;  
  10.   
  11.     node = srsctx->rbtree->root;      //这里记录下要查找的树的根节点  
  12.     sentinel = srsctx->rbtree->sentinel;  //记录下哨兵节点  
  13.   
  14.     while (node != sentinel) {  
  15.   
  16.         if (node_key < node->key) {       //通过左右子树查找key一样的节点  
  17.             node = node->left;  
  18.             continue;  
  19.         }  
  20.   
  21.         if (node_key > node->key) {  
  22.             node = node->right;  
  23.             continue;  
  24.         }  
  25.   
  26.         /* node_key == node->key */  
  27.   
  28.         fcn = (requestchannel_st *) node;    //找到节点就转成节点数据结构,返回  
  29.   
  30.         return fcn;  
  31.     }  
  32.   
  33.     /* not found */  
  34.   
  35.     return NULL;  
  36. }  
阅读(1684) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册