Nginx源码-基础数据结构

本篇来看一下在nginx中有哪些基础的数据结构，nginx中数据结构较多，各种struct，本篇只看一些通用基础的数据结构，与具体模块相关的其他数据结构后续再慢慢介绍。

ngx_str_t

nginx的字符串类型，声明如下：

data指向字符串开始的存储地址，len表示字符串长度，因此nginx字符串与标准C字符串不同，不必以'\0'结尾。

ngx_pool_t

nginx的内存池类型，用于申请和撤销内存，统一管理，声明如下：

d是ngx_pool_data_t类型，指向和记录内存池所代表的一块内存

max表示当前内存池代表的内存块的大小

current指向内存池本身

large当要使用的内存大于max时，内存块链接在large上

cleanup用于内存撤销时，需要做的清理工作

log当前内存池进行内存操作时的log对象

ngx_array_t

nginx的数组类型，声明如下：

elts指向数组存放的第一个元素地址

nelts，已经分配的元素的个数

size数组中的元素的sizeof

nalloc，数组能存放的元素个数

pool，数组指向的内存池

ngx_list_t

nginx的链表类型，声明如下：

last指向链表节点的最后一个元素的指针

part链表的第一个元素

size：链表存放元素的sizeof

nalloc：每个链表元素是一个数组，nalloc指定了每个数组元素的个数

pool，用于链表分配元素的内存池

注意，nginx的链表与普通的链表不太一样，每个节点存放的不是要存放的元素本身，而是要存放元素组成的数组，可以理解成是一个块状链表。

ngx_list_part_t是ngx_list_t的节点类型，声明如下：

elts节点的起始位置，即第一个元素的地址

nelts节点中已经分配的元素个数

next指向下一个节点

思考一下，nginx为何把链表设计成这样，而不是像普通的链表那样呢？还是出于性能考虑，传统的链表查找速度是O(n)，插入删除是O(1)，而数组正好相反，nginx这么设计是综合考虑了数组和链表的优缺点，使得插入和删除都介于O(1)到O(n)之间，熟悉块状链表的读者应该知道，如果设计的好，这个时间复杂度最优可以到O(sqrt(n))。