Geo: IPv6 support.

The "ranges" mode is still limited to IPv4 only.

1 files changed, 197 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)
 {