locations tree

5 files changed, 745 insertions, 384 deletions

diff --git a/src/http/modules/ngx_http_rewrite_module.c b/src/http/modules/ngx_http_rewrite_module.c
index 341e05424..9c3d3fb28 100644
--- a/src/http/modules/ngx_http_rewrite_module.c
+++ b/src/http/modules/ngx_http_rewrite_module.c
@@ -524,7 +524,7 @@ ngx_http_rewrite_if(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     ngx_conf_t                    save;
     ngx_http_module_t            *module;
     ngx_http_conf_ctx_t          *ctx, *pctx;
-    ngx_http_core_loc_conf_t     *clcf, *pclcf, **clcfp;
+    ngx_http_core_loc_conf_t     *clcf, *pclcf;
     ngx_http_script_if_code_t    *if_code;
     ngx_http_rewrite_loc_conf_t  *nlcf;
 
@@ -567,21 +567,10 @@ ngx_http_rewrite_if(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     clcf->name = pclcf->name;
     clcf->noname = 1;
 
-    if (pclcf->locations == NULL) {
-        pclcf->locations = ngx_array_create(cf->pool, 2, sizeof(void *));
-        if (pclcf->locations == NULL) {
-            return NGX_CONF_ERROR;
-        }
-    }
-
-    clcfp = ngx_array_push(pclcf->locations);
-    if (clcfp == NULL) {
+    if (ngx_http_add_location(cf, &pclcf->locations, clcf) != NGX_OK) {
         return NGX_CONF_ERROR;
     }
 
-    *clcfp = clcf;
-
-
     if (ngx_http_rewrite_if_condition(cf, lcf) != NGX_CONF_OK) {
         return NGX_CONF_ERROR;
     }
diff --git a/src/http/ngx_http.c b/src/http/ngx_http.c
index c708ddf03..4e5500fb4 100644
--- a/src/http/ngx_http.c
+++ b/src/http/ngx_http.c
@@ -27,8 +27,21 @@ static ngx_int_t ngx_http_add_names(ngx_conf_t *cf,
     ngx_http_core_srv_conf_t *cscf, ngx_http_conf_in_addr_t *in_addr);
 
 static char *ngx_http_merge_locations(ngx_conf_t *cf,
-    ngx_array_t *locations, void **loc_conf, ngx_http_module_t *module,
+    ngx_queue_t *locations, void **loc_conf, ngx_http_module_t *module,
     ngx_uint_t ctx_index);
+static ngx_int_t ngx_http_init_locations(ngx_conf_t *cf,
+    ngx_http_core_srv_conf_t *cscf, ngx_http_core_loc_conf_t *pclcf);
+static ngx_int_t ngx_http_init_static_location_trees(ngx_conf_t *cf,
+    ngx_http_core_loc_conf_t *pclcf);
+static ngx_int_t ngx_http_cmp_locations(const ngx_queue_t *one,
+    const ngx_queue_t *two);
+static ngx_int_t ngx_http_join_exact_locations(ngx_conf_t *cf,
+    ngx_queue_t *locations);
+static void ngx_http_create_locations_list(ngx_queue_t *locations,
+    ngx_queue_t *q);
+static ngx_http_location_tree_node_t *
+    ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations,
+    size_t prefix);
 
 static ngx_int_t ngx_http_optimize_servers(ngx_conf_t *cf,
     ngx_http_core_main_conf_t *cmcf, ngx_array_t *in_ports);
@@ -91,6 +104,7 @@ ngx_http_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     ngx_array_t                  in_ports;
     ngx_http_module_t           *module;
     ngx_http_conf_ctx_t         *ctx;
+    ngx_http_core_loc_conf_t    *clcf;
     ngx_http_core_srv_conf_t   **cscfp;
     ngx_http_core_main_conf_t   *cmcf;
 
@@ -206,8 +220,7 @@ ngx_http_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     rv = ngx_conf_parse(cf, NULL);
 
     if (rv != NGX_CONF_OK) {
-        *cf = pcf;
-        return rv;
+        goto failed;
     }
 
     /*
@@ -231,8 +244,7 @@ ngx_http_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
         if (module->init_main_conf) {
             rv = module->init_main_conf(cf, ctx->main_conf[mi]);
             if (rv != NGX_CONF_OK) {
-                *cf = pcf;
-                return rv;
+                goto failed;
             }
         }
 
@@ -241,12 +253,10 @@ ngx_http_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
             /* merge the server{}s' srv_conf's */
 
             if (module->merge_srv_conf) {
-                rv = module->merge_srv_conf(cf,
-                                            ctx->srv_conf[mi],
+                rv = module->merge_srv_conf(cf, ctx->srv_conf[mi],
                                             cscfp[s]->ctx->srv_conf[mi]);
                 if (rv != NGX_CONF_OK) {
-                    *cf = pcf;
-                    return rv;
+                    goto failed;
                 }
             }
 
@@ -254,28 +264,43 @@ ngx_http_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
 
                 /* merge the server{}'s loc_conf */
 
-                rv = module->merge_loc_conf(cf,
-                                            ctx->loc_conf[mi],
+                rv = module->merge_loc_conf(cf, ctx->loc_conf[mi],
                                             cscfp[s]->ctx->loc_conf[mi]);
                 if (rv != NGX_CONF_OK) {
-                    *cf = pcf;
-                    return rv;
+                    goto failed;
                 }
 
                 /* merge the locations{}' loc_conf's */
 
-                rv = ngx_http_merge_locations(cf, &cscfp[s]->locations,
+                clcf = cscfp[s]->ctx->loc_conf[ngx_http_core_module.ctx_index];
+
+                rv = ngx_http_merge_locations(cf, clcf->locations,
                                               cscfp[s]->ctx->loc_conf,
                                               module, mi);
                 if (rv != NGX_CONF_OK) {
-                    *cf = pcf;
-                    return rv;
+                    goto failed;
                 }
             }
         }
     }
 
 
+    /* create location trees */
+
+    for (s = 0; s < cmcf->servers.nelts; s++) {
+
+        clcf = cscfp[s]->ctx->loc_conf[ngx_http_core_module.ctx_index];
+
+        if (ngx_http_init_locations(cf, cscfp[s], clcf) != NGX_OK) {
+            return NGX_CONF_ERROR;
+        }
+
+        if (ngx_http_init_static_location_trees(cf, clcf) != NGX_OK) {
+            return NGX_CONF_ERROR;
+        }
+    }
+
+
     if (ngx_http_init_phases(cf, cmcf) != NGX_OK) {
         return NGX_CONF_ERROR;
     }
@@ -337,6 +362,12 @@ ngx_http_block(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     }
 
     return NGX_CONF_OK;
+
+failed:
+
+    *cf = pcf;
+
+    return rv;
 }
 
 
@@ -544,6 +575,511 @@ ngx_http_init_phase_handlers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf)
 }
 
 
