首页 > 代码库 > Nginx源码完全注释(4)ngx_queue.h / ngx_queue.c
Nginx源码完全注释(4)ngx_queue.h / ngx_queue.c
队列头文件ngx_queue.h
#include <ngx_config.h>#include <ngx_core.h>#ifndef _NGX_QUEUE_H_INCLUDED_#define _NGX_QUEUE_H_INCLUDED_typedef struct ngx_queue_s ngx_queue_t;// 队列的节点,也直接表示队列。注意这是一个双向循环队列struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next;};// 初始化队列 q 所指向的指针,prev 和 next 都是自己#define ngx_queue_init(q) (q)->prev = q; (q)->next = q// 如果表 h == h 的上一个,那么就是一个空队列,其实用 next 也可以的#define ngx_queue_empty(h) (h == (h)->prev)// 向 h 后面插入一个 x#define ngx_queue_insert_head(h, x) (x)->next = (h)->next; (x)->next->prev = x; (x)->prev = h; (h)->next = x// 在后面插入 insert after,就是 insert head#define ngx_queue_insert_after ngx_queue_insert_head// 向 h 前面插入一个 x#define ngx_queue_insert_tail(h, x) (x)->prev = (h)->prev; (x)->prev->next = x; (x)->next = h; (h)->prev = x// h 表示队列,第一个元素为 h->next#define ngx_queue_head(h) (h)->next// h 是头,h 的上一个就是尾#define ngx_queue_last(h) (h)->prev#define ngx_queue_sentinel(h) (h)// 返回节点 q 的下一个#define ngx_queue_next(q) (q)->next// 返回节点 q 的上一个#define ngx_queue_prev(q) (q)->prev#if (NGX_DEBUG)// debug 模式下要把 x 的 prev、next 成员置为 0,release 版可以省去此两句#define ngx_queue_remove(x) (x)->next->prev = (x)->prev; (x)->prev->next = (x)->next; (x)->prev = NULL; (x)->next = NULL#else// 删除一个节点#define ngx_queue_remove(x) (x)->next->prev = (x)->prev; (x)->prev->next = (x)->next#endif//// split 作用如下图所示://// ________________________________________________// ||--------------------------------------------||// || ||// |---| => |---| => … => |---| => |---| => … => |---| |---|// | h | | | | q | | | | | | n |// |---| <= |---| <= … <= |---| <= |---| <= … <= |---| |---|//// __________________________ __________________________________// ||----------------------|| ||------------------------------||// || || || ||// |---| => |---| => … => |---| |---| => |---| => … => |---| => |---|// | h | | | | | | q | | | | | | n |// |---| <= |---| <= … => |---| |---| <= |---| <= … <= |---| <= |---|//#define ngx_queue_split(h, q, n) (n)->prev = (h)->prev; (n)->prev->next = n; (n)->next = q; (h)->prev = (q)->prev; (h)->prev->next = h; (q)->prev = n;// 将 n 代表的队列(n 为队列头)接到 h 表示的队列后面//// _________________________ _________________________// ||---------------------|| ||---------------------||// || || || ||// |---| => |---| => … => |---| |---| => |---| => … => |---|// | h | | | | | | n | |n1 | | |// |---| <= |---| <= … <= |---| |---| <= |---| <= … <= |---|//// ________________________________________________________// ||----------------------------------------------------||// || ||// |---| => |---| => … => |---| =========> |---| => … => |---|// | h | | | | | |n1 | | |// |---| <= |---| <= … <= |---| <========= |---| <= … <= |---|//#define ngx_queue_add(h, n) (h)->prev->next = (n)->next; (n)->next->prev = (h)->prev; (h)->prev = (n)->prev; (h)->prev->next = h;// 一般type如下:// typedef struct {// …// LINK q// } TYPE// 所以这个宏可以通过 q 找到其所在的结构体 TYPE 变量的地址#define ngx_queue_data(q, type, link) (type *) ((u_char *) q - offsetof(type, link))ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));#endif /* _NGX_QUEUE_H_INCLUDED_ */
队列源文件ngx_queue.c
#include #include /* * find the middle queue element if the queue has odd number of elements * or the first element of the queue‘s second part otherwise *///// 这是用两个指针来找链表中点的典型应用,在很多技巧性问答中常出现。//ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue){ ngx_queue_t *middle, *next; // middle 从第一个节点开始 middle = ngx_queue_head(queue); // 如果队列只有一个节点,或者为空 if (middle == ngx_queue_last(queue)) { return middle; } // next 也从第一个节点开始 next = ngx_queue_head(queue); for ( ;; ) { middle = ngx_queue_next(middle); next = ngx_queue_next(next); // 偶数个的情况是在这里返回 if (next == ngx_queue_last(queue)) { return middle; } next = ngx_queue_next(next); // 奇数个是在这里返回 if (next == ngx_queue_last(queue)) { return middle; } }}/* the stable insertion sort *///// 这是一个稳定就地排序(Stable In-place Sorting)。算法的三个性能指标(时间复杂度,空间复杂度,稳定性)// 相比之下,quick sort 和 merge sort 更快。但 quick sort 是非稳定的,merge sort 使用 O(n) 额外空间//voidngx_queue_sort(ngx_queue_t *queue, ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)){ ngx_queue_t *q, *prev, *next; q = ngx_queue_head(queue); // 空队列 if (q == ngx_queue_last(queue)) { return; } for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { prev = ngx_queue_prev(q); next = ngx_queue_next(q); ngx_queue_remove(q); // 在已排好序的节点中,向前找比 q 的内容小的。比较的标准由 cmp 确定 do { if (cmp(prev, q) <= 0) { break; } prev = ngx_queue_prev(prev); } while (prev != ngx_queue_sentinel(queue)); // 找到 prev 是比 q 的内容小的,在 prev 后面插入 ngx_queue_insert_after(prev, q); }}
从上面可以看出,create 是从 pool 分配定义 list 结构的内存,分配表头节点的内存。init 是初始化已有的 list。
Nginx源码完全注释(4)ngx_queue.h / ngx_queue.c
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。