Mercurial > hg > nginx-vendor-current

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
line wrap: on
line diff
--- a/src/core/ngx_radix_tree.c
+++ b/src/core/ngx_radix_tree.c
@@ -9,7 +9,7 @@
 #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 *
@@ -263,13 +263,210 @@ ngx_radix32tree_find(ngx_radix_tree_t *t
 }
 
 
-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;
     }
@@ -283,7 +480,7 @@ ngx_radix_alloc(ngx_radix_tree_t *tree)
         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);