Open Linkerist opened 5 years ago
ngx_list_t是Nginx封装的链表容器,它在Nginx中使用得很频繁,例如HTTP的头部就是用 ngx_list_t来存储的。当然,C语言封装的链表没有C++或Java等面向对象语言那么容易理解。 ngx_list_t单向链表与ngx_queue_t双向链表是完全不同的,它是负责容器内元素内存分配 的,因此,这两个容器在通用性的设计思路上是完全不同的。同时它与ngx_array_t也不一 样,它不是用完全连续的内存来存储元素,而是用单链表将多段内存块连接起来,每段内存块也存储了多个元素,有点像“数组+单链表”。先看一下ngx_list_t相关成员的定义:
typedef struct ngx_list_part_s ngx_list_part_t; struct ngx_list_part_s { void *elts; ngx_uint_t nelts; ngx_list_part_t *next; }; 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;
ngx_list_t描述整个链表,而ngx_list_part_t只描述链表的一个元素。这里要注意的是,ngx_list_t不是一个单纯的链表,为了便于理解,我们姑且称它为存储数组的链表,什么意思呢?抽象地说,就是每个链表元素ngx_list_part_t又是一个数组,拥有连续的内存,它既依赖于ngx_list_t里的size和nalloc来表示数组的容量,同时又依靠每个ngx_list_part_t成员中的nelts来表示数组当前已使用了多少容量。因此,ngx_list_t是一个链表容器,而链表中的元素又是一个数组。事实上,ngx_list_part_t数组中的元素才是用户想要存储的东西,ngx_list_t链表能够容纳的元素数量由ngx_list_part_t数组元素的个数与每个数组所能容纳的元素相乘得到。 这样设计有什么好处呢?
下面详述每个成员的意义
事实上,ngx_list_t中的所有数据都是由ngx_pool_t类型的pool内存池分配的,它们通常都是连续的内存(在由一个pool内存池分配的情况下)。下图可以看一下ngx_list_t的内存分布情况。 如上是由3个ngx_list_part_t数组元素组成的ngx_list_t链表可能拥有的一种内存分布结构,读者可以从这种较为常见的内存分布中看到ngx_list_t链表的用法。这里,pool内存池为其分配了连续的内存,最前端内存存储的是ngx_list_t结构中的成员,紧接着是第一个ngx_list_part_t结构占用的内存,然后是ngx_list_part_t结构指向的数组,它们一共占用size*nalloc字节,表示数组中拥有nalloc个大小为size的元素。其后面是第2个ngx_list_part_t结构以及它所指向的数组,依此类推。 对于链表,Nginx提供的接口包括:ngx_list_create接口用于创建新的链表,ngx_list_init接口用于初始化一个已有的链表,ngx_list_push接口用于添加新的元素,如下所示:
static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size) { list->part.elts = ngx_palloc(pool, n * size); if (list->part.elts == NULL) { return NGX_ERROR; } list->part.nelts = 0; list->part.next = NULL; list->last = &list->part; list->size = size; list->nalloc = n; list->pool = pool; return NGX_OK; } 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); 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; } 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 a new list part */ last = ngx_palloc(l->pool, sizeof(ngx_list_part_t)); if (last == NULL) { return NULL; } last->elts = ngx_palloc(l->pool, l->nalloc * l->size); if (last->elts == NULL) { return NULL; } last->nelts = 0; last->next = NULL; l->last->next = last; l->last = last; } elt = (char *) last->elts + l->size * last->nelts; last->nelts++; return elt; }
调用ngx_list_create创建元素时,pool参数是内存池对象,size是每个元素的大小,n是每个链表数组可容纳元素的个数(相当于ngx_list_t结构中的nalloc成员)。 ngx_list_create返回新创建的链表地址,如果创建失败,则返回NULL空指针。ngx_list_create被调用后至少会创建一个数组(不会创建空链表),其中包含n个大小为size字节的连续内存块,也就是ngx_list_t结构中的part成员。 下面看一个简单的例子,我们首先建立一个链表,它存储的元素是ngx_str_t,其中每个链表数组中存储4个元素,代码如下所示:
ngx_list_t* testlist = ngx_list_create(r->pool, 4,sizeof(ngx_str_t)); if (testlist == NULL) { return NGX_ERROR; }
ngx_list_init的使用方法与ngx_list_create非常类似,需要注意的是,这时链表数据结构已经创建好了,若ngx_list_init返回NGX_OK,则表示初始化成功,若返回NGX_ERROR,则表示失败。 调用ngx_list_push表示添加新的元素,传入的参数是ngx_list_t链表。正常情况下,返回的是新分配的元素首地址。如果返回NULL空指针,则表示添加失败。在使用它时通常先调用ngx_list_push得到返回的元素地址,再对返回的地址进行赋值。例如:
ngx_str_t* str = ngx_list_push(testlist); if (str == NULL) { return NGX_ERROR; } str->len= sizeof("Hello world"); str->data = "Hello world";
遍历链表时Nginx没有提供相应的接口,实际上也不需要。我们可以用以下方法遍历链表中的元素:
/* * * the iteration through the list: * * part = &list.part; * data = part->elts; * * for (i = 0 ;; i++) { * * if (i >= part->nelts) { * if (part->next == NULL) { * break; * } * * part = part->next; * data = part->elts; * i = 0; * } * * ... data[i] ... * * } */
本文暂取自代码、网络或书籍,只用作学习备忘,不作盈利等他用,如有侵权,请联系Linkerist@163.com
ngx_list_t是Nginx封装的链表容器,它在Nginx中使用得很频繁,例如HTTP的头部就是用 ngx_list_t来存储的。当然,C语言封装的链表没有C++或Java等面向对象语言那么容易理解。 ngx_list_t单向链表与ngx_queue_t双向链表是完全不同的,它是负责容器内元素内存分配 的,因此,这两个容器在通用性的设计思路上是完全不同的。同时它与ngx_array_t也不一 样,它不是用完全连续的内存来存储元素,而是用单链表将多段内存块连接起来,每段内存块也存储了多个元素,有点像“数组+单链表”。先看一下ngx_list_t相关成员的定义:
ngx_list_t描述整个链表,而ngx_list_part_t只描述链表的一个元素。这里要注意的是,ngx_list_t不是一个单纯的链表,为了便于理解,我们姑且称它为存储数组的链表,什么意思呢?抽象地说,就是每个链表元素ngx_list_part_t又是一个数组,拥有连续的内存,它既依赖于ngx_list_t里的size和nalloc来表示数组的容量,同时又依靠每个ngx_list_part_t成员中的nelts来表示数组当前已使用了多少容量。因此,ngx_list_t是一个链表容器,而链表中的元素又是一个数组。事实上,ngx_list_part_t数组中的元素才是用户想要存储的东西,ngx_list_t链表能够容纳的元素数量由ngx_list_part_t数组元素的个数与每个数组所能容纳的元素相乘得到。 这样设计有什么好处呢?
下面详述每个成员的意义
事实上,ngx_list_t中的所有数据都是由ngx_pool_t类型的pool内存池分配的,它们通常都是连续的内存(在由一个pool内存池分配的情况下)。下图可以看一下ngx_list_t的内存分布情况。 如上是由3个ngx_list_part_t数组元素组成的ngx_list_t链表可能拥有的一种内存分布结构,读者可以从这种较为常见的内存分布中看到ngx_list_t链表的用法。这里,pool内存池为其分配了连续的内存,最前端内存存储的是ngx_list_t结构中的成员,紧接着是第一个ngx_list_part_t结构占用的内存,然后是ngx_list_part_t结构指向的数组,它们一共占用size*nalloc字节,表示数组中拥有nalloc个大小为size的元素。其后面是第2个ngx_list_part_t结构以及它所指向的数组,依此类推。 对于链表,Nginx提供的接口包括:ngx_list_create接口用于创建新的链表,ngx_list_init接口用于初始化一个已有的链表,ngx_list_push接口用于添加新的元素,如下所示:
调用ngx_list_create创建元素时,pool参数是内存池对象,size是每个元素的大小,n是每个链表数组可容纳元素的个数(相当于ngx_list_t结构中的nalloc成员)。 ngx_list_create返回新创建的链表地址,如果创建失败,则返回NULL空指针。ngx_list_create被调用后至少会创建一个数组(不会创建空链表),其中包含n个大小为size字节的连续内存块,也就是ngx_list_t结构中的part成员。 下面看一个简单的例子,我们首先建立一个链表,它存储的元素是ngx_str_t,其中每个链表数组中存储4个元素,代码如下所示:
ngx_list_init的使用方法与ngx_list_create非常类似,需要注意的是,这时链表数据结构已经创建好了,若ngx_list_init返回NGX_OK,则表示初始化成功,若返回NGX_ERROR,则表示失败。 调用ngx_list_push表示添加新的元素,传入的参数是ngx_list_t链表。正常情况下,返回的是新分配的元素首地址。如果返回NULL空指针,则表示添加失败。在使用它时通常先调用ngx_list_push得到返回的元素地址,再对返回的地址进行赋值。例如:
遍历链表时Nginx没有提供相应的接口,实际上也不需要。我们可以用以下方法遍历链表中的元素:
本文暂取自代码、网络或书籍,只用作学习备忘,不作盈利等他用,如有侵权,请联系Linkerist@163.com