10.5　location的快速检索

从10.2.3节中可以了解到，每一个server块可以对应着多个location块，而一个location块还可以继续嵌套多个location块。每一批location块是通过双向链表与它的父配置块（要么属于server块，要么属于location块）关联起来的。由双向链表的查询效率可以知道，当一个请求根据10.4节中描述过的散列表快速查询到server块时，必须遍历其下的所有location组成的双向链表才能找到与其URI匹配的location配置块，这也是用户无法接受的。下面看看HTTP框架又是怎样通过静态的二叉查找树来保存location的。

//cmcf就是该http块下全局的ngx_http_core_main_conf_t结构体

cmcf=ctx-＞main_conf[ngx_http_core_module.ctx_index]；

/cscfp指向保存所有ngx_http_core_srv_conf_t结构体指针的servers动态数组的第1个元素/

cscfp=cmcf-＞servers.elts；

//遍历http块下的所有server块

for（s=0；s＜cmcf-＞servers.nelts；s++）{

/clcf是server块下的ngx_http_core_loc_conf_t结构体，10.2.3节曾经介绍过它的locations成员以双向链表关联着隶属于这个server块的所有location块对应的ngx_http_core_loc_conf_t结构体/

clcf=cscfp[s]-＞ctx-＞loc_conf[ngx_http_core_module.ctx_index]；

/将ngx_http_core_loc_conf_t组成的双向链表按照location匹配字符串进行排序。注意：这个操作是递归进行的，如果某个location块下还具有其他location，那么它的locations链表也会被排序/

if（ngx_http_init_locations（cf,cscfp[s]，clcf）！=NGX_OK）{

return NGX_CONF_ERROR；

}

/根据已经按照location字符串排序过的双向链表，快速地构建静态的二叉查找树。与ngx_http_init_locations方法类似，这个操作也是递归进行的/

if（ngx_http_init_static_location_trees（cf,clcf）！=NGX_OK）{

return NGX_CONF_ERROR；

}

}

注意，这里的二叉查找树并不是第7章中介绍过的红黑树，不过，为什么不使用红黑树呢？因为location是由nginx.conf中读取到的，它是静态不变的，不存在运行过程中在树中添加或者删除location的场景，而且红黑树的查询效率也没有重新构造的静态的完全平衡二叉树高。

这棵静态的二叉平衡查找树是用ngx_http_location_tree_node_t结构体来表示的，如下所示。

typedef struct ngx_http_location_tree_node_s ngx_http_location_tree_node_t；

struct ngx_http_location_tree_node_s{

//左子树

ngx_http_location_tree_node_t*left；

//右子树

ngx_http_location_tree_node_t*right；

//无法完全匹配的location组成的树

ngx_http_location_tree_node_t*tree；

/如果location对应的URI匹配字符串属于能够完全匹配的类型，则exact指向其对应的ngx_http_core_loc_conf_t结构体，否则为NULL空指针/

ngx_http_core_loc_conf_t*exact；

/如果location对应的URI匹配字符串属于无法完全匹配的类型，则inclusive指向其对应的ngx_http_core_loc_conf_t结构体，否则为NULL空指针/

ngx_http_core_loc_conf_t*inclusive；

//自动重定向标志

u_char auto_redirect；

//name字符串的实际长度

u_char len；

//name指向location对应的URI匹配表达式

u_char name[1]；

}；

HTTP框架在ngx_http_core_module模块中定义了ngx_http_core_find_location方法，用于从静态二叉查找树中快速检索到ngx_http_core_loc_conf_t结构体，这在第11章探讨HTTP请求的处理过程时将会碰到。