Mercurial > hg > nginx-vendor-current
view src/core/ngx_radix_tree.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 | 72eb30262aac |
children | 408f195b3482 |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev */ #include <ngx_config.h> #include <ngx_core.h> static void *ngx_radix_alloc(ngx_radix_tree_t *tree); ngx_radix_tree_t * ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate) { uint32_t key, mask, inc; ngx_radix_tree_t *tree; tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)); if (tree == NULL) { return NULL; } tree->pool = pool; tree->free = NULL; tree->start = NULL; tree->size = 0; tree->root = ngx_radix_alloc(tree); if (tree->root == NULL) { return NULL; } tree->root->right = NULL; tree->root->left = NULL; tree->root->parent = NULL; tree->root->value = NGX_RADIX_NO_VALUE; if (preallocate == 0) { return tree; } /* * The preallocation the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc. * increases the TLB hits even if for the first lookup iterations. * On the 32-bit platforms the 7 preallocated bits takes continuous 4K, * 8 - 8K, 9 - 16K, etc. On the 64-bit platforms the 6 preallocated bits * takes continuous 4K, 7 - 8K, 8 - 16K, etc. There is no sense to * to preallocate more than one page, because further preallocation * distributes the only bit per page. Instead, the random insertion * may distribute several bits per page. * * Thus, by default we preallocate maximum * 6 bits on amd64 (64-bit platform and 4K pages) * 7 bits on i386 (32-bit platform and 4K pages) * 7 bits on sparc64 in 64-bit mode (8K pages) * 8 bits on sparc64 in 32-bit mode (8K pages) */ if (preallocate == -1) { switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) { /* amd64 */ case 128: preallocate = 6; break; /* i386, sparc64 */ case 256: preallocate = 7; break; /* sparc64 in 32-bit mode */ default: preallocate = 8; } } mask = 0; inc = 0x80000000; while (preallocate--) { key = 0; mask >>= 1; mask |= 0x80000000; do { if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE) != NGX_OK) { return NULL; } key += inc; } while (key); inc >>= 1; } return tree; } ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, uintptr_t value) { uint32_t bit; ngx_radix_node_t *node, *next; bit = 0x80000000; node = tree->root; next = tree->root; while (bit & mask) { if (key & bit) { next = node->right; } else { next = node->left; } if (next == NULL) { break; } bit >>= 1; node = next; } if (next) { if (node->value != NGX_RADIX_NO_VALUE) { return NGX_BUSY; } node->value = value; return NGX_OK; } while (bit & mask) { next = ngx_radix_alloc(tree); if (next == NULL) { return NGX_ERROR; } next->right = NULL; next->left = NULL; next->parent = node; next->value = NGX_RADIX_NO_VALUE; if (key & bit) { node->right = next; } else { node->left = next; } bit >>= 1; node = next; } node->value = value; return NGX_OK; } ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) { uint32_t bit; ngx_radix_node_t *node; bit = 0x80000000; node = tree->root; while (node && (bit & mask)) { if (key & bit) { node = node->right; } else { node = node->left; } bit >>= 1; } if (node == NULL) { return NGX_ERROR; } if (node->right || node->left) { if (node->value != NGX_RADIX_NO_VALUE) { node->value = NGX_RADIX_NO_VALUE; return NGX_OK; } return NGX_ERROR; } for ( ;; ) { if (node->parent->right == node) { node->parent->right = NULL; } else { node->parent->left = NULL; } node->right = tree->free; tree->free = node; node = node->parent; if (node->right || node->left || node->value != NGX_RADIX_NO_VALUE || node->parent == NULL) { break; } } return NGX_OK; } uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) { uint32_t bit; uintptr_t value; ngx_radix_node_t *node; bit = 0x80000000; value = NGX_RADIX_NO_VALUE; node = tree->root; while (node) { if (node->value != NGX_RADIX_NO_VALUE) { value = node->value; } if (key & bit) { node = node->right; } else { node = node->left; } bit >>= 1; } return value; } static void * ngx_radix_alloc(ngx_radix_tree_t *tree) { char *p; if (tree->free) { p = (char *) tree->free; tree->free = tree->free->right; return p; } if (tree->size < sizeof(ngx_radix_node_t)) { tree->start = ngx_palloc(tree->pool, ngx_pagesize); if (tree->start == NULL) { return NULL; } tree->size = ngx_pagesize; } p = tree->start; tree->start += sizeof(ngx_radix_node_t); tree->size -= sizeof(ngx_radix_node_t); return p; }