Mercurial > hg > nginx
changeset 342:0ee0642af5f1
nginx-0.0.3-2004-05-26-23:33:53 import
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Wed, 26 May 2004 19:33:53 +0000 |
parents | 41e552841296 |
children | 6bdf858bff8c |
files | src/core/ngx_radix_tree.c src/core/ngx_radix_tree.h |
diffstat | 2 files changed, 91 insertions(+), 62 deletions(-) [+] |
line wrap: on
line diff
--- a/src/core/ngx_radix_tree.c Wed May 26 15:30:12 2004 +0000 +++ b/src/core/ngx_radix_tree.c Wed May 26 19:33:53 2004 +0000 @@ -18,12 +18,20 @@ return NULL; } - tree->root = NULL; tree->pool = pool; tree->free = NULL; tree->start = NULL; tree->size = 0; + if (!(tree->root = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { + return NULL; + } + + tree->root->value = (uintptr_t) 0; + tree->root->right = NULL; + tree->root->left = NULL; + tree->root->parent = NULL; + return tree; } @@ -32,7 +40,68 @@ uint32_t key, uint32_t mask, uintptr_t value) { uint32_t bit; - ngx_radix_node_t *node, *new; + ngx_radix_node_t *node, *next; + + bit = 0x80000000; + node = tree->root; + next = NULL; + + while (bit & mask) { + if (key & bit) { + next = node->right; + + } else { + next = node->left; + } + + bit >>= 1; + + if (next == NULL) { + break; + } + + node = next; + } + + if (next) { + if (node->value) { + return NGX_BUSY; + } + + node->value = value; + return NGX_OK; + } + + while (bit & mask) { + if (!(next = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { + return NGX_ERROR; + } + + next->value = value; + next->right = NULL; + next->left = NULL; + next->parent = node; + + if (key & bit) { + node->right = next; + + } else { + node->left = next; + } + + bit >>= 1; + node = next; + } + + return NGX_OK; +} + + +ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, + uint32_t key, uint32_t mask) +{ + uint32_t bit; + ngx_radix_node_t *node; bit = 0x80000000; node = tree->root; @@ -48,77 +117,36 @@ bit >>= 1; } - if (node) { - if (node->value) { - return NGX_BUSY; - } + if (node == NULL) { + return NGX_ERROR; + } - node->value = value; + if (node->right || node->left) { + node->value = (uintptr_t) 0; return NGX_OK; } - while (bit & mask) { - if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { - return NGX_ERROR; + for ( ;; ) { + if (node->parent->right == node) { + node->parent->right = NULL; + } else { + node->parent->left = NULL; } - new->value = value; - new->right = NULL; - new->left = NULL; - - if (key & bit) { - node->right = new; + node->right = tree->free; + tree->free = node; - } else { - node->left = new; + node = node->parent; + + if (node->right || node->left || node->value || node->parent == NULL) { + break; } - - bit >>= 1; - new = node; } return NGX_OK; } -void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask) -{ - uint32_t bit; - ngx_radix_node_t *node, **prev; - - bit = 0x80000000; - node = tree->root; - prev = NULL; - - while (node && (bit & mask)) { - if (key & bit) { - prev = &node->right;; - node = node->right; - - } else { - prev = &node->left;; - node = node->left; - } - - bit >>= 1; - } - - if (node) { - - /* the leaf nodes are moved to the free list only */ - - if (node->right == NULL && node->left == NULL) { - *prev = NULL; - node->right = tree->free; - tree->free = node; - - } else { - node->value = (uintptr_t) 0; - } - } -} - - uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) { uint32_t bit;
--- a/src/core/ngx_radix_tree.h Wed May 26 15:30:12 2004 +0000 +++ b/src/core/ngx_radix_tree.h Wed May 26 19:33:53 2004 +0000 @@ -9,9 +9,10 @@ typedef struct ngx_radix_node_s ngx_radix_node_t; struct ngx_radix_node_s { - uintptr_t value; ngx_radix_node_t *right; ngx_radix_node_t *left; + ngx_radix_node_t *parent; + uintptr_t value; }; @@ -27,8 +28,8 @@ ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool); ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, uintptr_t value); -void ngx_radix32tree_delete(ngx_radix_tree_t *tree, - uint32_t key, uint32_t mask); +ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, + uint32_t key, uint32_t mask); uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key);