Nginx 基本数据结构

l 中所有大块内存链表上的内存，小块内存链上的内存块都修改为可用。但是不会去处理 cleanup链表上的项目。 ngx_array_tngx_array_t 是 Nginx 内部使用的数组结构。Nginx 的数组结构在存储上与大家认知的 C 语言内置的数组有相似性，比如实际上存储数据的区域也是一大块连续的内存。但是数组除了存储数据的内存以外还包含一些元信息来描述相关的一些信息。下面我们从数组的定义上来详细的了解一下。ngx_array_t 的定义位于src/core/ngx_array.c|h里面。 typedef struct ngx_array_s ngx_array_t; struct ngx_array_s { void *elts; ngx_uint_t nelts; size_t size; ngx_uint_t nalloc; ngx_pool_t *pool; };elts: 指向实际的数据存储区域。 nelts: 数组实际元素个数。size: 数组单个元素的大小，单位是字节。 nalloc: 数组的容量。表示该数组在不引发扩容的前提下，可以最多存储的元素的个数。当 nelts 增长到达 nalloc 时，如果再往此数组中存储元素，则会引发数组的扩容。数组的容量将会扩展到原有容量的 2 倍大小。实际上是分配新的一块内存，新的一块内存的大小是原有内存大小的 2 倍。原有的数据会被拷贝到新的一块内存中。 pool: 该数组用来分配内存的内存池。下面介绍 ngx_array_t 相关操作函数。 ngx_array_t *ngx_array_create(ngx_pool_t *p, ngx_uint_t n, size_t size);创建一个新的数组对象，并返回这个对象。 p: 数组分配内存使用的内存池；n: 数组的初始容量大小，即在不扩容的情况下最多可以容纳的元素个数。size: 单个元素的大小，单位是字节。 void ngx_array_destroy(ngx_array_t *a);销毁该数组对象，并释放其分配的内存回内存池。 void *ngx_array_push(ngx_array_t *a);在数组 a 上新追加一个元素，并返回指向新元素的指针。需要把返回的指针使用类型转换，转换为具体的类型，然后再给新元素本身或者是各字段（如果数组的元素是复杂类型）赋值。 void *ngx_array_push_n(ngx_array_t *a, ngx_uint_t n);在数组 a 上追加 n 个元素，并返回指向这些追加元素的首个元素的位置的指针。 static ngx_inline ngx_int_t ngx_array_init(ngx_array_t *array, ngx_pool_t *pool, ngx_uint_t n, size_t size);如果一个数组对象是被分配在堆上的，那么当调用 ngx_array_destroy 销毁以后，如果想再次使用，就可以调用此函数。如果一个数组对象是被分配在栈上的，那么就需要调用此函数，进行初始化的工作以后，才可以使用。注意事项由于使用 ngx_palloc 分配内存，数组在扩容时，旧的内存不会被释放，会造成内存的浪费。因此，最好能提前规划好数组的容量，在创建或者初始化的时候一次搞定，避免多次扩容，造成内存浪费。ngx_hash_tngx_hash_t 是 Nginx 自己的 hash 表的实现。定义和实现位于src/core/ngx_hash.h|c中。ngx_hash_t 的实现也与数据结构教科书上所描述的 hash 表的实现是大同小异。对于常用的解决冲突的方法有线性探测，二次探测和开链法等。ngx_hash_t 使用的是最常用的一种，也就是开链法，这也是 STL 中的 hash 表使用的方法。 但是 ngx_hash_t 的实现又有其几个显著的特点:ngx_hash_t 不像其他的 hash 表的实现，可以插入删除元素，它只能一次初始化，就构建起整个 hash 表以后，既不能再删除，也不能在插入元素了。ngx_hash_t 的开链并不是真的开了一个链表，实际上是开了一段连续的存储空间，几乎可以看做是一个数组。这是因为 ngx_hash_t 在初始化的时候，会经历一次预计算的过程，提前把每个桶里面会有多少元素放进去给计算出来，这样就提前知道每个桶的大小了。那么就不需要使用链表，一段连续的存储空间就足够了。这也从一定程度上节省了内存的使用。从上面的描述，我们可以看出来，这个值越大，越造成内存的浪费。就两步，首先是初始化，然后就可以在里面进行查找了。下面我们详细来看一下。ngx_hash_t 的初始化。 ngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts);首先我们来看一下初始化函数。该函数的第一个参数 hinit 是初始化的一些参数的一个集合。 names 是初始化一个 ngx_hash_t 所需要的所有 key 的一个数组。而 nelts 就是 key 的个数。下面先看一下 ngx_hash_init_t 类型，该类型提供了初始化一个 hash 表所需要的一些基本信息。 typedef struct { ngx_hash_t *hash; ngx_hash_key_pt key; ngx_uint_t max_size; ngx_uint_t bucket_size; char *name; ngx_pool_t *pool; ngx_pool_t *temp_pool; } ngx_hash_init_t;hash: 该字段如果为 NULL，那么调用完初始化函数后，该字段指向新创建出来的 hash 表。如果该字段不为 NULL，那么在初始的时候，所有的数据被插入了这个字段所指的 hash 表中。key: 指向从字符串生成 hash 值的 hash 函数。Nginx 的源代码中提供了默认的实现函数 ngx_hash_key_lc。max_size: hash 表中的桶的个数。该字段越大，元素存储时冲突的可能性越小，每个桶中存储的元素会更少，则查询起来的速度更快。当然，这个值越大，越造成内存的浪费也越大，(实际上也浪费不了多少)。:bucket_size: 每个桶的最大限制大小，单位是字节。如果在初始化一个 hash 表的时候，发现某个桶里面无法存的下所有属于该桶的元素，则 hash 表初始化失败。name: 该 hash 表的名字。pool: 该 hash 表分配内存使用的 pool。temp_pool: 该 hash 表使用的临时 pool，在初始化完成以后，该 pool 可以被释放和销毁掉。下面来看一下存储 hash 表 key 的数组的结构。 typedef struct { ngx_str_t key; ngx_uint_t key_hash; void *value; } ngx_hash_key_t;key 和 value 的含义显而易见，就不用解释了。key_hash 是对 key 使用 hash 函数计算出来的值。对这两个结构分析完成以后，我想大家应该都已经明白这个函数应该是如何使用了吧。该函数成功初始化一个 hash 表以后，返回 NGX_OK，否则返回 NGX_ERROR。 void *ngx_hash_find(ngx_h