Nginx源码学习之路----熟悉Nginx基本的数据结构之动态

2016-06-12 本文已影响341人亼亼

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.