4.4　队列

队列通常是一种先进先出的数据结构。在实际工作中，队列多用于异步的任务处理。Nginx的队列由包含头节点的双向循环链表实现，是一种双向队列。

Nginx的队列定义如下：

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

从上述结构体定义可以看出，队列只有前驱和后继节点。我们不禁要问，队列的数据节点存在哪里呢？先保留这个疑问，看一下队列的初始化和插入过程。

Nginx用宏ngx_queue_init初始化一个队列，定义如下：

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

队列初始化时必须有一个头节点。当头节点的prev和next指针都指向自己时，队列是只有一个头节点的空队列。

Nginx可以用ngx_queue_insert_head实现头插法来插入数据，也可以用ngx_queue_insert_tail实现尾插法来插入数据，这两个方法的原理是一样的，只需要修改指针的指向。下面以头插法为例进行简要说明。

#define ngx_queue_insert_head(h, x)        \
    (x)->next = (h)->next;                 \
    (x)->next->prev = x;                   \
    (x)->prev = h;                         \
    (h)->next = x

从上面的宏可以看出，头插法插入一个头节点分以下4步。

1）修改新插入节点x的next指针指向h节点的下一个节点；

2）修改x的下一个节点的prev指针指向x；

3）修改x的prev指针指向h节点；

4）修改头指针指向x。

假设原队列除头节点外有两个数据，插入一个节点的效果如图4-1所示，其中实线代表修改指针指向，虚线表示断开指针指向。

尾插法和头插法原理类似，这里不再详细展开。

我们已经知道队列中插入节点的原理。下面来看一下队列中删除节点的原理。Nginx用宏ngx_queue_remove来删除队列的节点：

#define ngx_queue_remove(x)               \
    (x)->next->prev = (x)->prev;          \
    (x)->prev->next = (x)->next

删除节点原理更简单，直接修改要删除节点的前后节点指针即可，并没有释放节点内存。释放内存的操作应由开发者自己来完成。队列中删除x节点的效果如图4-2所示。

之前我们提到，队列结构体中有next和prev指针，它的数据存放在哪里我们还是不清楚。下面来研究一下队列中的数据是怎么存储的。Nginx中队列获取数据是由宏ngx_queue_data来实现的，具体定义为：

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

offsetof是C语言的一个库函数，它返回一个结构体成员相对于结构体开头的字节偏移量。在offsetof(type，link)中，函数返回link成员相对于type结构体开头的字节偏移量。q是一个队列节点，实际上是一个结构体的成员变量。我们以一个实例来说明，Nginx会将网络连接状态初始化为一个队列，并从头部插入节点，方法如下：

ngx_queue_insert_head(
    (ngx_queue_t *) &ngx_cycle->reusable_connections_queue, &c->queue);

可以看到，往队列里添加的节点是&c->queue，而c->queue是结构体ngx_connection_s的一个成员变量。c的定义为：

ngx_connection_s *c;

ngx_connection_s的简要定义如下：

struct ngx_connection_s {
    void               *data;
    ngx_event_t        *read;
    ngx_event_t        *write;
    ...
    ngx_queue_t         queue;
    ...
};

我们得出结论，在往队列中添加节点时，这个节点实际上是一个结构体内存的首地址向后偏移一定位置的地址。这个位置向前偏移相同的位置，并强制转换成对应的类型就可以获取节点真正存储的值。如图4-3所示，队列的节点包括成员1，成员2，…，成员N等属性，队列的prev、next等指针全部在节点的一个类型为ngx_queue_t的属性中，从这个属性所在的位置向前偏移offsetof(type，link)便可以获取队列的节点。

我们已经知道队列的内存结构，也知道了队列的初始化以及节点插入和删除过程。下面来看一下队列的拆分和合并。

队列拆分代码如下：

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

这段代码的含义为：以数据q为界，将队列h拆分为h和n两个队列，其中拆分后数据q位于第二个队列中。队列拆分实际上是以数据q作为第二个队列的第一个节点，数据q的前一个节点作为前一个队列的最后一个节点。如图4-4所示，按照图中顺序调整指针就可以完成队列的拆分。

队列合并代码如下：

#define ngx_queue_add(h, n)               \
    (h)->prev->next = (n)->next;          \
    (n)->next->prev = (h)->prev;          \
    (h)->prev = (n)->prev;                \
    (h)->prev->next = h;

这段代码的含义为：将队列n添加到队列h的尾部。同队列拆分一样，队列合并主要是调整两个队列的头节点和最后一个节点的指针，使两个队列组成一个双向队列。如图4-5所示，按顺序调整指针指向就可以完成队列的合并。

Nginx还提供了其他的宏来操作队列，如表4-2所示。