nginx的作者为追求极致的高效，自己实现了很多颇具特色的nginx风格的数据结构以及公共函数。比如，nginx提供了带长度的字符串，根据编译器选项优化过的字符串拷贝函数ngx_copy等。

ngxstrt

typedef struct { size_t len; u_char *data; } ngx_str_t; ngxstrt只有两个成员，其中data指针指向字符串起始地址，len表示字符串的有效长度。注意，ngxstrt的data成员指向的并不是普通的字符串，因为这段字符串未必会以'\0'作为结尾，所以使用时必须根据长度len来使用data成员。以下是比较methodname的方法：if (0 == ngx_strncmp( r->method_name.data, "PUT", r->method_name.len) )用户请求“GET /test?a=1 http/1.1\r\n”存储到内存地址0x1d0b0110上，这时只需要把r->methodname设置为{len = 3, data = 0x1d0b0110}就可以表示方法名“GET”，而不需要单独为method_name再分配内存冗余的存储字符串。

ngxlistt

ngxlist t是一个顺序容器，它实际上是动态数组和单向链表的结合体，扩容起来比动态数组简单的多，可以一次扩容一个数组，所以说它结合了 链表插入删除不需要移动的和数组下标快速索引的优势。 ``` typedef struct ngxlistparts ngxlistpartt;

//描述链表中的一个结点，这个结点又是一个数组 struct ngxlistpart_s { void *elts; //首地址 ngxuintt nelts; //已经使用的个数 ngx_listpartt *next; //下一个链表节点的指针 };

typedef struct { ngxlistpart_t *last; //链表中最后一个数组元素 ngxlistpartt part; //链表中的首个数组元素 sizet size; //每个数组元素占用的空间大小 ngxuintt nalloc; //每个数组结点的容量，即每个数组最多可以存放多少个元素 ngxpoolt *pool; //链表中的内存池对象指针 } ngxlistt; ```

初始化链表时，规定链表中元素的内存占用大小为size，一次性向ngxpoolt内存池申请size * nelts大小的内存空间，作为链表的节点

为什么重复造ngxlistt这么个轮子?

一句话：为了提高效率。

通常list在使用过程中每个节点意味着一次内存申请，这是一种效率低下的内存使用方式，ngxlistt使用一次申请一块内存的方式减少内存申请次数，提高效率。nginx对于内存分配的苛刻真是值得我们学习。

ngxqueuet

ngxqueuet是nginx提供的一个轻量级的双向链表容器，它不负责存储数据，既不提供数据的内存分配，它只有两个指针负责把数据链入链表，它跟stl提供的queue不同，stl提供的queue帮助用户存储数据，用户只需要相容器里添加数据即可，而ngxqueuet,用户必须自己提供存储数据的内存，并且必须定义一种数据结构把ngxqueuet包含在其中，然后利用ngxqueuet提供的函数来进行相应的操作。

``` typedef struct ngxqueues ngxqueuet;

struct ngxqueues { ngxqueuet *prev; ngxqueuet *next; }; ``` 这和Linux内核的数据结构很像，它们都将链表节点塞入数据结构。

如何使用？struct fox { unsigned long tail_length; unsigned long weight; bool is_fantastic; struct list_head list; }所以它用fox.list.next指向下一个节点，用fox.list.prev指向上一个节点。那我们如何从listhead找到fox的地址呢。内核提供了一个containerof()宏可以从链表指针找到父结构中包含的任何变量。 总结一下nginx队列的优点： * 可以高效的执行插入、删除、合并等操作。 * 一个纯粹的双向链表，它不负责链表元素所占内存的分配，与Nginx封装的ngxpoolt内存池完全无关； * 具有排序功能； * 支持两个链表间的合并；

ngxhasht

Nginx中自造的哈希表属于内部使用的数据结构，因此，并不是一个通用的哈希表。此外，为了提高效率，nginx作者做了相当多的优化，这些优化使得Nginx中的哈希表与常规的哈希表长得不一样。

