Nginx源码解读-list

发表于 更新于 分类于

前言

Nginx中list的实现很简单，内部采用链表的形式串联起多个节点，其中每个节点采用一个数组的形式，可以存储多个数据。在源码文件中src/core/ngx_list.h|.c中可以看到相关的函数并不多，只有创建，初始化，添加三个方法，在明白了内存池的相关逻辑后，阅读起来还是很轻松的。

储备知识

数据格式定义

节点

1
2
3
4
5
6
7
typedef struct ngx_list_part_s  ngx_list_part_t;

struct ngx_list_part_s {
    void             *elts;     //节点保存元素的地方
    ngx_uint_t        nelts;    //节点的实际使用数量
    ngx_list_part_t  *next;     //下一个节点位置
};

list

1
2
3
4
5
6
7
typedef struct {
    ngx_list_part_t  *last;     //list中最后一个节点的位置
    ngx_list_part_t   part;     //list节点信息
    size_t            size;     //每个元素的大小
    ngx_uint_t        nalloc;   //每个节点可容纳元素的大小
    ngx_pool_t       *pool;     //list操作的相关的内存池
} ngx_list_t;

主要函数

ngx_list_create

创建list 参数顺序依次为 内存相关的内存池pool 每个节点的容量大小n 每个元素的大小size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

ngx_list_t *
ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    ngx_list_t  *list;

    /* 申请list结构的存储空间 */
    list = ngx_palloc(pool, sizeof(ngx_list_t));
    if (list == NULL) {
        return NULL;
    }

    /* 初始化list 为节点分配存储空间 */
    if (ngx_list_init(list, pool, n, size) != NGX_OK) {
        return NULL;
    }

    return list;
}

ngx_list_init

list初始化 主要是为节点申请存储空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    /* list节点申请数据存储空间 */
    list->part.elts = ngx_palloc(pool, n * size);
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }

    list->part.nelts = 0;
    list->part.next = NULL;
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return NGX_OK;
}

ngx_list_push

往list中插入数据 该方法返回一个list中的地址 赋值操作在外部完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;

    last = l->last;

    /* 当最后一个可用节点的实际使用数量 等于 节点的容量大小时  也就是最后一个节点已经满了 */
    if (last->nelts == l->nalloc) {

        /* 创建一个新的节点 */
        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
        if (last == NULL) {
            return NULL;
        }

        /* 为新节点的元素存储 申请空间 */
        last->elts = ngx_palloc(l->pool, l->nalloc * l->size);
        if (last->elts == NULL) {
            return NULL;
        }

        /* 初始化新节点 */
        last->nelts = 0;
        last->next = NULL;

        /* 把新节点挂在list后面 */
        l->last->next = last;

        /* 指定list中最后一个可用节点 */
        l->last = last;
    }

    /* 获取list最后一个节点上 新元素的位置 (节点数据存储起始地址 + 每个数据单元大小 * 节点实际使用数量 ) */
    elt = (char *) last->elts + l->size * last->nelts;
    last->nelts++;

    return elt;
}