Nginx源码解读-数组

发表于 更新于 分类于

前言

数组在Nginx中是通过ngx_array_t的结构体实现的，在这个结构体中，分别记录了数组的容量大小、实际使用的数量、每个元素的大小以及存储数组元素空间的起始地址，其内部存储数组元素的地方是一块连续的空间。在相关的函数中，都会看到为了维持这个连续性而进行的一些操作。

连续性是指当内存池为数组元素分配存储空间后，该内存池没有为其他的场景再次分配内存，接下来当数组需要扩大容量的时候，内存池能够接着上次为数组元素分配的地址结尾处接着分配空间，从而保证数组元素存储空间的连续。

储备知识

数据结构定义

1
2
3
4
5
6
7
typedef struct {
    void        *elts;      //元素存储位置的起始地址
    ngx_uint_t   nelts;     //数组中实际使用数量
    size_t       size;      //数组每一个元素的大小
    ngx_uint_t   nalloc;    //数组的总容量大小
    ngx_pool_t  *pool;      //数组存储的内存池
} ngx_array_t;

主要函数

ngx_array_create

该函数作用是创建一个数组并返回，参数列表依次为存储数组的内存池p、数组的容量n、数组每个元素的大小size

注意:在这个方法中只是去申请了ngx_array_t大小的内存，用来存储元素的内存申请是在初始化ngx_array_init中完成的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ngx_array_t *
ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size)
{
    ngx_array_t *a;

    /* 在内存池中申请`ngx_array_t`大小的内存 */
    a = ngx_palloc(p, sizeof(ngx_array_t));
    if (a == NULL) {
        return NULL;
    }

    /* 初始化数组 */
    if (ngx_array_init(a, p, n, size) != NGX_OK) {
        return NULL;
    }

    return a;
}

ngx_array_init

初始化数组，设置数组各个参数的值，为数组元素申请存储空间，参数列表依次是待初始化的数组array、存储数组的内存池pool、数组容量大小n、数组每个元素大小size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static ngx_inline ngx_int_t
ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
    
    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_destroy

销毁数组，主要操作是释放存储数组元素空间和存储数组的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
53
54
55
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)
        {

            /* 移动内存池的可分配指针 并把数组的容量加一 */
            p->d.last += a->size;
            a->nalloc++;

        } else {

            /* 当内存池不能保证元素存储空间的连续性 或者 内存池剩余大小不够放下一个元素了 这种情况重新申请内存，大小扩大一倍，把内存池中源数据拷贝过去 */

            /* 创建一个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;
}

ngx_array_push_n

向数组内添加n个元素 返回n个元素存储空间的起始地址 具体的赋值操作在外部完成

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
53
54
55
56
57
58
59
60
61
void *
ngx_array_push_n(ngx_array_t *a, ngx_uint_t n)
{
    void        *elt, *new;
    size_t       size;
    ngx_uint_t   nalloc;
    ngx_pool_t  *p;

    /* n个元素需要的空间大小 */
    size = n * a->size;

    /* 如果超过了数组的容量 */
    if (a->nelts + n > a->nalloc) {

        /* the array is full */

        p = a->pool;

        /* 如果数组在内存池中能够保证连续 且 内存池中可分配空间大小满足要申请的n个元素大小 */
        if ((u_char *) a->elts + a->size * a->nalloc == p->d.last
            && p->d.last + size <= p->d.end)
        {
            /*
             * the array allocation is the last in the pool
             * and there is space for new allocation
             */

            /* 直接移动内存池可分配指针 并把数组容量加上n */ 
            p->d.last += size;
            a->nalloc += n;

        } else {
            /* 数组在内存池中不能够保证连续 或者 内存池中可分配空间大小 */
            /* allocate a new array */

            /* 扩容后的数组容量大小 */
            nalloc = 2 * ((n >= a->nalloc) ? n : a->nalloc);

            /* 从内存池中申请内存 */
            new = ngx_palloc(p, nalloc * a->size);
            if (new == NULL) {
                return NULL;
            }

            /* 把之前存储数组元素的内存数据拷贝到新的内存中 */
            ngx_memcpy(new, a->elts, a->nelts * a->size);
            
            /* 重新指向一下保存数组元素的地址 和数组大小 */
            a->elts = new;
            a->nalloc = nalloc;
        }
    }

    /* 获取内存池中新元素的位置  元素起始地址 + (每个元素大小 * 数组实际使用大小)  */
    elt = (u_char *) a->elts + a->size * a->nelts;

    /* 数组实际使用数量 加n */
    a->nelts += n;

    return elt;
}