nginx链表ngx_list

本文主要是介绍nginx链表ngx_list_t，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本博客（http://blog.csdn.net/livelylittlefish ）贴出作者（阿波）相关研究、学习内容所做的笔记，欢迎广大朋友指正！

【注】继续转载

Content

1.链表结构

1.2 ngx_list_t的逻辑结构

2.1创建链表

3.一个例子

3.2如何编译

4.小结

0. 序

本文继续介绍nginx的容器——链表。

链表实现文件：文件：./src/core/ngx_list.h/.c。.表示nginx-1.0.4代码目录，本文为/usr/src/nginx-1.0.4。

1. 链表结构

1.1 ngx_list_t结构

nginx的链表(头)结构为ngx_list_t，链表节点结构为ngx_list_part_t，定义如下。

[cpp]  view plain copy  
 typedef struct ngx_list_part_s ngx_list_part_t;  
    
 struct ngx_list_part_s {      //链表节点结构  
     void             *elts;   //指向该节点实际的数据区(该数据区中可以存放nalloc个大小为size的元素)  
     ngx_uint_t        nelts;  //实际存放的元素个数  
     ngx_list_part_t  *next;   //指向下一个节点  
 };  
    
 typedef struct{              //链表头结构  
     ngx_list_part_t  *last;   //指向链表最后一个节点(part)  
     ngx_list_part_t   part;   //链表头中包含的第一个节点(part)  
     size_t            size;   //每个元素大小  
     ngx_uint_t        nalloc; //链表所含空间个数，即实际分配的小空间的个数  
     ngx_pool_t       *pool;   //该链表节点空间在此内存池中分配  
 }ngx_list_t;  

其中，sizeof(ngx_list_t)=28，sizeof(ngx_list_part_t)=12。

由此可见，nginx的链表也要从内存池中分配。对于每一个节点(list part)将分配nalloc个大小为size的小空间，实际分配的大小为(nalloc * size)。详见下文的分析。

1.2 ngx_list_t的逻辑结构

ngx_list_t结构引用了ngx_pool_t结构，因此本文参考nginx-1.0.4源码分析—内存池结构ngx_pool_t及内存管理一文画出相关结构的逻辑图，如下。注：本文采用UML的方式画出该图。

2. 链表操作

链表操作共3个，如下。

[cpp]  view plain copy  
 //创建链表  
 ngx_list_t*ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);  
    
 //初始化链表  
 static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,  
     ngx_uint_tn, size_t size);  
    
 //添加元素  
 void*ngx_list_push(ngx_list_t *l)  

他们的实现都很简单，本文只分析创建链表和添加元素操作。

2.1创建链表

创建链表的操作实现如下，首先分配链表头(28B)，然后分配头节点(即链表头中包含的part)数据区，两次分配均在传入的内存池(pool指向的内存池)中进行。然后简单初始化链表头并返回链表头的起始位置。

[cpp]  view plain copy  
 ngx_list_t *  
 ngx_list_create(ngx_pool_t*pool, ngx_uint_t n, size_t size)  
 {  
     ngx_list_t *list;  
    
     list = ngx_palloc(pool,sizeof(ngx_list_t));  //从内存池中分配链表头  
     if (list == NULL) {  
         return NULL;  
     }  
    
     list->part.elts =ngx_palloc(pool, n * size); //接着分配n*size大小的区域作为链表数据区  
     if (list->part.elts == NULL) {  
         return NULL;  
     }  
    
     list->part.nelts = 0;     //初始化  
     list->part.next = NULL;  
     list->last = &list->part;  
     list->size = size;  
     list->nalloc = n;  
     list->pool = pool;  
    
     return list;    //返回链表头的起始位置  
 }  

创建链表后内存池的物理结构图如下。

2.2添加元素

添加元素操作实现如下，同nginx数组实现类似，其实际的添加操作并不在该函数中完成。函数ngx_list_push返回可以在该链表数据区中放置元素(元素可以是1个或多个)的位置，而添加操作即在获得添加位置之后进行，如后文的例子。

