nginx数据结构之list

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

<DIV>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;    //下一块 }; 
<DIV><IMG style="MARGIN: 0pt 10px 0pt 0pt" alt="nginx的数据结构(2) 链表ngx_list_s - hankjin - 云水居" src="http://img762.ph.126.net/W4Je8W9P-g8CKaYDwosBhg==/4947485665643323940.png" __1312281485406__="ev_6093348017"></DIV>上图的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 是一种比较特殊的链表：块链表。</DIV>
<DIV> </DIV>
<DIV>本文摘自：<a href="http://hankjin.blog.163.com/blog/static/33731937201091111303630/" target="_blank">http://hankjin.blog.163.com/blog/static/33731937201091111303630/</A>感谢作者的辛勤成果</DIV>

页: [1]

Chinaunix's Archiver

nginx数据结构之list