队列结构ngx_queue_t

Content

0. 序

1. 队列结构

2. 队列操作

2.1 在头节点之后插入

2.2 在尾节点之后插入

2.3 删除节点

2.4 分割队列

2.5 链接队列

2.6 获取中间节点

2.7 队列排序

2.8 如何获取队列节点数据

3. 一个例子

3.1代码

3.2如何编译

3.3 运行结果

4.小结

0. 序

本文继续介绍nginx的数据结构——队列。

链表实现文件：文件：./src/core/ngx_queue.h/.c。.表示nginx-1.0.4代码目录，本文为/usr/src/nginx-1.0.4。

1.队列结构

nginx的队列是由具有头节点的双向循环链表实现的，每一个节点结构为ngx_queue_t，定义如下。

typedef struct ngx_queue_s  ngx_queue_t;
struct ngx_queue_s {          //队列结构
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

其中，sizeof(ngx_queue_t)=8。

从队列结构定义可以看出，nginx的队列结构里并没有其节点的数据内容。

2. 队列操作

队列有如下操作。

//初始化队列
ngx_queue_init(q)
//判断队列是否为空
ngx_queue_empty(h)
//在头节点之后插入新节点
ngx_queue_insert_head(h, x)
//在尾节点之后插入新节点
ngx_queue_insert_tail(h, x)
//删除节点x
ngx_queue_remove(x)
//分割队列
ngx_queue_split(h, q, n)
//链接队列
ngx_queue_add(h, n)
//获取队列的中间节点
ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue)
//排序队列(稳定的插入排序)
void ngx_queue_sort(ngx_queue_t *queue,ngx_int_t (*cmp)(const ngx_queue_t*, const ngx_queue_t*))

其中，插入节点、取队列头、取队列尾等操作由宏实现，获取中间节点、排序等操作由函数实现。下面简单介绍。

2.1 在头节点之后插入

在头节点之后插入操作由宏ngx_queue_insert_head完成，如下。

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

画出该操作的逻辑图，如下。

图中虚线表示被修改/删除的指针，蓝色表示新修改/增加的指针。下同。

2.2在尾节点之后插入

在尾节点之后插入操作由宏ngx_queue_insert_tail完成，如下。

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

该操作的逻辑图如下。

2.3 删除节点

在尾节点之后插入操作由宏ngx_queue_remove完成，如下。

#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

该操作的逻辑图如下。

2.4 分割队列

分割队列操作由宏ngx_queue_split完成，如下。

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

该宏有3个参数，h为队列头(即链表头指针)，将该队列从q节点将队列(链表)分割为两个队列(链表)，q之后的节点组成的新队列的头节点为n，图形演示如下。

2.5 链接队列

链接队列由宏ngx_queue_add完成，操作如下。

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

其中，h、n分别为两个队列的指针，即头节点指针，该操作将n队列链接在h队列之后。演示图形如下。

宏ngx_queue_split和ngx_queue_add只在http模块locations相关操作中使用，在后续的讨论http模块locations相关操作时再详细叙述。

2.6 获取中间节点

中间节点，若队列有奇数个(除头节点外)节点，则返回中间的节点；若队列有偶数个节点，则返回后半个队列的第一个节点。操作如下。

/*
 * find the middle queue element if the queue has odd number of elements
 * or the first element of the queue’s second part otherwise
 */
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;
        }
    }
}

为什么该算法能够找到中间节点？

——注意代码中的next指针，其每次均会后移两个位置(节点)，而middle指针每次后移一个位置(节点)。演示图形如下。

2.7 队列排序

队列排序采用的是稳定的简单插入排序方法，即从第一个节点开始遍历，依次将当前节点(q)插入前面已经排好序的队列(链表)中，下面程序中，前面已经排好序的队列的尾节点为prev。操作如下。

/* the stable insertion sort */
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);  //prev指针前移
        } while (prev != ngx_queue_sentinel(queue));
        ngx_queue_insert_after(prev, q);  //将q插入prev节点之后(此处即为简单插入)
    }
}

该排序操作使用前面介绍的宏来完成其插入动作，只是一些简单的修改指针指向的操作，效率较高。关于该操作的例子，请参考后文的内容。

2.8 如何获取队列节点数据

由队列基本结构和以上操作可知，nginx的队列操作只对链表指针进行简单的修改指向操作，并不负责节点数据空间的分配。因此，用户在使用nginx队列时，要自己定义数据结构并分配空间，且在其中包含一个ngx_queue_t的指针或者对象，当需要获取队列节点数据时，使用ngx_queue_data宏，其定义如下。

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

