注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

nginx的数据结构(1) 数组ngx_array_s  

2010-10-11 17:21:13|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

查看全文


nginx 定义了多种数据结构,包括:
1.数组: ngx_array_t 在core/ngx_array.{h,c}
2.链表: ngx_list_t 在core/ngx_list.{h,c}
3.队列: ngx_queue_t 在core/ngx_queue.{h,c}
4.基树: ngx_radix_tree_t 在core/ngx_radix_tree.{h,c}
5.红黑树: ngx_rbtree_t 在core/ngx_rbtree.{h,c}

其中的数组是比较简单的一个结构,如下所示:
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)。
+-----------------+----------+--------+----+-----

查看全文

  评论这张
 
阅读(1397)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017