Nginx 源码分析：ngx_list_t

摘要：源码路径版本主要作用分析是对通常的这种数据结构重复的造轮子。链表使用的内存池。在堆上创建调用函数与的分析类似，调用该函数会自动向申请内存空间。

版本：1.8.0

srccoreNgx_list.h
srccoreNgx_list.c

ngx_list_t是Nginx对通常的list这种数据结构重复的造轮子。

在本篇中，我们先来分析Nginx是如何造这个轮子的，然后对比说明，ngx_list_t和list有什么不同，最后再分析Nginx作者Igor Sysoev重复造轮子的原因。

如果你看过我对ngx_pool_t的分析，很容易就会想到，构造一个list需要定义两个结构：

用于管理链表节点自身的结构体；

比如，可以这么定义

typedef struct list_s list_t;
typedef struct node_s node_t;
struct node_s {
    void     *elt;  // 节点使用的内存块起始位置；
    size_t    max;  // 节点内存块的大小；
    node_t   *next; // 下一个内存块的地址；
};

用于管理整个链表的结构体；

比如，可以这么定义

struct list_s {
    node_t    node;    //链表节点
    list_t    *curr;   //当前使用的链表节点
};

Nginx使用ngx_pool_t来管理内存的使用，所以向链表中增加元素时，就意味着需要使用ngx_pool_t的操作函数ngx_palloc。因此，增加一个元素，就对应一次ngx_palloc调用。

这是相对效率低下的操作方式。Nginx为了提高效率，做了这样的改动：

  
初始化链表时，规定链表中元素的内存占用大小为size，一次性向ngx_pool_t内存池申请size * nelts大小的内存空间，作为链表的节点

示意图如下：

这样做的目的在于减少内存的申请次数，从而提高效率

基于以上分析，就很容易理解ngx_list_t结构体的含义。ngx_list_t 是用来管理整个链表的结构体。

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各成员变量含义如下：

last：指向链表中最后一个ngx_list_part_t，用于管理整个链表，含义很明确。

part：链表第一个节点，表示一块连续的内存空间。

size：链表中每个节点中存放元素大小。

size：链表中每个节点可以存放的元素个数。

pool：链表使用的内存池。

ngx_list_part_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;
};

elts：链表节点使用的内存块地址。

nelts：当前链表节点已经存放的元素个数。

next：指向链表的下一个节点。

分两点来分析：

1）ngx_list_t的创建；
2）ngx_list_t添加元素；

ngx_list_t的创建分成两部分：

创建ngx_list_t结构体本身

向ngx_pool_t申请ngx_list_t使用的内存空间

两种方式：

在堆上创建，即，向ngx_pool_t申请空间。

在栈上创建，即，直接创建ngx_pool_t局部变量。

在堆上创建调用函数：

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

    if (ngx_list_init(list, pool, n, size) != NGX_OK) {
        return NULL;
    }

    return list;
}

与ngx_array_t的分析类似，调用该函数会自动向ngx_pool_t申请内存空间。

调用函数：

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_t中分配出元素空间，并返回其指针。

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_t的链表节点不是list中的节点，而是将list中的节点作为元素，组成一个内存块，作为ngx_list_t的链表节点存在。

ngx_list_t使用ngx_pool_t内存池来管理内存。

一句话：为了提高效率。

通常list在使用过程中每个节点意味着一次内存申请，这是一种效率低下的内存使用方式，ngx_list_t使用一次申请一块内存的方式减少内存申请次数，提高效率。