注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

nginx的数据结构(3) 队列ngx_queue_s  

2010-10-12 09:52:11|  分类: Network |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
nginx 的队列定义在 core/ngx_queue.h中
struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};
首先这个队列很奇怪,因为它只有上一元素与下一元素的指针,却没有数据的结构成员。
那么它是如何存储与取得队列节点中的数据呢?看core/ngx_queue.h中的定义:
#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))
其实ngx_queue只是一个幌子,真正存储在队列中的元素是包含ngx_queue成员的结构。换句话说:如果一个结构想使用队列的方式存储,那么这个结构就要包含ngx_queue成员。

offset
这里用到了C语言的一个技巧:offsetof 函数:根据结构的成员的指针定位结构的指针:理解了这个,ngx_queue 就明白了。
例如
struct x_s{
 int a;
 int b;
} x;
则 &x.b = &x + (&x.b - &x) = &x + offsetof(struct x_s, b);
所以只要一个结构里有ngx_queue成员,就可以根据ngx_queue成员的指针获得这个结构的指针。
如http/ngx_http_cache.h中的ngx_http_file_cache_node_t结构,包含一个ngx_queue的成员queue,然后在http/ngx_http_file_cache.c文件中采用这种方法从队列中获取结构:
ngx_http_file_cache_node_t *fcn = ngx_queue_data(q, ngx_http_file_cache_node_t, queue);
根据上面的ngx_queue_data的定义: type=ngx_http_file_cache_node_t, offset=queue,所以可以展开为:
ngx_http_file_cache_node_t *fcn =
(ngx_http_file_cache_node_t*) ((u_char*)q - offset(ngx_http_file_cache_node_t, queue));
ngx_http_file_cache_node结构如下所示:
+-------+---------+----+
| node | queue | ...  |
+-------+---------+----+
结构的起始指针 = queue的起始位置 - queue在结构内的偏移.

nginx 的一个四节点的队列 ngx_queue 如下所示:
1的next指向2,2的next指向3,3的next指向4,4的next指向1
2的prev指向1,3的prev指向2,4的prev指向3,1的prev指向4
每个要使用队列存储的结构必须包含ngx_queue成员,有点像继承,其实是组合,组合优于继承!
nginx的数据结构(3) 队列ngx_queue_s - hankjin - 云水居
 
nginx 的队列基本操作和传统队列没有什么区别,基本都用宏的方式定义在core/ngx_queue.h中,与众不同的操作有两个,定义在core/ngx_queue.c中:
取队列中间元素:
从ngx_queue的定义可以看出,nginx 的队列设计非常简单,没有存储队列的长度信息。所以要取得队列中间的一个元素,最简单的方法是:先遍历队列计算出队列长度n,然后再从队列头走n/2步,就找到队列中间的元素了。算法复杂度为O(n)+O(n/2)=O(3n/2)
但 nginx 没有采取这种方式,而是用了两个指针,一个步长为1,另一个步长为2,同时向前移动,当步长为2的指针到达队列末尾的时候,步长为1的指针刚好在队列的开头。
算法复杂度也是O(n)+(n/2)=O(3n/2)
但它的优点有两个,一是局部性较好,二是代码比较优雅。一个循环比两个循环看起来好看一些:)。
代码见core/ngx_queue.c的ngx_queue_middle函数:
    middle = ngx_queue_head(queue);  //步长为1的指针m
    next = ngx_queue_head(queue);      //步长为2的指针n
    for ( ;; ) {//遍历队列
        middle = ngx_queue_next(middle);    //m走一步
        next = ngx_queue_next(next);            //n走一步
        if (next == ngx_queue_last(queue)) {
            return middle;//n到头了
        }  
        next = ngx_queue_next(next);           //n再走一步
        if (next == ngx_queue_last(queue)) {
            return middle;//n到头了
        }  
    }  

队列排序:

排序算法主要有插入,选择,快排,堆排等,考虑到队列没有随机访问能力的问题,使用插入排序是队列排序的一个较好的选择,而 nginx 也确实选用了这种方法:
从队列的第2个节点开始,针对每个节点,先从队列里拿出来,然后再向前找适当的位置,再插入。
代码见core/ngx_queue.c的ngx_queue_sort函数:
    q = ngx_queue_head(queue);
    for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { //2-n
        prev = ngx_queue_prev(q); //记录前一个节点
        next = ngx_queue_next(q);  //记录后一个节点
        ngx_queue_remove(q);       //1。先把当前节点从队列中取出
        do {   //2。向前查找,找到插入的位置(即比当前节点小的节点)
            if (cmp(prev, q) <= 0)  break;
            prev = ngx_queue_prev(prev);
        } while (prev != ngx_queue_sentinel(queue));
        ngx_queue_insert_after(prev, q);//3。插入当前节点。。
    }
}
例如
有一个int 队列:
2 3 5 8 4 6 9
进行到第5个元素4时,首先将4从中取出,
2 3 5 8 6 9
然后向前查,8-5-3,发现3比4小,则在3后面插入4
2 3 4 5 8 6 9
接着处理下一个节点6
  评论这张
 
阅读(1534)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017