Mercurial > hg > nginx
comparison 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 |
comparison
equal
deleted
inserted
replaced
486:d4ddc4c6f97c | 487:31ff3e943e16 |
---|---|
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; |