NGINX中常用的数据结构

本文主要对NGINX常用的数据结构进行总结，并给出简单的应用例子。在NGINX中，常用的数据结构包括ngx_list_t、ngx_queue_t、ngx_array_t、ngx_rbtree_t和ngx_hash_t等。下面对其进行详细的说明 。

1、ngx_list_t是NGINX提供的链表结构，具体代码如下：

struct ngx_list_part_s {

    void             *elts;

    ngx_uint_t        nelts;

    ngx_list_part_t  *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;

NGINX的链表就像用一根藤曼上接的若干葫芦，每个葫芦的容量都不通过。在ngx_list_t结构中，size表示每个元素的最大内存占用量，也就是用户存储的每个数据大小都得小于size。nalloc表示可以存储多少个元素。借用上面的例子，就是一个葫芦的容量为每个元素的最大容量size乘以元素个数nalloc。到这里，我们自然会想到，还需要一个量来表示葫芦的水位，也就是以占用的从相互空间 ，这个量就是ngx_list_part_s结构中的nelts。下面给出一个NGINX链表的例子，如下：

//给出ngx_list_t的两个主要成员nalloc和size；

ngx_list_t * tmp_list = ngx_list_create(r->pool,4,sizeof(ngx_int_t));

for(ngx_int_t i=0;i<10;++i){

ngx_int_t *rst = ngx_list_push(i);

If(NULL == rst)

return NGX_ERROR;

} 

ngx_list_part_t *tmp_part = &tmp_list.part;

ngx_int_t *tmp_elt = part->elts;

for(int i=0; ;++i){

if(tmp_part->nelts<=i){

If(NULL == tmp_part->next)

Return NGX_OK;

//进入下一个“葫芦”

tmp_part = tmp_part->next;

i= 0;

}

//遍历同一个“葫芦”里的元素

}

2、ngx_array_t：ngx_list_t的功能与C++中的list相似，而ngx_array_t则与C++中的vector更加相似。它们都实现了数据的连续存储，也就是可以用[]进行元素访问。而且也同样实现了动态存储，例如当ngx_array_t容器存储的元素已满时，则会扩大ngx_array_t的容量 。下面先看下具体代码：

typedef struct {

    void        *elts;

    ngx_uint_t   nelts;

    size_t       size;

    ngx_uint_t   nalloc;

    ngx_pool_t  *pool;

} ngx_array_t;

下面结合C++中的vector对上面的结构进行说明。nelts返回容器中一用元素的个数，相当于vector中的size()成员函数。nalloc是ngx_array_t的实际容量也就是vector的capacity()成员函数返回的数值。而 vector的reserve()成员函数返回的数值等于nalloc-nelts也就是还能容下的元素。ngx_array_t的关键和vector是一样的就是两点：数据连续存储和动态扩容。连续存储很好理解，而动态扩容是指当容器满时，再想起插入元素，容器此时该如何处理。下面先简单的介绍下C++ vector的扩容方式，之后再详细地介绍ngx_array_t的扩容方式。

C++ vector的扩容方式很简单，当容器满时，按着一定策略增加vector容量。比如：以加倍当前容量的分配策略来实现。没有固定的实现，可以自由选择，但是必须保证push_back的高效性。而ngx_array_t的策略很直接，与具体的插入函数有关，比如当调用ngx_array_push时只扩充一个自己，而调用ngx_array_push_n扩充n个字节。下面给出一个应用实例，如下：

//首先创建一个ngx_array_t

ngx_array_t *tmp_array = ngx_array_create(cf->pool,1sizeof(ngx_int_t));

//元素的插入

for(int i=0;i<100;++i){

ngx_int_t *tmp = ngx_array_push(tmp_array);

Tmp->num = i;

}

//元素遍历

ngx_int_t *tmp = tmp_array->elts;

for(int i=0;inelts;++i){

//遍历tmp[i]

}

3、ngx_queue_t: NGINX提供的一个双向链表结构。所谓的双向链表就是同时可以在链表的头部和尾部进行插入和删除操作，且其时间为O(1)(普通的单链表对尾部进行操作时，需要的时间为O(n))。双向链表结构与单链表结构相同，只是在链表头部增加了一个指针，指向链表的尾部。双向链表的代码很简单，如下：

struct ngx_queue_s {

    ngx_queue_t  *prev;