[cpp]  view plain copy  
 void *  
 ngx_list_push(ngx_list_t*l)  
 {  
     void             *elt;  
     ngx_list_part_t  *last;  
    
     last = l->last;  
    
     if (last->nelts ==l->nalloc) {  //链表数据区满  
    
         /* the last part is full, allocate anew list part */  
    
         last =ngx_palloc(l->pool, sizeof(ngx_list_part_t));  //分配节点(list part)  
         if (last == NULL) {  
             return NULL;  
         }  
    
         last->elts =ngx_palloc(l->pool, l->nalloc * l->size);//分配该节点(part)的数据区  
         if (last->elts == NULL) {  
             return NULL;  
         }  
    
         last->nelts = 0;  
         last->next = NULL;  
    
         l->last->next =last;  //将分配的list part插入链表  
         l->last = last;        //并修改list头的last指针  
     }  
    
     elt = (char *)last->elts + l->size * last->nelts; //计算下一个数据在链表数据区中的位置  
     last->nelts++;  //实际存放的数据个数加1  
    
     return elt;  //返回该位置  
 }  

由此可见，向链表中添加元素实际上就是从内存池中分配链表节点(part)及其该节点的实际数据区，并修改链表节点(part)信息。

注1：与数组的区别，数组数据区满时要扩充数据区空间；而链表每次要分配节点及其数据区。

注2：链表的每个节点(part)的数据区中可以放置1个或多个元素，这里的元素可以是一个整数，也可以是一个结构。

下图是一个有3个节点的链表的逻辑结构图。

图中的线太多，容易眼晕，下面这个图可能好一些。

3. 一个例子

理解并掌握开源软件的最好方式莫过于自己写一些测试代码，或者改写软件本身，并进行调试来进一步理解开源软件的原理和设计方法。本节给出一个创建内存池并从中分配一个链表的简单例子。在该例中，链表的每个节点(part)可存放5个元素，每个元素4字节大小，创建链表后，要向链表添加15个整型元素。

3.1代码

[cpp]  view plain copy  
 /** 
  * ngx_list_t test, to test ngx_list_create, ngx_list_push 
  */  
   
 #include <stdio.h>  
 #include "ngx_config.h"  
 #include "ngx_conf_file.h"  
 #include "nginx.h"  
 #include "ngx_core.h"  
 #include "ngx_string.h"  
 #include "ngx_palloc.h"  
 #include "ngx_list.h"  
   
 volatile ngx_cycle_t  *ngx_cycle;  
   
 void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,  
             const char *fmt, ...)  
 {  
 }  
   
 void dump_pool(ngx_pool_t* pool)  
 {  
     while (pool)  
     {  
         printf("pool = 0x%x\n", pool);  
         printf("  .d\n");  
         printf("    .last = 0x%x\n", pool->d.last);  
         printf("    .end = 0x%x\n", pool->d.end);  
         printf("    .next = 0x%x\n", pool->d.next);  
         printf("    .failed = %d\n", pool->d.failed);  
         printf("  .max = %d\n", pool->max);  
         printf("  .current = 0x%x\n", pool->current);  
         printf("  .chain = 0x%x\n", pool->chain);  
         printf("  .large = 0x%x\n", pool->large);  
         printf("  .cleanup = 0x%x\n", pool->cleanup);  
         printf("  .log = 0x%x\n", pool->log);  
         printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);  
         pool = pool->d.next;  
     }  
 }  
   
 void dump_list_part(ngx_list_t* list, ngx_list_part_t* part)  
 {  
     int *ptr = (int*)(part->elts);  
     int loop = 0;  
   
     printf("  .part = 0x%x\n", &(list->part));  
     printf("    .elts = 0x%x  ", part->elts);  
     printf("(");  
     for (; loop < list->nalloc - 1; loop++)  
     {  
         printf("0x%x, ", ptr[loop]);  
     }  
     printf("0x%x)\n", ptr[loop]);  
     printf("    .nelts = %d\n", part->nelts);  
     printf("    .next = 0x%x", part->next);  
     if (part->next)  
         printf(" -->\n");  
     printf(" \n");  
 }  
   
 void dump_list(ngx_list_t* list)  
 {  
     if (list == NULL)  
         return;  
   
     printf("list = 0x%x\n", list);  
     printf("  .last = 0x%x\n", list->last);  
     printf("  .part = 0x%x\n", &(list->part));  
     printf("  .size = %d\n", list->size);  
     printf("  .nalloc = %d\n", list->nalloc);  
     printf("  .pool = 0x%x\n\n", list->pool);  
   
     printf("elements:\n");  
   
     ngx_list_part_t *part = &(list->part);  
     while (part)  
     {  
         dump_list_part(list, part);  
         part = part->next;  
     }  
     printf("\n");  
 }  
   
 int main()  
 {  
     ngx_pool_t *pool;  
     int i;  
   
     printf("--------------------------------\n");  
     printf("create a new pool:\n");  
     printf("--------------------------------\n");  
     pool = ngx_create_pool(1024, NULL);  
     dump_pool(pool);  
   
     printf("--------------------------------\n");  
     printf("alloc an list from the pool:\n");  
     printf("--------------------------------\n");  
     ngx_list_t *list = ngx_list_create(pool, 5, sizeof(int));  
     dump_pool(pool);  
   
     for (i = 0; i < 15; i++)  
     {  
         int *ptr = ngx_list_push(list);  
         *ptr = i + 1;  
     }  
   
     printf("--------------------------------\n");  
     printf("the list information:\n");  
     printf("--------------------------------\n");  
     dump_list(list);  
   
     printf("--------------------------------\n");  
     printf("the pool at the end:\n");  
     printf("--------------------------------\n");  
     dump_pool(pool);  
   
     ngx_destroy_pool(pool);  
     return 0;  
 }  

