nginx高階資料結構原始碼分析（一）-----雙向鍊錶

ng_queue_t是Nginx提供的一個順序容器，它以雙向鍊錶的方式將資料組織在一起。

鍊錶作為順序容器的優點在於，它可以高效的執行插入、刪除、合併等操作，在移動鍊錶中的元素時只需要修改指針的指向，因此，它很適合頻繁修改容器的場合。

相對於其他順序容器，它的優勢有以下三點：

 （1）  實現了排序功能，採用額是插入排序，雖然不太適合超大規模資料的排序，雖然不太適合但是簡單實用。

（2）  它非常輕量級，不負責鍊錶元素所佔記憶體的分配。 ngx_queue_t只是把這些分配號記憶體的元素用雙向鍊錶連結起來

（3）  支援兩個鍊錶的合併。

Nginx在設計這個雙向鍊錶時，由於容器與元素共用了ngx_queue_t結構體，為了避免此結構體成員的意義混亂，Nginx封裝了鍊錶容器與元素的所有方法。

ngx_queue_t的頭檔：

gx_queue_t的實作檔中只有兩個方法：一個是傳回鍊錶中的中心元素，還有一個是對鍊錶排序。

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};


#define ngx_queue_init(q)                                                     \初始化，为空，都指向容器结构体
    (q)->prev = q;                                                            \
    (q)->next = q


#define ngx_queue_empty(h)                                                    \是否为空
    (h == (h)->prev)


#define ngx_queue_insert_head(h, x)                                           \插入链表容器头部
    (x)->next = (h)->next;                                                    \
    (x)->next->prev = x;                                                      \
    (x)->prev = h;                                                            \
    (h)->next = x


#define ngx_queue_insert_after   ngx_queue_insert_head


#define ngx_queue_insert_tail(h, x)                                           \插入链表容器尾部
    (x)->prev = (h)->prev;                                                    \
    (x)->prev->next = x;                                                      \
    (x)->next = h;                                                            \
    (h)->prev = x


#define ngx_queue_head(h)                                                     \返回第一个结构体指针
    (h)->next


#define ngx_queue_last(h)                                                     \返回最后一个结构体指针
    (h)->prev


#define ngx_queue_sentinel(h)                                                 \返回容器结构体指针
    (h)


#define ngx_queue_next(q)                                                     \返回q的下一个元素
    (q)->next


#define ngx_queue_prev(q)                                                     \返回q的上一个元素
    (q)->prev


#if (NGX_DEBUG)

#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
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next

#endif


#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;


#define ngx_queue_add(h, n)                                                   \合并链表
    (h)->prev->next = (n)->next;                                              \
    (n)->next->prev = (h)->prev;                                              \
    (h)->prev = (n)->prev;                                                    \
    (h)->prev->next = h;


#define ngx_queue_data(q, type, link)                                         \返回q所属结构体地址
    (type *) ((u_char *) q - offsetof(type, link))

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。

以上就介紹了nginx高階資料結構原始碼分析（一）-----雙向鍊錶，包含了方面的內容，希望對PHP教學有興趣的朋友有所幫助。