//链表
typedef struct {
ngx_list_part_t *last; //指向最后一个数组元素
ngx_list_part_t part; //首元素
size_t size; //限制每个数组元素占用空间大小,也就是用户要存储的一个数据所 占用的字节数必须小于或等于size。
ngx_uint_t nalloc; //最多可存储数据数
ngx_pool_t *pool; //管理内存分配的内存池对象
} ngx_list_t;
//节点
/*
每个链表元素ngx_list_part_t又是一个数组,拥有连续的内存,
它既依赖于ngx_list_t里的size和nalloc来表示数组的容量,
同时又依靠每个ngx_list_part_t成员中的nelts来表示数组当前已使用了多少容量。
*/
struct ngx_list_part_s {
void *elts; //指向数组的起始地址
ngx_uint_t nelts; //表示数组中已经使用元素数量
ngx_list_part_t *next; //下一个链表元素的地址
};
1、通用链表 2、小块的内存使用链表访问效率是低下的,使用数组通过偏移量来直接访问内存则要高 效得多。
/**
* 创建链表
*/
ngx_list_t *
ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
ngx_list_t *list;
/* 从内存池上面分配一块内存,存储ngx_list_t数据结构 */
list = ngx_palloc(pool, sizeof(ngx_list_t));
if (list == NULL) {
return NULL;
}
/* 分配一个链表节点的内存块。内存大小 n * size*/
list->part.elts = ngx_palloc(pool, n * size);
if (list->part.elts == NULL) {
return NULL;
}
list->part.nelts = 0; /* 使用的元素个数 */
list->part.next = NULL; /* 下一个节点 */
list->last = &list->part; /* 最后一个节点地址 */
list->size = size; /* 每个元素的大小 */
list->nalloc = n; /* 分配多少个 */
list->pool = pool; /* 线程池 */
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 = l->last;
/* 如果最后一个链表节点的元素已经用完,则需要创建一个新的链表*/
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;
}
/* 分配一个链表节点的内存块。内存大小 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;
}
/* 返回元素指针 */
elt = (char *) last->elts + l->size * last->nelts;
last->nelts++;
return elt;
}
没了,就这些了。
我全局搜索了源码,其实用到的地方也不多。
双向链表一并看一下:
一般情况下,会在业务的数据结构中,放置一个ngx_queue_t的数据结构。通过这个数据结构进行双向链表的连接。 链表和业务数据结构之间进行了解耦,使用更加灵活和方便。
示例:
/**
* 该结构体用于描述一个网络连接
*/
struct ngx_connection_s {
void *data; //连接未使用时,data用于充当连接池中空闲链表中的next指针。连接使用时由模块而定,HTTP中,data指向ngx_http_request_t
ngx_event_t *read; //连接对应的读事件
ngx_event_t *write; //连接对应的写事件
ngx_socket_t fd; //套接字句柄
ngx_recv_pt recv; //直接接受网络字节流
ngx_send_pt send; //直接发送网络字节流
ngx_recv_chain_pt recv_chain; //网络字节流接收链表
ngx_send_chain_pt send_chain; //网络字节流发送链表
/*用来将当前连接以双向链表元素的形式添加到ngx_cycle_t核心结构体
* 的reuseable_connection_queue双向链表中,表示可以重用的连接*/
ngx_queue_t queue;
/* 省去部分 */
};
这个结构的方法就比较多一些了,包括了增删查、分离合并等。就不展开了。