Mercurial > hg > nginx
changeset 2368:62be1c4edfba radix_with_skip
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 | 6f76c9027e59 |
children | 12e8e0045096 |
files | src/core/ngx_radix_tree.c src/core/ngx_radix_tree.h |
diffstat | 2 files changed, 48 insertions(+), 43 deletions(-) [+] |
line wrap: on
line diff
--- a/src/core/ngx_radix_tree.c Wed Dec 03 13:16:33 2008 +0000 +++ b/src/core/ngx_radix_tree.c Wed Dec 03 13:23:07 2008 +0000 @@ -8,6 +8,8 @@ #include <ngx_core.h> +static ngx_int_t ngx_radix32tree_delete_node(ngx_radix_tree_t *tree, + uint32_t key, uint32_t mask, ngx_radix_node_t **pnode, uint32_t bit); static void *ngx_radix_alloc(ngx_radix_tree_t *tree); @@ -34,7 +36,7 @@ tree->root->right = NULL; tree->root->left = NULL; - tree->root->parent = NULL; + tree->root->skip = 0; tree->root->value = NGX_RADIX_NO_VALUE; if (preallocate == 0) { @@ -149,7 +151,7 @@ next->right = NULL; next->left = NULL; - next->parent = node; + next->skip = 0; next->value = NGX_RADIX_NO_VALUE; if (key & bit) { @@ -172,61 +174,64 @@ ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) { - uint32_t bit; + return ngx_radix32tree_delete_node(tree, key, mask, &tree->root, + 0x80000000); +} + + +static ngx_int_t +ngx_radix32tree_delete_node(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, + ngx_radix_node_t **pnode, uint32_t bit) +{ ngx_radix_node_t *node; - bit = 0x80000000; - node = tree->root; - - while (node && (bit & mask)) { - if (key & bit) { - node = node->right; - - } else { - node = node->left; - } - - bit >>= 1; - } + node = *pnode; if (node == NULL) { return NGX_ERROR; } - if (node->right || node->left) { - if (node->value != NGX_RADIX_NO_VALUE) { - node->value = NGX_RADIX_NO_VALUE; - return NGX_OK; + if ((bit & mask) == 0) { + + if (node->right || node->left) { + + if (node->value != NGX_RADIX_NO_VALUE) { + node->value = NGX_RADIX_NO_VALUE; + return NGX_OK; + } + + return NGX_ERROR; + + } else { + node->right = tree->free; + tree->free = node; + + *pnode = NULL; } + return NGX_OK; + } + + if (ngx_radix32tree_delete_node(tree, key, mask, + (key & bit) ? &node->right : &node->left, + bit >> 1) + != NGX_OK) + { return NGX_ERROR; } - for ( ;; ) { - if (node->parent->right == node) { - node->parent->right = NULL; - - } else { - node->parent->left = NULL; - } - - node->right = tree->free; - tree->free = node; - - node = node->parent; + if (node->right || node->left) { + return NGX_OK; + } - if (node->right || node->left) { - break; - } + if (node->value != NGX_RADIX_NO_VALUE) { + return NGX_OK; + } - if (node->value != NGX_RADIX_NO_VALUE) { - break; - } + node->right = tree->free; + tree->free = node; - if (node->parent == NULL) { - break; - } - } + *pnode = NULL; return NGX_OK; }