Mercurial > hg > nginx
diff src/core/ngx_radix_tree.c @ 487:31ff3e943e16 release-0.1.18
nginx-0.1.18-RELEASE import
*) Workaround: the default values of the devpoll_events and the
devpoll_changes directives changed from 512 to 32 to be compatible
with Solaris 10.
*) Bugfix: the proxy_set_x_var and fastcgi_set_var directives were not
inherited.
*) Bugfix: in the redirect rewrite directive the arguments were
concatenated with URI by the "&" rather than the "?".
*) Bugfix: the lines without trailing ";" in the file being included by
the ngx_http_geo_module were silently ignored.
*) Feature: the ngx_http_stub_status_module.
*) Bugfix: the unknown log format in the access_log directive caused
the segmentation fault.
*) Feature: the new "document_root" parameter of the fastcgi_params
directive.
*) Feature: the fastcgi_redirect_errors directive.
*) Feature: the new "break" modifier of the "rewrite" directive allows
to stop the rewrite/location cycle and sets the current
configuration to the request.
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Wed, 09 Feb 2005 14:31:07 +0000 |
parents | 4ebe09b07e30 |
children | 45a460f82aec |
line wrap: on
line diff
--- a/src/core/ngx_radix_tree.c +++ b/src/core/ngx_radix_tree.c @@ -11,8 +11,10 @@ static void *ngx_radix_alloc(ngx_radix_tree_t *tree); -ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool) +ngx_radix_tree_t * +ngx_radix_tree_create(ngx_pool_t *pool, ngx_uint_t preallocate) { + uint32_t key, mask, inc; ngx_radix_tree_t *tree; if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { @@ -33,12 +35,43 @@ ngx_radix_tree_t *ngx_radix_tree_create( tree->root->parent = NULL; tree->root->value = NGX_RADIX_NO_VALUE; + /* + * We preallocate the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc., + * to increase 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. + */ + + 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) +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; @@ -100,8 +133,8 @@ ngx_int_t ngx_radix32tree_insert(ngx_rad } -ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, - uint32_t key, uint32_t mask) +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; @@ -158,7 +191,8 @@ ngx_int_t ngx_radix32tree_delete(ngx_rad } -uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) +uintptr_t +ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) { uint32_t bit; uintptr_t value; @@ -187,7 +221,8 @@ uintptr_t ngx_radix32tree_find(ngx_radix } -static void *ngx_radix_alloc(ngx_radix_tree_t *tree) +static void * +ngx_radix_alloc(ngx_radix_tree_t *tree) { char *p;