8.nginx源码分析之数据结构：ngx_list_t

╰+攻爆jí腚メ 2022-07-15 01:56 220阅读 0赞

# nginx源码分析之数据结构：ngx\_list\_t #

ngx\_list\_t是一个单项链表，在nginx的头文件ngx\_list.h中主要定义了两个结构体来描述链表：

单链表的控制信息：

typedef struct {
        ngx_list_part_t  *last;      //链表的最有一个节点地址
        ngx_list_part_t   part;      //链表的头节点
        size_t            size;      //每个元素的大小
        ngx_uint_t        nalloc;    //链表节点所包含的空间（块）个数
        ngx_pool_t       *pool;      //链表对应的内存池地址
    } ngx_list_t;

单链表的节点信息：

struct ngx_list_part_s {
        void             *elts;     //存储的区块大小，size * nalloc
        ngx_uint_t        nelts;    //实际存储的元素个数
        ngx_list_part_t  *next;     //下一个节点的地址
    };

控制信息和节点信息的关系如下所示：  
![这里写图片描述][20161029114955937]

单链表的接口非常简单，只包含了创建和添加元素的方法，在nginx中所有的元素释放操作都由内存池进行销毁：

//创建单链表
    ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);
    //添加元素
    void *ngx_list_push(ngx_list_t *list);

关于上述两个接口的实现在ngx\_list.c文件中进行了定义：

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;
        }
    
        //对单链表进行初始化
        if (ngx_list_init(list, pool, n, size) != NGX_OK) {
            return NULL;
        }
    
        return list;
    }

单链表的初始化操作在ngx\_list.h文件中进行了定义：

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 */
    
            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;
            }
    
            last->nelts = 0;
            last->next = NULL;
    
            l->last->next = last;
            l->last = last;
        }
    
        //在目标节点中申请内存，并且把地址elt返回给调用者
        elt = (char *) last->elts + l->size * last->nelts;
        last->nelts++;
    
        return elt;
    }

## 小结 ##

单链表的操作非常单一，希望大家早点get，赶紧进入下一个章节！

[20161029114955937]: /images/20220715/935d482606ac4e48912022c10c2a918a.png