Mercurial > hg > nginx

comparison src/core/ngx_radix_tree.c @ 2369:12e8e0045096 radix_with_skip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add radix tree skip node
author Igor Sysoev <igor@sysoev.ru>
date Wed, 03 Dec 2008 13:26:02 +0000
parents 62be1c4edfba
children
comparison
equal deleted inserted replaced
2368:62be1c4edfba 2369:12e8e0045096
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, 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); 12 uint32_t key, uint32_t mask, ngx_radix_node_t **pnode, uint32_t bit);
13 void ngx_radix32tree_compress_node(ngx_radix_tree_t *tree,
14 ngx_radix_node_t *node);
13 static void *ngx_radix_alloc(ngx_radix_tree_t *tree); 15 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
14 16
15 17
16 ngx_radix_tree_t * 18 ngx_radix_tree_t *
17 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate) 19 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
26 28
27 tree->pool = pool; 29 tree->pool = pool;
28 tree->free = NULL; 30 tree->free = NULL;
29 tree->start = NULL; 31 tree->start = NULL;
30 tree->size = 0; 32 tree->size = 0;
33 tree->count = 0;
31 34
32 tree->root = ngx_radix_alloc(tree); 35 tree->root = ngx_radix_alloc(tree);
33 if (tree->root == NULL) { 36 if (tree->root == NULL) {
34 return NULL; 37 return NULL;
35 } 38 }
203 return NGX_ERROR; 206 return NGX_ERROR;
204 207
205 } else { 208 } else {
206 node->right = tree->free; 209 node->right = tree->free;
207 tree->free = node; 210 tree->free = node;
211 tree->count--;
208 212
209 *pnode = NULL; 213 *pnode = NULL;
210 } 214 }
211 215
212 return NGX_OK; 216 return NGX_OK;
228 return NGX_OK; 232 return NGX_OK;
229 } 233 }
230 234
231 node->right = tree->free; 235 node->right = tree->free;
232 tree->free = node; 236 tree->free = node;
237 tree->count--;
233 238
234 *pnode = NULL; 239 *pnode = NULL;
235 240
236 return NGX_OK; 241 return NGX_OK;
242 }
243
244
245 void
246 ngx_radix32tree_compress(ngx_radix_tree_t *tree)
247 {
248 if (tree->root) {
249 ngx_radix32tree_compress_node(tree, tree->root);
250 }
251 }
252
253
254 void
255 ngx_radix32tree_compress_node(ngx_radix_tree_t *tree, ngx_radix_node_t *node)
256 {
257 uintptr_t skip;
258 ngx_radix_node_t *n;
259
260 if (node->right) {
261
262 skip = 0;
263
264 for (n = node->right;
265 n->right && n->left == NULL && n->value == NGX_RADIX_NO_VALUE;
266 n = node->right)
267 {
268 node->right = n->right;
269
270 n->right = tree->free;
271 tree->free = n;
272 tree->count--;
273
274 skip++;
275 }
276
277 node->right->skip = skip;
278
279 ngx_radix32tree_compress_node(tree, node->right);
280 }
281
282 if (node->left) {
283
284 skip = 0;
285
286 for (n = node->left;
287 n->left && n->right == NULL && n->value == NGX_RADIX_NO_VALUE;
288 n = node->left)
289 {
290 node->left = n->left;
291
292 n->right = tree->free;
293 tree->free = n;
294 tree->count--;
295
296 skip++;
297 }
298
299 node->left->skip = skip;
300
301 ngx_radix32tree_compress_node(tree, node->left);
302 }
237 } 303 }
238 304
239 305
240 uintptr_t 306 uintptr_t
241 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) 307 ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
242 { 308 {
243 uint32_t bit; 309 uint32_t bit, test;
244 uintptr_t value; 310 uintptr_t value, skip;
245 ngx_radix_node_t *node; 311 ngx_radix_node_t *node;
246 312
247 bit = 0x80000000;
248 value = NGX_RADIX_NO_VALUE; 313 value = NGX_RADIX_NO_VALUE;
249 node = tree->root; 314 node = tree->root;
250 315
251 while (node) { 316 if (node == NULL) {
317 return NGX_RADIX_NO_VALUE;
318 }
319
320 bit = 0x80000000;
321
322 for ( ;; ) {
323
252 if (node->value != NGX_RADIX_NO_VALUE) { 324 if (node->value != NGX_RADIX_NO_VALUE) {
253 value = node->value; 325 value = node->value;
254 } 326 }
255 327
256 if (key & bit) { 328 if (key & bit) {
257 node = node->right; 329 node = node->right;
330 test = 0;
258 331
259 } else { 332 } else {
260 node = node->left; 333 node = node->left;
334 test = bit >> 1;
335 }
336
337 if (node == NULL) {
338 return value;
261 } 339 }
262 340
263 bit >>= 1; 341 bit >>= 1;
264 } 342
265 343 for (skip = node->skip; skip; skip--) {
266 return value; 344
345 if ((key & bit) == test) {
346 return value;
347 }
348
349 bit >>= 1;
350 test >>= 1;
351 }
352 }
267 } 353 }
268 354
269 355
270 static void * 356 static void *
271 ngx_radix_alloc(ngx_radix_tree_t *tree) 357 ngx_radix_alloc(ngx_radix_tree_t *tree)
273 char *p; 359 char *p;
274 360
275 if (tree->free) { 361 if (tree->free) {
276 p = (char *) tree->free; 362 p = (char *) tree->free;
277 tree->free = tree->free->right; 363 tree->free = tree->free->right;
364 tree->count++;
278 return p; 365 return p;
279 } 366 }
280 367
281 if (tree->size < sizeof(ngx_radix_node_t)) { 368 if (tree->size < sizeof(ngx_radix_node_t)) {
282 tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize); 369 tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
288 } 375 }
289 376
290 p = tree->start; 377 p = tree->start;
291 tree->start += sizeof(ngx_radix_node_t); 378 tree->start += sizeof(ngx_radix_node_t);
292 tree->size -= sizeof(ngx_radix_node_t); 379 tree->size -= sizeof(ngx_radix_node_t);
380 tree->count++;
293 381
294 return p; 382 return p;
295 } 383 }