由Nginx源码写双向循环链表

Nginx是一款轻量级的Web 服务器/反向代理服务器及电子邮件（IMAP/POP3）代理服务器，在BSD-like 协议下发行。其特点是占有内存少，并发能力强，事实上nginx的并发能力确实在同类型的网页服务器中表现较好，中国大陆使用nginx网站用户有：百度、京东、新浪、网易、腾讯、淘宝等。

Nginx提供了轻量级的双向链表,仅有指针域,而无数据域.用户在使用的时候需要自定义一个包含了这个指针域的结构体,其指针域定义如下:

typedef struct ngx_queue_s ngx_queue_t; struct ngx_queue_s { ngx_queue_t *prev; // 前置指针域 ngx_queue_t *next; // 后置指针域 };

用户使用的图示: 大概扫了一眼实现的源码,看了下风格,我模仿它写了一个双向循环链表.

初始化

提示: 方法名: ngx_queue_init(h)

参数含义: h为链表容器结构体ngx_queue_t的指针

执行意义: 将链表容器初始化,这时会自动置为空链表

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

判空

提示: 方法名: ngx_queue_empty(h)

参数含义: h为链表容器结构体ngx_queue_t的指针

执行意义: 检测链表容器中是否为空,即是否没有一个元素存在.如果返回非0,表示链表h是空的.

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

插入元素

此处使用的思想正如我在之前的《单链表》一文中写的链表插入的思想,归纳为八个字:先斩后奏,先左后右.传送链接:单链表 提示: 方法名: ngx_queue_insert_head(h,x)

参数含义: h为链表容器结构体ngx_queue_t的指针,x为插入元素结构体中ngx_queue_t成员的指针

执行意义: 将元素x插入到链表容器h的头部

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

提示: 方法名: ngx_queue_insert_tail(h,x)

参数含义: h为链表容器结构体ngx_queue_t的指针,x为插入元素结构体中ngx_queue_t成员的指针

执行意义: 将元素x插入到链表容器h的末尾

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

查找

提示: 方法名: ngx_queue_head(h)

参数含义: h为链表容器结构体ngx_queue_t的指针

执行意义: 返回链表容器h中的第一个元素的ngx_queue_t结构体指针

#define ngx_queue_head(q) \ (q) -> next

提示: 方法名: ngx_queue_last(h)

参数含义: h为链表容器结构体ngx_queue_t的指针

执行意义: 返回链表容器h中的最后一个元素的ngx_queue_t结构体指针

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

提示: 方法名: ngx_queue_next(q)

参数含义: q为链表中某一个元素结构体的ngx_queue_t成员的指针

执行意义: 返回q元素的下一个元素

#define ngx_queue_next(q) \ (q) -> next

提示: 方法名: ngx_queue_prev(q)

参数含义: q为链表中某一个元素结构体的ngx_queue_t成员的指针

执行意义: 返回q元素的上一个元素

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

删除

提示: 方法名: ngx_queue_remove(x)

参数含义: x为插入元素结构体中ngx_queue_t成员的指针

执行意义: 由容器中移除x元素

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

寻址

提示: 方法名: ngx_queue_data(q, type, link)

参数含义: q为链表中某一个元素结构体中ngx_queue_t成员的指针,type为链表元素的结构体类型名称(该结构体中必须包含ngx_queue_t类型的成员),link是上面这个结构体重ngx_queue_t类型的成员名字

执行意义: 返回q元素(ngx_queue_t类型)所属结构体(任何struct类型,其中可在任意位置包含ngx_queue_t类型的成员)的地址

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

这里用到了offsetof这个宏.

C 库宏 offsetof(type, member-designator) 会生成一个类型为 size_t 的整型常量，它是一个结构成员相对于结构开头的字节偏移量。成员是由 member-designator 给定的，结构的名称是在 type 中给定的。

全部代码及测试代码

这里只测试了部分宏函数.

#include <iostream> using namespace std; typedef struct ngx_queue_s ngx_queue_t; struct ngx_queue_s { ngx_queue_t *prev; // 前置指针域 ngx_queue_t *next; // 后置指针域 }; #define ngx_queue_init(q) \ (q) -> prev = q; \ (q) -> next = q; #define ngx_queue_empty(q) \ (q == (q) -> prev) #define ngx_queue_insert_head(q,x) \ (x) -> prev = q; \ (x) -> next = (q) -> next; \ (q) -> next -> prev = x; \ (q) -> next = x; #define ngx_queue_insert_tail(q,x) \ (x) -> prev = (q) -> prev; \ (x) -> next = q; \ (q) -> prev -> next = x; \ (q) -> prev = x; #define ngx_queue_head(q) \ (q) -> next #define ngx_queue_last(q) \ (q) -> prev #define ngx_queue_remove(x) \ (x) -> prev -> next = (x) -> next; \ (x) -> next -> prev = (x) -> prev; #define ngx_queue_next(q) \ (q) -> next #define ngx_queue_prev(q) \ (q) -> prev #define ngx_queue_data(q, type, link) \ (type *)((unsigned char *)q - offsetof(type, link)) typedef struct { ngx_queue_t p; int data; }User;//用户自定义结构体 void printNginx(ngx_queue_t *node) { ngx_queue_t *e = ngx_queue_head(node);//第一个结点 while (e != node) { User *node = ngx_queue_data(e, User, p);//寻址 cout << node->data << "\t"; e = ngx_queue_next(e); } cout << endl; } int main(void) { User *user=new User; ngx_queue_t *head = &(user->p);//头结点 ngx_queue_init(head); if (ngx_queue_empty(head)) { cout << "链表为空!" << endl; } int n; cout << "请输入插入元素的个数(正在使用头插法):"; cin >> n; while (n--) { User *node=new User; ngx_queue_t *e = &(node->p); cout << "请输入元素的数据:"; cin >> node->data; ngx_queue_insert_head(head, e); } printNginx(head); system("pause"); return 0; }

事实上,在写测试代码的时候相当困难,中间改写了很多次,其根本原因是不熟悉其体现的思想.不过好在多次思考,断点调试,揣摩代码,最终才有了这篇文章.