- /* src/core/ngx_queue.h */
- typedef struct ngx_queue_s ngx_queue_t;
- /* 一个以容器为哨兵的双向链表。 对于容器而言,prev指向最后一个元素,next指向第一个元素。当容器为空(容器中没有元素)时,prev和next都指向容器。 对于元素而言,prev指向前一个元素,next指向后一个元素。第一个元素的prev指向容器,最后一个元素的next指向容器。 */
- struct ngx_queue_s {
- ngx_queue_t * prev;
- ngx_queue_t * next;
- }; // 初始化容器q,得到一个空容器#define ngx_queue_init(q) \ (q)->prev = q; \ (q)->next = q// 判断容器h是否为空#define ngx_queue_empty(h) \ (h == (h)->prev)// 将元素x插入容器h的头部#define ngx_queue_insert_head(h, x) \ (x)->next = (h)->next; \ (x)->next->prev = x; \ (x)->prev = h; \ (h)->next = x// 将元素x插入到元素h后面#define ngx_queue_insert_after ngx_queue_insert_head// 将元素x插入容器h的尾部#define ngx_queue_insert_tail(h, x) \ (x)->prev = (h)->prev; \ (x)->prev->next = x; \ (x)->next = h; \ (h)->prev = x// 得到容器h的第一个元素#define ngx_queue_head(h) \ (h)->next// 得到容器h的最后一个元素#define ngx_queue_last(h) \ (h)->prev// 得到容器h的哨兵#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)// 移除元素x#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// 以元素q为界拆分容器h,h由前半部分组成(不包含q),容器n由后半部分组成(q是第一个元素)#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;// 合并容器h和n,将n插入h的尾部#define ngx_queue_add(h, n) \ (h)->prev->next = (n)->next; \ (n)->next->prev = (h)->prev; \ (h)->prev = (n)->prev; \ (h)->prev->next = h;// 得到元素q所属结构体的地址#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 *));
- /* src/core/ngx_queue.c */
- /* * find the middle queue element if the queue has odd number of elements * or the first element of the queue's second part otherwise */
- // 当容器有N个元素时,返回容器的第(N/2+1)个元素ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue){ ngx_queue_t *middle, *next; middle = ngx_queue_head(queue); if (middle == ngx_queue_last(queue)) { return middle; } next = ngx_queue_head(queue); // middle走一步,next走两步 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 */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); // 每次循环从链表的第一个元素到prev是升序的,从prev开始往前寻找第一个不大于q的元素,即为q需要插入的位置 do { if (cmp(prev, q) <= 0) { break; } prev = ngx_queue_prev(prev); } while (prev != ngx_queue_sentinel(queue)); ngx_queue_insert_after(prev, q); }}
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: