Chinaunix首页 | 论坛 | 博客
  • 博客访问: 279123
  • 博文数量: 134
  • 博客积分: 667
  • 博客等级: 上士
  • 技术积分: 770
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-08 15:19
文章分类

全部博文(134)

文章存档

2012年(134)

分类: LINUX

2012-06-13 10:17:47

Content

0. 

1. 队列结构

2. 队列操作

2.1 在头节点之后插入

2.2 在尾节点之后插入

2.3 删除节点

2.4 分割队列

2.5 链接队列

2.6 获取中间节点

2.7 队列排序

2.8 如何获取队列节点数据

3. 一个例子

3.1代码

3.2如何编译

3.3 运行结果

4.小结


0. 


本文继续介绍nginx的数据结构——队列。

链表实现文件:文件:./src/core/ngx_queue.h/.c.表示nginx-1.0.4代码目录,本文为/usr/src/nginx-1.0.4


1.队列结构


nginx的队列是由具有头节点的双向循环链表实现的,每一个节点结构为ngx_queue_t,定义如下。


点击(此处)折叠或打开

  1. typedef struct ngx_queue_s ngx_queue_t;
  2. struct ngx_queue_s { //队列结构
  3.     ngx_queue_t *prev;
  4.     ngx_queue_t *next;
  5. };

其中,sizeof(ngx_queue_t)=8

从队列结构定义可以看出,nginx的队列结构里并没有其节点的数据内容。


2. 队列操作


队列有如下操作。


点击(此处)折叠或打开

  1. //初始化队列
  2. ngx_queue_init(q)
  3. //判断队列是否为空
  4. ngx_queue_empty(h)
  5. //在头节点之后插入新节点
  6. ngx_queue_insert_head(h, x)
  7. //在尾节点之后插入新节点
  8. ngx_queue_insert_tail(h, x)
  9. //删除节点x
  10. ngx_queue_remove(x)
  11. //分割队列
  12. ngx_queue_split(h, q, n)
  13. //链接队列
  14. ngx_queue_add(h, n)
  15. //获取队列的中间节点
  16. ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue)
  17. //排序队列(稳定的插入排序)
  18. void ngx_queue_sort(ngx_queue_t *queue,ngx_int_t (*cmp)(const ngx_queue_t*, const ngx_queue_t*))

其中,插入节点、取队列头、取队列尾等操作由宏实现,获取中间节点、排序等操作由函数实现。下面简单介绍。


2.1 在头节点之后插入


在头节点之后插入操作由宏ngx_queue_insert_head完成,如下。


点击(此处)折叠或打开

  1. #define ngx_queue_insert_head(h, x) \
  2.     (x)->next = (h)->next; \
  3.     (x)->next->prev = x; \
  4.     (x)->prev = h; \
  5.     (h)->next = x
画出该操作的逻辑图,如下。


图中虚线表示被修改/删除的指针,蓝色表示新修改/增加的指针。下同。


2.2在尾节点之后插入


在尾节点之后插入操作由宏ngx_queue_insert_tail完成,如下。


点击(此处)折叠或打开

  1. #define ngx_queue_insert_tail(h, x) \
  2.     (x)->prev = (h)->prev; \
  3.     (x)->prev->next = x; \
  4.     (x)->next = h; \
  5.     (h)->prev = x

该操作的逻辑图如下。



2.3 删除节点


在尾节点之后插入操作由宏ngx_queue_remove完成,如下。


点击(此处)折叠或打开

  1. #if (NGX_DEBUG)
  2. #define ngx_queue_remove(x) \
  3.     (x)->next->prev = (x)->prev; \
  4.     (x)->prev->next = (x)->next; \
  5.     (x)->prev = NULL; \
  6.     (x)->next = NULL
  7. #else
  8. #define ngx_queue_remove(x) \
  9.     (x)->next->prev = (x)->prev; \
  10.     (x)->prev->next = (x)->next
  11. #endif
该操作的逻辑图如下。


2.4 分割队列

分割队列操作由宏ngx_queue_split完成,如下。


