nginx 单向链表

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_list_t
  • part：链表的首个数组元素。
  • last：指向链表的最后一个数组元素。
  • size：前面讲过，链表中的每个ngx_list_part_t元素都是一个数组。因为数组存储的是某种类型的数据结构，且ngx_list_t是非常灵活的数据结构，所以它不会限制存储什么样的数据，只是通过size限制每一个数组元素的占用的空间大小，也就是用户要存储的一个数据所占用的字节数必须小于或等于size。
  • nalloc：链表的数组元素一旦分配后是不可更改的。nalloc表示每个ngx_list_part_t数组的容量，即最多可存储多少个数据。
  • pool：链表中管理内存分配的内存池对象。用户要存放的数据占用的内存都是由pool分配的，下文中会详细介绍。
• ngx_list_part_t
  • elts：指向数组的起始地址。
  • nelts：表示数组中已经使用了多少个元素。当然，nelts必须小于ngx_list_t结构体中的nalloc。
  • next：下一个链表元素ngx_list_part_t的地址。

事实上，ngx_list_t中的所有数据都是由ngx_pool_t类型的pool内存池分配的，它们通常都是连续的内存（在由一个pool内存池分配的情况下）。下图可以看一下ngx_list_t的内存分布情况。

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