nginx-vendor-current: src/core/ngx_radix

comparison src/core/ngx_radix_tree.c @ 694:88a1b4797f2e NGINX_1_3_10

nginx 1.3.10 *) Change: domain names specified in configuration file are now resolved to IPv6 addresses as well as IPv4 ones. *) Change: now if the "include" directive with mask is used on Unix systems, included files are sorted in alphabetical order. *) Change: the "add_header" directive adds headers to 201 responses. *) Feature: the "geo" directive now supports IPv6 addresses in CIDR notation. *) Feature: the "flush" and "gzip" parameters of the "access_log" directive. *) Feature: variables support in the "auth_basic" directive. *) Bugfix: nginx could not be built with the ngx_http_perl_module in some cases. *) Bugfix: a segmentation fault might occur in a worker process if the ngx_http_xslt_module was used. *) Bugfix: nginx could not be built on MacOSX in some cases. Thanks to Piotr Sikora. *) Bugfix: the "limit_rate" directive with high rates might result in truncated responses on 32-bit platforms. Thanks to Alexey Antropov. *) Bugfix: a segmentation fault might occur in a worker process if the "if" directive was used. Thanks to Piotr Sikora. *) Bugfix: a "100 Continue" response was issued with "413 Request Entity Too Large" responses. *) Bugfix: the "image_filter", "image_filter_jpeg_quality" and "image_filter_sharpen" directives might be inherited incorrectly. Thanks to Ian Babrou. *) Bugfix: "crypt_r() failed" errors might appear if the "auth_basic" directive was used on Linux. *) Bugfix: in backup servers handling. Thanks to Thomas Chen. *) Bugfix: proxied HEAD requests might return incorrect response if the "gzip" directive was used.

author	Igor Sysoev <http://sysoev.ru>
date	Tue, 25 Dec 2012 00:00:00 +0400
parents	660139fd80ca
children

comparison

equal deleted inserted replaced

-:cfd4279acc6e
+:88a1b4797f2e
 #include <ngx_config.h>
 #include <ngx_core.h>
-static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
+static ngx_radix_node_t *ngx_radix_alloc(ngx_radix_tree_t *tree);
 ngx_radix_tree_t *
 ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
 {
 return value;
 }
-static void *
+#if (NGX_HAVE_INET6)
+ngx_int_t
+ngx_radix128tree_insert(ngx_radix_tree_t *tree, u_char *key, u_char *mask,
+uintptr_t value)
+{
+u_char             bit;
+ngx_uint_t         i;
+ngx_radix_node_t  *node, *next;
+i = 0;
+bit = 0x80;
+node = tree->root;
+next = tree->root;
+while (bit & mask[i]) {
+if (key[i] & bit) {
+next = node->right;
+} else {
+next = node->left;
+}
+if (next == NULL) {
+break;
+}
+bit >>= 1;
+node = next;
+if (bit == 0) {
+if (++i == 16) {
+break;
+}
+bit = 0x80;
+}
+}
+if (next) {
+if (node->value != NGX_RADIX_NO_VALUE) {
+return NGX_BUSY;
+}
+node->value = value;
+return NGX_OK;
+}
+while (bit & mask[i]) {
+next = ngx_radix_alloc(tree);
+if (next == NULL) {
+return NGX_ERROR;
+}
+next->right = NULL;
+next->left = NULL;
+next->parent = node;
+next->value = NGX_RADIX_NO_VALUE;
+if (key[i] & bit) {
+node->right = next;
+} else {
+node->left = next;
+}
+bit >>= 1;
+node = next;
+if (bit == 0) {
+if (++i == 16) {
+break;
+}
+bit = 0x80;
+}
+}
+node->value = value;
+return NGX_OK;
+}
+ngx_int_t
+ngx_radix128tree_delete(ngx_radix_tree_t *tree, u_char *key, u_char *mask)
+{
+u_char             bit;
+ngx_uint_t         i;
+ngx_radix_node_t  *node;
+i = 0;
+bit = 0x80;
+node = tree->root;
+while (node && (bit & mask[i])) {
+if (key[i] & bit) {
+node = node->right;
+} else {
+node = node->left;
+}
+bit >>= 1;
+if (bit == 0) {
+if (++i == 16) {
+break;
+}
+bit = 0x80;
+}
+}
+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;
+}
+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) {
+break;
+}
+if (node->value != NGX_RADIX_NO_VALUE) {
+break;
+}
+if (node->parent == NULL) {
+break;
+}
+}
+return NGX_OK;
+}
+uintptr_t
+ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key)
+{
+u_char             bit;
+uintptr_t          value;
+ngx_uint_t         i;
+ngx_radix_node_t  *node;
+i = 0;
+bit = 0x80;
+value = NGX_RADIX_NO_VALUE;
+node = tree->root;
+while (node) {
+if (node->value != NGX_RADIX_NO_VALUE) {
+value = node->value;
+}
+if (key[i] & bit) {
+node = node->right;
+} else {
+node = node->left;
+}
+bit >>= 1;
+if (bit == 0) {
+i++;
+bit = 0x80;
+}
+}
+return value;
+}
+#endif
+static ngx_radix_node_t *
 ngx_radix_alloc(ngx_radix_tree_t *tree)
 {
-char  *p;
+ngx_radix_node_t  *p;
 if (tree->free) {
-p = (char *) tree->free;
+p = tree->free;
 tree->free = tree->free->right;
 return p;
 }
 if (tree->size < sizeof(ngx_radix_node_t)) {
 }
 tree->size = ngx_pagesize;
 }
-p = tree->start;
+p = (ngx_radix_node_t *) tree->start;
 tree->start += sizeof(ngx_radix_node_t);
 tree->size -= sizeof(ngx_radix_node_t);
 return p;
 }

Mercurial > hg > nginx-vendor-current

comparison src/core/ngx_radix_tree.c @ 694:88a1b4797f2e NGINX_1_3_10