Chinaunix首页 | 论坛 | 博客

zjm001的ChinaUnix博客zjm.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zjm001

  • 博客访问： 293855
  • 博文数量： 134
  • 博客积分： 667
  • 博客等级： 上士
  • 技术积分： 770
  • 用 户 组： 普通用户
  • 注册时间： 2012-04-08 15:19
文章分类

全部博文（134）

文章存档

2012年（134）

我的朋友
最近访客
推荐博文
相关博文
链表结构ngx_list_t

分类： LINUX

2012-06-12 17:18:48

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，定义如下。


点击(此处)折叠或打开

  1. typedef struct ngx_list_part_s ngx_list_part_t;
  2.  
  3. struct ngx_list_part_s { //链表节点结构
  4.     void *elts; //指向该节点实际的数据区(该数据区中可以存放nalloc个大小为size的元素)
  5.     ngx_uint_t nelts; //实际存放的元素个数
  6.     ngx_list_part_t *next; //指向下一个节点
  7. };
  8.  
  9. typedef struct{ //链表头结构
  10.     ngx_list_part_t *last; //指向链表最后一个节点(part)
  11.     ngx_list_part_t part; //链表头中包含的第一个节点(part)
  12.     size_t size; //每个元素大小
  13.     ngx_uint_t nalloc; //链表所含空间个数，即实际分配的小空间的个数
  14.     ngx_pool_t *pool; //该链表节点空间在此内存池中分配
  15. }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个，如下。


点击(此处)折叠或打开

  1. //创建链表
  2. ngx_list_t*ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
  3.  
  4. //初始化链表
  5. static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,
  6.     ngx_uint_tn, size_t size);
  7.  
  8. //添加元素
  9. void*ngx_list_push(ngx_list_t *l)
他们的实现都很简单，本文只分析创建链表和添加元素操作。

 

2.1创建链表

 

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


点击(此处)折叠或打开

  1. ngx_list_t *
  2. ngx_list_create(ngx_pool_t*pool, ngx_uint_t n, size_t size)
  3. {
  4.     ngx_list_t *list;
  5.  
  6.     list = ngx_palloc(pool,sizeof(ngx_list_t)); //从内存池中分配链表头
  7.     if (list == NULL) {
  8.         return NULL;
  9.     }
  10.  
  11.     list->part.elts =ngx_palloc(pool, n * size); //接着分配n*size大小的区域作为链表数据区
  12.     if (list->part.elts == NULL) {
  13.         return NULL;
  14.     }
  15.  
  16.     list->part.nelts = 0; //初始化
  17.     list->part.next = NULL;
  18.     list->last = &list->part;
  19.     list->size = size;
  20.     list->nalloc = n;
  21.     list->pool = pool;
  22.  
  23.     return list; //返回链表头的起始位置
  24. }
创建链表后内存池的物理结构图如下。


2.2添加元素

 

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


点击(此处)折叠或打开

  1. void *
  2. ngx_list_push(ngx_list_t*l)
  3. {
  4.     void *elt;
  5.     ngx_list_part_t *last;
  6.  
  7.     last = l->last;
  8.  
  9.     if (last->nelts ==l->nalloc) { //链表数据区满
  10.  
  11.         /* the last part is full, allocate anew list part */
  12.  
  13.         last =ngx_palloc(l->pool, sizeof(ngx_list_part_t)); //分配节点(list part)
  14.         if (last == NULL) {
  15.             return NULL;
  16.         }
  17.  
  18.         last->elts =ngx_palloc(l->pool, l->nalloc * l->size);//分配该节点(part)的数据区
  19.         if (last->elts == NULL) {
  20.             return NULL;
  21.         }
  22.  
  23.         last->nelts = 0;
  24.         last->next = NULL;
  25.  
  26.         l->last->next =last; //将分配的list part插入链表
  27.         l->last = last; //并修改list头的last指针
  28.     }
  29.  
  30.     elt = (char *)last->elts + l->size * last->nelts; //计算下一个数据在链表数据区中的位置
  31.     last->nelts++; //实际存放的数据个数加1
  32.  
  33.     return elt; //返回该位置
  34. }
