Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 2368:62be1c4edfba radix_with_skip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove parent from radix tree node to add skip field
author Igor Sysoev <igor@sysoev.ru>
date Wed, 03 Dec 2008 13:23:07 +0000
parents 3aa4fd0e7dc5
children 12e8e0045096
comparison
equal deleted inserted replaced
2367:6f76c9027e59 2368:62be1c4edfba
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 ngx_int_t ngx_radix32tree_delete_node(ngx_radix_tree_t *tree,
12 uint32_t key, uint32_t mask, ngx_radix_node_t **pnode, uint32_t bit);
11 static void *ngx_radix_alloc(ngx_radix_tree_t *tree); 13 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
12 14
13 15
14 ngx_radix_tree_t * 16 ngx_radix_tree_t *
15 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate) 17 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
32 return NULL; 34 return NULL;
33 } 35 }
34 36
35 tree->root->right = NULL; 37 tree->root->right = NULL;
36 tree->root->left = NULL; 38 tree->root->left = NULL;
37 tree->root->parent = NULL; 39 tree->root->skip = 0;
38 tree->root->value = NGX_RADIX_NO_VALUE; 40 tree->root->value = NGX_RADIX_NO_VALUE;
39 41
40 if (preallocate == 0) { 42 if (preallocate == 0) {
41 return tree; 43 return tree;
42 } 44 }
147 return NGX_ERROR; 149 return NGX_ERROR;
148 } 150 }
149 151
150 next->right = NULL; 152 next->right = NULL;
151 next->left = NULL; 153 next->left = NULL;
152 next->parent = node; 154 next->skip = 0;
153 next->value = NGX_RADIX_NO_VALUE; 155 next->value = NGX_RADIX_NO_VALUE;
154 156
155 if (key & bit) { 157 if (key & bit) {
156 node->right = next; 158 node->right = next;
157 159
170 172
171 173
172 ngx_int_t 174 ngx_int_t
173 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) 175 ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
174 { 176 {
175 uint32_t bit; 177 return ngx_radix32tree_delete_node(tree, key, mask, &tree->root,
178 0x80000000);
179 }
180
181
182 static ngx_int_t
183 ngx_radix32tree_delete_node(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
184 ngx_radix_node_t **pnode, uint32_t bit)
185 {
176 ngx_radix_node_t *node; 186 ngx_radix_node_t *node;
177 187
178 bit = 0x80000000; 188 node = *pnode;
179 node = tree->root;
180
181 while (node && (bit & mask)) {
182 if (key & bit) {
183 node = node->right;
184
185 } else {
186 node = node->left;
187 }
188
189 bit >>= 1;
190 }
191 189
192 if (node == NULL) { 190 if (node == NULL) {
193 return NGX_ERROR; 191 return NGX_ERROR;
194 } 192 }
195 193
194 if ((bit & mask) == 0) {
195
196 if (node->right || node->left) {
197
198 if (node->value != NGX_RADIX_NO_VALUE) {
199 node->value = NGX_RADIX_NO_VALUE;
200 return NGX_OK;
201 }
202
203 return NGX_ERROR;
204
205 } else {
206 node->right = tree->free;
207 tree->free = node;
208
209 *pnode = NULL;
210 }
211
212 return NGX_OK;
213 }
214
215 if (ngx_radix32tree_delete_node(tree, key, mask,
216 (key & bit) ? &node->right : &node->left,
217 bit >> 1)
218 != NGX_OK)
219 {
220 return NGX_ERROR;
221 }
222
196 if (node->right || node->left) { 223 if (node->right || node->left) {
197 if (node->value != NGX_RADIX_NO_VALUE) { 224 return NGX_OK;
198 node->value = NGX_RADIX_NO_VALUE; 225 }
199 return NGX_OK; 226
200 } 227 if (node->value != NGX_RADIX_NO_VALUE) {
201 228 return NGX_OK;
202 return NGX_ERROR; 229 }
203 } 230
204 231 node->right = tree->free;
205 for ( ;; ) { 232 tree->free = node;
206 if (node->parent->right == node) { 233
207 node->parent->right = NULL; 234 *pnode = NULL;
208
209 } else {
210 node->parent->left = NULL;
211 }
212
213 node->right = tree->free;
214 tree->free = node;
215
216 node = node->parent;
217
218 if (node->right || node->left) {
219 break;
220 }
221
222 if (node->value != NGX_RADIX_NO_VALUE) {
223 break;
224 }
225
226 if (node->parent == NULL) {
227 break;
228 }
229 }
230 235
231 return NGX_OK; 236 return NGX_OK;
232 } 237 }
233 238
234 239