+static char *
+ngx_http_merge_locations(ngx_conf_t *cf, ngx_queue_t *locations,
+    void **loc_conf, ngx_http_module_t *module, ngx_uint_t ctx_index)
+{
+    char                       *rv;
+    ngx_queue_t                *q;
+    ngx_http_core_loc_conf_t   *clcf;
+    ngx_http_location_queue_t  *lq;
+
+    if (locations == NULL) {
+        return NGX_CONF_OK;
+    }
+
+    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;
+
+        rv = module->merge_loc_conf(cf, loc_conf[ctx_index],
+                                    clcf->loc_conf[ctx_index]);
+        if (rv != NGX_CONF_OK) {
+            return rv;
+        }
+
+        rv = ngx_http_merge_locations(cf, clcf->locations, clcf->loc_conf,
+                                      module, ctx_index);
+        if (rv != NGX_CONF_OK) {
+            return rv;
+        }
+    }
+
+    return NGX_CONF_OK;
+}
+
+
+static ngx_int_t
+ngx_http_init_locations(ngx_conf_t *cf, ngx_http_core_srv_conf_t *cscf,
+    ngx_http_core_loc_conf_t *pclcf)
+{
+    ngx_uint_t                   n;
+    ngx_queue_t                 *q, *locations, *named, tail;
+    ngx_http_core_loc_conf_t    *clcf;
+    ngx_http_location_queue_t   *lq;
+    ngx_http_core_loc_conf_t   **clcfp;
+#if (NGX_PCRE)
+    ngx_uint_t                   r;
+    ngx_queue_t                 *regex;
+#endif
+
+    locations = pclcf->locations;
+
+    if (locations == NULL) {
+        return NGX_OK;
+    }
+
+    ngx_queue_sort(locations, ngx_http_cmp_locations);
+
+    named = NULL;
+    n = 0;
+#if (NGX_PCRE)
+    regex = NULL;
+    r = 0;
+#endif
+
+    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_locations(cf, NULL, clcf) != NGX_OK) {
+            return NGX_ERROR;
+        }
+
+#if (NGX_PCRE)
+
+        if (clcf->regex) {
+            r++;
+
+            if (regex == NULL) {
+                regex = q;
+            }
+
+            continue;
+        }
+
+#endif
+
+        if (clcf->named) {
+            n++;
+
+            if (named == NULL) {
+                named = q;
+            }
+
+            continue;
+        }
+
+        if (clcf->noname) {
+            break;
+        }
+    }
+
+    if (q != ngx_queue_sentinel(locations)) {
+        ngx_queue_split(locations, q, &tail);
+    }
+
+    if (named) {
+        clcfp = ngx_palloc(cf->pool,
+                           (n + 1) * sizeof(ngx_http_core_loc_conf_t **));
+        if (clcfp == NULL) {
+            return NGX_ERROR;
+        }
+
+        cscf->named_locations = clcfp;
+
+        for (q = named;
+             q != ngx_queue_sentinel(locations);
+             q = ngx_queue_next(q))
+        {
+            lq = (ngx_http_location_queue_t *) q;
+
+            *(clcfp++) = lq->exact;
+        }
+
+        *clcfp = NULL;
+
+        ngx_queue_split(locations, named, &tail);
+    }
+
+#if (NGX_PCRE)
+
+    if (regex) {
+
+        clcfp = ngx_palloc(cf->pool,
+                           (r + 1) * sizeof(ngx_http_core_loc_conf_t **));
+        if (clcfp == NULL) {
+            return NGX_ERROR;
+        }
+
+        pclcf->regex_locations = clcfp;
+
+        for (q = regex;
+             q != ngx_queue_sentinel(locations);
+             q = ngx_queue_next(q))
+        {
+            lq = (ngx_http_location_queue_t *) q;
+
+            *(clcfp++) = lq->exact;
+        }
+
+        *clcfp = NULL;
+
+        ngx_queue_split(locations, regex, &tail);
+    }
+
+#endif
+
+    return NGX_OK;
+}
+
+
+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;
+    }
+
+    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;
+        }
+    }
+
+    if (ngx_http_join_exact_locations(cf, locations) != NGX_OK) {
+        return NGX_ERROR;
+    }
+
+    ngx_http_create_locations_list(locations, ngx_queue_head(locations));
+
+    pclcf->static_locations = ngx_http_create_locations_tree(cf, locations, 0);
+    if (pclcf->static_locations == NULL) {
+        return NGX_ERROR;
+    }
+
+    return NGX_OK;
+}
+
+
+ngx_int_t
+ngx_http_add_location(ngx_conf_t *cf, ngx_queue_t **locations,
+    ngx_http_core_loc_conf_t *clcf)
+{
+    ngx_http_location_queue_t  *lq;
+
+    if (*locations == NULL) {
+        *locations = ngx_palloc(cf->temp_pool,
+                                sizeof(ngx_http_location_queue_t));
+        if (*locations == NULL) {
+            return NGX_ERROR;
+        }
+
+        ngx_queue_init(*locations);
+    }
+
+    lq = ngx_palloc(cf->temp_pool, sizeof(ngx_http_location_queue_t));
+    if (lq == NULL) {
+        return NGX_ERROR;
+    }
+
+    if (clcf->exact_match
+#if (NGX_PCRE)
+        || clcf->regex
+#endif
+        || clcf->named || clcf->noname)
+    {
+        lq->exact = clcf;
+        lq->inclusive = NULL;
+
+    } else {
+        lq->exact = NULL;
+        lq->inclusive = clcf;
+    }
+
+    lq->name = &clcf->name;
+    lq->file_name = cf->conf_file->file.name.data;
+    lq->line = cf->conf_file->line;
+
+    ngx_queue_init(&lq->list);
+
+    ngx_queue_insert_tail(*locations, &lq->queue);
+
+    return NGX_OK;
+}
+
+
+static ngx_int_t
+ngx_http_cmp_locations(const ngx_queue_t *one, const ngx_queue_t *two)
+{
+    ngx_int_t                   rc;
+    ngx_http_core_loc_conf_t   *first, *second;
+    ngx_http_location_queue_t  *lq1, *lq2;
+
+    lq1 = (ngx_http_location_queue_t *) one;
+    lq2 = (ngx_http_location_queue_t *) two;
+
+    first = lq1->exact ? lq1->exact : lq1->inclusive;
+    second = lq2->exact ? lq2->exact : lq2->inclusive;
+
+    if (first->noname && !second->noname) {
+        /* shift no named locations to the end */
+        return 1;
+    }
+
+    if (!first->noname && second->noname) {
+        /* shift no named locations to the end */
+        return -1;
+    }
+
+    if (first->noname || second->noname) {
+        /* do not sort no named locations */
+        return 0;
+    }
+
+    if (first->named && !second->named) {
+        /* shift named locations to the end */
+        return 1;
+    }
+
+    if (!first->named && second->named) {
+        /* shift named locations to the end */
+        return -1;
+    }
+
+    if (first->named && second->named) {
+        return ngx_strcmp(first->name.data, second->name.data);
+    }
+
+#if (NGX_PCRE)
+
+    if (first->regex && !second->regex) {
+        /* shift the regex matches to the end */
+        return 1;
+    }
+
+    if (!first->regex && second->regex) {
+        /* shift the regex matches to the end */
+        return -1;
+    }
+
+    if (first->regex || second->regex) {
+        /* do not sort the regex matches */
+        return 0;
+    }
+
+#endif
+
+    rc = ngx_strcmp(first->name.data, second->name.data);
+
+    if (rc == 0 && !first->exact_match && second->exact_match) {
+        /* an exact match must be before the same inclusive one */
+        return 1;
+    }
+
+    return rc;
+}
+
+
+static ngx_int_t
+ngx_http_join_exact_locations(ngx_conf_t *cf, ngx_queue_t *locations)
+{
+    ngx_queue_t                *q, *x;
+    ngx_http_location_queue_t  *lq, *lx;
+
+    q = ngx_queue_head(locations);
+
+    while (q != ngx_queue_last(locations)) {
+
+        x = ngx_queue_next(q);
+
+        lq = (ngx_http_location_queue_t *) q;
+        lx = (ngx_http_location_queue_t *) x;
+
+        if (ngx_strcmp(lq->name->data, lx->name->data) == 0) {
+
+            if ((lq->exact && lx->exact) || (lq->inclusive && lx->inclusive)) {
+                ngx_log_error(NGX_LOG_EMERG, cf->log, 0,
+                              "duplicate location \"%V\" in %s:%ui",
+                              lx->name, lx->file_name, lx->line);
+
+                return NGX_ERROR;
+            }
+
+            lq->inclusive = lx->inclusive;
+
+            ngx_queue_remove(x);
+
+            continue;
+        }
+
+        q = ngx_queue_next(q);
+    }
+
+    return NGX_OK;
+}
+
+
+static void
+ngx_http_create_locations_list(ngx_queue_t *locations, ngx_queue_t *q)
+{
+    u_char                     *name;
+    size_t                      len;
+    ngx_queue_t                *x, tail;
+    ngx_http_location_queue_t  *lq, *lx;
+
+    if (q == ngx_queue_last(locations)) {
+        return;
+    }
+
+    lq = (ngx_http_location_queue_t *) q;
+
+    if (lq->inclusive == NULL) {
+        ngx_http_create_locations_list(locations, ngx_queue_next(q));
+        return;
+    }
+
+    len = lq->name->len;
+    name = lq->name->data;
+
+    for (x = ngx_queue_next(q);
+         x != ngx_queue_sentinel(locations);
+         x = ngx_queue_next(x))
+    {
+        lx = (ngx_http_location_queue_t *) x;
+
+        if (len > lx->name->len
+            || (ngx_strncmp(name, lx->name->data, len) != 0))
+        {
+            break;
+        }
+    }
+
+    q = ngx_queue_next(q);
+
+    if (q == x) {
+        ngx_http_create_locations_list(locations, x);
+        return;
+    }
+
+    ngx_queue_split(locations, q, &tail);
+    ngx_queue_add(&lq->list, &tail);
+
+    if (x == ngx_queue_sentinel(locations)) {
+        ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list));
+        return;
+    }
+
+    ngx_queue_split(&lq->list, x, &tail);
+    ngx_queue_add(locations, &tail);
+
+    ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list));
+
+    ngx_http_create_locations_list(locations, x);
+}
+
+
+/*
+ * to keep cache locality for left leaf nodes, allocate nodes in following
+ * order: node, left subtree, right subtree, inclusive subtree
+ */
+
+static ngx_http_location_tree_node_t *
+ngx_http_create_locations_tree(ngx_conf_t *cf, ngx_queue_t *locations,
+    size_t prefix)
+{
+    size_t                          len;
+    ngx_queue_t                    *q, tail;
+    ngx_http_location_queue_t      *lq;
+    ngx_http_location_tree_node_t  *node;
+
+    q = ngx_queue_middle(locations);
+
+    lq = (ngx_http_location_queue_t *) q;
+    len = lq->name->len - prefix;
+
+    node = ngx_pcalloc(cf->pool,
+                       offsetof(ngx_http_location_tree_node_t, name) + len);
+    if (node == NULL) {
+        return 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;
+    }
+
+    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;
+    }
+
+    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;
+    }
+
+    node->tree = ngx_http_create_locations_tree(cf, &lq->list, prefix + len);
+    if (node->tree == NULL) {
+        return NULL;
+    }
+
+    return node;
+}
+
+
 static ngx_int_t
 ngx_http_init_server_lists(ngx_conf_t *cf, ngx_array_t *servers,
     ngx_array_t *in_ports)
