- ngx_queue_t双向链表
- ngx_array_t动态数组
- ngx_list_t单向链表—>基础数据结构以涉及
- ngx_rbtree_t红黑树
- ngx_radix_tree_t基数树
- 支持通配符的散列表
ngx_queue_t双向链表
Nginx链表不负责链表元素所占内存的分配且与ngx_pool_t内存池无关，支持两个链表间的合并，链表排序的功能。
Nginx链表结构仅有两个成员：prev指针与next指针，在空间上也只会增加两个指针的内存消耗。该链表的使用方式是，对于某结构体只要包含该ngx_queue_t类型的成员，就组成了该类结构体的链表，在向链表容器中添加，删除元素时都使用该结构体中的ngx_queue_t类型成员指针。
1 | typedef struct ngx_queue_s ngx_queue_t; |
2 | struct ngx_queue_s { |
3 | ngx_queue_t prev; |
4 | ngx_queue_t next; |
5 | }; |
ngx_queue_t双向链表容器支持的方法：
| 方法名 | 说明 |
|---|---|
ngx_queue_init(h) |
将链表容器h初始化，此时会自动置为空链表。 |
ngx_queue_empty(h) |
检查链表容器是否为空，返回非0，表示链表h为空。 |
ngx_queue_insert_head(h,x) |
将元素x插入到链表容器h的头部 |
ngx_queue_insert_tail(h,x) |
将元素x插入到链表容器h的末尾 |
ngx_queue_head(h) |
返回链表容器h中的第一个元素的ngx_queue_t结构体指针 |
ngx_queue_last(h) |
返回链表容器中的最后一个元素的ngx_queue_t结构体指针 |
ngx_queue_sentinel(h) |
返回链表容器结构体的指针 |
ngx_queue_remove(x) |
在容器中移除x元素 |
ngx_queue_split(h,q,n) |
拆分链表，将链表h以元素q为界拆分成两个链表h(不包括q)和n(q是首元素) |
ngx_queue_add(h,n) |
合并链表，将n链表添加到h链表的末尾 |
ngx_queue_middle(h) |
返回链表中心元素，返回第$N/2+1$个元素。 |
ngx_queue_sort(h,cmpfunc) |
插入排序方式对链表进行排序。cmpfunc原型为ngx_int_t (*cmpfunc)(const ngx_queue_t *, const ngx_queue_t *) |
ngx_queue_t双向链表中的元素所支持的方法：
| 方法名 | 说明 |
|---|---|
ngx_queue_next(q) |
返回q元素的下一个元素 |
ngx_queue_prev(q) |
返回q元素的上一个元素 |
ngx_queue_data(q,type,link) |
返回q元素所属结构体的地址 |
ngx_queue_insert_after(q,x) |
将元素x插入到元素q之后 |
ngx_array_t动态数组
ngx_array_t容器：访问速度快，允许元素个数具备不确定性，负责元素占用内存的分配，这些内存将由内存池统一管理。
1 | typedef struct{ |
2 | void *elts; /* 指向数组的首地址 */ |
3 | ngx_uint_t nelts; /* 数组中已经使用的元素个数 */ |
4 | size_t size; /* 每个数组元素占用的内存大小 */ |
5 | ngx_uint_t nalloc; /* 当前数组中能够容纳元素个数的总大小 */ |
6 | ngx_pool_t *pool; /* 内存池对象 */ |
7 | }ngx_array_t; |
| 方法名 | 说明 |
|---|---|
ngx_array_create(ngx_pool_t *p,ngx_uint_t n,size_t size) |
创建一个动态数组，并预分配n个大小为size的内存空间 |
ngx_array_init(ngx_array_t *a,ngx_pool_t *p,ngx_uint_t n,size_t size) |
初始化一个已经存在的动态数组，并预分配n个大小为size的内存空间 |
ngx_array_destroy(ngx_array_t *a) |
销毁已经分配的数组元素空间和ngx_array_t动态数组对象。 |
ngx_array_push(ngx_array_t *a) |
向当前动态数组中添加元素，返回这个新添加元素的地址，会自动扩容。 |
ngx_array_push_n(ngx_array_t *a,ngx_uint_t n) |
向当前动态数组添加n个元素，返回新添加这批元素中的第一个元素地址 |
