Skip to content

Latest commit

 

History

History
138 lines (107 loc) · 4.48 KB

20190411_ngx_list_t.md

File metadata and controls

138 lines (107 loc) · 4.48 KB

链表结构——ngx_list_t

ngx_list_t是链表容器，链表容器内存分配是基于内存池进行的，操作方便，效率高。 Nginx链表容器和普通链表类似，均有链表表头和链表节点，通过节点指针组成链表。

链表结构

Nginx链表结构

// ngx_list_part_t 是结构体ngx_list_part_s的别名，描述的是链表的一个元素。
typedef struct ngx_list_part_s ngx_list_part_t;

// 链表中的节点结构
struct ngx_list_part_s {
    void           *elts;    //指向数组的起始地址
    ngx_uint_t     nelts;    //数组中已经使用了多少个元素，nelts必须小于ngx_list_t结构中的nalloc
    ngx_list_part_t *next;   //下一个链表元素ngx_list_part_t的地址
};
// 链表结构
typedef struct {
    ngx_list_part_t  *last;   //指向链表的最后一个数组元素
    ngx_list_part_t  part;    //链表的首个数组元素
    size_t           size;    //限制每个数组元素占用的空间大小
    ngx_uint_t       nalloc;  //表示每个ngx_list_part_t数组的容量，一旦分配后不可更改
    ngx_pool_t       *pool;   //链表中管理内存分配的内存池对象
} ngx_list_t;

ngx_list_t不是单纯的链表，是一个存储数组的链表。每个链表元素ngx_list_part_s又是一个数组，连续的内存，依赖 于ngx_list_t中的Size和nalloc来表述数组的容量，同时又依赖于ngx_list_part_t成员中的nelts来表示数组当前已使用的容量。故，ngx_list_t是一个链表容器，而链表中的元素又是一个数组。

链表操作

Nginx 链表的操作只有两个：创建链表 和 添加元素。由于链表的内存分配是基于内存池，所有内存的销毁由内存池进行，即链表没有销毁操作。

ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
void *ngx_list_push(ngx_list_t *list);

创建链表

创建新的链表时，首先分配链表表头，再对该链表进行初始化，在初始化过程中分配头节点数据区内存。

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

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

添加元素

添加元素到链表时，都是从最后一个节点开始，首先判断最后一个节点的数据区是否能存放新增加的元素， 若足以存储该新元素，则返回存储新元素内存的位置，若没有足够的内存存储新增加的元素，则分配一个新的节点。 再把该新的节点连接到现有链表中，并返回存储新元素内存的位置。

void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;
    /* 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;
}

测试脚本

源码