我的书签
添加书签
移除书签7.7.2 支持通配符的散列表
如果散列表元素的关键字是URI域名，Nginx设计了支持简单通配符的散列表ngx_hash_combined_t，那么它可以支持简单的前置通配符或者后置通配符。
1.原理
所谓支持通配符的散列表，就是把基本散列表中元素的关键字，用去除通配符以后的字符作为关键字加入，原理其实很简单。例如，对于关键字为"www.test."这样带通配符的情况，直接建立一个专用的后置通配符散列表，存储元素的关键字为www.test。这样，如果要检索www.test.cn是否匹配www.test.，可用Nginx提供的专用方法ngx_hash_find_wc_tail检索，ngx_hash_find_wc_tail方法会把要查询的www.test.cn转化为www.test字符串再开始查询。
同样，对于关键字为".test.com"这样带前置通配符的情况，也直接建立了一个专用的前置通配符散列表，存储元素的关键字为com.test.。如果我们要检索smtp.test.com是否匹配.test.com，可用Nginx提供的专用方法ngx_hash_find_wc_head检索，ngx_hash_find_wc_head方法会把要查询的smtp.test.com转化为com.test.字符串再开始查询（如图7-11所示）。
图 7-11 ngx_hash_wildcard_t基本通配符散列表
Nginx封装了ngx_hash_wildcard_t结构体，专用于表示前置或者后置通配符的散列表。
typedef struct{
//基本散列表
ngx_hash_t hash；
/当使用这个ngx_hash_wildcard_t通配符散列表作为某容器的元素时，可以使用这个value指针指向用户数据/
void*value；
}ngx_hash_wildcard_t；
实际上，ngx_hash_wildcard_t只是对ngx_hash_t进行了简单的封装，所加的value指针其用途也是多样化的。ngx_hash_wildcard_t同时提供了两种方法，分别用于查询前置或者后置通配符的元素，见表7-9。
下面回顾一下Nginx对于server_name主机名通配符的支持规则。
❑首先，选择所有字符串完全匹配的server_name，如www.testweb.com。
❑其次，选择通配符在前面的server_name，如*.testweb.com。
❑再次，选择通配符在后面的server_name，如www.testweb.*。
实际上，上面介绍的这个规则就是Nginx实现的ngx_hash_combined_t通配符散列表的规则。下面先来看一下ngx_hash_combined_t的结构，代码如下。
typedef struct{
//用于精确匹配的基本散列表
ngx_hash_t hash；
//用于查询前置通配符的散列表
ngx_hash_wildcard_t*wc_head；
//用于查询后置通配符的散列表
ngx_hash_wildcard_t*wc_tail；
}ngx_hash_combined_t；
如图7-12所示，ngx_hash_combined_t是由3个散列表所组成：第1个散列表hash是普通的基本散列表，第2个散列表wc_head所包含的都是带前置通配符的元素，第3个散列表wc_tail所包含的都是带后置通配符的元素。
注意 前置通配符散列表中元素的关键字，在把*通配符去掉后，会按照“.”符号分隔，并以倒序的方式作为关键字来存储元素。相应的，在查询元素时也是做相同处理。
在查询元素时，可以使用ngx_hash_combined_t提供的方法ngx_hash_find_combined，下面先来看看它的定义（它的参数、返回值含义与ngx_hash_find_wc_head或者ngx_hash_find_wc_tail方法相同）。
图 7-12 ngx_hash_combined_t通配符散列表的结构示意图
voidngx_hash_find_combined（ngx_hash_combined_thash,ngx_uint_t key,u_char*name,size_t len）；
在实际向ngx_hash_combined_t通配符散列表查询元素时，ngx_hash_find_combined方法的活动图如图7-13所示，这是有严格顺序的，即当1个查询关键字同时匹配3个散列表时，一定是返回普通的完全匹配散列表的相应元素。
图 7-13 通配符散列表ngx_hash_find_combined方法查询元素的活动图
2.如何初始化
上文中对于普通的散列表和通配符散列表的原理和查询方法做了详细的解释，实际上，Nginx也封装了完善的初始化方法，以用于这些散列表，并且Nginx还具备在初始化时添加通配符元素的能力。鉴于此，如果功能较多，初始化方法的使用就会有些复杂。下面介绍一下初始化方法的使用。
Nginx专门提供了ngx_hash_init_t结构体用于初始化散列表，代码如下。
typedef struct{
//指向普通的完全匹配散列表
ngx_hash_t*hash；
//用于初始化预添加元素的散列方法
ngx_hash_key_pt key；
//散列表中槽的最大数目
ngx_uint_t max_size；
//散列表中一个槽的空间大小，它限制了每个散列表元素关键字的最大长度
ngx_uint_t bucket_size；
//散列表的名称
char*name；
/内存池，它分配散列表（最多3个，包括1个普通散列表、1个前置通配符散列表、1个后置通配符散列表）中的所有槽/
ngx_pool_t*pool；
/临时内存池，它仅存在于初始化散列表之前。它主要用于分配一些临时的动态数组，带通配符的元素在初始化时需要用到这些数组/
ngx_pool_t*temp_pool；
}ngx_hash_init_t；
ngx_hash_init_t结构体的用途只在于初始化散列表，到底初始化散列表时会预分配多少个槽呢？这并不完全由max_size成员决定的，而是由在做初始化准备时预先加入到散列表的所有元素决定的，包括这些元素的总数、每个元素关键字的长度等，还包括操作系统一个页面的大小。这个算法较复杂，可以在ngx_hash_init_t函数中得到。我们在使用它时只需要了解在初始化后每个ngx_hash_t结构体中的size成员不由ngx_hash_init_t完全决定即可。图7-14显示了ngx_hash_init_t结构体及其支持的方法。
图 7-14 ngx_hash_init_t的结构及其提供的方法
ngx_hash_init_t的这两个方法负责将ngx_hash_keys_arrays_t中的相应元素初始化到散列表中，表7-10描述了这两个初始化方法的用法。
表7-10的两个方法都用到了ngx_hash_key_t结构，下面简单地介绍一下它的成员。实际上，如果只是使用散列表，完全可以不用关心ngx_hash_key_t的结构，但为了更深入地理解和应用还是简要介绍一下它。
typedef struct{
//元素关键字
ngx_str_t key；
//由散列方法算出来的关键码
ngx_uint_t key_hash；
//指向实际的用户数据
void*value；
}ngx_hash_key_t；
ngx_hash_keys_arrays_t对应的ngx_hash_add_key方法负责构造ngx_hash_key_t结构。下面来看一下ngx_hash_keys_arrays_t结构体，它不负责构造散列表，然而它却是使用ngx_hash_init或者ngx_hash_wildcard_init方法的前提条件，换句话说，如果先构造好了ngx_hash_keys_arrays_t结构体，就可以非常简单地调用ngx_hash_init或者ngx_hash_wildcard_init方法来创建支持通配符的散列表了。
typedef struct{
/下面的keys_hash、dns_wc_head_hash、dns_wc_tail_hash都是简易散列表，而hsize指明了散列表的槽个数，其简易散列方法也需要对hsize求余/
ngx_uint_t hsize；
/内存池，用于分配永久性内存，到目前的Nginx版本为止，该pool成员没有任何意义/
ngx_pool_t*pool；
//临时内存池，下面的动态数组需要的内存都由temp_pool内存池分配
ngx_pool_t*temp_pool；
//用动态数组以ngx_hash_key_t结构体保存着不含有通配符关键字的元素
ngx_array_t keys；
/一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t动态数组。在用户添加的元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加到ngx_array_t动态数组中。这里所有的用户元素的关键字都不可以带通配符，表示精确匹配/
ngx_array_t*keys_hash；
/用动态数组以ngx_hash_key_t结构体保存着含有前置通配符关键字的元素生成的中间关键字/
ngx_array_t dns_wc_head；
/一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t动态数组。在用户添加元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加到ngx_array_t动态数组中。这里所有的用户元素的关键字都带前置通配符/
ngx_array_t*dns_wc_head_hash；
/用动态数组以ngx_hash_key_t结构体保存着含有后置通配符关键字的元素生成的中间关键字/
ngx_array_t dns_wc_tail；
/一个极其简易的散列表，它以数组的形式保存着hsize个元素，每个元素都是ngx_array_t动态数组。在用户添加元素过程中，会根据关键码将用户的ngx_str_t类型的关键字添加到ngx_array_t动态数组中。这里所有的用户元素的关键字都带后置通配符/
ngx_array_t*dns_wc_tail_hash；
}ngx_hash_keys_arrays_t；
如图7-15所示，ngx_hash_keys_arrays_t中的3个动态数组容器keys、dns_wc_head、dns_wc_tail会以ngx_hash_key_t结构体作为元素类型，分别保存完全匹配关键字、带前置通配符的关键字、带后置通配符的关键字。同时，ngx_hash_keys_arrays_t建立了3个简易的散列表keys_hash、dns_wc_head_hash、dns_wc_tail_hash，这3个散列表用于快速向上述3个动态数组容器中插入元素。
为什么要设立这3个简易散列表呢？如果没有这3个散列表，在向keys、dns_wc_head、dns_wc_tail动态数组添加元素时，为了避免出现相同关键字的元素，每添加一个关键字元素都需要遍历整个数组。有了keys_hash、dns_wc_head_hash、dns_wc_tail_hash这3个简易散列表后，每向keys、dns_wc_head、dns_wc_tail动态数组添加1个元素时，就用这个元素的关键字计算出散列码，然后按照散列码在keys_hash、dns_wc_head_hash、dns_wc_tail_hash散列表中的相应位置建立ngx_array_t动态数组，动态数组中的每个元素是ngx_str_t，它指向关键字字符串。这样，再次添加同名关键字时，就可以由散列码立刻获得曾经添加的关键字，以此来判定是否合法或者进行元素合并操作。
图 7-15 ngx_hash_keys_arrays_t中动态数组、散列表成员的简易示意图
ngx_hash_keys_arrays_t之所以设计得比较复杂，是为了让keys、dns_wc_head、dns_wc_tail这3个动态数组中存放的都是有效的元素。表7-11介绍了ngx_hash_keys_arrays_t提供的两个方法。
ngx_hash_keys_array_init方法的type参数将会决定ngx_hash_keys_arrays_t中3个简易散列表的大小。当type为NGX_HASH_SMALL时，这3个散列表中槽的数目为107个；当type为NGX_HASH_LARGE时，这3个散列表中槽的数目为10007个。
在使用ngx_hash_keys_array_init初始化ngx_hash_keys_arrays_t结构体后，就可以调用ngx_hash_add_key方法向其加入散列表元素了。当添加元素成功后，再调用ngx_hash_init_t提供的两个初始化方法来创建散列表，这样得到的散列表就是完全可用的容器了。
