关于Nginx中的链表分析

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链吧。