Mercurial > hg > nginx-vendor-current
view src/core/ngx_radix_tree.c @ 122:d25a1d6034f1 NGINX_0_3_8
nginx 0.3.8
*) Security: nginx now checks URI got from a backend in
"X-Accel-Redirect" header line or in SSI file for the "/../" paths
and zeroes.
*) Change: nginx now does not treat the empty user name in the
"Authorization" header line as valid one.
*) Feature: the "ssl_session_timeout" directives of the
ngx_http_ssl_module and ngx_imap_ssl_module.
*) Feature: the "auth_http_header" directive of the
ngx_imap_auth_http_module.
*) Feature: the "add_header" directive.
*) Feature: the ngx_http_realip_module.
*) Feature: the new variables to use in the "log_format" directive:
$bytes_sent, $apache_bytes_sent, $status, $time_gmt, $uri,
$request_time, $request_length, $upstream_status,
$upstream_response_time, $gzip_ratio, $uid_got, $uid_set,
$connection, $pipe, and $msec. The parameters in the "%name" form
will be canceled soon.
*) Change: now the false variable values in the "if" directive are the
empty string "" and string starting with "0".
*) Bugfix: while using proxied or FastCGI-server nginx may leave
connections and temporary files with client requests in open state.
*) Bugfix: the worker processes did not flush the buffered logs on
graceful exit.
*) Bugfix: if the request URI was changes by the "rewrite" directive
and the request was proxied in location given by regular expression,
then the incorrect request was transferred to backend; bug appeared
in 0.2.6.
*) Bugfix: the "expires" directive did not remove the previous
"Expires" header.
*) Bugfix: nginx may stop to accept requests if the "rtsig" method and
several worker processes were used.
*) Bugfix: the "\"" and "\'" escape symbols were incorrectly handled in
SSI commands.
*) Bugfix: if the response was ended just after the SSI command and
gzipping was used, then the response did not transferred complete or
did not transferred at all.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Wed, 09 Nov 2005 00:00:00 +0300 |
parents | 408f195b3482 |
children | f745bf973510 |
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) { break; } if (node->value != NGX_RADIX_NO_VALUE) { break; } if (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; }