Nginx源码研究(5)——单向链表结构ngx_list_t

本文 http://blog.codeg.cn/2015/01/04/ngx_list_t/ 是作者zieckey在研究和学习相关内容时所做的笔记,欢迎广大朋友指正和交流! 版权所有,欢迎转载和分享,但请保留此段声明。

简介

本文主要介绍Nginx单向链表结构ngx_list_t这一重要的数据结构的使用方法和具体实现。

该链表结构与我们常说的链表结构(例如std::list)不太一样。它虽然符合list类型数据结构的一些特点,比如可以添加元素,实现动态自增长,不会像数组类型的数据结构,受到初始设定的数组容量的限制,但不同点在于它的节点,std::list每个节点只能存放一个元素,ngx_list_t的节点却是一个固定大小的数组,可以存放多个元素。当添加元素到这个list里面的时候,会在最尾部的节点里的数组上添加元素,如果这个节点的数组存满了,就再增加一个新的节点到这个list里面去。

源代码位置

src/core/ngx_list.{h,c}

数据结构

// ngx_list_part_s是代表ngx_list_t链表的一个节点。
// 它自身包含了一个数组,用来存放最终的元素
struct ngx_list_part_s {
    void             *elts; //链表元素elts数组,数组申请的空间大小为size*nalloc
    ngx_uint_t        nelts; //当前已使用的elts个数,一定要小于等于nalloc
    ngx_list_part_t  *next; //指向ngx_list_t中的下个链表part
};

// ngx_list_t结构是一个链表,链表中每个节点是ngx_list_part_t结构。
// 而ngx_list_part_t中有个elts是一个数组,储存了任意大小固定的元素,它是由ngx_pool_t分配的连续空间
typedef struct {
    ngx_list_part_t  *last; //指向链表中最后一个元素,其作用相当于尾指针。插入新的节点时,从此开始。
    ngx_list_part_t   part; //链表中第一个元素,其作用相当于头指针。遍历时,从此开始。
    size_t            size; //链表中每个元素的大小
    ngx_uint_t        nalloc; //链表的每个ngx_list_part_t中elts数组的所能容纳的最大元素个数
    ngx_pool_t       *pool; //当前list数据存放的内存池
} ngx_list_t;


// 具体实现比较简单,就不在累述。

内存结构图

阅读源码时,请参考下方的内存结构。

备注:从参考博客4摘录

测试代码

该测试代码的完整工程的编译和运行方式请参考 https://github.com/zieckey/nginx-research项目。Linux&Windows都测试通过。

#include "allinc.h"

namespace {
    struct ListElement {
        ngx_str_t name;
        int id;
    };

    static const char* names[] = { "codeg", "jane", "zieckey", "codeg4", "codeg5", "codeg6", "codeg7", "codeg8", "codeg9", "codeg10" };
}

TEST_UNIT(ngx_list)
{
    ngx_uint_t nalloc = 4;
    ngx_list_t *list = ngx_list_create(g_pool, nalloc, sizeof(ListElement));

    // insert element to the list
    for (size_t i = 0; i < H_ARRAYSIZE(names); i++)
    {
        ListElement* u = (ListElement*)ngx_list_push(list);
        u->id = i;
        u->name.data = (u_char*)names[i];
        u->name.len = strlen(names[i]);
    }
    
    H_TEST_ASSERT(list->nalloc == nalloc);
    H_TEST_ASSERT(list->last->next == NULL);
    H_TEST_ASSERT(list->last->nelts == H_ARRAYSIZE(names) % nalloc);
    H_TEST_ASSERT(list->last == list->part.next->next);

    // traverse the list
    int count = 0;
    for (ngx_list_part_t* part = &list->part; part; part = part->next)
    {
        for (ngx_uint_t n = 0; n < part->nelts; ++n)
        {
            ListElement* u = (ListElement*)(part->elts) + n;
            //printf("id=%d name=%s\n", u->id, (char*)u->name.data);
            H_TEST_ASSERT(strncmp((char*)u->name.data, names[count++], u->name.len) == 0);
        }
    }
    H_TEST_ASSERT(count == H_ARRAYSIZE(names));
}

从下面运行调试截图可以较为清晰的看出ngx_list_t的三级结构list --> node --> element。上述例子的list中有10个元素,分为三个节点存储,前两个节点都存满了(4个),最后一个节点存放了两个元素,但内存都已经分配好了。

参考:

  1. 淘宝:Nginx开发从入门到精通 http://tengine.taobao.org/book/chapter_02.html#ngx-list-t-100
  2. nginx源码注释 https://github.com/zieckey/nginx-1.0.14_comment/blob/master/src/core/ngx_list.h
  3. nginx源码注释 https://github.com/zieckey/nginx-1.0.14_comment/blob/master/src/core/ngx_list.c
  4. nginx代码分析-基本结构-单链表ngx_list_t http://my.oschina.net/chenzhuo/blog/175999