Nginx 高级数据结构

本文主要是介绍Nginx 高级数据结构，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

- 1. ngx_queue_t
- 2. ngx_array_t
- 3. ngx_rbtree_t
- 4. ngx_hash_t (待更新)

Nginx的高级数据包括ngx_queue_t, ngx_array_t, ngx_list_t, ngx_rbtree_t, ngx_radix_tree_t, ngx_hash_t。

1. ngx_queue_t

ngx_queue_t双向链表是Nginx提供的轻量级链表容器，与Nginx的内存池无关，因此这个链表不会负责分配内存来存放元素，这个数据结构仅仅把已经分配好的内存元素使用双向链表连接起来，所以对每个用户来说，只需要增加两个指针的空间即可，消耗的内存很少。同时，ngx_queue_t还提供了一个非常简易的插入排序法。相对于Nginx其他顺序容器，它的优势在于:

实现了排序功能
非常轻量级，是一个纯粹的双向链表，它不负责链表元素所占内存的分配，与Nginx封装的ngx_pool_t内存池完全无关。
支持两个链表间的合并

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

它的实现非常简单，仅有两个成员prev, next。

实现访问API:

ngx_queue_init(q)                  //初始化链表  q为空
ngx_queue_empty(h)                 //检测链表是否为空
ngx_queue_insert_head(h, x)        //将x插入到h的头部
ngx_queue_insert_tail(h, x)        //将x插入到h的尾部
ngx_queue_head(h)                  //返回链表h中的第一个元素的结构体指针
ngx_queue_last(h)                  //返回链表h中的最后一个元素的结构体指针
ngx_queue_sentinel(h)              //返回链表容器结构体的指针
ngx_queue_remove(x)                //移除x结构体元素
ngx_queue_split(h, q, n)           // 以元素q为界分为h和n两个链表，其中h是前半部分(不包括q)，n是后半部分(包括q)
ngx_queue_add(h, n)                //合并链表，将n添加到h的尾部
ngx_queue_middle(h)                //返回链表的中心元素，假如有N个，返回N/2+1个元素
ngx_queue_sort(h, compfunc)        //使用插入排序对链表进行排序，compfunc需要自己实现

对于链表中的每一个元素，其类型可以是任意的struct结构体，但这个结构体中必须要有一个ngx_queue_t 类型的成员，在向链表容器中添加、删除时都是使用结构体中的ngx_queue_t类型成员的指针。当ngx_queue_t作为链表的元素成员使用时，他具有下面4种用法:

ngx_queue_next(q)                  //返回链表q的下一个元素
ngx_queue_prev(q)                  //返回q的上一个元素
ngx_queue_data(q, type, link)      //返回q元素所属结构体中可在任意位置包含ngx_queue_t的地址
ngx_queue_insert_after(q, x)       //和ngx_queue_insert_head相同，因为是双向链表，没有头尾之分

Test SampleCode:

#include <stdio.h>
#include <string.h>

#include "ngx_config.h"

#include "ngx_core.h"


#include "ngx_list.h"
#include "ngx_palloc.h"
#include "ngx_string.h"
#include "ngx_queue.h"

ngx_queue_t queueContainer;

typedef struct {
    u_char *str;
    ngx_queue_t qEle;
    int num;
}TestNode;

ngx_int_t compTestNode(const ngx_queue_t* a, const ngx_queue_t *b) {
    TestNode *aNode = ngx_queue_data(a, TestNode, qEle);
    TestNode *bNode = ngx_queue_data(b, TestNode, qEle);

    return aNode->num > bNode->num;
}

volatile ngx_cycle_t *ngx_cycle;
 
void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log,
			ngx_err_t err, const char *fmt, ...)
{



}

int main() {
    TestNode node[5];

    ngx_queue_init(&queueContainer);

    for (int i = 0; i < 5; i++) {
        node[i].num = i;
        
    }
    ngx_queue_insert_tail(&queueContainer, &node[1].qEle);
    ngx_queue_insert_tail(&queueContainer, &node[4].qEle);
    ngx_queue_insert_tail(&queueContainer, &node[0].qEle);
    ngx_queue_insert_tail(&queueContainer, &node[2].qEle);
    ngx_queue_insert_tail(&queueContainer, &node[3].qEle);

    ngx_queue_sort(&queueContainer, compTestNode);

    ngx_queue_t *q;
    for (q = ngx_queue_head(&queueContainer); q != ngx_queue_sentinel(&queueContainer); q = ngx_queue_next(q)) {
        TestNode *eleNode = ngx_queue_data(q, TestNode, qEle);
        printf("%d\n", eleNode->num);
    }

    return 0;
}