由该宏定义可以看出，一般定义队列节点结构(该结构类型为type)时，需要将真正的数据放在前面，而ngx_queue_t结构放在后面，故该宏使用减法计算整个节点结构的起始地址(需要进行类型转换)。关于该宏的使用，请参考下文的代码。

3. 一个例子

本节给出一个创建内存池并从中分配队列头节点和其他节点组成队列的简单例子。在该例中，队列的数据是一系列的二维点(x,y分别表示该点的横、纵坐标)，将这些点插入队列后进行排序，以此向读者展示nginx队列的使用方法。

3.1代码

/**
 * ngx_queue_t test
 */

#include <stdio.h>
#include "ngx_config.h"
#include "ngx_conf_file.h"
#include "nginx.h"
#include "ngx_core.h"
#include "ngx_palloc.h"
#include "ngx_queue.h"

//2-dimensional point (x, y) queue structure
typedef struct
{
    int x;
    int y;
} my_point_t;

typedef struct
{
    my_point_t point;
    ngx_queue_t queue;
} my_point_queue_t;

volatile ngx_cycle_t  *ngx_cycle;

void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
            const char *fmt, ...)
{
}

void dump_pool(ngx_pool_t* pool)
{
    while (pool)
    {
        printf("pool = 0x%x\n", pool);
        printf("  .d\n");
        printf("    .last = 0x%x\n", pool->d.last);
        printf("    .end = 0x%x\n", pool->d.end);
        printf("    .next = 0x%x\n", pool->d.next);
        printf("    .failed = %d\n", pool->d.failed);
        printf("  .max = %d\n", pool->max);
        printf("  .current = 0x%x\n", pool->current);
        printf("  .chain = 0x%x\n", pool->chain);
        printf("  .large = 0x%x\n", pool->large);
        printf("  .cleanup = 0x%x\n", pool->cleanup);
        printf("  .log = 0x%x\n", pool->log);
        printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);
        pool = pool->d.next;
    }
}

void dump_queue_from_head(ngx_queue_t *que)
{
    ngx_queue_t *q = ngx_queue_head(que);

    printf("(0x%x: (0x%x, 0x%x)) <==> \n", que, que->prev, que->next);

    for (; q != ngx_queue_sentinel(que); q = ngx_queue_next(q))
    {
        my_point_queue_t *point = ngx_queue_data(q, my_point_queue_t, queue);
        printf("(0x%x: (%-2d, %-2d), 0x%x: (0x%x, 0x%x)) <==> \n", point, point->point.x,
            point->point.y, &point->queue, point->queue.prev, point->queue.next);
    }
}

void dump_queue_from_tail(ngx_queue_t *que)
{
    ngx_queue_t *q = ngx_queue_last(que);

    printf("(0x%x: (0x%x, 0x%x)) <==> \n", que, que->prev, que->next);

    for (; q != ngx_queue_sentinel(que); q = ngx_queue_prev(q))
    {
        my_point_queue_t *point = ngx_queue_data(q, my_point_queue_t, queue);
        printf("(0x%x: (%-2d, %-2d), 0x%x: (0x%x, 0x%x)) <==> \n", point, point->point.x,
            point->point.y, &point->queue, point->queue.prev, point->queue.next);
    }
}

//sort from small to big
ngx_int_t my_point_cmp(const ngx_queue_t* lhs, const ngx_queue_t* rhs)
{
    my_point_queue_t *pt1 = ngx_queue_data(lhs, my_point_queue_t, queue);
    my_point_queue_t *pt2 = ngx_queue_data(rhs, my_point_queue_t, queue);

    if (pt1->point.x < pt2->point.x)
        return 0;
    else if (pt1->point.x > pt2->point.x)
        return 1;
    else if (pt1->point.y < pt2->point.y)
        return 0;
    else if (pt1->point.y > pt2->point.y)
        return 1;
    return 1;
}

#define Max_Num 6

