Merge of r4993, r4994, r4997, r5000: geo ipv6 support.

*) Geo: IPv6 support.  The "ranges" mode is still limited to IPv4 only.

*) Geo: properly initialize ngx_cidr_t when dealing with "default".

*) Geo: made "default" affect both IPv4 and IPv6 when using prefixes.
   Previously, "default" was equivalent to specifying 0.0.0.0/0, now
   it's equivalent to specifying both 0.0.0.0/0 and ::/0 (if support
   for IPv6 is enabled) with the same value.

*) Geo: improved code readability.

2 files changed, 206 insertions, 0 deletions

diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c
index ad3b23811..c1d873749 100644
--- a/src/core/ngx_radix_tree.c
+++ b/src/core/ngx_radix_tree.c
@@ -263,6 +263,203 @@ ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
 }
 
 
+#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)
 {
diff --git a/src/core/ngx_radix_tree.h b/src/core/ngx_radix_tree.h
index 65ee69b26..4fe06e014 100644
--- a/src/core/ngx_radix_tree.h
+++ b/src/core/ngx_radix_tree.h
@@ -36,11 +36,20 @@ typedef struct {
 
 ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool,
     ngx_int_t preallocate);
+
 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
     uint32_t key, uint32_t mask, uintptr_t value);
 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);
 
+#if (NGX_HAVE_INET6)
+ngx_int_t ngx_radix128tree_insert(ngx_radix_tree_t *tree,
+    u_char *key, u_char *mask, uintptr_t value);
+ngx_int_t ngx_radix128tree_delete(ngx_radix_tree_t *tree,
+    u_char *key, u_char *mask);
+uintptr_t ngx_radix128tree_find(ngx_radix_tree_t *tree, u_char *key);
+#endif
+
 
 #endif /* _NGX_RADIX_TREE_H_INCLUDED_ */