Mercurial > hg > nginx
view src/core/ngx_radix_tree.c @ 473:8e8f3af115b5 release-0.1.11
nginx-0.1.11-RELEASE import
*) Feature: the worker_priority directive.
*) Change: both tcp_nopush and tcp_nodelay directives affect the
transferred response.
*) Bugfix: nginx did not call initgroups().
Thanks to Andrew Sitnikov and Andrei Nigmatulin.
*) Change: now the ngx_http_autoindex_module shows the file size in the
bytes.
*) Bugfix: the ngx_http_autoindex_module returned the 500 error if the
broken symlink was in a directory.
*) Bugfix: the files bigger than 4G could not be transferred using
sendfile.
*) Bugfix: if the backend was resolved to several backends and there
was an error while the response waiting then process may got caught
in an endless loop.
*) Bugfix: the worker process may exit with the "unknown cycle" message
when the /dev/poll method was used.
*) Bugfix: "close() channel failed" errors.
*) Bugfix: the autodetection of the "nobody" and "nogroup" groups.
*) Bugfix: the send_lowat directive did not work on Linux.
*) Bugfix: the segmentation fault occurred if there was no events
section in configuration.
*) Bugfix: nginx could not be built on OpenBSD.
*) Bugfix: the double slashes in "://" in the URI were converted to
":/".
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Thu, 02 Dec 2004 18:40:46 +0000 |
parents | 42d11f017717 |
children | 4ebe09b07e30 |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev */ #include <ngx_config.h> #include <ngx_core.h> 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->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; } 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, *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; while (node && (bit & mask)) { if (key & bit) { node = node->right; } else { node = node->left; } bit >>= 1; } if (node == NULL) { return NGX_ERROR; } if (node->right || node->left) { node->value = (uintptr_t) 0; return NGX_OK; } 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 || node->value || node->parent == NULL) { break; } } return NGX_OK; } 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 = (uintptr_t) 0; 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->free) { p = (char *) tree->free; tree->free = tree->free->right; return p; } if (tree->size < size) { if (!(tree->start = ngx_palloc(tree->pool, ngx_pagesize))) { return NULL; } tree->size = ngx_pagesize; } p = tree->start; tree->start += size; tree->size -= size; return p; }