Nginx数据结构之ngx_list_t

Nginx数据结构之ngx_list_t

ngx_list_t是Nginx封装的链表容器,他在Nginx中使用得很频繁。
与普通链表不同,不同点就在于它的节点,它的节点不像我们常见的list的节点,只能存放一个元素,ngx_list_t的节点实际上是一个固定大小的数组。

结构定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct ngx_list_part_s  ngx_list_part_t;

struct ngx_list_part_s {
void *elts; // 节点中存放具体元素的内存的开始地址。
ngx_uint_t nelts; // 节点中已有元素个数。这个值是不能大于链表头节点ngx_list_t类型中的nalloc字段的。
ngx_list_part_t *next;
};


typedef struct {
ngx_list_part_t *last; // 指向该链表的最后一个节点
ngx_list_part_t part; // 该链表的首个存放具体元素的节点
size_t size; // 数组存储的是某种类型的数据结构,且ngx_list_t是非常灵活的数据结构,只是通过size限制每一个数组元素占用空间的大小
ngx_uint_t nalloc; // 每个节点所含的固定大小的数组的容量。
ngx_pool_t *pool; // 该list使用的分配内存的pool。
} ngx_list_t;

图解结构

解释

  • ngx_list_t中的pool内存池为其分配了连续的内存
  • 最前端内存存储ngx_list_t结构体的成员
  • 紧接着是第一个ngx_list_part_t结构占用的内存
  • 然后是ngx_list_part_t结构指向的数组,共占用size*nalloc字节,表示数组中拥有nalloc个大小为size的元素
  • 其后面2个ngx_list_part_t结构以及它所指向的数组,依次类推。

Nginx提供的接口

ngx_list_create 创建新的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* ngx_list_create 创建元素时,
* pool参数是内存池对象
* n是每个链表可容纳元素的个数 相当于ngx_list_t结构中nalloc成员
* size是每个元素的大小
*
* 返回 包含n个大小为size字节的连续内存块,也就是ngx_list_t结构中的part成员
*/
ngx_list_t * ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
ngx_list_t *list;

list = ngx_palloc(pool, sizeof(ngx_list_t));
if (list == NULL) {
return NULL;
}

if (ngx_list_init(list, pool, n, size) != NGX_OK) {
return NULL;
}

return list;
}

ngx_list_init 初始化已有的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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->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 添加新的元素

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
/**
* ngx_list_push 表示添加新的元素,传入的参数是ngx_list_t链表
* 正常情况下,返回的是新分配的元素首地址
* 如果返回NULL空指针,则添加失败
* 在使用它时通常先调用ngx_list_push得到返回的元素地址,再对返回的地址进行赋值
*/
void * ngx_list_push(ngx_list_t *l)
{
void *elt;
ngx_list_part_t *last;

last = l->last;

//存储list的内存满了 有兴趣看源码 如何做的
if (last->nelts == l->nalloc) {
....
/* the last part is full, allocate a new list part */
....
}

elt = (char *) last->elts + l->size * last->nelts;
last->nelts++;

return elt;
}

遍历链表的demo

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
the iteration through the list:

part = &list.part; // part用于指向链表中的每一个ngx_list_part_t数组
data = part->elts; // 根据链表中的数据类型,把数组里的elts转化为该类型使用

// i表示元素在链表的每个ngx_list_part_t数组里的序号
for (i = 0 ;; i++) {

if (i >= part->nelts) { // 地址
if (part->next == NULL) {
//如果某个ngx_list_part_t数组的next指针为空,则说明遍历完链表
break;
}

// 访问下一个ngx_list_part_t
part = part->next;
data = part->elts;

将序号置为0,准备重新访问下一个数组
i = 0;
}

// 输出每个ngx_list_part_t数组中的元素
... data[i] ...
}

参考文档
http://tengine.taobao.org/book/chapter_02.html
深入理解Nginx
代码注释 https://github.com/gxpisme/read_nginx/commit/48518fd2dcbd862e01bd86ff49ba9f82fe9a430a

xpisme wechat
微信号