@@ -756,38 +1292,6 @@ ngx_http_add_names(ngx_conf_t *cf, ngx_http_core_srv_conf_t *cscf,
 }
 
 
-static char *
-ngx_http_merge_locations(ngx_conf_t *cf, ngx_array_t *locations,
-    void **loc_conf, ngx_http_module_t *module, ngx_uint_t ctx_index)
-{
-    char                       *rv;
-    ngx_uint_t                  i;
-    ngx_http_core_loc_conf_t  **clcfp;
-
-    clcfp = locations->elts;
-
-    for (i = 0; i < locations->nelts; i++) {
-        rv = module->merge_loc_conf(cf, loc_conf[ctx_index],
-                                    clcfp[i]->loc_conf[ctx_index]);
-        if (rv != NGX_CONF_OK) {
-            return rv;
-        }
-
-        if (clcfp[i]->locations == NULL) {
-            continue;
-        }
-
-        rv = ngx_http_merge_locations(cf, clcfp[i]->locations,
-                                      clcfp[i]->loc_conf, module, ctx_index);
-        if (rv != NGX_CONF_OK) {
-            return rv;
-        }
-    }
-
-    return NGX_CONF_OK;
-}
-
-
 static ngx_int_t
 ngx_http_optimize_servers(ngx_conf_t *cf, ngx_http_core_main_conf_t *cmcf,
     ngx_array_t *in_ports)
