nginx数据结构之queue

ChianXu 发表于 2011-12-22 08:54

<DIV>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成员，有点像继承，其实是组合，组合优于继承！ 
<DIV><IMG style="MARGIN: 0pt 10px 0pt 0pt" alt="nginx的数据结构(3) 队列ngx_queue_s - hankjin - 云水居" src="http://img.ph.126.net/X0JOadhePkhf5UxKVHKUfw==/3715188217604423853.png" __1312281576390__="ev_5298548970"></DIV>  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</DIV>
<DIV> </DIV>
<DIV>本文摘自：<a href="http://hankjin.blog.163.com/blog/static/33731937201091293749946/" target="_blank">http://hankjin.blog.163.com/blog/static/33731937201091293749946/</A>感谢作者的辛勤成果</DIV>

页: [1]

Chinaunix's Archiver

nginx数据结构之queue