nginx之链表

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

typedef struct ngx_list_part_sngx_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;

链表操作共3个，如下。

//创建链表

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)

创建链表

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

ngx_list_t *

ngx_list_create(ngx_pool_t*pool, ngx_uint_tn, 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;    //返回链表头的起始位置

}

添加元素

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

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)信息。

代码例子：

/**

 *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;

}