2

Nginx源码分析-基础数据结构(二)

 3 years ago
source link: https://atticuslab.com/2020/10/07/nginx-annotated-5/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
  1. ngx_queue_t双向链表
  2. ngx_array_t动态数组
  3. ngx_list_t单向链表—>基础数据结构以涉及
  4. ngx_rbtree_t红黑树
  5. ngx_radix_tree_t基数树
  6. 支持通配符的散列表

ngx_queue_t双向链表

Nginx链表不负责链表元素所占内存的分配且与ngx_pool_t内存池无关，支持两个链表间的合并，链表排序的功能。

Nginx链表结构仅有两个成员：prev指针与next指针，在空间上也只会增加两个指针的内存消耗。该链表的使用方式是，对于某结构体只要包含该ngx_queue_t类型的成员，就组成了该类结构体的链表，在向链表容器中添加，删除元素时都使用该结构体中的ngx_queue_t类型成员指针。

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+1N/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容器：访问速度快，允许元素个数具备不确定性，负责元素占用内存的分配，这些内存将由内存池统一管理。

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个元素，返回新添加这批元素中的第一个元素地址

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK