Mercurial > hg > nginx-ranges

diff src/core/ngx_radix_tree.c @ 36:a39d1b793287 NGINX_0_1_18

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.1.18 *) 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 <http://sysoev.ru>
date Wed, 09 Feb 2005 00:00:00 +0300
parents aab2ea7c0458
children 2879cd3a40cb
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;