Nginx源码研究（5）——单向链表结构ngx_list_t

// 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;


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

#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));
}