int main()
{
    ngx_pool_t *pool;
    ngx_queue_t *myque;
    my_point_queue_t *point;
    my_point_t points[Max_Num] = {
            {10, 1}, {20, 9}, {9, 9}, {90, 80}, {5, 3}, {50, 20}
    };
    int i;

    printf("--------------------------------\n");
    printf("create a new pool:\n");
    printf("--------------------------------\n");
    pool = ngx_create_pool(1024, NULL);
    dump_pool(pool);

    printf("--------------------------------\n");
    printf("alloc a queue head and nodes :\n");
    printf("--------------------------------\n");
    myque = ngx_palloc(pool, sizeof(ngx_queue_t));  //alloc a queue head
    ngx_queue_init(myque);  //init the queue

    //insert  some points into the queue
    for (i = 0; i < Max_Num; i++)
    {
        point = (my_point_queue_t*)ngx_palloc(pool, sizeof(my_point_queue_t));
        point->point.x = points[i].x;
        point->point.y = points[i].y;
        ngx_queue_init(&point->queue);

        //insert this point into the points queue
        ngx_queue_insert_head(myque, &point->queue);
    }

    dump_queue_from_tail(myque);
    printf("\n");

    printf("--------------------------------\n");
    printf("sort the queue:\n");
    printf("--------------------------------\n");
    ngx_queue_sort(myque, my_point_cmp);
    dump_queue_from_head(myque);
    printf("\n");

    printf("--------------------------------\n");
    printf("the pool at the end:\n");
    printf("--------------------------------\n");
    dump_pool(pool);

    ngx_destroy_pool(pool);
    return 0;
}

3.2如何编译

请参考nginx-1.0.4源码分析—内存池结构ngx_pool_t及内存管理一文。本文编写的makefile文件如下。

CXX = gcc
CXXFLAGS += -g -Wall -Wextra
NGX_ROOT = /usr/src/nginx-1.0.4
TARGETS = ngx_queue_t_test
TARGETS_C_FILE = $(TARGETS).c
CLEANUP = rm -f $(TARGETS) *.o
all: $(TARGETS)
clean:
$(CLEANUP)
CORE_INCS = -I. \
-I$(NGX_ROOT)/src/core \
-I$(NGX_ROOT)/src/event \
-I$(NGX_ROOT)/src/event/modules \
-I$(NGX_ROOT)/src/os/unix \
-I$(NGX_ROOT)/objs \
NGX_PALLOC = $(NGX_ROOT)/objs/src/core/ngx_palloc.o
NGX_STRING = $(NGX_ROOT)/objs/src/core/ngx_string.o
NGX_ALLOC = $(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
NGX_QUEUE = $(NGX_ROOT)/objs/src/core/ngx_queue.o
$(TARGETS): $(TARGETS_C_FILE)
$(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING) $(NGX_ALLOC) $(NGX_QUEUE) $^ -o $@

3.3 运行结果

# ./ngx_queue_t_test
--------------------------------
create a new pool:
--------------------------------
pool = 0x8bcf020
  .d
    .last = 0x8bcf048
    .end = 0x8bcf420
    .next = 0x0
    .failed = 0
  .max = 984
  .current = 0x8bcf020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0
available pool memory = 984

--------------------------------
alloc a queue head and nodes :
--------------------------------
(0x8bcf048: (0x8bcf058, 0x8bcf0a8)) <==>
(0x8bcf050: (10, 1 ), 0x8bcf058: (0x8bcf068, 0x8bcf048)) <==>
(0x8bcf060: (20, 9 ), 0x8bcf068: (0x8bcf078, 0x8bcf058)) <==>
(0x8bcf070: (9 , 9 ), 0x8bcf078: (0x8bcf088, 0x8bcf068)) <==>
(0x8bcf080: (90, 80), 0x8bcf088: (0x8bcf098, 0x8bcf078)) <==>
(0x8bcf090: (5 , 3 ), 0x8bcf098: (0x8bcf0a8, 0x8bcf088)) <==>
(0x8bcf0a0: (50, 20), 0x8bcf0a8: (0x8bcf048, 0x8bcf098)) <==>

--------------------------------
sort the queue:
--------------------------------
(0x8bcf048: (0x8bcf088, 0x8bcf098)) <==>
(0x8bcf090: (5 , 3 ), 0x8bcf098: (0x8bcf048, 0x8bcf078)) <==>
(0x8bcf070: (9 , 9 ), 0x8bcf078: (0x8bcf098, 0x8bcf058)) <==>
(0x8bcf050: (10, 1 ), 0x8bcf058: (0x8bcf078, 0x8bcf068)) <==>
(0x8bcf060: (20, 9 ), 0x8bcf068: (0x8bcf058, 0x8bcf0a8)) <==>
(0x8bcf0a0: (50, 20), 0x8bcf0a8: (0x8bcf068, 0x8bcf088)) <==>
(0x8bcf080: (90, 80), 0x8bcf088: (0x8bcf0a8, 0x8bcf048)) <==>

--------------------------------
the pool at the end:
--------------------------------
pool = 0x8bcf020
  .d
    .last = 0x8bcf0b0
    .end = 0x8bcf420
    .next = 0x0
    .failed = 0
  .max = 984
  .current = 0x8bcf020
  .chain = 0x0
  .large = 0x0
  .cleanup = 0x0
  .log = 0x0
available pool memory = 880

该队列的逻辑图如下。