``` typedef struct { //hash元素结构 void *value; //value，即某个key对应的值，即<key,value>中的value ushort len; //name长度 uchar name[1]; //某个要hash的数据(在nginx中表现为字符串)，即<key,value>中的key } ngx_hasheltt;

typedef struct { //hash结构 ngxhashelt_t **buckets; //hashbuckets(有size个buckets) ngxuintt size; //hashbuckets个数

} ngxhasht; ```

根据哈希表的概念可知：哈希表本身就是一个数组，因此，是一块连续的内存空间。 在Nginx中，内存的管理都是通过ngxpoolt来管理的）,因此，需要一个用来管理这块连续内存的结构体。

但是由于哈希表为了解决冲突问题，通常采用链地址法，所以，这个管理内存的结构体会使用指针的指针。

另外，由于Nginx的哈希表是只读的，冲突的元素个数可以在初始化是确定，所以使用数组来代替链表解决冲突是更优的选择。

这个用来代替链表的数组还有个名字叫hash桶，所以，会在Nginx源码中看到buckets这样的命名。 nginx 的 hash 在查找时使用的是分桶后线性查找法，因此当分桶数确定时查找效率同其中的总 key-val 对数量成反比。

ngx_array _t

ngx_array _t是一个顺序容器，支持达到数组容量上限时动态改变数组的大小，类似于STL中vector，具有以下特性：

• 下标直接索引，访问速度快
• 动态增长
• 由slab内存池统一管理分配出的内存，效率高

slab是Linux操作系统的一种内存分配机制，slab分配算法采用cache 存储内核对象。slab 缓存、从缓存中分配和释放对象然后销毁缓存的过程必须要定义一个 kmem_cache 对象，然后对其进行初始化这个特定的缓存包含 32 字节的对象。

数据结构定义：

typedef struct { void *elts; //数组的首地址 ngx_uint_t nelts; //数组中已经使用的元素个数 size_t size; //每个数组元素占用内存大小 ngx_uint_t nalloc; //当前数组中能容纳袁术个数的总大小 ngx_pool_t *pool; //内存池对象 } ngx_array_t;这里介绍一下他的push，比stl的vector内存分配更高效。 ``` void * ngxarraypush(ngxarrayt *a) { void *elt, *new; sizet size; ngxpool_t *p;

//使用的和预先分配的个数相等，数组已满
if (a->nelts == a->nalloc) {

    /* the array is full */

    //再分配预分配nalloc个，现在就有2*nalloc个了
    size = a->size * a->nalloc;

    p = a->pool;

    //如果内存池内存还够，直接从内存池分配，只分配一个
    if ((u_char *) a->elts + size == p->d.last
        && p->d.last + a->size <= p->d.end)
    {
        /*
         * the array allocation is the last in the pool
         * and there is space for new allocation
         */

        //内存池尾指针后移一个元素大小，分配内存一个元素，并把nalloc+1
        p->d.last += a->size;
        a->nalloc++;

    //如果内存池内存不够了，分配一个新的数组，大小为两倍的nalloc
    } else {
        /* allocate a new array */

        //内存分配
        new = ngx_palloc(p, 2 * size);
        if (new == NULL) {
            return NULL;
        }

        //将以前的数组拷贝到新数组，并将数组大小设置为以前二倍
        ngx_memcpy(new, a->elts, size);
        a->elts = new;
        a->nalloc *= 2;
    }
}

//已分配个数+1 ，并返回之
elt = (u_char *) a->elts + a->size * a->nelts;
a->nelts++;

return elt;

} ```

当内存池有空间时，数组满后仅增加一个元素，当内存池没有未分配空间时，直接分配2*nalloc 个大小，有了内存池，比vector直接2n+1更加有效。

这里做一下个人对数据结构的总结吧：

数据结构毫无疑问的是在编程上非常重要的一部分内容，在我的学习过程中，我经历了迷茫，入门，熟悉等阶段。不要一味的赶时髦去学习各种新技术，这种思想其实不是很好，新技术每天都在出，学不完的，一定要把握根本，数据结构就是根本之一，其实所有语言都是万变不离其中的，只要把编程之本数据结构和算法等等学习透彻，其他语言什么的都迎刃而解了。