nginx数据结构之ngx_list分析(nginx0.1.0)
/*
* Copyright (C) Igor Sysoev
*/
#ifndef _NGX_LIST_H_INCLUDED_
#define _NGX_LIST_H_INCLUDED_
#include <ngx_config.h>
#include <ngx_core.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_s结构体
ngx_list_part_t part; // ngx_list_part_s链表的第一个节点,相当于头指针
/*
size: 每个ngx_list_part_s结构体管理的内存中,分配的粒度,即每个元素的大小
nalloc: 每个ngx_list_part_s结构体可以分配几个size大小的内存,
nalloc和size是ngx_list_part_s结构体的共同属性,所以放到全局
*/
size_t size;
ngx_uint_t nalloc;
ngx_pool_t *pool;
} ngx_list_t;
ngx_inline static ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool,
ngx_uint_t n, size_t size)
{
// 分配第一个ngx_list_part_t节点
if (!(list->part.elts = ngx_palloc(pool, n * size))) {
return NGX_ERROR;
}
// 初始化使用个数为0,
list->part.nelts = 0;
list->part.next = NULL;
// 指向当前可分配内存的节点
list->last = &list->part;
// 粒度
list->size = size;
// 每个ngx_list_part_t结构体可分配的块个数
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_ */
/*
* Copyright (C) Igor Sysoev
*/
#include <ngx_config.h>
#include <ngx_core.h>
void *ngx_list_push(ngx_list_t *l)
{
void *elt;
ngx_list_part_t *last;
// 指向当前可用的节点
last = l->last;
// 已使用的个数等于最多能使用的个数,说明已经没有可使用的空间,再分配一个ngx_list_part_t
if (last->nelts == l->nalloc) {
/* the last part is full, allocate a new list part */
// 分配一个新的节点
if (!(last = ngx_palloc(l->pool, sizeof(ngx_list_part_t)))) {
return NULL;
}
// 给上面新分配的节点申请固定大小的内存,供他管理
if (!(last->elts = ngx_palloc(l->pool, l->nalloc * l->size))) {
return NULL;
}
// 当前新分配的节点已使用块数为0
last->nelts = 0;
last->next = NULL;
// 链成链表,第一个ngx_list_part_t节点充当头指针,可以通过ngx_list_t->part访问
l->last->next = last;
// 指向当前可使用的ngx_list_part_t节点
l->last = last;
}
// 当前可分配内存的块首地址加上已经使用的内存,即下一个可用块的首地址
elt = (char *) last->elts + l->size * last->nelts;
// 当前节点已分配内存块数加1
last->nelts++;
// 返回可使用的内存首地址,在该函数外写入数据
return elt;
}