Nginx 基本数据结构

ash_t *hash, ngx_uint_t key, u_char *name, size_t len);在 hash 里面查找 key 对应的 value。实际上这里的 key 是对真正的 key（也就是 name）计算出的 hash 值。len 是 name 的长度。如果查找成功，则返回指向 value 的指针，否则返回 NULL。ngx_hash_wildcard_tNginx 为了处理带有通配符的域名的匹配问题，实现了 ngx_hash_wildcard_t 这样的 hash 表。他可以支持两种类型的带有通配符的域名。一种是通配符在前的，例如：\*.abc.com，也可以省略掉星号，直接写成.abc.com。这样的 key，可以匹配 www.abc.com，qqq.www.abc.com 之类的。另外一种是通配符在末尾的，例如：mail.xxx.\*，请特别注意通配符在末尾的不像位于开始的通配符可以被省略掉。这样的通配符，可以匹配 mail.xxx.com、mail.xxx.com.cn、mail.xxx.net 之类的域名。有一点必须说明，就是一个 ngx_hash_wildcard_t 类型的 hash 表只能包含通配符在前的key或者是通配符在后的key。不能同时包含两种类型的通配符的 key。ngx_hash_wildcard_t 类型变量的构建是通过函数 ngx_hash_wildcard_init 完成的，而查询是通过函数 ngx_hash_find_wc_head 或者 ngx_hash_find_wc_tail 来做的。ngx_hash_find_wc_head 查询包含通配符在前的 key 的 hash 表的，而 ngx_hash_find_wc_tail 是查询包含通配符在后的 key 的 hash 表的。下面详细说明这几个函数的用法。 ngx_int_t ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names, ngx_uint_t nelts);该函数用来构建一个可以包含通配符 key 的 hash 表。hinit: 构造一个通配符 hash 表的一些参数的一个集合。关于该参数对应的类型的说明，请参见 ngx_hash_t 类型中 ngx_hash_init 函数的说明。names: 构造此 hash 表的所有的通配符 key 的数组。特别要注意的是这里的 key 已经都是被预处理过的。例如：\*.abc.com或者.abc.com被预处理完成以后，变成了com.abc.。而mail.xxx.\*则被预处理为mail.xxx.。为什么会被处理这样？这里不得不简单地描述一下通配符 hash 表的实现原理。当构造此类型的 hash 表的时候，实际上是构造了一个 hash 表的一个“链表”，是通过 hash 表中的 key “链接”起来的。比如：对于\*.abc.com将会构造出 2 个 hash 表，第一个 hash 表中有一个 key 为 com 的表项，该表项的 value 包含有指向第二个 hash 表的指针，而第二个 hash 表中有一个表项 abc，该表项的 value 包含有指向\*.abc.com对应的 value 的指针。那么查询的时候，比如查询 www.abc.com 的时候，先查 com，通过查 com 可以找到第二级的 hash 表，在第二级 hash 表中，再查找 abc，依次类推，直到在某一级的 hash 表中查到的表项对应的 value 对应一个真正的值而非一个指向下一级 hash 表的指针的时候，查询过程结束。这里有一点需要特别注意的，就是 names 数组中元素的 value 值低两位 bit 必须为 0（有特殊用途）。如果不满足这个条件，这个 hash 表查询不出正确结果。nelts: names 数组元素的个数。该函数执行成功返回 NGX_OK，否则 NGX_ERROR。 void *ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len);该函数查询包含通配符在前的 key 的 hash 表的。hwc: hash 表对象的指针。name: 需要查询的域名，例如: www.abc.com。len: name 的长度。该函数返回匹配的通配符对应 value。如果没有查到，返回 NULL。 void *ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len);该函数查询包含通配符在末尾的 key 的 hash 表的。参数及返回值请参加上个函数的说明。ngx_hash_combined_t组合类型 hash 表，该 hash 表的定义如下： typedef struct { ngx_hash_t hash; ngx_hash_wildcard_t *wc_head; ngx_hash_wildcard_t *wc_tail; } ngx_hash_combined_t;从其定义显见，该类型实际上包含了三个 hash 表，一个普通 hash 表，一个包含前向通配符的 hash 表和一个包含后向通配符的 hash 表。Nginx 提供该类型的作用，在于提供一个方便的容器包含三个类型的 hash 表，当有包含通配符的和不包含通配符的一组 key 构建 hash 表以后，以一种方便的方式来查询，你不需要再考虑一个 key 到底是应该到哪个类型的 hash 表里去查了。构造这样一组合 hash 表的时候，首先定义一个该类型的变量，再分别构造其包含的三个子 hash 表即可。对于该类型 hash 表的查询，Nginx 提供了一个方便的函数 ngx_hash_find_combined。 void *ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key, u_char *name, size_t len);该函数在此组合 hash 表中，依次查询其三个子 hash 表，看是否匹配，一旦找到，立即返回查找结果，也就是说如果有多个可能匹配，则只返回第一个匹配的结果。hash: 此组合 hash 表对象。key: 根据 name 计算出的 hash 值。name: key 的具体内容。len: name 的长度。返回查询的结果，未查到则返回 NULL。ngx_hash_keys_arrays_t大家看到在构建一个 ngx_hash_wildcard_t 的时候，需要对通配符的哪些 key 进行预处理。这个处理起来比较麻烦。而当有一组 key，这些里面既有无通配符的 key，也有包含通配符的 key 的时候。我们就需要构建三个 hash 表，一个包含普通的 key 的 hash 表，一个包含前向通配符的 hash 表，一个包含后向通配符的 hash 表（或者也可以把这三个 hash 表组合成一个 ngx_hash_combined_t）。在这种情况下，为了让大家方便的构造这些 hash 表，Nginx 提供给了此辅助类型。该类型以及相关的操作函数也定义在src/core/ngx_hash.h|c里。我们先来看一下该类型的定义。 typedef struct { ngx_uint_t hsize; ngx_pool_t *pool; ngx_pool_t *temp_pool; ngx_array_t keys; ngx_array_t *keys_hash; ngx_array_t dns_wc_head; ngx_array_t *dns_wc_head_hash; ngx_array_t dns_wc_tail; ngx_array_t *dns_wc_tail_hash; } ngx_hash_keys_arrays_t;hsize: 将要构建的 hash 表的桶的个数。对于使用这个结构中