4. nginx基本数据结构之链表ngx_list_t

nginx的链表ngx_list_t很有特色，其特别之处是链表的链表的元素分层次（权且这么理解），即链表是由部分(ngx_list_part_t)组成，每个部分使用指针链接，每个部分可以看作一个数组，该数组的元素是我们平常链表的元素。即ngx_list_t -> ngx_list_part_t -> element

ngx_list.h 代码

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;
    // 链表中part数组中的元素大小
    size_t            size;
    // 链表part数组的容量
    ngx_uint_t        nalloc;
    // 内存池
    ngx_pool_t *pool;
} ngx_list_t;

// 在内存池pool分配 ngx_list_t 对象，并初始化
ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);

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

// 遍历链表的基本代码结构
/*
 *
 * 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] ...
 *
 * }
 */

// 从链表尾部获取一个空元素
void *ngx_list_push(ngx_list_t *list);