由此可见，向链表中添加元素实际上就是从内存池中分配链表节点(part)及其该节点的实际数据区，并修改链表节点(part)信息。

 

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

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

 

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

 

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

 

3. 一个例子

 

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

 

3.1代码


点击(此处)折叠或打开

  1. /**
  2.  * ngx_list_t test, to test ngx_list_create, ngx_list_push
  3.  */

  5. #include <stdio.h>
  6. #include "ngx_config.h"
  7. #include "ngx_conf_file.h"
  8. #include "nginx.h"
  9. #include "ngx_core.h"
  10. #include "ngx_string.h"
  11. #include "ngx_palloc.h"
  12. #include "ngx_list.h"

  14. volatile ngx_cycle_t *ngx_cycle;

  16. void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
  17.             const char *fmt, ...)
  18. {
  19. }

  21. void dump_pool(ngx_pool_t* pool)
  22. {
  23.     while (pool)
  24.     {
  25.         printf("pool = 0x%x\n", pool);
  26.         printf(" .d\n");
  27.         printf(" .last = 0x%x\n", pool->d.last);
  28.         printf(" .end = 0x%x\n", pool->d.end);
  29.         printf(" .next = 0x%x\n", pool->d.next);
  30.         printf(" .failed = %d\n", pool->d.failed);
  31.         printf(" .max = %d\n", pool->max);
  32.         printf(" .current = 0x%x\n", pool->current);
  33.         printf(" .chain = 0x%x\n", pool->chain);
  34.         printf(" .large = 0x%x\n", pool->large);
  35.         printf(" .cleanup = 0x%x\n", pool->cleanup);
  36.         printf(" .log = 0x%x\n", pool->log);
  37.         printf("available pool memory = %d\n\n", pool->d.end - pool->d.last);
  38.         pool = pool->d.next;
  39.     }
  40. }

  42. void dump_list_part(ngx_list_t* list, ngx_list_part_t* part)
  43. {
  44.     int *ptr = (int*)(part->elts);
  45.     int loop = 0;

  47.     printf(" .part = 0x%x\n", &(list->part));
  48.     printf(" .elts = 0x%x ", part->elts);
  49.     printf("(");
  50.     for (; loop < list->nalloc - 1; loop++)
  51.     {
  52.         printf("0x%x, ", ptr[loop]);
  53.     }
  54.     printf("0x%x)\n", ptr[loop]);
  55.     printf(" .nelts = %d\n", part->nelts);
  56.     printf(" .next = 0x%x", part->next);
  57.     if (part->next)
  58.         printf(" -->\n");
  59.     printf(" \n");
  60. }

  62. void dump_list(ngx_list_t* list)
  63. {
  64.     if (list == NULL)
  65.         return;

  67.     printf("list = 0x%x\n", list);
  68.     printf(" .last = 0x%x\n", list->last);
  69.     printf(" .part = 0x%x\n", &(list->part));
  70.     printf(" .size = %d\n", list->size);
  71.     printf(" .nalloc = %d\n", list->nalloc);
  72.     printf(" .pool = 0x%x\n\n", list->pool);

  74.     printf("elements:\n");

  76.     ngx_list_part_t *part = &(list->part);
  77.     while (part)
  78.     {
  79.         dump_list_part(list, part);
  80.         part = part->next;
  81.     }
  82.     printf("\n");
  83. }

  85. int main()
  86. {
  87.     ngx_pool_t *pool;
  88.     int i;

  90.     printf("--------------------------------\n");
  91.     printf("create a new pool:\n");
  92.     printf("--------------------------------\n");
  93.     pool = ngx_create_pool(1024, NULL);
  94.     dump_pool(pool);

  96.     printf("--------------------------------\n");
  97.     printf("alloc an list from the pool:\n");
  98.     printf("--------------------------------\n");
  99.     ngx_list_t *list = ngx_list_create(pool, 5, sizeof(int));
  100.     dump_pool(pool);

  102.     for (i = 0; i < 15; i++)
  103.     {
  104.         int *ptr = ngx_list_push(list);
  105.         *ptr = i + 1;
  106.     }

  108.     printf("--------------------------------\n");
  109.     printf("the list information:\n");
  110.     printf("--------------------------------\n");
  111.     dump_list(list);

  113.     printf("--------------------------------\n");
  114.     printf("the pool at the end:\n");
  115.     printf("--------------------------------\n");
  116.     dump_pool(pool);

  118.     ngx_destroy_pool(pool);
  119.     return 0;
  120. }
