Mercurial > hg > nginx-quic
comparison src/core/ngx_radix_tree.c @ 485:4ebe09b07e30 release-0.1.17
nginx-0.1.17-RELEASE import
*) Change: the ngx_http_rewrite_module was rewritten from the scratch.
Now it is possible to redirect, to return the error codes, to check
the variables and referrers. The directives can be used inside
locations. The redirect directive was canceled.
*) Feature: the ngx_http_geo_module.
*) Feature: the proxy_set_x_var and fastcgi_set_var directives.
*) Bugfix: the location configuration with "=" modifier may be used in
another location.
*) Bugfix: the correct content type was set only for requests that use
small caps letters in extension.
*) Bugfix: if the proxy_pass or fastcgi_pass directives were set in the
location, and access was denied, and the error was redirected to a
static page, then the segmentation fault occurred.
*) Bugfix: if in a proxied "Location" header was a relative URL, then a
host name and a slash were added to them; the bug had appeared in
0.1.14.
*) Bugfix: the system error message was not logged on Linux.
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Thu, 03 Feb 2005 19:33:37 +0000 |
parents | 42d11f017717 |
children | 31ff3e943e16 |
comparison
equal
deleted
inserted
replaced
484:60452f1c0c62 | 485:4ebe09b07e30 |
---|---|
6 | 6 |
7 #include <ngx_config.h> | 7 #include <ngx_config.h> |
8 #include <ngx_core.h> | 8 #include <ngx_core.h> |
9 | 9 |
10 | 10 |
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size); | 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 *ngx_radix_tree_create(ngx_pool_t *pool) |
15 { | 15 { |
16 ngx_radix_tree_t *tree; | 16 ngx_radix_tree_t *tree; |
22 tree->pool = pool; | 22 tree->pool = pool; |
23 tree->free = NULL; | 23 tree->free = NULL; |
24 tree->start = NULL; | 24 tree->start = NULL; |
25 tree->size = 0; | 25 tree->size = 0; |
26 | 26 |
27 if (!(tree->root = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { | 27 if (!(tree->root = ngx_radix_alloc(tree))) { |
28 return NULL; | 28 return NULL; |
29 } | 29 } |
30 | 30 |
31 tree->root->value = (uintptr_t) 0; | |
32 tree->root->right = NULL; | 31 tree->root->right = NULL; |
33 tree->root->left = NULL; | 32 tree->root->left = NULL; |
34 tree->root->parent = NULL; | 33 tree->root->parent = NULL; |
34 tree->root->value = NGX_RADIX_NO_VALUE; | |
35 | 35 |
36 return tree; | 36 return tree; |
37 } | 37 } |
38 | 38 |
39 | 39 |
42 { | 42 { |
43 uint32_t bit; | 43 uint32_t bit; |
44 ngx_radix_node_t *node, *next; | 44 ngx_radix_node_t *node, *next; |
45 | 45 |
46 bit = 0x80000000; | 46 bit = 0x80000000; |
47 | |
47 node = tree->root; | 48 node = tree->root; |
48 next = NULL; | 49 next = tree->root; |
49 | 50 |
50 while (bit & mask) { | 51 while (bit & mask) { |
51 if (key & bit) { | 52 if (key & bit) { |
52 next = node->right; | 53 next = node->right; |
53 | 54 |
54 } else { | 55 } else { |
55 next = node->left; | 56 next = node->left; |
56 } | 57 } |
57 | |
58 bit >>= 1; | |
59 | 58 |
60 if (next == NULL) { | 59 if (next == NULL) { |
61 break; | 60 break; |
62 } | 61 } |
63 | 62 |
63 bit >>= 1; | |
64 node = next; | 64 node = next; |
65 } | 65 } |
66 | 66 |
67 if (next) { | 67 if (next) { |
68 if (node->value) { | 68 if (node->value != NGX_RADIX_NO_VALUE) { |
69 return NGX_BUSY; | 69 return NGX_BUSY; |
70 } | 70 } |
71 | 71 |
72 node->value = value; | 72 node->value = value; |
73 return NGX_OK; | 73 return NGX_OK; |
74 } | 74 } |
75 | 75 |
76 while (bit & mask) { | 76 while (bit & mask) { |
77 if (!(next = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { | 77 if (!(next = ngx_radix_alloc(tree))) { |
78 return NGX_ERROR; | 78 return NGX_ERROR; |
79 } | 79 } |
80 | 80 |
81 next->value = value; | |
82 next->right = NULL; | 81 next->right = NULL; |
83 next->left = NULL; | 82 next->left = NULL; |
84 next->parent = node; | 83 next->parent = node; |
84 next->value = NGX_RADIX_NO_VALUE; | |
85 | 85 |
86 if (key & bit) { | 86 if (key & bit) { |
87 node->right = next; | 87 node->right = next; |
88 | 88 |
89 } else { | 89 } else { |
91 } | 91 } |
92 | 92 |
93 bit >>= 1; | 93 bit >>= 1; |
94 node = next; | 94 node = next; |
95 } | 95 } |
96 | |
97 node->value = value; | |
96 | 98 |
97 return NGX_OK; | 99 return NGX_OK; |
98 } | 100 } |
99 | 101 |
100 | 102 |
121 if (node == NULL) { | 123 if (node == NULL) { |
122 return NGX_ERROR; | 124 return NGX_ERROR; |
123 } | 125 } |
124 | 126 |
125 if (node->right || node->left) { | 127 if (node->right || node->left) { |
126 node->value = (uintptr_t) 0; | 128 if (node->value != NGX_RADIX_NO_VALUE) { |
127 return NGX_OK; | 129 node->value = NGX_RADIX_NO_VALUE; |
130 return NGX_OK; | |
131 } | |
132 | |
133 return NGX_ERROR; | |
128 } | 134 } |
129 | 135 |
130 for ( ;; ) { | 136 for ( ;; ) { |
131 if (node->parent->right == node) { | 137 if (node->parent->right == node) { |
132 node->parent->right = NULL; | 138 node->parent->right = NULL; |
137 node->right = tree->free; | 143 node->right = tree->free; |
138 tree->free = node; | 144 tree->free = node; |
139 | 145 |
140 node = node->parent; | 146 node = node->parent; |
141 | 147 |
142 if (node->right || node->left || node->value || node->parent == NULL) { | 148 if (node->right |
149 || node->left | |
150 || node->value != NGX_RADIX_NO_VALUE | |
151 || node->parent == NULL) | |
152 { | |
143 break; | 153 break; |
144 } | 154 } |
145 } | 155 } |
146 | 156 |
147 return NGX_OK; | 157 return NGX_OK; |
153 uint32_t bit; | 163 uint32_t bit; |
154 uintptr_t value; | 164 uintptr_t value; |
155 ngx_radix_node_t *node; | 165 ngx_radix_node_t *node; |
156 | 166 |
157 bit = 0x80000000; | 167 bit = 0x80000000; |
158 value = (uintptr_t) 0; | 168 value = NGX_RADIX_NO_VALUE; |
159 node = tree->root; | 169 node = tree->root; |
160 | 170 |
161 while (node) { | 171 while (node) { |
162 if (node->value) { | 172 if (node->value != NGX_RADIX_NO_VALUE) { |
163 value = node->value; | 173 value = node->value; |
164 } | 174 } |
165 | 175 |
166 if (key & bit) { | 176 if (key & bit) { |
167 node = node->right; | 177 node = node->right; |
175 | 185 |
176 return value; | 186 return value; |
177 } | 187 } |
178 | 188 |
179 | 189 |
180 static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size) | 190 static void *ngx_radix_alloc(ngx_radix_tree_t *tree) |
181 { | 191 { |
182 char *p; | 192 char *p; |
183 | 193 |
184 if (tree->free) { | 194 if (tree->free) { |
185 p = (char *) tree->free; | 195 p = (char *) tree->free; |
186 tree->free = tree->free->right; | 196 tree->free = tree->free->right; |
187 return p; | 197 return p; |
188 } | 198 } |
189 | 199 |
190 if (tree->size < size) { | 200 if (tree->size < sizeof(ngx_radix_node_t)) { |
191 if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) { | 201 if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) { |
192 return NULL; | 202 return NULL; |
193 } | 203 } |
194 | 204 |
195 tree->size = ngx_pagesize; | 205 tree->size = ngx_pagesize; |
196 } | 206 } |
197 | 207 |
198 p = tree->start; | 208 p = tree->start; |
199 tree->start += size; | 209 tree->start += sizeof(ngx_radix_node_t); |
200 tree->size -= size; | 210 tree->size -= sizeof(ngx_radix_node_t); |
201 | 211 |
202 return p; | 212 return p; |
203 } | 213 } |