    ngx_queue_t  *next;

};

ngx_queue_s将链表抽象为两个指针一个指向前一个节点，另一个指向下一个节点。当若干个元素需要组成双向链表时，只需将此结构插入元素总即可。这种实现与linux内核中链表的实现是一样的，这种实现体现了一种高度的抽象。下面具体的说下是怎么实现链表结构的。假设，我们定义一个结构Node，并想将其用链表进行存储，则需要如下定义Node：

typedef struct{

ngx_int_t elem;

typedef ngx_queue_s nlist;

}Node;

那么我们如何构造链表呢？首先我们定义一个ngx_queue_s，然后对其进行初始化，如下：

ngx_queue_s tmp_list;

ngx_queue_init(&tmp_list);

注意：在实现时，需要自己进行内存分配，此处简单起见，使用了栈分配方式。那么我们怎么将Node存放于链表中呢？如下，我们将5个整数添加到tmp_list中去，代码如下：

Node tmp_node[5];

for(int i=0;i<5;++i){

tmp_node[i].elem = i;

ngx_queue_insert_tail(&mp_list,&tmp_node[i].nlist);

}

上面的代码就是将5个Node中的nlist连接起来。那么自然会想，我们如何通过nlist来获取存储它的结构呢？这要用到一个宏，如下：

#define ngx_queue_data(q,type,link) (type*)((u_char*)q-offsetof(type,link))

offsetof是一个求解偏移量的宏。下面简单的说下这个宏的实现原理，然后给出一个例子。这个宏的实现关键是利用了一个C语言的特性：类型所占的内存在编译是确定。因为有了了这个特性，我们可以首先通过(u_char*)q获得nlist在当前结构中的地址，只要再减去nlist在Node内存中的偏移(offsetof(type,link))，我们就可以得到Node的地址啦。我们给出对Node tmp_node[5]的遍历代码，如下：

for(ngx_queue_s *p = ngx_queue_head(&tmp_list);p!=ngx_queue_sentinel(&tmp_list);

p = ngx_queue_next(q)){

Node* tmp_node = ngx_queue_next(p,Node,nlist);

//对接点进行操作

}

4、ngx_rbtree_t:就像linux内核和STL一样，NGINX也提供了红黑树这种近似平衡二叉树数据结构。原来写过一篇红黑树的两种实现的总结(主要是STL和linux内核实现)：http://blog.chinaunix.net/uid-28311809-id-3823619.html。我们可以看到NGINX之中的红黑树的实现与linux内核是一样的，都是把红黑树抽象为具有某些性质的节点，然后将其添加到要构造红黑树的结构中。其中，这些性质如下：

struct ngx_rbtree_node_s {

    ngx_rbtree_key_t       key;

    ngx_rbtree_node_t     *left;

    ngx_rbtree_node_t     *right;

    ngx_rbtree_node_t     *parent;

    u_char                 color;

    u_char                 data;

};

以上的这些性质显然是红黑树节点应该具有的性质。下面我们以一个例子对红黑树进行说明。我们创建一颗红黑树，如下：

ngx_rbtree_t tmp_rb;

ngx_rbtree_node_s sentinel;

ngx_rbtree_init(tmp_rb);

首先，我们定义了一颗红黑树tmp_rb，它是对整棵树的描述。其结构为ngx_rbtree_t，代码如下：

typedef struct ngx_rbtree_s  ngx_rbtree_t;

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,

    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

struct ngx_rbtree_s {

    ngx_rbtree_node_t     *root;

    ngx_rbtree_node_t     *sentinel;

