Nginx循环链表

Nginx循环链表设计

采用双向链表数据结构实现
使用哨兵节点简化实现，避免多余的判断
链表结构不关联具体数据，业务结构体通过将链表结构作为成员从而支持链表操作（类似插件）
链表基础操作通过宏实现，同时支持自定义排序（使用稳定的插入排序）

双向链表基本操作

链表结构体只有两个指针，prev指向前一个节点，next指向下一个节点

typedef struct ngx_queue_s  ngx_queue_t;

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

初始化：prev和 next都指向哨兵节点

#define ngx_queue_init(q)                                                     \
    (q)->prev = q;                                                            \
    (q)->next = q

判断链表是否为空：检查 prev或 next是否指向哨兵节点即可

#define ngx_queue_empty(h)                                                    \
    (h == (h)->prev)

头插法新插入一个节点，定义另一个宏 ngx_queue_insert_after用于表示将 x插入 h之后（只是为了可读性，实现方法并没有变）

#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

尾插法插入一个节点，由于使用的双向链表，尾插法的时间复杂度为 O(1)

#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)->next


#define ngx_queue_prev(q)                                                     \
    (q)->prev

移除给定节点：debug模式下移除节点会初始化 prev和 next指针

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

#endif

链表分割：这部分只看代码会有点懵，看 nginx的使用就可以知道 q是链表 h中的一个节点，这个宏的功能就是将 q及其后面部分的链表节点分割出来，n作为这个新链表的头部（因此 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的节点拼接到链表 h（注意，拼接完后对 n的数据结构并没有发生改变，相当于链表 h中有一段是 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;

获取链表所在结构体的指针：通过 offsetof获取链表结构体成员在结构体中的偏移，然后用链表成员地址减偏移即可得到业务结构体地址

#define ngx_queue_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

// 举例子
typedef struct Connection_s {
	int fd;
	ngx_queue_t queue;
    char buf[1024];
} Connection_t;

// 获取业务结构体 Connectin_t 的指针
ngx_queue_t *h = xxx;
pconn = ngx_queue(h, Connection_t, queue);

获取链表中间节点

如果链表为空则返回哨兵节点指针
奇数个节点返回中点，偶数节点返回第二部分的第一个节点（若有 4 个节点，返回第 3 个节点）

使用快慢指针算法取中点

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

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

自定义链表排序

使用稳定的插入排序算法，比较函数自定义

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

        do {
            if (cmp(prev, q) <= 0) {
                break;
            }

            prev = ngx_queue_prev(prev);

        } while (prev != ngx_queue_sentinel(queue));

        ngx_queue_insert_after(prev, q);
    }
}

在自定义排序这里，可以用前面的 ngx_queue_data方法获取业务结构体，或者将 ngx_queue_t成员作为结构体的第一个成员。获取业务结构体后再根据其他成员的值进行比较，例如下面的 People_t链表按金钱大小从小到大排序

typedef struct People_s {
    int money;
    ngx_queue_t queue;
} People_t;


ngx_int_t people_cmp(const ngx_queue_t *a, const ngx_queue_t *b) {
    People_t *pa = ngx_queue_data(a, People_t, queue);
    People_t *pb = ngx_queue_data(b, People_t, queue);

    if (pa->money < pb->money)
        return -1;
    if (pa->money == pb->money)
        return 0;

    return 1;
}

int main(int argc, char* argv[]) {
    People_t a, b, c;
    a.money = 100;
    b.money = 50;
    c.money = 300;
    ngx_queue_init(&a.queue);
    ngx_queue_init(&b.queue);
    ngx_queue_init(&c.queue);
    

    ngx_queue_t h;
    ngx_queue_init(&h);

    ngx_queue_insert_tail(&h, &a.queue);
    ngx_queue_insert_tail(&h, &b.queue);
    ngx_queue_insert_tail(&h, &c.queue);


    for (ngx_queue_t *p = ngx_queue_head(&h); p != ngx_queue_sentinel(&h); p = ngx_queue_next(p)) {
        People_t *t = ngx_queue_data(p, People_t, queue);
        printf("money:%d\n", t->money);
    }

    ngx_queue_sort(&h, people_cmp);

    for (ngx_queue_t *p = ngx_queue_head(&h); p != ngx_queue_sentinel(&h); p = ngx_queue_next(p)) {
        People_t *t = ngx_queue_data(p, People_t, queue);
        printf("money:%d\n", t->money);
    }


    return 0;
}