Mercurial > hg > nginx-ranges

comparison 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
comparison
equal deleted inserted replaced
35:ef53675fe4a6 36:a39d1b793287
9 9
10 10
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree); 11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
12 12
13 13
14 ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool) 14 ngx_radix_tree_t *
15 { 15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_uint_t preallocate)
16 {
17 uint32_t key, mask, inc;
16 ngx_radix_tree_t *tree; 18 ngx_radix_tree_t *tree;
17 19
18 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { 20 if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) {
19 return NULL; 21 return NULL;
20 } 22 }
31 tree->root->right = NULL; 33 tree->root->right = NULL;
32 tree->root->left = NULL; 34 tree->root->left = NULL;
33 tree->root->parent = NULL; 35 tree->root->parent = NULL;
34 tree->root->value = NGX_RADIX_NO_VALUE; 36 tree->root->value = NGX_RADIX_NO_VALUE;
35 37
38 /*
39 * We preallocate the first nodes: 0, 1, 00, 01, 10, 11, 000, 001, etc.,
40 * to increase the TLB hits even if for the first lookup iterations.
41 * On the 32-bit platforms the 7 preallocated bits takes continuous 4K,
42 * 8 - 8K, 9 - 16K, etc.
43 */
44
45 mask = 0;
46 inc = 0x80000000;
47
48 while (preallocate--) {
49
50 key = 0;
51 mask >>= 1;
52 mask |= 0x80000000;
53
54 do {
55 if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
56 != NGX_OK)
57 {
58 return NULL;
59 }
60
61 key += inc;
62
63 } while (key);
64
65 inc >>= 1;
66 }
67
36 return tree; 68 return tree;
37 } 69 }
38 70
39 71
40 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, 72 ngx_int_t
41 uint32_t key, uint32_t mask, uintptr_t value) 73 ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
74 uintptr_t value)
42 { 75 {
43 uint32_t bit; 76 uint32_t bit;
44 ngx_radix_node_t *node, *next; 77 ngx_radix_node_t *node, *next;
45 78
46 bit = 0x80000000; 79 bit = 0x80000000;
98 131
99 return NGX_OK; 132 return NGX_OK;
100 } 133 }
101 134
102 135
103 ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, 136 ngx_int_t
104 uint32_t key, uint32_t mask) 137 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
105 { 138 {
106 uint32_t bit; 139 uint32_t bit;
107 ngx_radix_node_t *node; 140 ngx_radix_node_t *node;
108 141
109 bit = 0x80000000; 142 bit = 0x80000000;
156 189
157 return NGX_OK; 190 return NGX_OK;
158 } 191 }
159 192
160 193
161 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) 194 uintptr_t
195 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
162 { 196 {
163 uint32_t bit; 197 uint32_t bit;
164 uintptr_t value; 198 uintptr_t value;
165 ngx_radix_node_t *node; 199 ngx_radix_node_t *node;
166 200
185 219
186 return value; 220 return value;
187 } 221 }
188 222
189 223
190 static void *ngx_radix_alloc(ngx_radix_tree_t *tree) 224 static void *
225 ngx_radix_alloc(ngx_radix_tree_t *tree)
191 { 226 {
192 char *p; 227 char *p;
193 228
194 if (tree->free) { 229 if (tree->free) {
195 p = (char *) tree->free; 230 p = (char *) tree->free;