Nginx 源码分析：ngx_queue_t

Yuqi 发布于2019-06-25 13:18 / 1352人阅读

摘要：源文件路径版本主要作用分析是提供的双向链表。同时，由于这种链表没有节点成员变量，所以需要作为带有节点变量的结构体的成员变量存在，这种情况下，称这种链表为寄宿链表，链表所在结构体称为宿主。和常规的双向链表操作基本相同。

源文件路径

版本：1.8.0

srccoreNgx_queue.h
srccoreNgx_queue.c

主要作用分析

ngx_queue_t是Nginx提供的双向链表。

通常意义上的双向链表是长成这个样子的：

struct double_link_s {
    int            node;
    double_link_t *prev;
    double_link_t *next;
};

包含三个要素：节点数据data，指向前一个节点的指针prev及指向后一下节点的指针next。

然后就是老生常谈的对于双向链表的创建、插入、删除等等。我就不详说了，自行google即可。

其实，如果你仔细观察一下，就会发现，对双向链表的操作基本都是围绕prev和next展开的，与节点数据data关系不大。

所以，将双向链表的操作抽象出来，形成与链表节点无关的抽象可以帮助我们更好的去操作各种节点类型的双向链表。

这种链表的特点是只有prev和next两个变量，没有表示链表节点的成员变量。因此，这种链表也被称为轻量级链表。

同时，由于这种链表没有节点成员变量，所以需要作为带有节点变量的结构体的成员变量存在，这种情况下，称这种链表为寄宿链表，链表所在结构体称为宿主。

举个栗子，就是长成这个样子：

typedef double_link_s double_link_t;
struct double_link_s {
    double_link_t *prev;
    double_link_t *next;
};

struct node_s {
    int             node;
    double_link_t   link;
}

简单来说，如果想将结构体作为链表节点，那么就将这种轻量级链表作为成员变量加入到自身。

示意图如下：

这样，操作链表就是操作链表中的轻量级链表，因此，可以定义出通用的链表结构。

在Nginx中，这个通用的双向链表结构就是ngx_queue_t。这不是Nginx发明的，在Linux内核中也使用这种链表。

数据结构

ngx_queue_t

根据上述分析，定义轻量级链表很简单。

typedef struct ngx_queue_s  ngx_queue_t;

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

ngx_queue_t的管理和使用

既然是双向链表，那么关于双向链表的基本操作是相同的。所以，不需要多解释，直接看源码即可。

ngx_queue_t初始化

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

使用ngx_queue_t类型的变量q初始化链表，由于是初始化，因此prev和next均指向自身。q作为管理整个链表的空节点。

判断ngx_queue_t是否为空

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

插入操作

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

虽然宏的名字叫insert_head，实际上可以是插入的通用操作。所以，在源码中有

#define ngx_queue_insert_after   ngx_queue_insert_head

这里跟正常的双链表插入操作没有区别。

如何获取链表节点

采用寄宿链表，一个绕不开的问题就是，如何根据链表获得节点的数据。

这里解决的基本思路如下：

寄宿链表是链表节点结构体的一个成员变量，虽然结构体可能因为对齐的问题使得各个成员变量在空间上不连续，但是，整个结构体本身仍然可以看作一块连续的内存区域。

所以，可以利用offsetof宏计算出寄宿链表成员变量相对于结构体起始位置的偏移量

寄宿链表的起始地址 - 寄宿链表成员变量相对于结构体起始位置的偏移量 = 结构体的起始地址

所以，ngx_queue_t获取节点数据就利用了上述方法

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

其中q为寄宿链表变量，type为寄宿链表所在结构体的类型，link为寄宿链表在type结构体中的变量名。
这个宏返回宿主结构体的首地址。

获取双向链表中间节点

这属于双向链表操作的老梗了，就是使用了双指针，移动速度差一倍，速度快的指针到末尾时，速度慢的所在就是中间位置。

源码如下

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

当然，还有其他操作，比如排序，移除等等。和常规的双向链表操作基本相同。
这里就不详细描述了。

私有云服务器托管 nginx源码分析 nginx源码 nginx日志分析 ngx_queue_t

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/15092.html

Nginx 源码分析：ngx_queue_t

摘要：源文件路径版本主要作用分析是提供的双向链表。同时，由于这种链表没有节点成员变量，所以需要作为带有节点变量的结构体的成员变量存在，这种情况下，称这种链表为寄宿链表，链表所在结构体称为宿主。和常规的双向链表操作基本相同。源文件路径版本：1.8.0 srccoreNgx_queue.h srccoreNgx_queue.c 主要作用分析 ngx_queue_t是Nginx提供的...

jsyzchen 2019-07-25 13:30 评论0 收藏0
Nginx 源码分析：ngx_queue_t

摘要：源文件路径版本主要作用分析是提供的双向链表。同时，由于这种链表没有节点成员变量，所以需要作为带有节点变量的结构体的成员变量存在，这种情况下，称这种链表为寄宿链表，链表所在结构体称为宿主。和常规的双向链表操作基本相同。源文件路径版本：1.8.0 srccoreNgx_queue.h srccoreNgx_queue.c 主要作用分析 ngx_queue_t是Nginx提供的...

IamDLY 2019-05-29 18:06 评论0 收藏0
Nginx 源码分析第三篇之 ngx_queue 队列

摘要：相关系列前面分析了数组，现在看一下队列和哈希表的实现。队列是一个双向链表，实现了一个队列的操作逻辑。它们都将链表节点塞入数据结构。对于常用的解决冲突的方法有线性探测二次探测和开链法等。相关系列：http://www.codefrom.com/p/nginx 前面分析了ngx_array_t数组，现在看一下ngx_queue队列和ngx_hash哈希表的实现。 ngx_qu...

frontoldman 2019-07-25 13:31 评论0 收藏0
【Nginx源码研究】nginx限流模块详解

摘要：限流算法最简单粗暴的限流算法就是计数器法了，而比较常用的有漏桶算法和令牌桶算法计数器计数器法是限流算法里最简单也是最容易实现的一种算法。运营研发团队李乐高并发系统有三把利器：缓存、降级和限流；限流的目的是通过对并发访问/请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务（定向到错误页）、排队等待（秒杀）、降级（返回兜底数据或默认数据）；高并发系统常见的限流有：限制总并发...

voyagelab 2019-07-25 14:28 评论0 收藏0
【Nginx源码分析】Nginx配置文件解析（二）

摘要：配置文件解析一配置解析流程解析配置的入口函数是，其输入参数表示配置文件路径，如果为表明此时解析的是指令块。函数逻辑比较简单，就是读取完整指令，并调用函数处理指令。运营研发团队李乐本文作为nginx配置文件解析的第二篇，开始讲解nginx配置文件解析的源码，在阅读本文之前，希望你已经阅读过第一篇。《nginx配置文件解析（一）》 1.1配置解析流程解析配置的入口函数是ngx_...

JerryC 2019-07-25 14:30 评论0 收藏0