    ngx_rbtree_insert_pt   insert;

};

在上面的结构中，root代表根节点，sentinel是哨兵节点，颜色为黑色(算法导论有详细的介绍)，insert是一个函数指针，此函数指针的目的是，当ngx_rbtree_node_s结构中的key相同时用insert区分节点。也就是说，在ngx_rbtree中可以存在两个key相同的节点。接下来，我们定义一个自己的结构，表示红黑树的节点，如下：

typedef struct{

ngx_rbtree_node_s rb_node;

int elem;

}RB_Node;

下面，我们构造一颗红黑树，如下：

typedef struct RB_Node tmp_rb_node[30];

for(int i=0;i<30;++i){

tmp_rb_node[i].elem = rand()%30;

tmp_rb_node[i].rb_node.key = tmp_rb_node[i].elem;

ngx_rbtree_insert(&tmp_rb,&tmp_rb_node[i].rb_node);

}

我们可以清楚的看到，在创建红黑树时，只是将RB_Node中的rb_node插入了红黑树。这和上面的ngx_queue_s很相似啊。同样的也涉及了如何通过rb_node获得RB_Node结构的问题。同样可以利用，ngx_queue_s中的方法。但是我们看到RB_Node的定义中，rb_node是放在结构中的第一位的，这也就意味着，RB_Node结构的地址与rb_node的地址是相通的。只需进行类型转换就可以啦。

红黑树中还定义了一些其他方法，例如查找，删除等操作，这里就不在叙述啦。

5、ngx_hash_t：因为哈希表的操作速度相当快，因此NGINX也提供了相应的结构。对于哈希表的实现原理，就不再累述啦。下面先给出哈希表的两个主要结构代码，如下：

typedef struct {

    void             *value;

    u_short           len;

    u_char            name[1];

} ngx_hash_elt_t;

typedef struct {

    ngx_hash_elt_t  **buckets;

    ngx_uint_t        size;

} ngx_hash_t;

在第一个结构中，value是指向自定义数据的指针，len是数据的长度，而name元素关键字的首地址。在第二个结构ngx_hash_t中，bucket是指向散列表第一个元素的指针，而size则表示此散列表中存在多少个槽。同时NGINX的哈希表也支持通配符，也就是说其关键字构成可以是*,*.test.org或者org。但在 生成key时会去掉通配符生成关键字。在进行关键字查找时，遵循以下查找顺序：

1）、选择完全匹配的字符串，如：

2）、选择通配符在前面的，如：*.test.org

3）、最后选择通配符在后面的，如：

下面，我们结合具体例子（带通配符）进行说明。如下：

//首先定义一个两个结构，未初始化散列表做准备，此处就不给出源代码了。

ngx_hash_init_t hash;

ngx_hash_keys_arrays_t h_array;

ngx_hash_combined_t c_hash;

//是通配符散列表的规则，其中存放三个成员：hash、wc_head和wc_tail

ngx_memzero(&ha,sizeof(ngx_hash_keys_arrays_t ));

//主要用于分配一些临时动态数组

h_array.temp_pool = ngx_create_pool(16384,cf->log)

If(NULL == ha.temp_pool)

return NGX_ERROR;

//用于分配列表中的所有的槽，最多三个，如ngx_hash_combined_t结构

Ha.pool = cf->pool;

if(ngx_hash_keys_array_init(&ha,NGX_HASH_LARGER) != NGX_OK)

return NGX_ERROR;

//定义三个元素，表示前通配、后通配和完全匹配

ngx_str_t server[3];

server[0].len = ngx_strlen(“com”);

server[0].data = ngx_pcalloc(cf->pool,ngx_strlen(“ww.test.com”));

ngx_memcpy(erver[0].date,“*.test.com”,ngx_strlen(“com”));

server[0].len = ngx_strlen(“*.test.com”);

server[0].data = ngx_pcalloc(cf->pool,ngx_strlen(“*.test.com”));

ngx_memcpy(erver[0].date,“*”,ngx_strlen(“*.test.com”));

server[0].len = ngx_strlen(“*”);

server[0].data = ngx_pcalloc(cf->pool,ngx_strlen(“*”));

ngx_memcpy(erver[0].date,“*.test.com”,ngx_strlen(“*”));

//将server[3]添加到ngx_hash_keys_arrays_t 当中

for(int i=0;i<3;++i){

ngx_hash_add_key(&h_array, &server[i],&server[i],NGX_HASH_WILDCARD_KEY);

}

//注意：flage设置为NGX_HASH_WILDCARD_KEY才会处理通配符。

//初始化一些常量

hash.key = ngx_hash_key_lc;

hash.max_size = 100;

hash.bucket_size = 40;

hash.name = “test_server_name”;

if(h_array.key_nelts) {

//初始化标准匹配

}

if(h_array.dns_wc_head.nelts){

//初始化前置通配符匹配

}

if(h_array.dns_wc_tail.nelts){

//初始化后置通配符匹配

}

//最后销毁temp_pool 

ngx_destroy_pool(h_array.temp_pool );

总结：我们通过上面的总结发现nginx中的一些结构和STL和linux内核中的一些结构很相似，但也有自己的特色，例如：哈希表和链表。
本文出处：http://blog.chinaunix.net/uid-28311809-id-4253454.html