nginx之数据结构list结构

在任何一套成熟的C语言写的服务器或者语言或者应用里都包含有一些基本的数据结构操作，

一般是 array、list、hash、buf等，剖析nginx的list是下面这种结构：

元素本身的长度是size，每个桶可承担n项，那么当你插入第n+1个元素的时候，要创建一个新桶。因此nginx的list内部元素是定长结构。

例如：

mctx->variables = ngx_list_create(r->pool, 4,
                                                  sizeof(ngx_http_ssi_var_t));

前提是nginx的所有内存操作都建立在pool基础上，其中每4个元素为一个桶，当插入第五个元素的时候新建一个桶。nginx把这种桶成为part。应该就是一个子列表的意思。

下面具体来看和list有关的结构和方法：

typedef struct ngx_list_part_s ngx_list_part_t;

struct ngx_list_part_s {
    void             *elts;
    ngx_uint_t        nelts;
    ngx_list_part_t *next;
};

这是一个桶（子列表），elts是首元素的指针，nelts是元素总个数，next是下一个桶的指针。

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;

这是list的上层结构，last是最后一个桶的指针，part是第一个桶，size是每个元素的大小，nalloc是每个桶里存放多少个元素，当nelts和nalloc相等表明子列表已经到达了桶底。需要分配一个新桶来使用。pool是这个列表所基于的pool地址。

列表一共有三种操作：

ngx_list_create(); //创建及初始化队列
ngx_list_init();        //初始化队列
ngx_list_push(); //找到下一个插入位置的指针并返回

nginx的list遍历和list表的实际插入并不是在这三个函数中完成的，而是散落在外面，可能是作者觉得这样足够灵活。

由于空间是提前分配的，因此ngx_list_push()实际上返回的只是一段定长空间的指针，我们举个例子：

遍历列表

part = &cycle->open_files.part;
        file = part->elts;

        for (i = 0; /* void */ ; i++) {

            if (i >= part->nelts) {
                if (part->next == NULL) {
                    break;
                }
                part = part->next;
                file = part->elts;
                i = 0;
            }

            if (full.len != file[i].name.len) {
                continue;
            }

            if (ngx_strcmp(full.data, file[i].name.data) == 0) {
                return &file[i];
            }
        }

由于存在桶的概念，所以遍历需要一个for循环和一个if语句双重嵌套，以满足当一个桶遍历结束后，遍历下一个桶。

插入一个元素

file = ngx_list_push(&cycle->open_files);
    if (file == NULL) {
        return NULL;
    }

    if (name) {
        file->fd = NGX_INVALID_FILE;
        file->name = full;

    } else {
        file->fd = ngx_stderr_fileno;
        file->name.len = 0;
        file->name.data = NULL;
    }

    file->buffer = NULL;

    return file;

首先返回file指针，然后对file进行赋值。

本文摘自：

http://hi.baidu.com/langwan/blog/item/02eea1ef8698481efdfa3cd0.html

非常感谢langwan先生给我们的帮助