nginx数据结构之array

ChianXu 发表于 2011-12-22 08:54

<DIV>数组是比较简单的一个结构，如下所示： core/ngx_array.h struct ngx_array_s {     void        *elts;      //数组元素所在的内存地址     ngx_uint_t   nelts;  //数组中已有的元素个数     size_t       size;     //数组中每个元素的大小     ngx_uint_t   nalloc; //已分配空间中可存放的元素个数     ngx_pool_t  *pool;  //内存池指针 }; 1. 创建数组的操作如下所示： 1. 首先在内存池pool中申请一小片内存，用于ngx_array_s结构 2. 将数组的元素大小size和个数nalloc相乘，计算出数组所需内存，并在内存池pool中申请一片内存，用于存放元素 +-----------------+----------+--------+----+-----------+ | ngx_array_s   |  elem1  | elem2 | .... | elemn    | +-----------------+----------+--------+----+-----------+ 代码见core/ngx_array.c的ngx_array_create函数： a = ngx_palloc(p, sizeof(ngx_array_t));  申请数组的数据结构的内存 a->elts = ngx_palloc(p, n * size);           申请数组内的元素的内存 2. 加入元素： 当数组不满的时候，直接将元素放入适当的位置即可。 当数组中已有元素的个数nelts等于数组中可存放元素个数时，若要再添加元素，则需要先扩展元素内存的大小，nginx采取的策略是扩展为原来大小的2倍 扩展方法分两种情况： 1. 元素内存之后的连续的内存尚未使用，则直接将内存池的空闲指针向后移动即可 2. 元素内存之后的连续的内存已被使用，则重新从内存池中空闲内存中申请一块可以存放nalloc*2个元素的内存，并将原来的nalloc个元素复制过去。 2.1 情况1： ngx_array_s的elts指针指向数组内元素的起始位置，加上数组内元素的大小(元素大小和元素个数的乘积)，即可算出数组元素的结尾位置aend。内存池pool有一个last指针，指向当前空闲内存的位置，如果aend==last，则表示数组后面的空间是空闲的，如果空闲空间的大小足够放下一个元素，则可以直接将pool的free指针向后移动，即可实现ngx_array的扩展。 +-----------------+----------+--------+----+-----------+------------+ | ngx_array_s   |  elem1  | elem2 | .... | elemn    | newelem | +-----------------+----------+--------+----+-----------+------------+ 代码见core/ngx_array.c的ngx_array_push函数 if ((u_char *) a->elts + size == p->last //元素后面的空间是空闲的      && p->last + a->size <= p->end) //并且空间空间足够 {        p->last += a->size; //内存池的指针向后移动       a->nalloc++; //本数组的可容纳元素个数加1 } 2.2 情况2： 如果数组元素的结尾位置的pool的last指针不等，意味着数组元素后面被其它数据(something)占用了，就去pool的空闲空间中申请一块更大的内存，nginx采用原来大小的2倍，然后将原来的nalloc个元素(elem1-n)复制到新内存中(xelem1-n)，并加入新元素(newelem)。 +-----------------+----------+--------+----+-----------+-------------+----------+--------+----+-----------+-----------+----+---------+ | ngx_array_s   |  elem1  | elem2 | .... | elemn    | something | xelem1  | xelem2| .... | xelemn   | newelem | ... | elem2n | +-----------------+----------+--------+----+-----------+-------------+----------+--------+----+-----------+-----------+----+---------+ 代码见core/ngx_array.c的ngx_array_push函数： else {             new = ngx_palloc(p, 2 * size); //申请新内存             ngx_memcpy(new, a->elts, size); //拷贝旧元素             a->elts = new; //修改元素内存指针             a->nalloc *= 2; //修改可容纳元素个数 } 3. 释放数组： nginx 释放数组的方式很简单，和创建数组的方式相似： 如果元素的后面是空闲内存，即元素与空闲内存是连续的，则直接移动pool的last指针，将元素占用的内存加入空闲内存；然后判断数组的数据结构后面是否空闲内存，如果是则移动pool的last指针，将数组的数据结构内存加入空闲内存。 第一步将元素归还pool +-----------------+----------+--------+----+-----------+ | ngx_array_s   |  elem1  | elem2 | .... | elemn    | +-----------------+----------+--------+----+-----------+ 去除元素后，pool的last指针前移，第二步将结构归还pool +-----------------+ | ngx_array_s   | +-----------------+ 代码见core/ngx_array.c的ngx_array_destroy函数     if ((u_char *) a->elts + a->size * a->nalloc == p->last) {//连续内存         p->last -= a->size * a->nalloc;//释放元素     }     if ((u_char *) a + sizeof(ngx_array_t) == p->last) {//连续内存         p->last = (u_char *) a;//释放数组数据结构     } 问题： 数组的设计很简单，和C++的vector设计基本一致。 特别的地方是：它从已经申请的pool中申请与释放内存，并不需要与操作系统接口调用，因此效率更好。 但是很明显这里没有处理碎片，例如先申请一个2个元素的数组a，再申请一个3个元素的数组b，再往a中加入3个元素，则a的原来两个元素()的内存就没有用了。但是也没有指针指向这块内存，只有等pool失效的时候才会回收。 +-----------+----------+--------+----------+--------+--------+---------+--------+---------+----+---------+ | array a   |  elem1  | elem2 | array_b | elem1 | elem2 | elem3  | xelem1| xelem2 |  ... | elem4 | +-----------+----------+--------+----------+--------+--------+---------+--------+---------+----+---------+ 1. 申请产生空洞 向a中加入第3个元素时，elem2后面已经被array_b占用，所以要申请原来大小的2倍(2*2=4)的新内存(xelem1-4)。 并将array_a的eles指针指向这块新内存。此时黑体的elem1和elem2已经无人管理了，只有等pool失效的时候才能归还。 2. 释放产生空洞 如果此时释放数组b，数组b的结尾元素elem3，而pool的last指向数组a的elem4的尾部，明显二者不同，所以数组b的内存也不能归还pool。 但是由于nginx还有对pool的管理，所以不这个空洞只是暂时的，当pool销毁时，整个pool的内存都会归还，空洞随之消失。</DIV>
<DIV> </DIV>
<DIV>本文摘自：<a href="http://hankjin.blog.163.com/blog/static/33731937201091142542388/" target="_blank">http://hankjin.blog.163.com/blog/static/33731937201091142542388/</A>感谢作者的辛勤成果，同时希望更多的人把更多的思想分享给大家</DIV>

页: [1]

Chinaunix's Archiver

nginx数据结构之array