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

云水居

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

 
 
 

日志

 
 

nginx的数据结构(2) 链表ngx_list_s  

2010-10-11 23:55:12|  分类: Network |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
nginx 的链表的定义在core/ngx_list.h中:
typedef struct {
    ngx_list_part_t  *last;     //最后一块
    ngx_list_part_t   part;     //第一块
    size_t            size;         //元素大小
    ngx_uint_t        nalloc;   //每块可存的元素个数
    ngx_pool_t       *pool;   //内存池
} ngx_list_t;

nginx 的链表和传统的链表不同,不是将每个元素通过指针连接起来,而是将每块元素通过指针连接起来。
链表块的定义如下:
struct ngx_list_part_s {
    void             *elts;           //元素所在内存
    ngx_uint_t        nelts;     //已经存储的元素个数
    ngx_list_part_t  *next;    //下一块
};
nginx的数据结构(2) 链表ngx_list_s - hankjin - 云水居
上图的ngx_list包含四个块,共 3*n+m 个元素。注意,只有最后一个块才可能处于不満状态,因为和 ngx_array 一样,ngx_list 也没有定义元素删除操作。甚至ngx_list连整个链表销毁的操作也没定义。
 
链表结构内包含第一个块,以及最后一个块的指针。
1。创建链表:
创建链表主要是申请两块内存,初始化一些变量:
申请ngx_list_t,因为ngx_list_t中包括一个ngx_list_part,所以申请ngx_list_t的同时也申请到了一个ngx_list_part
申请ngx_list_part的元素数组的内存
代码如core/ngx_list.c的ngx_list_create所示
    list = ngx_palloc(pool, sizeof(ngx_list_t));//申请ngx_list_t内存
    list->part.elts = ngx_palloc(pool, n * size);//申请元素数组的内存(元素个数*每个元素的大小)
    list->part.nelts = 0;//已存0个元素
    list->part.next = NULL;//只有一个块
    list->last = &list->part;//最后一个块即为当前块
    list->nalloc = n;//可存的元素个数

2。加入元素:
加入元素时,首先根据ngx_list_t的last指针定位最后一块,
然后检测最后一块的元素是否已经用完了,ngx_list_part_t->nelts == ngx_list_t->nalloc
如果没満,则将最后一块的第nelts元素返回即可。
代码如core/ngx_list.c的ngx_list_push所示:
    elt = (char *) last->elts + l->size * last->nelts; //空闲元素位置
    last->nelts++; //已存储的元素个数+1
如果满了,则申请一个新的链表块,并加入链
if (last->nelts == l->nalloc) {//如果最后一个块的元素已经用完了
        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t)); //申请一个块结构
        last->elts = ngx_palloc(l->pool, l->nalloc * l->size);//申请新块的元素数组
        last->nelts = 0;//初始化新块
        last->next = NULL;
        l->last->next = last;//将新块加入链表
        l->last = last;//修改链表的last指针,让其指向新申请的块
然后再定位并返回元素。

3。遍历链表:
nginx 链表的与众不同导致其遍历方式也与一般链表不同。
要遍历每个块的每个元素,需要维护两个指针和一个下标:当前块指针,当前元素指针和当前元素下标
常见的nginx链表访问方式如下所示:
//core/ngx_cycle.c中的ngx_init_cycle函数中对file的操作部分
    part = mylist->part;//块指针初始化为第一块
    ele = part->elts; //元素指针初始化为元素指针
    for (i = 0; /* void */ ; i++) {
        if (i >= part->nelts) {//当前块遍历完成
            if (part->next == NULL) {//如果没有其它块,则退出循环
                break;
            }   
            part = part->next;//当前块指向下一块
            ele = part->elts; //修改当前块的元素指针
            i = 0; //修改元素指针的下标
        }
优点
ngx_list 采用分块的方式进行内存管理,确实在很大程度上降低了从内存池申请内存的频率,对性能提升有较好的帮助。
但分块的特点也决定了元素删除操作较难处理,而ngx_list没有定义删除操作,难道是因为这个原因?
nginx 定义了还定义了队列 ngx_queue 的数据结构, 与 ngx_list 相比,ngx_queue 更像链表。可以说 ngx_list 是一种比较特殊的链表:块链表。
  评论这张
 
阅读(1275)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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