【Nginx 源码学习】Nginx 中的 “deque“

//链表
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;		//下一个链表元素的地址
};

/**
 * 创建链表
 */
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;
}

/**
 * 该结构体用于描述一个网络连接
 */
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;
 
	/* 省去部分 */
};