nginx源码分析-双向链表

基本介绍

nginx的双向链表结构里只有与节点关联的信息，没有任何与业务相关的信息，从而做到数据与业务解耦

数据结构定义

// 双向链表
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_data(q, type, link)                                         \
    (type *) ((u_char *) q - offsetof(type, link))

上面的方法类似于linux内核中大量使用的一个宏定义

#define list_entry(ptr, type, member) \
    ((type *)((char *)(ptr) - (size_t)(&((type *)0)->member)))

这个宏可以分为5步（减号后面）：

1. 0
2. ((type) *0)
3. ((type *)0)->member)
4. &((type *)0)->member
5. (size_t)(&((type *)0)->member)

1. 内存地址0开始
2. 将0转换为type类型的结构体指针，让编译器认为这个结构是开始于程序段的起始位置
3. 引用结构体的member成员
4. 取这个成员的地址（不关心具体内容）
5. 将取到的地址强制转换为size_t类型

最终得到的是结构体成员相对于结构体首地址的偏移

减号前面：
ptr是具体的结构体成员，用ptr的地址减掉上面说的偏移，就得到结构体的首地址了

函数实现

// 初始化链表
#define ngx_queue_init(q)                                                     \
    (q)->prev = q;                                                            \
    (q)->next = q

// 判断是否为空
#define ngx_queue_empty(h)                                                    \
    (h == (h)->prev)

// 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

// 插在h后
#define ngx_queue_insert_tail(h, x)                                           \
    (x)->prev = (h)->prev;                                                    \
    (x)->prev->next = x;                                                      \
    (x)->next = h;                                                            \
    (h)->prev = x

// h是尾部  返回链表的第一个元素
#define ngx_queue_head(h)                                                     \
    (h)->next

// h是头部  返回连表的最后一个元素
#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


#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

// 分割链表
#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;


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

2020.8.24 15:21 深圳