动态数组结构 -- ngx_array_t

2015-03-19 21:37:16   最后更新: 2015-03-19 21:37:16   访问数量:648




数组是 C 语言中最常用的数据类型之一,它使用整块内存,按固定大小分割,所以很容易定位到指定序号的元素,因此,在所有容器中,数组的随机访问速度是最快的

但是 C 语言的数组是不能动态扩展的,所以 nginx 对他进行了一个封装,成为了类似于 C++ STL 中 vector 的数据类型

具有以下优点:

  1. 访问速度快
  2. 元素个数不确定,并可以动态扩充
  3. 内存池统一管理内存

 

nginx 动态数组相关的声明和定义分别在:ngx_array.h 和 ngx_array.c 两个文件中

 

// struct ngx_array_t // nginx 数组结构 {{{ typedef struct { void *elts; // 数组起始位置 ngx_uint_t nelts; // 数组元素个数 size_t size; // 单个元素大小 ngx_uint_t nalloc; // 空间能够容纳元素个数 ngx_pool_t *pool; // 内存池 } ngx_array_t; // }}}

 

 

结构说明

动态数组结构域说明
意义
elts真正的连续存储内存的首地址
nelts当前已经存在数组中的元素个数
size每个元素的大小
nalloc当前数组空间所能容纳的元素个数
pool指向数组分配所在的内存池

 

nginx 动态数组主要提供了以下操作函数:

动态数组操作函数
函数名意义
ngx_array_init数组结构初始化(ngx_array_create 中调用)
ngx_array_create动态数组创建
ngx_array_destroy动态数组销毁
ngx_array_push在动态数组尾部插入一个元素
ngx_array_push_n在动态数组尾部插入n个元素

 

// ngx_array_t * ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size) // 数组创建 {{{ 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_t 结构分配了空间,然后调用了 ngx_array_init 函数初始化 ngx_array_t 结构的各个域,并未实际的存储区域分配空间

 

// static ngx_inline ngx_int_t // ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, // ngx_uint_t n, size_t size) // 数组结构初始化 {{{ 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 */ 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; } // }}}

 

 

// void ngx_array_destroy(ngx_array_t *a) // 数组销毁 {{{ 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; } } // }}}

 

 

如果该连续存储区域或 ngx_array_t 是内存池已用空间的尾部,则将他们释放掉,以便可以节约这部分空间的使用,否则不做任何处理

 

// void * ngx_array_push(ngx_array_t *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; } // }}}

 

 

如果空间足够,则插入该元素,并更新 ngx_array_t 各个域的值

否则开辟新的连续内存,并将数组中所有数据全部拷贝到新的内存,并添加元素,这样做虽然消耗了一定的效率,但是保证了数组空间的连续性,也就保证了今后随机访问的高效性

 

// void * ngx_array_push_n(ngx_array_t *a, ngx_uint_t n) // 在数组中追加 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; } // }}}

 

 

与 ngx_array_push 的操作非常类似,只是他一次性插入 n 个元素,提高了效率

 






技术帖      算法      c++      cpp      c语言      数据结构      龙潭书斋      nginx      c      server      内存池      webserver      动态数组      stl      vector     


京ICP备15018585号