列表头文件ngx_list.h
#ifndef _NGX_LIST_H_INCLUDED_#define _NGX_LIST_H_INCLUDED_#include#include typedef struct ngx_list_part_s ngx_list_part_t; // 一个 part 相当于列表的一个节点 struct ngx_list_part_s { void *elts; // 数据存储区 ngx_uint_t nelts; // 已存储元素个数 ngx_list_part_t *next; //下一个 part }; // 列表定义 typedef struct { ngx_list_part_t *last; // 最后一个part的位置 ngx_list_part_t part; // 表头 size_t size; ngx_uint_t nalloc; // 列表单个节点的最大元素数 ngx_pool_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 的第一个元素的数据存储区分配 n * size 的大小 list->part.elts = ngx_palloc(pool, n * size); if (list->part.elts == NULL) { return NGX_ERROR; } list->part.nelts = 0; // 已存元素数为 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); #endif /* _NGX_LIST_H_INCLUDED_ */
列表源文件ngx_list.c
#include#include 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; } // 链表表头节点的已存元素数为 0 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 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; } // 最后一个节点的已存元素数为 0 last->nelts = 0; last->next = NULL; // 新搞出来这个节点，接到最后一个节点后边 l->last->next = last; // 把这个新节点当成最后一个节点 l->last = last; } // 最后一个节点的数据存储区起始位置 + 元素大小 * 最后节点的已存元素数 // 就是下一个可以放元素的位置 elt = (char *) last->elts + l->size * last->nelts; // 最后一个节点的已存元素数加1 last->nelts++; // 返回下一个可以放元素的位置 return elt; }
从上面可以看出，create 是从 pool 分配定义 list 结构的内存，分配表头节点的内存。init 是初始化已有的 list。