3.2如何编译

请参考nginx-1.0.4源码分析—内存池结构ngx_pool_t及内存管理一文。本文编写的makefile文件如下。

[cpp]  view plain copy  
 CXX = gcc  
 CXXFLAGS +=-g -Wall -Wextra  
    
 NGX_ROOT =/usr/src/nginx-1.0.4  
    
 TARGETS =ngx_list_t_test  
 TARGETS_C_FILE= $(TARGETS).c  
    
 CLEANUP = rm-f $(TARGETS) *.o  
    
 all:$(TARGETS)  
    
 clean:  
 $(CLEANUP)  
    
 CORE_INCS =-I. \  
 -I$(NGX_ROOT)/src/core \  
 -I$(NGX_ROOT)/src/event \  
 -I$(NGX_ROOT)/src/event/modules \  
 -I$(NGX_ROOT)/src/os/unix \  
 -I$(NGX_ROOT)/objs \  
    
 NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o  
 NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o  
 NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o  
 NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o  
    
 $(TARGETS):$(TARGETS_C_FILE)  
 $(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING)$(NGX_ALLOC) $(NGX_LIST) $^ -o $@  

3.3运行结果

[plain]  view plain copy  
 # ./ngx_list_t_test  
 -------------------------------- create a new pool:  
 -------------------------------- pool = 0x9208020 .d .last = 0x9208048  
     .end = 0x9208420  
     .next = 0x0  
     .failed = 0 .max = 984  
   .current = 0x9208020  
   .chain = 0x0  
   .large = 0x0  
   .cleanup = 0x0  
   .log = 0x0 available pool memory = 984  
 -------------------------------- alloc an list from the pool:  
 -------------------------------- pool = 0x9208020 .d .last = 0x9208078  
     .end = 0x9208420  
     .next = 0x0  
     .failed = 0 .max = 984  
   .current = 0x9208020  
   .chain = 0x0  
   .large = 0x0  
   .cleanup = 0x0  
   .log = 0x0 available pool memory = 936  
 -------------------------------- the list information:  
 -------------------------------- list = 0x9208048 .last = 0x9208098  
   .part = 0x920804c  
   .size = 4  
   .nalloc = 5  
   .pool = 0x9208020  
 elements: .part = 0x920804c .elts = 0x9208064  (0x1, 0x2, 0x3, 0x4, 0x5)  
     .nelts = 5  
     .next = 0x9208078 -->  
   .part = 0x920804c .elts = 0x9208084  (0x6, 0x7, 0x8, 0x9, 0xa)  
     .nelts = 5  
     .next = 0x9208098 -->  
   .part = 0x920804c .elts = 0x92080a4  (0xb, 0xc, 0xd, 0xe, 0xf)  
     .nelts = 5  
     .next = 0x0   
 -------------------------------- the pool at the end:  
 -------------------------------- pool = 0x9208020 .d .last = 0x92080b8  
     .end = 0x9208420  
     .next = 0x0  
     .failed = 0 .max = 984  
   .current = 0x9208020  
   .chain = 0x0  
   .large = 0x0  
   .cleanup = 0x0  
   .log = 0x0 available pool memory = 872  