From 36de6230cc3f0e3dec75951ad8e8109f9b7a829c Mon Sep 17 00:00:00 2001
From: Igor Sysoev <igor@sysoev.ru>
Date: Wed, 3 Dec 2008 13:23:07 +0000
Subject: [PATCH] remove parent from radix tree node to add skip field

---
 src/core/ngx_radix_tree.c | 83 +++++++++++++++++++++------------------
 src/core/ngx_radix_tree.h |  2 +-
 2 files changed, 45 insertions(+), 40 deletions(-)

diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c
index f339e6fab..9a368ca1a 100644
--- a/src/core/ngx_radix_tree.c
+++ b/src/core/ngx_radix_tree.c
@@ -8,6 +8,8 @@
 #include <ngx_core.h>
 
 
+static ngx_int_t ngx_radix32tree_delete_node(ngx_radix_tree_t *tree,
+    uint32_t key, uint32_t mask, ngx_radix_node_t **pnode, uint32_t bit);
 static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
 
 
@@ -34,7 +36,7 @@ ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
 
     tree->root->right = NULL;
     tree->root->left = NULL;
-    tree->root->parent = NULL;
+    tree->root->skip = 0;
     tree->root->value = NGX_RADIX_NO_VALUE;
 
     if (preallocate == 0) {
@@ -149,7 +151,7 @@ ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
 
         next->right = NULL;
         next->left = NULL;
-        next->parent = node;
+        next->skip = 0;
         next->value = NGX_RADIX_NO_VALUE;
 
         if (key & bit) {
@@ -172,62 +174,65 @@ ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
 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;
+    return ngx_radix32tree_delete_node(tree, key, mask, &tree->root,
+                                       0x80000000);
+}
 
-    bit = 0x80000000;
-    node = tree->root;
 
-    while (node && (bit & mask)) {
-        if (key & bit) {
-            node = node->right;
-
-        } else {
-            node = node->left;
-        }
+static ngx_int_t
+ngx_radix32tree_delete_node(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
+    ngx_radix_node_t **pnode, uint32_t bit)
+{
+    ngx_radix_node_t  *node;
 
-        bit >>= 1;
-    }
+    node = *pnode;
 
     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;
-        }
+    if ((bit & mask) == 0) {
 
-        return NGX_ERROR;
-    }
+        if (node->right || node->left) {
+
+            if (node->value != NGX_RADIX_NO_VALUE) {
+                node->value = NGX_RADIX_NO_VALUE;
+                return NGX_OK;
+            }
 
-    for ( ;; ) {
-        if (node->parent->right == node) {
-            node->parent->right = NULL;
+            return NGX_ERROR;
 
         } else {
-            node->parent->left = NULL;
-        }
+            node->right = tree->free;
+            tree->free = node;
 
-        node->right = tree->free;
-        tree->free = node;
+            *pnode = NULL;
+        }
 
-        node = node->parent;
+        return NGX_OK;
+    }
 
-        if (node->right || node->left) {
-            break;
-        }
+    if (ngx_radix32tree_delete_node(tree, key, mask,
+                                    (key & bit) ? &node->right : &node->left,
+                                    bit >> 1)
+        != NGX_OK)
+    {
+        return NGX_ERROR;
+    }
 
-        if (node->value != NGX_RADIX_NO_VALUE) {
-            break;
-        }
+    if (node->right || node->left) {
+        return NGX_OK;
+    }
 
-        if (node->parent == NULL) {
-            break;
-        }
+    if (node->value != NGX_RADIX_NO_VALUE) {
+        return NGX_OK;
     }
 
+    node->right = tree->free;
+    tree->free = node;
+
+    *pnode = NULL;
+
     return NGX_OK;
 }
 
diff --git a/src/core/ngx_radix_tree.h b/src/core/ngx_radix_tree.h
index 02a9f383b..c5bdd9875 100644
--- a/src/core/ngx_radix_tree.h
+++ b/src/core/ngx_radix_tree.h
@@ -19,7 +19,7 @@ typedef struct ngx_radix_node_s  ngx_radix_node_t;
 struct ngx_radix_node_s {
     ngx_radix_node_t  *right;
     ngx_radix_node_t  *left;
-    ngx_radix_node_t  *parent;
+    ngx_uint_t         skip;
     uintptr_t          value;
 };
 
-- 
2.47.3