Nginx中大量用到链表操作,关于链表的使用,据我观察,有三种不同的方法,接下来我将好好分析一下:
首先第一种即将单链表与数组相结合,一个链表节点并非只保存一块数据,而是保存一块可以容纳若干块数据的缓冲区,具体实现在ngx_list.c和ngx_list.h两个文件中;第二种即为比较常规的双向环链,具体实现在ngx_queue.h中;第三种实现在ngx_event_posted.h中,其实也是双向链表,至于为什么要实现成这样,我会在后面谈谈我的看法。这里,我想重点向大家展示后两种的实现,大家看看有什么区别,希望能有人告诉我为什么要有这样的区别。以下贴出的代码只是为了展示实现机制,并不一定完全取自Nginx源码。
先给出第一种实现,如下:
- struct list_head {
- struct list_head *next, *prev;
- };
- #define LIST_HEAD_INIT(name) { &(name), &(name) }
- #define LIST_HEAD(name) \
- struct list_head name = LIST_HEAD_INIT(name)
- static inline void INIT_LIST_HEAD(struct list_head *list)
- {
- list->next = list;
- list->prev = list;
- }
- static inline void __list_add(struct list_head *new,
- struct list_head *prev,
- struct list_head *next)
- {
- next->prev = new;
- new->next = next;
- new->prev = prev;
- prev->next = new;
- }
- static inline void list_add(struct list_head *new, struct list_head *head)
- {
- __list_add(new, head, head->next);
- }
- static inline void list_add_tail(struct list_head *new, struct list_head *head)
- {
- __list_add(new, head->prev, head);
- }
- static inline void __list_del(struct list_head * prev, struct list_head * next)
- {
- next->prev = prev;
- prev->next = next;
- }
- static inline void list_del(struct list_head *entry)
- {
- __list_del(entry->prev, entry->next);
- entry->next = LIST_POISON1;
- entry->prev = LIST_POISON2;
- }
再给出第二种实现,如下:
- struct hlist_head {
- struct hlist_node *first;
- };
- struct hlist_node {
- struct hlist_node *next, **pprev;
- };
- #define HLIST_HEAD_INIT { .first = NULL }
- #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
- #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
- static inline void INIT_HLIST_NODE(struct hlist_node *h)
- {
- h->next = NULL;
- h->pprev = NULL;
- }
- static inline int hlist_unhashed(const struct hlist_node *h)
- {
- return !h->pprev;
- }
- static inline int hlist_empty(const struct hlist_head *h)
- {
- return !h->first;
- }
- static inline void __hlist_del(struct hlist_node *n)
- {
- struct hlist_node *next = n->next;
- struct hlist_node **pprev = n->pprev;
- *pprev = next;
- if (next)
- next->pprev = pprev;
- }
- static inline void hlist_del(struct hlist_node *n)
- {
- __hlist_del(n);
- n->next = LIST_POISON1;
- n->pprev = LIST_POISON2;
- }
- static inline void hlist_del_init(struct hlist_node *n)
- {
- if (!hlist_unhashed(n)) {
- __hlist_del(n);
- INIT_HLIST_NODE(n);
- }
- }
- static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
- {
- struct hlist_node *first = h->first;
- n->next = first;
- if (first)
- first->pprev = &n->next;
- h->first = n;
- n->pprev = &h->first;
- }
- /* next must be != NULL */
- static inline void hlist_add_before(struct hlist_node *n,
- struct hlist_node *next)
- {
- n->pprev = next->pprev;
- n->next = next;
- next->pprev = &n->next;
- *(n->pprev) = n;
- }
- static inline void hlist_add_after(struct hlist_node *n,
- struct hlist_node *next)
- {
- next->next = n->next;
- n->next = next;
- next->pprev = &n->next;
- if(next->next)
- next->next->pprev = &next->next;
- }
以上两种实现都摘自Linux内核,第一种也许大家都很熟悉,但是第二种可能平时用的相对少一些吧。在Nginx中,在事件处理机制里用到了第二种实现。对于所有到达的事件,Nginx都没有立刻处理,而是先将其加入到任务队列,等稍后再一起处理。我们看看其任务队列是如何实现的:
- struct ngx_event_s {
- /* the links of the posted queue */
- ngx_event_t *next;
- ngx_event_t **prev;
- }
-
- ngx_thread_volatile ngx_event_t *ngx_posted_accept_events;
- ngx_thread_volatile ngx_event_t *ngx_posted_events;
- #define ngx_locked_post_event(ev, queue) \
- \
- if (ev->prev == NULL) { \
- ev->next = (ngx_event_t *) *queue; \
- ev->prev = (ngx_event_t **) queue; \
- *queue = ev; \
- \
- if (ev->next) { \
- ev->next->prev = &ev->next; \
- } \
- }
- #define ngx_delete_posted_event(ev) \
- \
- *(ev->prev) = ev->next; \
- \
- if (ev->next) { \
- ev->next->prev = ev->prev; \
- } \
- \
- ev->prev = NULL;
在我看来,这两种实现的区别在于头结点的表示,第一种实现通常其头结点为struct list_head head;
即为一个结构体,而非一个指针,但是事实上这个头结点消耗了两个指针。而第二种实现通常其头结点为 struct list_head *head,即只消耗了一个指针,这种实现非常适合于hash链表中,在hash链中,每个头结点都是一个指针保存在hash数组中。如果hash因子很大的话,第二种实现会节约不少内存。Nginx中的任务队列其实可看作是hash因子为1的hash链吧。
阅读(3126) | 评论(1) | 转发(1) |