diff --git a/src/http/ngx_http.h b/src/http/ngx_http.h
index 96de02adc..fe2b7cc6c 100644
--- a/src/http/ngx_http.h
+++ b/src/http/ngx_http.h
@@ -57,6 +57,10 @@ struct ngx_http_log_ctx_s {
 #define ngx_http_set_ctx(r, c, module)      r->ctx[module.ctx_index] = c;
 
 
+ngx_int_t ngx_http_add_location(ngx_conf_t *cf, ngx_queue_t **locations,
+    ngx_http_core_loc_conf_t *clcf);
+
+
 void ngx_http_init_connection(ngx_connection_t *c);
 
 #ifdef SSL_CTRL_SET_TLSEXT_HOSTNAME
diff --git a/src/http/ngx_http_core_module.c b/src/http/ngx_http_core_module.c
index f9b11b930..e0f1e1f90 100644
--- a/src/http/ngx_http_core_module.c
+++ b/src/http/ngx_http_core_module.c
@@ -17,19 +17,14 @@ typedef struct {
 } ngx_http_method_name_t;
 
 
-#define NGX_HTTP_LOCATION_EXACT           1
-#define NGX_HTTP_LOCATION_AUTO_REDIRECT   2
-#define NGX_HTTP_LOCATION_NOREGEX         3
-#define NGX_HTTP_LOCATION_REGEX           4
-
-
 #define NGX_HTTP_REQUEST_BODY_FILE_OFF    0
 #define NGX_HTTP_REQUEST_BODY_FILE_ON     1
 #define NGX_HTTP_REQUEST_BODY_FILE_CLEAN  2
 
 
-static ngx_int_t ngx_http_core_find_location(ngx_http_request_t *r,
-    ngx_array_t *locations, ngx_uint_t regex_start, size_t len);
+static ngx_int_t ngx_http_core_find_location(ngx_http_request_t *r);
+static ngx_int_t ngx_http_core_find_static_location(ngx_http_request_t *r,
+    ngx_http_location_tree_node_t *node);
 
 static ngx_int_t ngx_http_core_preconfiguration(ngx_conf_t *cf);
 static void *ngx_http_core_create_main_conf(ngx_conf_t *cf);
@@ -45,8 +40,6 @@ static char *ngx_http_core_server(ngx_conf_t *cf, ngx_command_t *cmd,
     void *dummy);
 static char *ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd,
     void *dummy);
-static ngx_int_t ngx_http_core_cmp_locations(const void *first,
-    const void *second);
 
 static char *ngx_http_core_types(ngx_conf_t *cf, ngx_command_t *cmd,
     void *conf);