3.2如何编译

 

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


点击(此处)折叠或打开

  1. CXX = gcc
  2. CXXFLAGS +=-g -Wall -Wextra
  3.  
  4. NGX_ROOT =/usr/src/nginx-1.0.4
  5.  
  6. TARGETS =ngx_list_t_test
  7. TARGETS_C_FILE= $(TARGETS).c
  8.  
  9. CLEANUP = rm-f $(TARGETS) *.o
  10.  
  11. all:$(TARGETS)
  12.  
  13. clean:
  14. $(CLEANUP)
  15.  
  16. CORE_INCS =-I. \
  17. -I$(NGX_ROOT)/src/core \
  18. -I$(NGX_ROOT)/src/event \
  19. -I$(NGX_ROOT)/src/event/modules \
  20. -I$(NGX_ROOT)/src/os/unix \
  21. -I$(NGX_ROOT)/objs \
  22.  
  23. NGX_PALLOC =$(NGX_ROOT)/objs/src/core/ngx_palloc.o
  24. NGX_STRING =$(NGX_ROOT)/objs/src/core/ngx_string.o
  25. NGX_ALLOC =$(NGX_ROOT)/objs/src/os/unix/ngx_alloc.o
  26. NGX_LIST =$(NGX_ROOT)/objs/src/core/ngx_list.o
  27.  
  28. $(TARGETS):$(TARGETS_C_FILE)
  29. $(CXX) $(CXXFLAGS) $(CORE_INCS) $(NGX_PALLOC) $(NGX_STRING)$(NGX_ALLOC) $(NGX_LIST) $^ -o $@
3.3运行结果

点击(此处)折叠或打开

  1. # ./ngx_list_t_test
  2. -------------------------------- create a new pool:
  3. -------------------------------- pool = 0x9208020 .d .last = 0x9208048
  4.     .end = 0x9208420
  5.     .next = 0x0
  6.     .failed = 0 .max = 984
  7.   .current = 0x9208020
  8.   .chain = 0x0
  9.   .large = 0x0
  10.   .cleanup = 0x0
  11.   .log = 0x0 available pool memory = 984
  12. -------------------------------- alloc an list from the pool:
  13. -------------------------------- pool = 0x9208020 .d .last = 0x9208078
  14.     .end = 0x9208420
  15.     .next = 0x0
  16.     .failed = 0 .max = 984
  17.   .current = 0x9208020
  18.   .chain = 0x0
  19.   .large = 0x0
  20.   .cleanup = 0x0
  21.   .log = 0x0 available pool memory = 936
  22. -------------------------------- the list information:
  23. -------------------------------- list = 0x9208048 .last = 0x9208098
  24.   .part = 0x920804c
  25.   .size = 4
  26.   .nalloc = 5
  27.   .pool = 0x9208020
  28. elements: .part = 0x920804c .elts = 0x9208064 (0x1, 0x2, 0x3, 0x4, 0x5)
  29.     .nelts = 5
  30.     .next = 0x9208078 -->
  31.   .part = 0x920804c .elts = 0x9208084 (0x6, 0x7, 0x8, 0x9, 0xa)
  32.     .nelts = 5
  33.     .next = 0x9208098 -->
  34.   .part = 0x920804c .elts = 0x92080a4 (0xb, 0xc, 0xd, 0xe, 0xf)
  35.     .nelts = 5
  36.     .next = 0x0
  37. -------------------------------- the pool at the end:
  38. -------------------------------- pool = 0x9208020 .d .last = 0x92080b8
  39.     .end = 0x9208420
  40.     .next = 0x0
  41.     .failed = 0 .max = 984
  42.   .current = 0x9208020
  43.   .chain = 0x0
  44.   .large = 0x0
  45.   .cleanup = 0x0
  46.   .log = 0x0 available pool memory = 872

该例子中内存池和数组的(内存)物理结构
阅读(1940) | 评论(0) | 转发(0) |
0

上一篇：数组结构ngx_array_t

下一篇：队列结构ngx_queue_t

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6