{ ngx_string("http),
  NGX_MAIN_CONF|NGX_CONF_BLOCK|NGX_CONF_NOARGS,
  ngx_http_block,
  0,
  0,
  NULL }

typedef struct {
  void        **main_conf;
  void        **srv_conf;
  void        **loc_conf;
} ngx_http_conf_ctx_t;

ngx_http_header_t  ngx_http_headers_in[] = {
  { ngx_string("Host"), offsetof(ngx_http_headers_in_t, host),
    ngx_http_process_host },

  { ngx_string("Connection"), offsetof(ngx_http_headers_in_t, connection),
    ngx_http_process_connection },
  ....
}

typedef struct {
  ngx_hash_combined_t        names;

  ngx_uint_t                 nregex;
  ngx_http_server_name_t    *regex;
} ngx_http_virtual_names_t;

struct ngx_http_addr_conf_s {
  /* the default server configuration for this address:port */
  ngx_http_core_srv_conf_t  *default_server;

  ngx_http_virtual_names_t  *virtual_names;

  unsigned                   ssl:1;
  unsigned                   http2:1;
  unsigned                   proxy_protocol:1;
};

typedef struct {
  ngx_hash_t            hash;
  ngx_hash_wildcard_t  *wc_head;
  ngx_hash_wildcard_t  *wc_tail;
} ngx_hash_combined_t;

location = / {
    [ configuration A ]
}

location / {
    [ configuration B ]
}

location /documents/ {
    [ configuration C ]
}

location ^~ /images/ {
    [ configuration D ]
}

location ~* \.(gif|jpg|jpeg)$ {
    [ configuration E ]
}

struct ngx_http_core_loc_conf_s {
  ngx_str_t           name;   /* URI 部分字符串 */
  ngx_http_regex_t    *regex; /* 正则引擎编译过的 正则表达式对象 */
  ...
  unsigned            named:1;        /* @ 修饰符 */
  unsigned            noname:1;       /* if () {} */
  unsigned            exact_match:1;  /* = 修饰符 */
  unsigned            noregex:1;      /* ^= 修饰符 */

  ...
  ngx_http_location_tree_node_t   *static_location;
  ngx_http_core_loc_conf_t        **regex_location;
  void                **loc_conf;
  ...
  ngx_queue_t         *locations; /* 连接 `location` 作用域，由
                                     ngx_http_location_queue_t 强制转
                                     换而来 */
};

typedef struct {
  ngx_queue_t                 queue;
  ngx_http_core_loc_conf_t    *exact; /* exact_match, regex, named, noname */
  ngx_http_core_loc_conf_t    *inclusive; /* 非 exact 的 location */
  ngx_str_t                   *name;
} 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;     // 精确匹配的location配置
  ngx_http_core_loc_conf_t        *inclusive; // inclusive匹配的location配置

  u_char                          auto_redirect;
  u_char                          len;
  u_char                          name[1];
};

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) {
    // 如果不是inclusive类型的location，直接跳过，继续队列中下一个location的处理
    ngx_http_create_locations_list(locations, ngx_queue_next(q));
    return;
  }

  len = lq->name->len;
  name = lq->name->data;

  // 从该location的下一个元素开始遍历队列
  for (x = ngx_queue_next(q);
    x != ngx_queue_sentinel(locations);
    x = ngx_queue_next(x))
  {
    lx = (ngx_http_location_queue_t *) x;

    // 找到第一个不以q的location做为前缀的location就退出循环
    // 比如当前队列location为：/a /ab /abc /b
    // 这里的q就是/a，x就是/b，中间的/ab和/abc都是以/a为前缀的，不会终止循环
    if (len > lx->name->len
      || ngx_filename_cmp(name, lx->name->data, len) != 0)
    {
      break;
    }
  }

  q = ngx_queue_next(q);

  if (q == x) { // 如果x就是q的下一个元素，说明没有找到前缀匹配的，那么直接进入x进行下次递归调用
    ngx_http_create_locations_list(locations, x);
    return;
  }

  // 到了这里说明前面找到有前缀匹配的location了

  // 这里将与q相同前缀的节点，分离出队列
  ngx_queue_split(locations, q, &tail);
  // 然后加入到q的list链表中
  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;
  }

  // 将x从队列中分离出来
  ngx_queue_split(&lq->list, x, &tail);
  // 放回到location队列中
  ngx_queue_add(locations, &tail);

  // 对lq->list做相同的操作
  ngx_http_create_locations_list(&lq->list, ngx_queue_head(&lq->list));

  // 对从x开始的剩余节点做相同的操作
  ngx_http_create_locations_list(locations, x);
}

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中
  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);

  // 从中间节点将location分为两部分
  ngx_queue_split(locations, q, &tail);

  // 如果分离完毕location队列为空
  if (ngx_queue_empty(locations)) {
    /*
     * ngx_queue_split() insures that if left part is empty,
     * then right one is empty too
     */
    // 直接跳到构造inclusive类型的子树
    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:
  // 到这里构造inclusive类型的树保存到tree成员中

  // list为空说明没有inclusive类型的location了
  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;
}