Open Linkerist opened 5 years ago
ngx_array_t动态数组类似于C++语言STL库的vector容器,它用连续的内存存放着大小相同的元素(就像数组),这使得它按照下标检索数据的效率非常高,可以用O(1)的时间来访问随机元素。相比数组,它的优势在于,数组通常是固定大小的,而ngx_array_t可以在达到容量最大值时自动扩容(扩容算法与常见的vector容器不同)。ngx_array_t与ngx_queue_t的一个显著不同点在于,ngx_queue_t并不负责为容器元素分配内存,而ngx_array_t是负责容器元素的内存分配的。ngx_array_t也是Nginx中应用非常广泛的数据结构,本章介绍的支持通配符的散列表中就有使用它的例子。 ngx_array_t是一个顺序容器,它在Nginx中大量使用。ngx_array_t容器以数组的形式存储元素,并支持在达到数组容量的上限时动态改变数组的大小。
为什么设计ngx_array_t动态数组
数组的优势是它的访问速度。由于它使用一块完整的内存,并按照固定大小存储每一个元素,所以在访问数组的任意一个元素时,都可以根据下标直接寻址找到它,另外,数组的访问速度是常量级的,在所有的数据结构中它的速度都是最快的。然而,正是由于数组使用一块连续的内存存储所有的元素,所以它的大小直接决定了所消耗的内存。可见,如果预分配的数组过大,肯定会浪费宝贵的内存资源。那么,数组的大小究竟应该分配多少才是够用的呢?当数组大小无法确定时,动态数组就“登场”了。 C++语言的STL中的vector容器就像ngx_array_t一样是一个动态数组。它们在数组的大小达到已经分配内存的上限时,会自动扩充数组的大小。具备了这个特点之后,ngx_array_t动态数组的用处就大多了,而且它内置了Nginx封装的内存池,因此,它分配的内存也是在内存池中申请得到。ngx_array_t容器具备以下3个优点:
动态数组的使用方法 ngx_array_t动态数组的实现仅使用1个结构体,如下所示。
typedef struct ngx_array_s ngx_array_t; struct ngx_array_s { // elts指向数组的首地址 void *elts; // nelts是数组中已经使用的元素个数 ngx_uint_t nelts; // 每个数组元素占用的内存大小 size_t size; // 当前数组中能够容纳元素个数的总大小 ngx_uint_t nalloc; // 内存池对象 ngx_pool_t *pool; };
如上已经简单描述了ngx_array_t结构体中各成员的意义,通过下图,读者可以有更直观的理解。
array = { .elts = 0x808600ff, .nelts = 3, .size = 4, .nalloc = 5, .pool = ? }
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) { /* * 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; } 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; } a->elts = ngx_palloc(p, n * size); if (a->elts == NULL) { return NULL; } a->nelts = 0; a->size = size; a->nalloc = n; a->pool = p; return 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; } } 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; } 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_t结构体,那么可以先调用ngx_array_init方法初始化动态数组。如果要重新在内存池上定义ngx_array_t结构体,则可以调用ngx_array_create方法创建动态数组。这两个方法都会预分配一定容量的数组元素。 在向动态数组中添加新元素时,最好调用ngx_array_push或者ngx_array_push_n方法,这两个方法会在达到数组预分配容量上限时自动扩容,这比直接操作ngx_array_t结构体中的成员要好得多,具体将在7.3.3节的例子中详细说明。
Note: 因为ngx_array_destroy是在内存池中销毁动态数组及其分配的元素内存的(如果动态数组的ngx_array_t结构体内存是利用栈等非内存池方式分配,那么调用ngx_array_destroy会导致不可预估的错误),所以它必须与ngx_array_create配对使用。
使用动态数组的例子 如下以一个简单的例子说明如何使用动态数组。这里仍然以《nginx 双向链表》中介绍的TestNode作为数组中的元素类型。首先,调用ngx_array_create方法创建动态数组,代码如下。
ngx_array_t* dynamicArray = ngx_array_create(cf->pool, 1, sizeof(TestNode));
这里创建的动态数组只预分配了1个元素的空间,每个元素占用的内存字节数为sizeof(TestNode),也就是TestNode结构体占用的空间大小。 然后,调用ngx_array_push方法向dynamicArray数组中添加两个元素,代码如下。
TestNode* a = ngx_array_push(dynamicArray); a->num = 1; a = ngx_array_push(dynamicArray); a->num = 2;
这两个元素的num值分别为1和2。注意,在添加第2个元素时,实际已经发生过一次扩容了,因为调用ngx_array_create方法时只预分配了1个元素的空间。下面尝试用ngx_array_push_n方法一次性添加3个元素,代码如下。
TestNode* b = ngx_array_push_n(dynamicArray, 3); b->num = 3; (b+1)->num = 4; (b+2)->num = 5;
这3个元素的num值分别为3、4、5。下面来看一下是如何遍历dynamicArray动态数组的,代码如下。
TestNode* nodeArray = dynamicArray->elts; ngx_uint_t arraySeq = 0; for (; arraySeq < dynamicArray->nelts; arraySeq++) { a = nodeArray + arraySeq; // 下面处理数组中的元素a … }
了解了遍历dynamicArray动态数组的方法后,再来看一下销毁动态数组的方法,这就非常简单了,如下所示:
ngx_array_destroy(dynamicArray);
动态数组的扩容方式 如下介绍当动态数组达到容量上限时是如何进行扩容的。ngx_array_push和ngx_array_push_n方法都可能引发扩容操作。 当已经使用的元素个数达到动态数组预分配元素的个数时,再次调用ngx_array_push或者ngx_array_push_n方法将引发扩容操作。ngx_array_push方法会申请ngx_array_t结构体中size字节大小的内存,而ngx_array_push_n方法将会申请n(n是ngx_array_push_n的参数,表示需要添加n个元素)个size字节大小的内存。每次扩容的大小将受制于内存池的以下两种情形:
Note: 上述第2种情形涉及数据的复制。新扩容一倍以上的动态数组将在全新的内存块上,这时将有一个步骤将原动态数组中的元素复制到新的动态数组中,当数组非常大时,这个步骤可能会耗时较长。
本文暂取自代码、网络或书籍,只用作学习备忘,不作盈利等他用,如有侵权,请联系Linkerist@163.com
ngx_array_t动态数组类似于C++语言STL库的vector容器,它用连续的内存存放着大小相同的元素(就像数组),这使得它按照下标检索数据的效率非常高,可以用O(1)的时间来访问随机元素。相比数组,它的优势在于,数组通常是固定大小的,而ngx_array_t可以在达到容量最大值时自动扩容(扩容算法与常见的vector容器不同)。ngx_array_t与ngx_queue_t的一个显著不同点在于,ngx_queue_t并不负责为容器元素分配内存,而ngx_array_t是负责容器元素的内存分配的。ngx_array_t也是Nginx中应用非常广泛的数据结构,本章介绍的支持通配符的散列表中就有使用它的例子。 ngx_array_t是一个顺序容器,它在Nginx中大量使用。ngx_array_t容器以数组的形式存储元素,并支持在达到数组容量的上限时动态改变数组的大小。
为什么设计ngx_array_t动态数组
数组的优势是它的访问速度。由于它使用一块完整的内存,并按照固定大小存储每一个元素,所以在访问数组的任意一个元素时,都可以根据下标直接寻址找到它,另外,数组的访问速度是常量级的,在所有的数据结构中它的速度都是最快的。然而,正是由于数组使用一块连续的内存存储所有的元素,所以它的大小直接决定了所消耗的内存。可见,如果预分配的数组过大,肯定会浪费宝贵的内存资源。那么,数组的大小究竟应该分配多少才是够用的呢?当数组大小无法确定时,动态数组就“登场”了。 C++语言的STL中的vector容器就像ngx_array_t一样是一个动态数组。它们在数组的大小达到已经分配内存的上限时,会自动扩充数组的大小。具备了这个特点之后,ngx_array_t动态数组的用处就大多了,而且它内置了Nginx封装的内存池,因此,它分配的内存也是在内存池中申请得到。ngx_array_t容器具备以下3个优点:
动态数组的使用方法 ngx_array_t动态数组的实现仅使用1个结构体,如下所示。
如上已经简单描述了ngx_array_t结构体中各成员的意义,通过下图,读者可以有更直观的理解。
ngx_array_t动态数组还提供了若干种基本方法,如下
如果使用已经定义过的ngx_array_t结构体,那么可以先调用ngx_array_init方法初始化动态数组。如果要重新在内存池上定义ngx_array_t结构体,则可以调用ngx_array_create方法创建动态数组。这两个方法都会预分配一定容量的数组元素。 在向动态数组中添加新元素时,最好调用ngx_array_push或者ngx_array_push_n方法,这两个方法会在达到数组预分配容量上限时自动扩容,这比直接操作ngx_array_t结构体中的成员要好得多,具体将在7.3.3节的例子中详细说明。
使用动态数组的例子 如下以一个简单的例子说明如何使用动态数组。这里仍然以《nginx 双向链表》中介绍的TestNode作为数组中的元素类型。首先,调用ngx_array_create方法创建动态数组,代码如下。
这里创建的动态数组只预分配了1个元素的空间,每个元素占用的内存字节数为sizeof(TestNode),也就是TestNode结构体占用的空间大小。 然后,调用ngx_array_push方法向dynamicArray数组中添加两个元素,代码如下。
这两个元素的num值分别为1和2。注意,在添加第2个元素时,实际已经发生过一次扩容了,因为调用ngx_array_create方法时只预分配了1个元素的空间。下面尝试用ngx_array_push_n方法一次性添加3个元素,代码如下。
这3个元素的num值分别为3、4、5。下面来看一下是如何遍历dynamicArray动态数组的,代码如下。
了解了遍历dynamicArray动态数组的方法后,再来看一下销毁动态数组的方法,这就非常简单了,如下所示:
动态数组的扩容方式 如下介绍当动态数组达到容量上限时是如何进行扩容的。ngx_array_push和ngx_array_push_n方法都可能引发扩容操作。 当已经使用的元素个数达到动态数组预分配元素的个数时,再次调用ngx_array_push或者ngx_array_push_n方法将引发扩容操作。ngx_array_push方法会申请ngx_array_t结构体中size字节大小的内存,而ngx_array_push_n方法将会申请n(n是ngx_array_push_n的参数,表示需要添加n个元素)个size字节大小的内存。每次扩容的大小将受制于内存池的以下两种情形:
本文暂取自代码、网络或书籍,只用作学习备忘,不作盈利等他用,如有侵权,请联系Linkerist@163.com