static ngx_int_t
ngx_http_init_static_location_trees(ngx_conf_t *cf,
ngx_http_core_loc_conf_t *pclcf)
{
ngx_queue_t *q, *locations;
ngx_http_core_loc_conf_t *clcf;
ngx_http_location_queue_t *lq;
locations = pclcf->locations;
if (locations == NULL) {
return NGX_OK;
}
if (ngx_queue_empty(locations)) {
return NGX_OK;
}
/* 这里也是由于nested location，需要递归一下 */
for (q = ngx_queue_head(locations);
q != ngx_queue_sentinel(locations);
q = ngx_queue_next(q))
{
lq = (ngx_http_location_queue_t *) q;
clcf = lq->exact ? lq->exact : lq->inclusive;
if (ngx_http_init_static_location_trees(cf, clcf) != NGX_OK) {
return NGX_ERROR;
}
}
/* join队列中名字相同的inclusive和exact类型location，也就是如果某个exact_match的location名字和普通字符串匹配的location名字相同的话，
就将它们合到一个节点中，分别保存在节点的exact和inclusive下，这一步的目的实际是去重，为后面的建立排序树做准备 */
if (ngx_http_join_exact_locations(cf, locations) != NGX_OK) {
return NGX_ERROR;
}
/* 递归每个location节点，得到当前节点的名字为其前缀的location的列表，保存在当前节点的list字段下 */
ngx_http_create_locations_list(locations, ngx_queue_head(locations));
/* 递归建立location三叉排序树 */
pclcf->static_locations = ngx_http_create_locations_tree(cf, locations, 0);
if (pclcf->static_locations == NULL) {
return NGX_ERROR;
}
return NGX_OK;
}
经过ngx_http_init_location（）函数处理之后，locations队列已经是排好序的了，建立三叉树的过程的主要工作都在ngx_http_create_locations_list()和ngx_http_create_locations_tree()中完成，这2个 函数都是递归函数，第1个函数递归locations队列中的每个节点，得到以当前节点的名字为前缀的location，并保存在当前节点的list字段 下，例如，对下列location：
location /xyz {
}
location = /xyz {
}
location /xyza {
}
location /xyzab {
}
location /xyzb {
}
location /abc {
}
location /efg {
}
location /efgaa {
}
排序的结果为/abc /efg /efgaa =/xyz /xyz /xyza /xyzab /xyzb，去重后结果为 /abc /efg /efgaa /xyz /xyza /xyzab/xyzb，ngx_http_create_locations_list()执行后的结果为：
最后，来看下ngx_http_create_locations_tree函数：
static ngx_http_location_tree_node_t *
ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations,
size_t prefix)
{
...
/* 根节点为locations队列的中间节点 */
q = ngx_queue_middle(locations);
lq = (ngx_http_location_queue_t *) q;
len = lq->name->len - prefix;
node = ngx_palloc(cf->pool,
offsetof(ngx_http_location_tree_node_t, name) + len);
if (node == NULL) {
return NULL;
}
node->left = NULL;
node->right = NULL;
node->tree = NULL;
node->exact = lq->exact;
node->inclusive = lq->inclusive;
node->auto_redirect = (u_char) ((lq->exact && lq->exact->auto_redirect)
|| (lq->inclusive && lq->inclusive->auto_redirect));
node->len = (u_char) len;
ngx_memcpy(node->name, &lq->name->data[prefix], len);
/* 从中间节点开始断开 */
ngx_queue_split(locations, q, &tail);
if (ngx_queue_empty(locations)) {
/*
* ngx_queue_split() insures that if left part is empty,
* then right one is empty too
*/
goto inclusive;
}
/* 从locations左半部分得到左子树 */
node->left = ngx_http_create_locations_tree(cf, locations, prefix);
if (node->left == NULL) {
return NULL;
}
ngx_queue_remove(q);
if (ngx_queue_empty(&tail)) {
goto inclusive;
}
/* 从locations右半部分得到右子树 */
node->right = ngx_http_create_locations_tree(cf, &tail, prefix);
if (node->right == NULL) {
return NULL;
}
inclusive:
if (ngx_queue_empty(&lq->list)) {
return node;
}
/* 从list队列得到tree子树 */
node->tree = ngx_http_create_locations_tree(cf, &lq->list, prefix + len);
if (node->tree == NULL) {
return NULL;
}
return node;
}
location tree节点的ngx_http_location_tree_node_s结构：
struct ngx_http_location_tree_node_s {
ngx_http_location_tree_node_t *left;
ngx_http_location_tree_node_t *right;
ngx_http_location_tree_node_t *tree;
ngx_http_core_loc_conf_t *exact;
ngx_http_core_loc_conf_t *inclusive;
u_char auto_redirect;
u_char len;
u_char name[1];
};
