08Nginx源码分析之单向链表结构(ngx_list.c)

一 单向链表结构

Nginx的list单向链表的结构和Nginx的数组结构Array有点类似，总体来说，数据结构也是非常简单清晰的。

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

2 ngx_list_part_t 节点结构

其中真正的链表节点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;  	/* 指向下一个链表节点 */
};
           

二 数据结构图

这幅图可以粗略看一下即可，具体要理解上面成员的含义还需要看下面的几个函数，不过也是非常简单。

三 函数实现

1 ngx_list_init函数

ngx_list_init函数的作用就是为首个节点开辟n*size大小的内存，然后初始化管理链表的结构的大小，容量等成员。总的来说，还是针对ngx_list_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)
{
	//1 为管理链表结构的首节点part初始化赋值
    list->part.elts = ngx_palloc(pool, n * size);
    if (list->part.elts == NULL) {
        return NGX_ERROR;
    }
    list->part.nelts = 0;
    list->part.next = NULL;

	//2 初始化管理链表的结构
    list->last = &list->part;
    list->size = size;
    list->nalloc = n;
    list->pool = pool;

    return NGX_OK;
}
           

2 ngx_list_create函数

从上面的ngx_list_init函数看完后，ngx_list_create函数首先调用palloc开辟链表结构的内存，然后调用ngx_list_init函数进行初始化，此时链表结构的首节点part(对象非指针)开辟了n*size的内存。

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

3 ngx_list_push函数

使用ngx_list_push方法可以使用一个元素，并且返回元素的指针地址(所以这个函数名感觉怪怪的)。如果节点中用于存储元素的内存已经用完，则会创建一个新的链表用于返回。

void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;
 
    last = l->last;
 
    /* 1 如果最后一个链表节点用于存储元素的内存已经用完，则需要创建一个新的链表*/
    if (last->nelts == l->nalloc) {
 
        /* the last part is full, allocate a new list part */
 
    	/* 分配一块内存，存储ngx_list_part_t数据结构 */
        last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
        if (last == NULL) {
            return NULL;
        }
 		
 		// 对节点进行初始化，与ngx_list_init函数类似
        /* 分配一个链表节点的内存块，大小为n*size。*/
        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;//更新链表结构的尾部节点
    }
 
 
    /* 2 返回元素首地址(下面两句建议画图理解非常简单) */
    elt = (char *) last->elts + l->size * last->nelts;//获取内存中未使用的内存。l->size为元素大小，last->nelts为已使用的个数。有人会问为啥是l->size，而不是last，因为nginx为了设计方便，直接将元素的size放在管理链表，这样就不用在每个节点都存放一个size，大量节省内存。
    last->nelts++;//更新该节点已使用内存的个数。
 
    return elt;
}
           

通过上面3个函数的分析，nginx的单向链表的每个节点都可以存放n个size大小的元素，当一个节点的内存被使用完时，调用push获取内存会自动开辟新的节点，以使节点里面有新的内存可以返回。