点击(此处)折叠或打开

  1. #define ngx_queue_split(h, q, n) \
  2.     (n)->prev = (h)->prev; \
  3.     (n)->prev->next = n; \
  4.     (n)->next = q; \
  5.     (h)->prev = (q)->prev; \
  6.     (h)->prev->next = h; \
  7.     (q)->prev = n;
该宏有3个参数,h为队列头(即链表头指针),将该队列从q节点将队列(链表)分割为两个队列(链表)q之后的节点组成的新队列的头节点为n,图形演示如下。


2.5 链接队列

链接队列由宏ngx_queue_add完成,操作如下。


点击(此处)折叠或打开

  1. #define ngx_queue_add(h, n) \
  2.     (h)->prev->next = (n)->next; \
  3.     (n)->next->prev = (h)->prev; \
  4.     (h)->prev = (n)->prev; \
  5.     (h)->prev->next = h;
其中,hn分别为两个队列的指针,即头节点指针,该操作将n队列链接在h队列之后。演示图形如下。


ngx_queue_splitngx_queue_add只在http模块locations相关操作中使用,在后续的讨论http模块locations相关操作时再详细叙述。

2.6 获取中间节点

中间节点,若队列有奇数个(除头节点外)节点,则返回中间的节点;若队列有偶数个节点,则返回后半个队列的第一个节点。操作如下。


点击(此处)折叠或打开

  1. /*
  2.  * find the middle queue element if the queue has odd number of elements
  3.  * or the first element of the queue’s second part otherwise
  4.  */
  5. ngx_queue_t *
  6. ngx_queue_middle(ngx_queue_t *queue)
  7. {
  8.     ngx_queue_t *middle, *next;
  9.     middle = ngx_queue_head(queue);
  10.     if (middle == ngx_queue_last(queue)) {
  11.         return middle;
  12.     }
  13.     next = ngx_queue_head(queue);
  14.     for ( ;; ) {
  15.         middle = ngx_queue_next(middle);
  16.         next = ngx_queue_next(next);
  17.         if (next == ngx_queue_last(queue)) {//偶数个节点,在此返回后半个队列的第一个节点
  18.             return middle;
  19.         }
  20.         next = ngx_queue_next(next);
  21.         if (next == ngx_queue_last(queue)) {//奇数个节点,在此返回中间节点
  22.             return middle;
  23.         }
  24.     }
  25. }

为什么该算法能够找到中间节点?

——注意代码中的next指针,其每次均会后移两个位置(节点),而middle指针每次后移一个位置(节点)。演示图形如下。


2.7 队列排序

队列排序采用的是稳定的简单插入排序方法,即从第一个节点开始遍历,依次将当前节点(q)插入前面已经排好序的队列(链表)中,下面程序中,前面已经排好序的队列的尾节点为prev。操作如下。


点击(此处)折叠或打开

  1. /* the stable insertion sort */
  2. void
  3. ngx_queue_sort(ngx_queue_t *queue,
  4.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
  5. {
  6.     ngx_queue_t *q, *prev, *next;
  7.     q = ngx_queue_head(queue);
  8.     if (q == ngx_queue_last(queue)) {
  9.         return;
  10.     }
  11.     for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
  12.         prev = ngx_queue_prev(q);
  13.         next = ngx_queue_next(q);
  14.         ngx_queue_remove(q);
  15.         do {
  16.             if (cmp(prev, q) <= 0) { //比较
  17.                 break;
  18.             }
  19.             prev = ngx_queue_prev(prev); //prev指针前移
  20.         } while (prev != ngx_queue_sentinel(queue));
  21.         ngx_queue_insert_after(prev, q); //将q插入prev节点之后(此处即为简单插入)
  22.     }
  23. }
该排序操作使用前面介绍的宏来完成其插入动作,只是一些简单的修改指针指向的操作,效率较高。关于该操作的例子,请参考后文的内容。

2.8 如何获取队列节点数据


由队列基本结构和以上操作可知,nginx的队列操作只对链表指针进行简单的修改指向操作,并不负责节点数据空间的分配。因此,用户在使用nginx队列时,要自己定义数据结构并分配空间,且在其中包含一个ngx_queue_t的指针或者对象,当需要获取队列节点数据时,使用ngx_queue_data宏,其定义如下。


点击(此处)折叠或打开

  1. #define ngx_queue_data(q, type, link) \
  2.     (type *) ((u_char *) q – offsetof(type, link))

由该宏定义可以看出,一般定义队列节点结构(该结构类型为type)时,需要将真正的数据放在前面,而ngx_queue_t结构放在后面,故该宏使用减法计算整个节点结构的起始地址(需要进行类型转换)。关于该宏的使用,请参考下文的代码。


3. 一个例子


本节给出一个创建内存池并从中分配队列头节点和其他节点组成队列的简单例子。在该例中,队列的数据是一系列的二维点(x,y分别表示该点的横、纵坐标),将这些点插入队列后进行排序,以此向读者展示nginx队列的使用方法。


3.1代码


点击(此处)折叠或打开

  1. /**
  2.  * ngx_queue_t test
  3.  */
  4.  
  5. #include <stdio.h>
  6. #include "ngx_config.h"
  7. #include "ngx_conf_file.h"
  8. #include "nginx.h"
  9. #include "ngx_core.h"
  10. #include "ngx_palloc.h"
  11. #include "ngx_queue.h"
  12.  
  13. //2-dimensional point (x, y) queue structure
  14. typedef struct
  15. {
  16.     int x;
  17.     int y;
  18. } my_point_t;
  19.  
  20. typedef struct
  21. {
  22.     my_point_t point;
  23.     ngx_queue_t queue;
  24. } my_point_queue_t;
  25.  
  26. volatile ngx_cycle_t *ngx_cycle;
  27.  
  28. void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
  29.             const char *fmt, ...)
  30. {
  31. }
  32.  
  33. void dump_pool(ngx_pool_t* pool)
  34. {
  35.     while (pool)
  36.     {
  37.         printf("pool = 0x%x\n", pool);
  38.         printf(" .d\n");
  39.         printf(" .last = 0x%x\n", pool->d.last);
  40.         printf(" .end = 0x%x\n", pool->d.end);
  41.         printf(" .next = 0x%x\n", pool->d.next);
  42.         printf(" .failed = %d\n", pool->d.failed);
  43.         printf(" .max = %d\n", pool->max);
  44.         printf(" .current = 0x%x\n", pool->current);
  45.         printf(" .chain = 0x%x\n", pool->chain);
  46.         printf(" .large = 0x%x\n", pool->large);
  47.         printf(" .cleanup = 0x%x\n", pool->cleanup);
  48.         printf(" .log = 0x%x\n", pool->log);
  49.         printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);
  50.         pool = pool->d.next;
  51.     }
  52. }
  53.  
  54. void dump_queue_from_head(ngx_queue_t *que)
  55. {
  56.     ngx_queue_t *q = ngx_queue_head(que);
  57.  
  58.     printf("(0x%x: (0x%x, 0x%x)) <==> \n", que, que->prev, que->next);
  59.  
  60.     for (; q != ngx_queue_sentinel(que); q = ngx_queue_next(q))
  61.     {
  62.         my_point_queue_t *point = ngx_queue_data(q, my_point_queue_t, queue);
  63.         printf("(0x%x: (%-2d, %-2d), 0x%x: (0x%x, 0x%x)) <==> \n", point, point->point.x,
  64.             point->point.y, &point->queue, point->queue.prev, point->queue.next);
  65.     }
  66. }
  67.  
  68. void dump_queue_from_tail(ngx_queue_t *que)
  69. {
  70.     ngx_queue_t *q = ngx_queue_last(que);
  71.  
  72.     printf("(0x%x: (0x%x, 0x%x)) <==> \n", que, que->prev, que->next);
  73.  
  74.     for (; q != ngx_queue_sentinel(que); q = ngx_queue_prev(q))
  75.     {
  76.         my_point_queue_t *point = ngx_queue_data(q, my_point_queue_t, queue);
  77.         printf("(0x%x: (%-2d, %-2d), 0x%x: (0x%x, 0x%x)) <==> \n", point, point->point.x,
  78.             point->point.y, &point->queue, point->queue.prev, point->queue.next);
  79.     }
  80. }
  81.  
  82. //sort from small to big
  83. ngx_int_t my_point_cmp(const ngx_queue_t* lhs, const ngx_queue_t* rhs)
  84. {
  85.     my_point_queue_t *pt1 = ngx_queue_data(lhs, my_point_queue_t, queue);
  86.     my_point_queue_t *pt2 = ngx_queue_data(rhs, my_point_queue_t, queue);
  87.  
  88.     if (pt1->point.x < pt2->point.x)
  89.         return 0;
  90.     else if (pt1->point.x > pt2->point.x)
  91.         return 1;
  92.     else if (pt1->point.y < pt2->point.y)
  93.         return 0;
  94.     else if (pt1->point.y > pt2->point.y)
  95.         return 1;
  96.     return 1;
  97. }
  98.  
  99. #define Max_Num 6
  100.  
  101. int main()
  102. {
  103.     ngx_pool_t *pool;
  104.     ngx_queue_t *myque;
  105.     my_point_queue_t *point;
  106.     my_point_t points[Max_Num] = {
  107.             {10, 1}, {20, 9}, {9, 9}, {90, 80}, {5, 3}, {50, 20}
  108.     };
  109.     int i;
  110.  
  111.     printf("--------------------------------\n");
  112.     printf("create a new pool:\n");
  113.     printf("--------------------------------\n");
  114.     pool = ngx_create_pool(1024, NULL);
  115.     dump_pool(pool);
  116.  
  117.     printf("--------------------------------\n");
  118.     printf("alloc a queue head and nodes :\n");
  119.     printf("--------------------------------\n");
  120.     myque = ngx_palloc(pool, sizeof(ngx_queue_t)); //alloc a queue head
  121.     ngx_queue_init(myque); //init the queue
  122.  
  123.     //insert some points into the queue
  124.     for (i = 0; i < Max_Num; i++)
  125.     {
  126.         point = (my_point_queue_t*)ngx_palloc(pool, sizeof(my_point_queue_t));
  127.         point->point.x = points[i].x;
  128.         point->point.y = points[i].y;
  129.         ngx_queue_init(&point->queue);
  130.  
  131.         //insert this point into the points queue
  132.         ngx_queue_insert_head(myque, &point->queue);
  133.     }
  134.  
  135.     dump_queue_from_tail(myque);
  136.     printf("\n");
  137.  
  138.     printf("--------------------------------\n");
  139.     printf("sort the queue:\n");
  140.     printf("--------------------------------\n");
  141.     ngx_queue_sort(myque, my_point_cmp);
  142.     dump_queue_from_head(myque);
  143.     printf("\n");
  144.  
  145.     printf("--------------------------------\n");
  146.     printf("the pool at the end:\n");
  147.     printf("--------------------------------\n");
  148.     dump_pool(pool);
  149.  
  150.     ngx_destroy_pool(pool);
  151.     return 0;
  152. }

