ngx_array_t 动态数组简介
- nginx所包装的动态数组和C++STL库中的vector容器类似,vector容器基于动态数组写的,即其本质也是一个动态数组.
- 数组的优点在于随机访问数组中的任意一个元素的时间复杂度为O(1).即常量级.但是唯一的缺点是其大小需要预先设定,并且是一块连续的内存,且这片内存的大小是固定的了.
为了克服这个缺点,动态数组应运而生了. - ngx_array_t 内置了Nginx封装的内存池,因此,它分配的内存也是在内存池中申请得到.
ngx_array_t容器具备的优点
- 访问速度快
- 允许元素个数具备不确定性
- 负责元素占用内存的分配,这些内存将由内存池统一管理
ngx_array_t数据结构实现
#include <stdio.h>
typedef struct ngx_array_s ngx_array_t;
struct ngx_array_s{
void *elts;//elts指向数组的首地址
ngx_uint_t nelts;//nelts是数组中已经使用的元素个数
size_t size;//每个元素占用内存的大小
ngx_uint_t nalloc;//当前数组中能够容纳元素个数的总大小
ngx_pool_t *pool;//内存池对象,管理内存分配
};
ngx_array_t动态数组的成员及其提供的方法.PNG
动态数组提供的方法.PNG
ngx_array_t 的创建方法
- 调用ngx_array_init方法初始化动态数组(已经存在一个该数据类型的变量)
- 调用ngx_array_create来创建一个动态数组,前提是这个数组还没有创建
注意这二者的区别,即这两个函数的返回值不同,init返回一个状态标识,create返回一个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;
}
if (ngx_array_init(a, p, n, size) != NGX_OK) {
return NULL;
}
return a;
}//返回一个ngx_array_t的指针
书中提到
因为ngx_array_destroy是在内存池中销毁动态数组及其分配的元素内存的(如果动态数组的ngx_array_t结构体内存时利用栈等非内存池方式分配,那么调用ngx_array_destroy会导致不可预估的错误),所以它必须与ngx_array_create配对使用!
动态数组的扩容方式
当已经使用的元素个数达到动态数组与分配元素的个数时,通过两种方式来进行扩容
- ngx_array_push 会申请sizeof(ngx_array_t)大小的内存
- ngx_array_push_n 会申请n * sizeof(ngx_array_t)大小的内存
每次扩容的大小将受制于内存池的以下两种情况
- 如果当前内存池中剩余的空间大于本次需要新增的空间的话,那么就是正常扩充相应大小的内存.
- 如果当前内存池剩余空间不足以扩充相应大小的内存时,那么这个时候需要注意,对于1.来说,会扩充原动态数组的容量的一倍.
对于2.如果n小于原先动态数组的容量,将会扩充一倍,如果n大于原先动态数组的容量,那么会扩充2*n大小的空间,扩容超过了一倍.
这体现了nginx预估用户行为的设计思想.
注意.PNG
总结
今天总共看了两个数据结构,而且斗地主也入门了.如果地主是你的上家,压死他!!
和同学一起打斗地主,他当参谋,一共打了一万多的欢乐豆,一个美好的午休时光,欢乐豆都被我败光了!!
斗地主从入门到精通啊,我发现我身边的人都是斗地主大神.
额,nginx看的效率还是比编程珠玑看的高的,毕竟这本书值得学习,如果想在后端发展以及服务器这方面发展的同学,都可以拿点源码来看看,边写边学习,效果不错.我的markdown还是没用出花样来啊!继续加油..\T*T/
明天试着整理一下红黑树,我感觉得先去复习一下二叉树了,明天再刷几道关于二叉树的剑指offer先.
预知后事如何,且听boomshakalaka.
