diff options
author | Igor Sysoev <igor@sysoev.ru> | 2004-05-25 19:28:46 +0400 |
---|---|---|
committer | Igor Sysoev <igor@sysoev.ru> | 2004-05-25 19:28:46 +0400 |
commit | 822834e2274e6b2946ee758981ba0c261cedc69e (patch) | |
tree | e23bc338faf7188d8ec8fea941d812fa312af20f /src/core/ngx_radix_tree.c | |
parent | 01b5eab38147e84a1cde453059279c5ad7ad2293 (diff) |
nginx-0.0.3-2004-05-25-19:28:46 import
Diffstat (limited to 'src/core/ngx_radix_tree.c')
-rw-r--r-- | src/core/ngx_radix_tree.c | 152 |
1 files changed, 152 insertions, 0 deletions
diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c new file mode 100644 index 000000000..d2716e144 --- /dev/null +++ b/src/core/ngx_radix_tree.c @@ -0,0 +1,152 @@ + +#include <ngx_config.h> +#include <ngx_core.h> + + +/* STUB: page size */ +#define NGX_RADIX_TREE_POOL_SIZE 4096 + + +static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size); + + +ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool) +{ + ngx_radix_tree_t *tree; + + if (!(tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t)))) { + return NULL; + } + + tree->root = NULL; + tree->pool = pool; + tree->free = NULL; + tree->size = 0; + + return tree; +} + + +ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, + uint32_t key, uint32_t mask, uintptr_t value) +{ + uint32_t bit; + ngx_radix_node_t *node, *new; + + bit = 0x80000000; + node = tree->root; + + while (node && (bit & mask)) { + if (key & bit) { + node = node->right; + + } else { + node = node->left; + } + + bit >>= 1; + } + + if (node) { + if (node->value) { + return NGX_BUSY; + } + + node->value = value; + return NGX_OK; + } + + while (bit & mask) { + if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) { + return NGX_ERROR; + } + + new->value = value; + + if (key & bit) { + node->right = new; + + } else { + node->left = new; + } + + 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; + + bit = 0x80000000; + node = tree->root; + + while (node && (bit & mask)) { + if (key & bit) { + node = node->right; + + } else { + node = node->left; + } + + bit >>= 1; + } + + if (node) { + node->value = (uintptr_t) 0; + } +} + + +uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key) +{ + uint32_t bit; + uintptr_t value; + ngx_radix_node_t *node; + + bit = 0x80000000; + value = NULL; + node = tree->root; + + while (node) { + if (node->value) { + value = node->value; + } + + if (key & bit) { + node = node->right; + + } else { + node = node->left; + } + + bit >>= 1; + } + + return value; +} + + +static void *ngx_radix_alloc(ngx_radix_tree_t *tree, size_t size) +{ + char *p; + + if (tree->size < size) { + if (!(tree->free = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) { + return NULL; + } + + tree->size = NGX_RADIX_TREE_POOL_SIZE; + } + + p = tree->free; + tree->free += size; + tree->size -= size; + + return p; +} |