3. nginx基本数据结构之动态数组ngx_array_t

ngx_array_t 是nginx中的动态数组，当数组容量已满，仍向其插入数据，数组会动态改变数组的容量。
数组的特点是使用下标访问元素，其访问速度是常量。数组使用一块连续内存存储其元素，如果容量固定，可以使用普通数组；但很多场景，数组中元素个数事先未知，如果分配太多内存，会浪费宝贵的内存资源，故开发动态数组。
动态数组现在是一个很常用的数据结构，如 C++ STL 中的 vector 。
现在让我们看一下nginx中的动态数组 ngx_array_t， 其中内置自己的内存池.
ngx_array_t定义

typedef struct {
    // 数组所有元素的首地址
    void *elts;
    // 数组中已有元素的个数
    ngx_uint_t   nelts;
    // 数组中元素的大小
    size_t       size;
    // 当前数组的容量，可变
    ngx_uint_t   nalloc;
    // 内置的内存池
    ngx_pool_t *pool;
} ngx_array_t;

ngx_array_t的方法

// 初始化一个已经存在的数组，数组的所有元素的内存在pool中分配
        ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
        // 从内存池 pool 中 分配一个 ngx_array_t 数组对象，并初始化该对象。
        // 与 ngx_array_destroy 配对使用
        ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size);
        // 销毁一个数组对象，与 ngx_array_create 配对使用
        void ngx_array_destroy(ngx_array_t *a);
        // 在数组的后面获取一个空元素 ，代码中原有的注释可以很容易的帮助我们理解。
        void *ngx_array_push(ngx_array_t *a);
        // 在数组的后面获取n个空元素
        void *ngx_array_push_n(ngx_array_t *a, ngx_uint_t n);
        static ngx_inline ngx_int_t
    /*
     * Copyright (C) Igor Sysoev
     * Copyright (C) Nginx, Inc.
     */
    #include <ngx_config.h>
    #include <ngx_core.h>
    // 从内存池 pool 中 分配一个 ngx_array_t 数组对象，并初始化该对象。
    // 与 ngx_array_destroy 配对使用
    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;
        }
        if (ngx_array_init(a, p, n, size) != NGX_OK) {
            return NULL;
        }
        return a;
    }
    // 销毁一个数组对象，与 ngx_array_create 配对使用
    void
    ngx_array_destroy(ngx_array_t *a)
    {
        ngx_pool_t *p;
        p = a->pool;
        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;
        }
    }
    // 在数组的后面获取一个空元素 ，代码中原有的注释可以很容易的帮助我们理解。
    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 */
                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;
    }
    // 在数组的后面获取n个空元素
    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;
        size = n * a->size;
        if (a->nelts + n > a->nalloc) {
            /* the array is full */
            p = a->pool;
            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
                 */
                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;
        a->nelts += n;
        return elt;
    }

在nginx_cycle.c的ngx_cycle_t * ngx_init_cycle(ngx_cycle_t *old_cycle)

// 可以使用 ngx_inline ngx_int_t
    // ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size)
    // 简化代码，如下：
    // ngx_int_t ret;
    // n = old_cycle->paths.nelts ? old_cycle->paths.nelts : 10;
    // ret = ngx_array_init(cycle->paths, pool, n, sizeof(ngx_path_t *));
    // if(ret == NGX_ERROR) {
    // ngx_destroy_pool(pool);
    // return NULL;
    // }
    n = old_cycle->paths.nelts ? old_cycle->paths.nelts : 10;
    cycle->paths.elts = ngx_pcalloc(pool, n * sizeof(ngx_path_t *));
    if (cycle->paths.elts == NULL) {
        ngx_destroy_pool(pool);
        return NULL;
    }

    cycle->paths.nelts = 0;
    cycle->paths.size = sizeof(ngx_path_t *);
    cycle->paths.nalloc = n;
    cycle->paths.pool = pool;