Mercurial > hg > nginx-vendor-0-8
view src/core/ngx_rbtree.c @ 58:b55cbf18157e NGINX_0_1_29
nginx 0.1.29
*) Feature: the ngx_http_ssi_module supports "include virtual" command.
*) Feature: the ngx_http_ssi_module supports the condition command like
'if expr="$NAME"' and "else" and "endif" commands. Only one nested
level is supported.
*) Feature: the ngx_http_ssi_module supports the DATE_LOCAL and
DATE_GMT variables and "config timefmt" command.
*) Feature: the "ssi_ignore_recycled_buffers" directive.
*) Bugfix: the "echo" command did not show the default value for the
empty QUERY_STRING variable.
*) Change: the ngx_http_proxy_module was rewritten.
*) Feature: the "proxy_redirect", "proxy_pass_request_headers",
"proxy_pass_request_body", and "proxy_method" directives.
*) Feature: the "proxy_set_header" directive. The "proxy_x_var" was
canceled and must be replaced with the proxy_set_header directive.
*) Change: the "proxy_preserve_host" is canceled and must be replaced
with the "proxy_set_header Host $host" and the "proxy_redirect off"
directives, the "proxy_set_header Host $host:$proxy_port" directive
and the appropriate proxy_redirect directives.
*) Change: the "proxy_set_x_real_ip" is canceled and must be replaced
with the "proxy_set_header X-Real-IP $remote_addr" directive.
*) Change: the "proxy_add_x_forwarded_for" is canceled and must be
replaced with
the "proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for"
directive.
*) Change: the "proxy_set_x_url" is canceled and must be replaced with
the "proxy_set_header X-URL http://$host:$server_port$request_uri"
directive.
*) Feature: the "fastcgi_param" directive.
*) Change: the "fastcgi_root", "fastcgi_set_var" and "fastcgi_params"
directive are canceled and must be replaced with the fastcgi_param
directives.
*) Feature: the "index" directive can use the variables.
*) Feature: the "index" directive can be used at http and server levels.
*) Change: the last index only in the "index" directive can be absolute.
*) Feature: the "rewrite" directive can use the variables.
*) Feature: the "internal" directive.
*) Feature: the CONTENT_LENGTH, CONTENT_TYPE, REMOTE_PORT, SERVER_ADDR,
SERVER_PORT, SERVER_PROTOCOL, DOCUMENT_ROOT, SERVER_NAME,
REQUEST_METHOD, REQUEST_URI, and REMOTE_USER variables.
*) Change: nginx now passes the invalid lines in a client request
headers or a backend response header.
*) Bugfix: if the backend did not transfer response for a long time and
the "send_timeout" was less than "proxy_read_timeout", then nginx
returned the 408 response.
*) Bugfix: the segmentation fault was occurred if the backend sent an
invalid line in response header; bug appeared in 0.1.26.
*) Bugfix: the segmentation fault may occurred in FastCGI fault
tolerance configuration.
*) Bugfix: the "expires" directive did not remove the previous
"Expires" and "Cache-Control" headers.
*) Bugfix: nginx did not take into account trailing dot in "Host"
header line.
*) Bugfix: the ngx_http_auth_module did not work under Linux.
*) Bugfix: the rewrite directive worked incorrectly, if the arguments
were in a request.
*) Bugfix: nginx could not be built on MacOS X.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Thu, 12 May 2005 00:00:00 +0400 |
parents | 41ccba1aba45 |
children | 45f7329b4bd0 |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev */ #include <ngx_config.h> #include <ngx_core.h> /* * The code is based on the algorithm described in the "Introduction * to Algorithms" by Cormen, Leiserson and Rivest. */ #define ngx_rbt_red(node) ((node)->color = 1) #define ngx_rbt_black(node) ((node)->color = 0) #define ngx_rbt_is_red(node) ((node)->color) #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node); static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node); void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node) { ngx_rbtree_t *temp; /* a binary tree insert */ if (*root == sentinel) { node->parent = NULL; node->left = sentinel; node->right = sentinel; ngx_rbt_black(node); *root = node; return; } temp = *root; for ( ;; ) { if (node->key < temp->key) { if (temp->left == sentinel) { temp->left = node; break; } temp = temp->left; continue; } if (temp->right == sentinel) { temp->right = node; break; } temp = temp->right; continue; } node->parent = temp; node->left = sentinel; node->right = sentinel; /* re-balance tree */ ngx_rbt_red(node); while (node != *root && ngx_rbt_is_red(node->parent)) { if (node->parent == node->parent->parent->left) { temp = node->parent->parent->right; if (ngx_rbt_is_red(temp)) { ngx_rbt_black(node->parent); ngx_rbt_black(temp); ngx_rbt_red(node->parent->parent); node = node->parent->parent; } else { if (node == node->parent->right) { node = node->parent; ngx_rbtree_left_rotate(root, sentinel, node); } ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); } } else { temp = node->parent->parent->left; if (ngx_rbt_is_red(temp)) { ngx_rbt_black(node->parent); ngx_rbt_black(temp); ngx_rbt_red(node->parent->parent); node = node->parent->parent; } else { if (node == node->parent->left) { node = node->parent; ngx_rbtree_right_rotate(root, sentinel, node); } ngx_rbt_black(node->parent); ngx_rbt_red(node->parent->parent); ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); } } } ngx_rbt_black(*root); } void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node) { ngx_int_t is_red; ngx_rbtree_t *subst, *temp, *w; /* a binary tree delete */ if (node->left == sentinel) { temp = node->right; subst = node; } else if (node->right == sentinel) { temp = node->left; subst = node; } else { subst = ngx_rbtree_min(node->right, sentinel); if (subst->left != sentinel) { temp = subst->left; } else { temp = subst->right; } } if (subst == *root) { *root = temp; ngx_rbt_black(temp); /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; return; } is_red = ngx_rbt_is_red(subst); if (subst == subst->parent->left) { subst->parent->left = temp; } else { subst->parent->right = temp; } if (subst == node) { temp->parent = subst->parent; } else { if (subst->parent == node) { temp->parent = subst; } else { temp->parent = subst->parent; } subst->left = node->left; subst->right = node->right; subst->parent = node->parent; ngx_rbt_copy_color(subst, node); if (node == *root) { *root = subst; } else { if (node == node->parent->left) { node->parent->left = subst; } else { node->parent->right = subst; } } if (subst->left != sentinel) { subst->left->parent = subst; } if (subst->right != sentinel) { subst->right->parent = subst; } /* DEBUG stuff */ node->left = NULL; node->right = NULL; node->parent = NULL; node->key = 0; } if (is_red) { return; } /* a delete fixup */ while (temp != *root && ngx_rbt_is_black(temp)) { if (temp == temp->parent->left) { w = temp->parent->right; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_left_rotate(root, sentinel, temp->parent); w = temp->parent->right; } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else { if (ngx_rbt_is_black(w->right)) { ngx_rbt_black(w->left); ngx_rbt_red(w); ngx_rbtree_right_rotate(root, sentinel, w); w = temp->parent->right; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->right); ngx_rbtree_left_rotate(root, sentinel, temp->parent); temp = *root; } } else { w = temp->parent->left; if (ngx_rbt_is_red(w)) { ngx_rbt_black(w); ngx_rbt_red(temp->parent); ngx_rbtree_right_rotate(root, sentinel, temp->parent); w = temp->parent->left; } if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { ngx_rbt_red(w); temp = temp->parent; } else { if (ngx_rbt_is_black(w->left)) { ngx_rbt_black(w->right); ngx_rbt_red(w); ngx_rbtree_left_rotate(root, sentinel, w); w = temp->parent->left; } ngx_rbt_copy_color(w, temp->parent); ngx_rbt_black(temp->parent); ngx_rbt_black(w->left); ngx_rbtree_right_rotate(root, sentinel, temp->parent); temp = *root; } } } ngx_rbt_black(temp); } static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node) { ngx_rbtree_t *temp; temp = node->right; node->right = temp->left; if (temp->left != sentinel) { temp->left->parent = node; } temp->parent = node->parent; if (node == *root) { *root = temp; } else if (node == node->parent->left) { node->parent->left = temp; } else { node->parent->right = temp; } temp->left = node; node->parent = temp; } static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node) { ngx_rbtree_t *temp; temp = node->left; node->left = temp->right; if (temp->right != sentinel) { temp->right->parent = node; } temp->parent = node->parent; if (node == *root) { *root = temp; } else if (node == node->parent->right) { node->parent->right = temp; } else { node->parent->left = temp; } temp->right = node; node->parent = temp; }