3.2如何编译


请参考nginx-1.0.4源码分析—内存池结构ngx_pool_t及内存管理一文。本文编写的makefile文件如下。


点击(此处)折叠或打开

  1. CXX = gcc
  2. CXXFLAGS += -g -Wall -Wextra
  3. NGX_ROOT = /usr/src/nginx-1.0.4
  4. TARGETS = ngx_queue_t_test
  5. TARGETS_C_FILE = $(TARGETS).c
  6. CLEANUP = rm -f $(TARGETS) *.o
  7. all: $(TARGETS)
  8. clean:
  9. $(CLEANUP)
  10. CORE_INCS = -I. \
  11. -I$(NGX_ROOT)/src/core \
  12. -I$(NGX_ROOT)/src/event \
  13. -I$(NGX_ROOT)/src/event/modules \
  14. -I$(NGX_ROOT)/src/os/unix \
  15. -I$(NGX_ROOT)/objs \
  16. NGX_PALLOC = $(NGX_ROOT)/objs/src/core/ngx_palloc.o
  17. NGX_STRING = $(NGX_ROOT)/objs/src/core/ngx_string.o
  18. NGX_ALLOC = $(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
  19. NGX_QUEUE = $(NGX_ROOT)/objs/src/core/ngx_queue.o
  20. $(TARGETS): $(TARGETS_C_FILE)
  21. $(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING) $(NGX_ALLOC) $(NGX_QUEUE) $^ -o $@
3.3 运行结果

点击(此处)折叠或打开

  1. # ./ngx_queue_t_test
  2. --------------------------------
  3. create a new pool:
  4. --------------------------------
  5. pool = 0x8bcf020
  6.   .d
  7.     .last = 0x8bcf048
  8.     .end = 0x8bcf420
  9.     .next = 0x0
  10.     .failed = 0
  11.   .max = 984
  12.   .current = 0x8bcf020
  13.   .chain = 0x0
  14.   .large = 0x0
  15.   .cleanup = 0x0
  16.   .log = 0x0
  17. available pool memory = 984

  18. --------------------------------
  19. alloc a queue head and nodes :
  20. --------------------------------
  21. (0x8bcf048: (0x8bcf058, 0x8bcf0a8)) <==>
  22. (0x8bcf050: (10, 1 ), 0x8bcf058: (0x8bcf068, 0x8bcf048)) <==>
  23. (0x8bcf060: (20, 9 ), 0x8bcf068: (0x8bcf078, 0x8bcf058)) <==>
  24. (0x8bcf070: (9 , 9 ), 0x8bcf078: (0x8bcf088, 0x8bcf068)) <==>
  25. (0x8bcf080: (90, 80), 0x8bcf088: (0x8bcf098, 0x8bcf078)) <==>
  26. (0x8bcf090: (5 , 3 ), 0x8bcf098: (0x8bcf0a8, 0x8bcf088)) <==>
  27. (0x8bcf0a0: (50, 20), 0x8bcf0a8: (0x8bcf048, 0x8bcf098)) <==>

  28. --------------------------------
  29. sort the queue:
  30. --------------------------------
  31. (0x8bcf048: (0x8bcf088, 0x8bcf098)) <==>
  32. (0x8bcf090: (5 , 3 ), 0x8bcf098: (0x8bcf048, 0x8bcf078)) <==>
  33. (0x8bcf070: (9 , 9 ), 0x8bcf078: (0x8bcf098, 0x8bcf058)) <==>
  34. (0x8bcf050: (10, 1 ), 0x8bcf058: (0x8bcf078, 0x8bcf068)) <==>
  35. (0x8bcf060: (20, 9 ), 0x8bcf068: (0x8bcf058, 0x8bcf0a8)) <==>
  36. (0x8bcf0a0: (50, 20), 0x8bcf0a8: (0x8bcf068, 0x8bcf088)) <==>
  37. (0x8bcf080: (90, 80), 0x8bcf088: (0x8bcf0a8, 0x8bcf048)) <==>

  38. --------------------------------
  39. the pool at the end:
  40. --------------------------------
  41. pool = 0x8bcf020
  42.   .d
  43.     .last = 0x8bcf0b0
  44.     .end = 0x8bcf420
  45.     .next = 0x0
  46.     .failed = 0
  47.   .max = 984
  48.   .current = 0x8bcf020
  49.   .chain = 0x0
  50.   .large = 0x0
  51.   .cleanup = 0x0
  52.   .log = 0x0
  53. available pool memory = 880

该队列的逻辑图如下。




阅读(1856) | 评论(1) | 转发(0) |
0

上一篇:链表结构ngx_list_t

下一篇:半同步半异步

给主人留下些什么吧!~~

最大行业软件2012-12-01 10:28:23

PTC Creo Elements/Pro 5.0 M070 Working for Win32-ISO 1DVD(最新多语言正式版包括简、繁体中文)

PTC Creo Elements/Pro 5.0 M070 Working for Win64-ISO 1DVD

PTC Creo Elements View (ex Product View) v10 F000 build 93 Pro Multilanguage Win32 1CD

PTC Creo Elements View (ex Product View) v10 F000 build 93 Pro Multilanguage Win64 1CD

 

PTC Pro/E WildFire+Pro/Mechancia 4.0 M110 Working for Win32-ISO 1DVD(最新多语言正式版包括简、繁体中文)

PTC Pro/E Wil