编译:

gcc -o ngx_queue_main ngx_queue_main.c  -I ../../nginx-1.16.1/src/core/ -I ../../nginx-1.16.1/objs/  -I ../../nginx-1.16.1/src/os/unix/ -I ../../pcre-8.44/ -I ../../nginx-1.16.1/src/event/ ../../nginx-1.16.1/objs/src/core/ngx_list.o ../../nginx-1.16.1/objs/src/core/ngx_string.o ../../nginx-1.16.1/objs/src/core/ngx_palloc.o ../../nginx-1.16.1/objs/src/os/unix/ngx_alloc.o../../nginx-1.16.1/objs/src/core/ngx_queue.o

2. ngx_array_t

ngx_array_t 是一个顺序的动态数组，在Nginx大量使用，支持达到数组容量上限时动态改变数组的大小。ngx_array_t 和C++ STL中的vector很类似，它内置了Nginx封装的内存池，因此，他分配的内存可以在内存池中申请得到。具备下面几个特点:

访问速度快
允许元素个数具备不确定性
负责元素占用内存的分配，这些内存由内存池统一管理

typedef struct {
    void        *elts;    //指向数组的首地址
    ngx_uint_t   nelts;   //数组中已经使用的元素个数
    size_t       size;   //每个元素占用的内存大小
    ngx_uint_t   nalloc; // 当前数组中能够容纳元素个数的总大小
    ngx_pool_t  *pool;    //内存池对象
} ngx_array_t;

提供了如下API:

ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size); //初始化1个已经存在的动态数组，并预分配n个大小为size的内存空间
ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size); //创建1个动态数组，并预分配n个大小为size的内存空间
ngx_array_destroy(ngx_array_t *a);                     // 销毁数组 和create配对使用
ngx_array_push(ngx_array_t *a);                        // 向当前a动态数组中添加1个元素，返回的是这个新添加元素的地址
ngx_array_push_n(ngx_array_t *a, ngx_uint_t n);        //向当前a动态数组中添加n个元素，返回的是新添加这批元素中第一个元素的地址

动态数组的扩容方式:

ngx_array_push 和ngx_array_push_n都可能引发扩容操作，ngx_array_push 方法将会申请 ngx_array_t结构体中size字节的大小，而ngx_array_push_n方法将会申请n个size字节大小的内存。每次扩容的大小将受制于内存池的以下两种情形:

如果当前内存池中剩余的空间的大于或者等于本次需要新增的空间，那么本次扩容将只扩容新增的空间。例如: 对于ngx_array_push来说，就是扩充1个元素，而对于ngx_array_push_n来说，就是扩充n个元素。
如果当前内存池中剩余的空间小于本次需要新增的空间，那么对ngx_array_push方法来说，会将原先动态数组的容量扩容一倍，而对于ngx_array_push_n 来说，如果参数n小于原先动态数组的容量，将会扩容一倍；如果参数n大于原先动态数组的容量，这时会分配2n大小的空间，扩容超过一倍，此时动态数组会被分配在全新的内存块上，会把原先的元素复制到新的动态数组中。

SampleCode:

#include <stdio.h>
#include <string.h>

#include "ngx_config.h"

#include "ngx_core.h"


#include "ngx_list.h"
#include "ngx_palloc.h"
#include "ngx_string.h"



#define N		10

typedef struct _key {
	int id;
	char name[32];
} Key;

volatile ngx_cycle_t *ngx_cycle;
 
void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log,
			ngx_err_t err, const char *fmt, ...)
{



}


void print_array(ngx_array_t *array) {

	Key *key = array->elts;

	int i = 0;
	for (i = 0;i < array->nelts;i ++) {
		printf("%s .\n", key[i].name);
	}

}

int main() {

	ngx_pool_t *pool = ngx_create_pool(1024, NULL);

	ngx_array_t *array = ngx_array_create(pool, N, sizeof(Key));

	int i = 0;
	Key *key = NULL;
	for (i = 0;i < 25;i ++) {

		key = ngx_array_push(array);
		key->id = i+1;
		sprintf(key->name, "array %d", key->id);
		
	}

	key = ngx_array_push_n(array, 10);
	for (i = 0;i < 10;i ++) {
		key[i].id = 25+i+1;
		sprintf(key[i].name, "array %d", key[i].id);
	}

	print_array(array);

}

编译:

gcc -o ngx_array_main ngx_array_main.c -I ../../nginx-1.16.1/src/core/ -I ../../nginx-1.16.1/objs/  -I ../../nginx-1.16.1/src/os/unix/ -I ../../pcre-8.44/ -I ../../nginx-1.16.1/src/event/  ../../nginx-1.16.1/objs/src/core/ngx_string.o ../../nginx-1.16.1/objs/src/core/ngx_palloc.o ../../nginx-1.16.1/objs/src/os/unix/ngx_alloc.o  ../../nginx-1.16.1/objs/src/core/ngx_array.o

3. ngx_rbtree_t

ngx_rbtree_t是使用红黑树实现的一种关联容器，Nginx模块的核心(定时器管理、文件缓存模块等)在需要快速检索、查找的场合下都使用了ngx_rbtree_t容器。

typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;              //uint的关键字
    ngx_rbtree_node_t     *left;             //左子节点
    ngx_rbtree_node_t     *right;           //右子节点
    ngx_rbtree_node_t     *parent;           //父节点
    u_char                 color;           //节点的颜色， 0:黑色 1:红色
    u_char                 data;           //1字节的节点数据 
};


typedef struct ngx_rbtree_s  ngx_rbtree_t;
//为解决不同节点含有相同关键字的元素冲突问题，红黑树设置了ngx_rbtree_insert_pt指针，这样可灵活地添加冲突元素
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; //指向NULL哨兵节点
    ngx_rbtree_insert_pt   insert;  //表示红黑树添加元素的函数指针，它决定在添加新节点时的行为究竟是替换还是新增
};

添加数据的三种API:

//向红黑树添加数据节点，每个数据节点的关键字都是唯一的，不存在同一个关键字有多个节点的问题
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);  
//添加数据节点的关键字可以不是唯一的，但它们是以字符串作为唯一的标识，存放在ngx_str_node_t结构体的str成员中
ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
//添加的数据节点的关键字表示时间或者时间差
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

红黑树的API:

ngx_rbtree_init(tree, s, i)   //初始化红黑树
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);   //向红黑树添加节点
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);  //从红黑树中删除节点

在初始化红黑树的时候，需要先分配好保存在红黑树的ngx_rbtree_t结构体，以及ngx_rbtree_node_t类型的哨兵节点，并选择或者自定义ngx_rbree_insert_pt类型的节点添加函数。

Samplecode:

#include <stdio.h>
#include <string.h>

#include "ngx_config.h"

#include "ngx_core.h"


#include "ngx_list.h"
#include "ngx_palloc.h"
#include "ngx_string.h"
#include "ngx_rbtree.h"


volatile ngx_cycle_t *ngx_cycle;
 
void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log,
			ngx_err_t err, const char *fmt, ...)
{



}


int main() {

	ngx_rbtree_t rbtree;
	ngx_rbtree_node_t sentinel;
	
	ngx_rbtree_init(&rbtree, &sentinel, ngx_str_rbtree_insert_value);

	ngx_str_node_t strnode[10];
	ngx_str_set(&strnode[0].str, "he");
	ngx_str_set(&strnode[1].str, "jon");
	ngx_str_set(&strnode[2].str, "Issac");
	ngx_str_set(&strnode[3].str, "tursom");
	ngx_str_set(&strnode[4].str, "will");

	ngx_str_set(&strnode[5].str, "birate");
	ngx_str_set(&strnode[6].str, "ren");
	ngx_str_set(&strnode[7].str, "stephen");
	ngx_str_set(&strnode[8].str, "ultimate");
	ngx_str_set(&strnode[9].str, "he");

	int i = 0;
	for (i = 0;i < 10;i ++) {
		strnode[i].node.key = i;
		ngx_rbtree_insert(&rbtree, &strnode[i].node);
	}

	ngx_str_t str = ngx_string("will");
	
	ngx_str_node_t *node = ngx_str_rbtree_lookup(&rbtree, &str, 0);
	if (node != NULL) {
		printf(" Exit\n");
	}
}

编译:

gcc -o ngx_array_main ngx_array_main.c -I ../../nginx-1.16.1/src/core/ -I ../../nginx-1.16.1/objs/  -I ../../nginx-1.16.1/src/os/unix/ -I ../../pcre-8.44/ -I ../../nginx-1.16.1/src/event/  ../../nginx-1.16.1/objs/src/core/ngx_string.o ../../nginx-1.16.1/objs/src/core/ngx_palloc.o ../../nginx-1.16.1/objs/src/os/unix/ngx_alloc.o  ../../nginx-1.16.1/objs/src/os/unix/ngx_rbtree.o

4. ngx_hash_t (待更新)

本文部分技术点出处，Linux C/C++服务器直播视频: 推荐免费订阅

这篇关于Nginx 高级数据结构的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Nginx教程