Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 485:4ebe09b07e30 release-0.1.17

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }