Nginx数据结构之ngx_array_t

Nginx数据结构之ngx_array_t 动态数组

在Nginx数组中,内存分配是基于内存池的,并不是固定不变的。
当存储的元素越来越多,内存不够时会扩容,以当前的长度的2倍扩容。

数据结构定义

代码

1
2
3
4
5
6
7
8
// 动态数组
typedef struct {
void *elts; //elts指向数组的首地址
ngx_uint_t nelts; //nelts数组中已经使用的元素个数
size_t size; //每个数组元素占用的内存大小
ngx_uint_t nalloc; //当前数组中能够容纳元素的总大小
ngx_pool_t *pool; //内存池对象
} ngx_array_t;

图解

基础

ngx_array_init 初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//初始化
static ngx_inline ngx_int_t
ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
/*
* set "array->nelts" before "array->elts", otherwise MSVC thinks
* that "array->nelts" may be used without having been initialized
*/

//初始化数组成员,注意:nelts必须比elts先初始化
array->nelts = 0;
array->size = size;
array->nalloc = n;
array->pool = pool;

//分配数组数据所需要的内存
array->elts = ngx_palloc(pool, n * size);
if (array->elts == NULL) {
return NGX_ERROR;
}

return NGX_OK;
}

ngx_array_create 创建动态数组对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//创建动态数组对象
ngx_array_t *
ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size)
{
ngx_array_t *a;

//分配动态数组头部
a = ngx_palloc(p, sizeof(ngx_array_t));
if (a == NULL) {
return NULL;
}

//分配容量为n 动态数组数据区 并将其初始化
if (ngx_array_init(a, p, n, size) != NGX_OK) {
return NULL;
}

return a;
}

ngx_array_destroy 销毁数组对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//销毁数组对象,即数组所占据的内存被内存池回收
void
ngx_array_destroy(ngx_array_t *a)
{
ngx_pool_t *p;

p = a->pool;

//移动内存池的last指针,释放数组所有元素所占据的内存
if ((u_char *) a->elts + a->size * a->nalloc == p->d.last) {
p->d.last -= a->size * a->nalloc;
}

//释放数组首指针所占据的内存
if ((u_char *) a + sizeof(ngx_array_t) == p->d.last) {
p->d.last = (u_char *) a;
}
}

ngx_array_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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void *
ngx_array_push(ngx_array_t *a)
{
void *elt, *new;
size_t size;
ngx_pool_t *p;

if (a->nelts == a->nalloc) {

/* the array is full 数组满了 */

//所有元素占用的内存大小
size = a->size * a->nalloc;

p = a->pool;

if ((u_char *) a->elts + size == p->d.last
&& p->d.last + a->size <= p->d.end)
{
/*
* 若当前内存池的内存空间至少可容纳一个元素大小
* the array allocation is the last in the pool
* and there is space for new allocation
*/

p->d.last += a->size;
a->nalloc++;

} else {
/* allocate a new array 分配新的数组内存*/

//新的数组内存是现有的2倍
new = ngx_palloc(p, 2 * size);
if (new == NULL) {
return NULL;
}

//首先把现有数组的所有元素复制到新的数组中
ngx_memcpy(new, a->elts, size);
//数组的首地址
a->elts = new;
//容纳元素的总大小
a->nalloc *= 2;
}
}

elt = (u_char *) a->elts + a->size * a->nelts;
a->nelts++;

//返回指向新增加元素的指针
return elt;
}

代码注释 https://github.com/gxpisme/read_nginx/commit/663a1aa7d885fd564c58d1a1092a20ebd08cad80

xpisme wechat
微信号