@@ -787,14 +780,11 @@ ngx_http_core_find_config_phase(ngx_http_request_t *r,
     size_t                     len;
     ngx_int_t                  rc;
     ngx_http_core_loc_conf_t  *clcf;
-    ngx_http_core_srv_conf_t  *cscf;
 
     r->content_handler = NULL;
     r->uri_changed = 0;
 
-    cscf = ngx_http_get_module_srv_conf(r, ngx_http_core_module);
-
-    rc = ngx_http_core_find_location(r, &cscf->locations, cscf->regex_start, 0);
+    rc = ngx_http_core_find_location(r);
 
     if (rc == NGX_HTTP_INTERNAL_SERVER_ERROR) {
         ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
@@ -832,8 +822,7 @@ ngx_http_core_find_config_phase(ngx_http_request_t *r,
         return NGX_OK;
     }
 
-
-    if (rc == NGX_HTTP_LOCATION_AUTO_REDIRECT) {
+    if (rc == NGX_DONE) {
         r->headers_out.location = ngx_list_push(&r->headers_out.headers);
         if (r->headers_out.location == NULL) {
             ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
@@ -1112,143 +1101,148 @@ ngx_http_update_location_config(ngx_http_request_t *r)
 
 
 static ngx_int_t
-ngx_http_core_find_location(ngx_http_request_t *r,
-    ngx_array_t *locations, ngx_uint_t regex_start, size_t len)
+ngx_http_core_find_location(ngx_http_request_t *r)
 {
-    ngx_int_t                  n, rc;
-    ngx_uint_t                 i, found;
-    ngx_http_core_loc_conf_t  *clcf, **clcfp;
-#if (NGX_PCRE)
-    ngx_uint_t                 noregex;
-#endif
-
-    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
-                   "find location for \"%V\"", &r->uri);
+    ngx_int_t                  rc;
+    ngx_http_core_loc_conf_t  *pclcf;
 
-    found = 0;
-#if (NGX_PCRE)
-    noregex = 0;
-#endif
+    pclcf = ngx_http_get_module_loc_conf(r, ngx_http_core_module);
 
-    clcfp = locations->elts;
-    for (i = 0; i < locations->nelts; i++) {
+    rc = ngx_http_core_find_static_location(r, pclcf->static_locations);
 
-        if (clcfp[i]->noname
-#if (NGX_PCRE)
-            || clcfp[i]->regex
-#endif
-            || clcfp[i]->named)
-        {
-            break;
-        }
+    if (rc == NGX_AGAIN) {
+        /* look up nested locations */
+        rc = ngx_http_core_find_location(r);
+    }
 
-        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
-                       "find location: %s\"%V\"",
-                       clcfp[i]->exact_match ? "= " : "", &clcfp[i]->name);
-
-        if (clcfp[i]->auto_redirect
-            && r->uri.len == clcfp[i]->name.len - 1
-            && ngx_strncmp(r->uri.data, clcfp[i]->name.data,
-                           clcfp[i]->name.len - 1)
-                == 0)
-        {
-            /* the locations are lexicographically sorted */
+    if (rc == NGX_OK || rc == NGX_DONE) {
+        return rc;
+    }
 
-            r->loc_conf = clcfp[i]->loc_conf;
+    /* rc == NGX_DECLINED or rc == NGX_AGAIN in nested location */
 
-            return NGX_HTTP_LOCATION_AUTO_REDIRECT;
-        }
+#if (NGX_PCRE)
+    {
+    ngx_int_t                  n;
+    ngx_http_core_loc_conf_t  *clcf, **clcfp;
 
-        if (r->uri.len < clcfp[i]->name.len) {
-            continue;
-        }
+    clcf = ngx_http_get_module_loc_conf(r, ngx_http_core_module);
 
-        n = ngx_strncmp(r->uri.data, clcfp[i]->name.data, clcfp[i]->name.len);
+    if (clcf->noregex == 0 && pclcf->regex_locations) {
 
-        if (n < 0) {
-            /* the locations are lexicographically sorted */
-            break;
-        }
+        for (clcfp = pclcf->regex_locations; *clcfp; clcfp++) {
 
-        if (n == 0) {
-            if (clcfp[i]->exact_match) {
+            ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
+                           "test location: ~ \"%V\"", &(*clcfp)->name);
 
-                if (r->uri.len == clcfp[i]->name.len) {
-                    r->loc_conf = clcfp[i]->loc_conf;
-                    return NGX_HTTP_LOCATION_EXACT;
-                }
+            n = ngx_regex_exec((*clcfp)->regex, &r->uri, NULL, 0);
 
+            if (n == NGX_REGEX_NO_MATCHED) {
                 continue;
             }
 
-            if (len > clcfp[i]->name.len) {
-                /* the previous match is longer */
-                break;
+            if (n < 0) {
+                ngx_log_error(NGX_LOG_ALERT, r->connection->log, 0,
+                              ngx_regex_exec_n
+                              " failed: %d on \"%V\" using \"%V\"",
+                              n, &r->uri, &(*clcfp)->name);
+                return NGX_HTTP_INTERNAL_SERVER_ERROR;
             }
 
-            found = 1;
+            /* match */
 
-            r->loc_conf = clcfp[i]->loc_conf;
-#if (NGX_PCRE)
-            noregex = clcfp[i]->noregex;
-#endif
+            r->loc_conf = (*clcfp)->loc_conf;
+
+            /* look up nested locations */
+
+            return ngx_http_core_find_location(r);
         }
     }
+    }
+#endif
 
-    if (found) {
-        clcf = ngx_http_get_module_loc_conf(r, ngx_http_core_module);
+    return rc;
+}
 
-        if (clcf->locations) {
-            rc = ngx_http_core_find_location(r, clcf->locations,
-                                             clcf->regex_start, len);
 
-            if (rc != NGX_OK) {
-                return rc;
-            }
-        }
-    }
+/*
+ * NGX_OK       - exact match
+ * NGX_DONE     - auto redirect
+ * NGX_AGAIN    - inclusive match
+ * NGX_DECLINED - no match
+ */
 
-#if (NGX_PCRE)
+static ngx_int_t
+ngx_http_core_find_static_location(ngx_http_request_t *r,
+    ngx_http_location_tree_node_t *node)
+{
+    u_char     *uri;
+    size_t      len, n;
+    ngx_int_t   rc, rv;
 
-    if (noregex) {
-        return NGX_HTTP_LOCATION_NOREGEX;
-    }
+    len = r->uri.len;
+    uri = r->uri.data;
 
-    /* regex matches */
+    rv = NGX_DECLINED;
 
-    for (i = regex_start; i < locations->nelts; i++) {
+    for ( ;; ) {
 
-        if (!clcfp[i]->regex) {
-            break;
+        if (node == NULL) {
+            return rv;
         }
 
-        ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
-                       "find location: ~ \"%V\"", &clcfp[i]->name);
+        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
+                       "test location: \"%*s\"", node->len, node->name);
 
-        n = ngx_regex_exec(clcfp[i]->regex, &r->uri, NULL, 0);
+        n = (len <= (size_t) node->len) ? len : node->len;
+
+        rc = ngx_memcmp(uri, node->name, n);
+
+        if (rc != 0) {
+            node = (rc < 0) ? node->left : node->right;
 
-        if (n == NGX_REGEX_NO_MATCHED) {
             continue;
         }
 
-        if (n < 0) {
-            ngx_log_error(NGX_LOG_ALERT, r->connection->log, 0,
-                          ngx_regex_exec_n
-                          " failed: %d on \"%V\" using \"%V\"",
-                          n, &r->uri, &clcfp[i]->name);
-            return NGX_HTTP_INTERNAL_SERVER_ERROR;
+        if (len > (size_t) node->len) {
+
+            if (node->inclusive) {
+
+                r->loc_conf = node->inclusive->loc_conf;
+                rv = NGX_AGAIN;
+
+                node = node->tree;
+                uri += n;
+                len -= n;
+
+                continue;
+            }
+
+            /* exact only */
+
+            node = node->right;
+
+            continue;
         }
 
-        /* match */
+        if (len == (size_t) node->len) {
 
-        r->loc_conf = clcfp[i]->loc_conf;
+            r->loc_conf = (node->exact) ? node->exact->loc_conf:
+                                          node->inclusive->loc_conf;
+            return NGX_OK;
+        }
 
-        return NGX_HTTP_LOCATION_REGEX;
-    }
+        /* len < node->len */
 
-#endif /* NGX_PCRE */
+        if (len + 1 == (size_t) node->len && node->auto_redirect) {
 
-    return NGX_OK;
+            r->loc_conf = (node->exact) ? node->exact->loc_conf:
+                                          node->inclusive->loc_conf;
+            rv = NGX_DONE;
+        }
+
+        node = node->left;
+    }
 }
 
 
@@ -1896,29 +1890,29 @@ ngx_http_internal_redirect(ngx_http_request_t *r,
 ngx_int_t
 ngx_http_named_location(ngx_http_request_t *r, ngx_str_t *name)
 {
-    ngx_uint_t                   i;
     ngx_http_core_srv_conf_t    *cscf;
     ngx_http_core_loc_conf_t   **clcfp;
     ngx_http_core_main_conf_t   *cmcf;
 
     cscf = ngx_http_get_module_srv_conf(r, ngx_http_core_module);
 
-    clcfp = cscf->locations.elts;
+    for (clcfp = cscf->named_locations; *clcfp; clcfp++) {
 
-    for (i = cscf->named_start; i < cscf->locations.nelts; i++) {
+        ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
+                       "test location: \"%V\"", &(*clcfp)->name);
 
-        if (name->len != clcfp[i]->name.len
-            || ngx_strncmp(name->data, clcfp[i]->name.data, name->len) != 0)
+        if (name->len != (*clcfp)->name.len
+            || ngx_strncmp(name->data, (*clcfp)->name.data, name->len) != 0)
         {
             continue;
         }
 
         ngx_log_debug3(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,
-                       "named location: %V \"%V?%V\"", name, &r->uri, &r->args);
+                       "using location: %V \"%V?%V\"", name, &r->uri, &r->args);
 
         r->internal = 1;
         r->content_handler = NULL;
-        r->loc_conf = clcfp[i]->loc_conf;
+        r->loc_conf = (*clcfp)->loc_conf;
 
         ngx_http_update_location_config(r);
 
@@ -1935,6 +1929,7 @@ ngx_http_named_location(ngx_http_request_t *r, ngx_str_t *name)
                   "could not find named location \"%V\"", name);
 
     ngx_http_finalize_request(r, NGX_HTTP_INTERNAL_SERVER_ERROR);
+
     return NGX_DONE;
 }
 
@@ -1983,7 +1978,6 @@ ngx_http_core_server(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
     ngx_http_module_t           *module;
     ngx_http_conf_ctx_t         *ctx, *http_ctx;
     ngx_http_core_srv_conf_t    *cscf, **cscfp;
-    ngx_http_core_loc_conf_t   **clcfp;
     ngx_http_core_main_conf_t   *cmcf;
 
     ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_conf_ctx_t));
@@ -2061,37 +2055,6 @@ ngx_http_core_server(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
 
     *cf = pcf;
 
-    if (rv != NGX_CONF_OK) {
-        return rv;
-    }
-
-    ngx_sort(cscf->locations.elts, (size_t) cscf->locations.nelts,
-             sizeof(ngx_http_core_loc_conf_t *), ngx_http_core_cmp_locations);
-
-    clcfp = cscf->locations.elts;
-
-#if (NGX_PCRE)
-
-    cscf->regex_start = cscf->locations.nelts;
-
-    for (i = 0; i < cscf->locations.nelts; i++) {
-        if (clcfp[i]->regex) {
-            cscf->regex_start = i;
-            break;
-        }
-    }
-
-#endif
-
-    cscf->named_start = cscf->locations.nelts;
-
-    for (i = 0; i < cscf->locations.nelts; i++) {
-        if (clcfp[i]->named) {
-            cscf->named_start = i;
-            break;
-        }
-    }
-
     return rv;
 }
 
@@ -2105,8 +2068,7 @@ ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
     ngx_conf_t                 save;
     ngx_http_module_t         *module;
     ngx_http_conf_ctx_t       *ctx, *pctx;
-    ngx_http_core_srv_conf_t  *cscf;
-    ngx_http_core_loc_conf_t  *clcf, *pclcf, **clcfp;
+    ngx_http_core_loc_conf_t  *clcf, *pclcf;
 
     ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_conf_ctx_t));
     if (ctx == NULL) {
@@ -2201,15 +2163,10 @@ ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
 
     pclcf = pctx->loc_conf[ngx_http_core_module.ctx_index];
 
-    if (pclcf->name.len == 0) {
-        cscf = ctx->srv_conf[ngx_http_core_module.ctx_index];
+    if (pclcf->name.len) {
 
-        clcfp = ngx_array_push(&cscf->locations);
-        if (clcfp == NULL) {
-            return NGX_CONF_ERROR;
-        }
+        /* nested location */
 
-    } else {
 #if 0
         clcf->prev_location = pclcf;
 #endif
@@ -2230,6 +2187,14 @@ ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
             return NGX_CONF_ERROR;
         }
 
+        if (clcf->named) {
+            ngx_conf_log_error(NGX_LOG_EMERG, cf, 0,
+                               "named location \"%V\" must be "
+                               "on server level only",
+                               &clcf->name);
+            return NGX_CONF_ERROR;
+        }
+
 #if (NGX_PCRE)
         if (clcf->regex == NULL
             && ngx_strncmp(clcf->name.data, pclcf->name.data, pclcf->name.len)
@@ -2244,22 +2209,11 @@ ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
                                &clcf->name, &pclcf->name);
             return NGX_CONF_ERROR;
         }
-
-        if (pclcf->locations == NULL) {
-            pclcf->locations = ngx_array_create(cf->pool, 2, sizeof(void *));
-
-            if (pclcf->locations == NULL) {
-                return NGX_CONF_ERROR;
-            }
-        }
-
-        clcfp = ngx_array_push(pclcf->locations);
-        if (clcfp == NULL) {
-            return NGX_CONF_ERROR;
-        }
     }
 
-    *clcfp = clcf;
+    if (ngx_http_add_location(cf, &pclcf->locations, clcf) != NGX_OK) {
+        return NGX_CONF_ERROR;
+    }
 
     save = *cf;
     cf->ctx = ctx;
@@ -2269,103 +2223,10 @@ ngx_http_core_location(ngx_conf_t *cf, ngx_command_t *cmd, void *dummy)
 
     *cf = save;
 
-    if (rv != NGX_CONF_OK) {
-        return rv;
-    }
-
-    if (clcf->locations == NULL) {
-        return rv;
-    }
-
-    ngx_sort(clcf->locations->elts, (size_t) clcf->locations->nelts,
-             sizeof(ngx_http_core_loc_conf_t *), ngx_http_core_cmp_locations);
-
-#if (NGX_PCRE)
-
-    clcf->regex_start = clcf->locations->nelts;
-    clcfp = clcf->locations->elts;
-
-    for (i = 0; i < clcf->locations->nelts; i++) {
-        if (clcfp[i]->regex) {
-            clcf->regex_start = i;
-            break;
-        }
-    }
-
-#endif
-
     return rv;
 }
 
 
-static ngx_int_t
-ngx_http_core_cmp_locations(const void *one, const void *two)
-{
-    ngx_int_t                  rc;
-    ngx_http_core_loc_conf_t  *first, *second;
-
-    first = *(ngx_http_core_loc_conf_t **) one;
-    second = *(ngx_http_core_loc_conf_t **) two;
-
-    if (first->named && !second->named) {
-        /* shift named locations to the end */
-        return 1;
-    }
-
-    if (!first->named && second->named) {
-        /* shift named locations to the end */
-        return -1;
-    }
-
-    if (first->named && second->named) {
-        return ngx_strcmp(first->name.data, second->name.data);
-    }
-
-    if (first->noname && !second->noname) {
-        /* shift no named locations to the end */
-        return 1;
-    }
-
-    if (!first->noname && second->noname) {
-        /* shift no named locations to the end */
-        return -1;
-    }
-
-    if (first->noname || second->noname) {
-        /* do not sort no named locations */
-        return 0;
-    }
-
-#if (NGX_PCRE)
-
-    if (first->regex && !second->regex) {
-        /* shift the regex matches to the end */
-        return 1;
-    }
-
-    if (!first->regex && second->regex) {
-        /* shift the regex matches to the end */
-        return -1;
-    }
-
-    if (first->regex || second->regex) {
-        /* do not sort the regex matches */
-        return 0;
-    }
-
-#endif
-
-    rc = ngx_strcmp(first->name.data, second->name.data);
-
-    if (rc == 0 && second->exact_match) {
-        /* an exact match must be before the same inclusive one */
-        return 1;
-    }
-
-    return rc;
-}
-
-
 static char *
 ngx_http_core_types(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
 {
@@ -2541,12 +2402,6 @@ ngx_http_core_create_srv_conf(ngx_conf_t *cf)
      *     conf->client_large_buffers.num = 0;
      */
 
-    if (ngx_array_init(&cscf->locations, cf->pool, 4, sizeof(void *))
-        == NGX_ERROR)
-    {
-        return NGX_CONF_ERROR;
-    }
-
     if (ngx_array_init(&cscf->listen, cf->pool, 4, sizeof(ngx_http_listen_t))
         == NGX_ERROR)
     {
@@ -3345,7 +3200,7 @@ static ngx_http_method_name_t  ngx_methods_names[] = {
 static char *
 ngx_http_core_limit_except(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
 {
-    ngx_http_core_loc_conf_t *clcf = conf;
+    ngx_http_core_loc_conf_t *pclcf = conf;
 
     char                      *rv;
     void                      *mconf;
@@ -3355,13 +3210,13 @@ ngx_http_core_limit_except(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     ngx_http_module_t         *module;
     ngx_http_conf_ctx_t       *ctx, *pctx;
     ngx_http_method_name_t    *name;
-    ngx_http_core_loc_conf_t  *lcf, **clcfp;
+    ngx_http_core_loc_conf_t  *clcf;
 
-    if (clcf->limit_except) {
+    if (pclcf->limit_except) {
         return "duplicate";
     }
 
-    clcf->limit_except = 0xffffffff;
+    pclcf->limit_except = 0xffffffff;
 
     value = cf->args->elts;
 
@@ -3369,7 +3224,7 @@ ngx_http_core_limit_except(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
         for (name = ngx_methods_names; name->name; name++) {
 
             if (ngx_strcasecmp(value[i].data, name->name) == 0) {
-                clcf->limit_except &= name->method;
+                pclcf->limit_except &= name->method;
                 goto next;
             }
         }
@@ -3382,8 +3237,8 @@ ngx_http_core_limit_except(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
         continue;
     }
 
-    if (!(clcf->limit_except & NGX_HTTP_GET)) {
-        clcf->limit_except &= (uint32_t) ~NGX_HTTP_HEAD;
+    if (!(pclcf->limit_except & NGX_HTTP_GET)) {
+        pclcf->limit_except &= (uint32_t) ~NGX_HTTP_HEAD;
     }
 
     ctx = ngx_pcalloc(cf->pool, sizeof(ngx_http_conf_ctx_t));
@@ -3419,27 +3274,16 @@ ngx_http_core_limit_except(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
     }
 
 
-    lcf = ctx->loc_conf[ngx_http_core_module.ctx_index];
-    clcf->limit_except_loc_conf = ctx->loc_conf;
-    lcf->loc_conf = ctx->loc_conf;
-    lcf->name = clcf->name;
-    lcf->noname = 1;
-
-    if (clcf->locations == NULL) {
-        clcf->locations = ngx_array_create(cf->pool, 2, sizeof(void *));
-        if (clcf->locations == NULL) {
-            return NGX_CONF_ERROR;
-        }
-    }
+    clcf = ctx->loc_conf[ngx_http_core_module.ctx_index];
+    pclcf->limit_except_loc_conf = ctx->loc_conf;
+    clcf->loc_conf = ctx->loc_conf;
+    clcf->name = pclcf->name;
+    clcf->noname = 1;
 
-    clcfp = ngx_array_push(clcf->locations);
-    if (clcfp == NULL) {
+    if (ngx_http_add_location(cf, &pclcf->locations, clcf) != NGX_OK) {
         return NGX_CONF_ERROR;
     }
 
-    *clcfp = lcf;
-
-
     save = *cf;
     cf->ctx = ctx;
     cf->cmd_type = NGX_HTTP_LMT_CONF;
diff --git a/src/http/ngx_http_core_module.h b/src/http/ngx_http_core_module.h
index bdc15d628..ac743f37f 100644
--- a/src/http/ngx_http_core_module.h
+++ b/src/http/ngx_http_core_module.h
@@ -28,6 +28,10 @@
 #define NGX_HTTP_SATISFY_ANY            1
 
 
+typedef struct ngx_http_location_tree_node_s  ngx_http_location_tree_node_t;
+typedef struct ngx_http_core_loc_conf_s  ngx_http_core_loc_conf_t;
+
+
 typedef struct {
     unsigned                   default_server:1;
     unsigned                   bind:1;
@@ -127,37 +131,30 @@ typedef struct {
 
 
 typedef struct {
-    /*
-     * array of the ngx_http_core_loc_conf_t *,
-     * used in the ngx_http_core_find_location() and in the merge phase
-     */
-    ngx_array_t                locations;
-
-    unsigned                   regex_start:15;
-    unsigned                   named_start:15;
-
     /* array of the ngx_http_listen_t, "listen" directive */
-    ngx_array_t                listen;
+    ngx_array_t                 listen;
 
     /* array of the ngx_http_server_name_t, "server_name" directive */
-    ngx_array_t                server_names;
+    ngx_array_t                 server_names;
 
     /* server ctx */
-    ngx_http_conf_ctx_t       *ctx;
+    ngx_http_conf_ctx_t        *ctx;
+
+    ngx_str_t                   server_name;
 
-    ngx_str_t                  server_name;
+    size_t                      connection_pool_size;
+    size_t                      request_pool_size;
+    size_t                      client_header_buffer_size;
 
-    size_t                     connection_pool_size;
-    size_t                     request_pool_size;
-    size_t                     client_header_buffer_size;
+    ngx_bufs_t                  large_client_header_buffers;
 
-    ngx_bufs_t                 large_client_header_buffers;
+    ngx_msec_t                  client_header_timeout;
 
-    ngx_msec_t                 client_header_timeout;
+    ngx_flag_t                  optimize_server_names;
+    ngx_flag_t                  ignore_invalid_headers;
+    ngx_flag_t                  merge_slashes;
 
-    ngx_flag_t                 optimize_server_names;
-    ngx_flag_t                 ignore_invalid_headers;
-    ngx_flag_t                 merge_slashes;
+    ngx_http_core_loc_conf_t  **named_locations;
 } ngx_http_core_srv_conf_t;
 
 
@@ -231,8 +228,6 @@ typedef struct {
 } ngx_http_err_page_t;
 
 
-typedef struct ngx_http_core_loc_conf_s  ngx_http_core_loc_conf_t;
-
 struct ngx_http_core_loc_conf_s {
     ngx_str_t     name;          /* location name */
 
@@ -240,8 +235,6 @@ struct ngx_http_core_loc_conf_s {
     ngx_regex_t  *regex;
 #endif
 
-    unsigned      regex_start:15;
-
     unsigned      noname:1;   /* "if () {}" block or limit_except */
     unsigned      named:1;
 
@@ -251,8 +244,10 @@ struct ngx_http_core_loc_conf_s {
     unsigned      auto_redirect:1;
     unsigned      alias:1;
 
-    /* array of inclusive ngx_http_core_loc_conf_t */
-    ngx_array_t  *locations;
+    ngx_queue_t  *locations;
+
+    ngx_http_location_tree_node_t   *static_locations;
+    ngx_http_core_loc_conf_t       **regex_locations;
 
     /* pointer to the modules' loc_conf */
     void        **loc_conf;
@@ -339,6 +334,31 @@ struct ngx_http_core_loc_conf_s {
 };
 
 
+typedef struct {
+    ngx_queue_t                      queue;
+    ngx_http_core_loc_conf_t        *exact;
+    ngx_http_core_loc_conf_t        *inclusive;
+    ngx_str_t                       *name;
+    u_char                          *file_name;
+    ngx_uint_t                       line;
+    ngx_queue_t                      list;
+} ngx_http_location_queue_t;
+
+
+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];
+};
+
+
 void ngx_http_core_run_phases(ngx_http_request_t *r);
 ngx_int_t ngx_http_core_generic_phase(ngx_http_request_t *r,
     ngx_http_phase_handler_t *ph);