Nginx 소스 코드 완전 주석 (4) ngxqueue.h / ngx_queue.c

#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_ */ 

#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)      // void ngx_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); } }