commit 87a7d1c44917e352e336c859c2a797e5d60b19da
author Igor Sysoev <igor@sysoev.ru> Wed May 26 19:33:53 2004 +0000
committer Igor Sysoev <igor@sysoev.ru> Wed May 26 19:33:53 2004 +0000
tree ce757c2ef98f779ac86a6cd528264bde32699e9e
parent a20b6e64c1dcfcf5ef7a586586496bc9cb67051f

nginx-0.0.3-2004-05-26-23:33:53 import

src/core/ngx_radix_tree.c

diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c
index 0933fa4..b63be1f 100644
--- a/src/core/ngx_radix_tree.c
+++ b/src/core/ngx_radix_tree.c
@@ -18,12 +18,20 @@
         return NULL;
     }
 
-    tree->root = NULL;
     tree->pool = pool;
     tree->free = NULL;
     tree->start = NULL;
     tree->size = 0;
 
+    if (!(tree->root = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) {
+        return NULL;
+    }
+
+    tree->root->value = (uintptr_t) 0;
+    tree->root->right = NULL;
+    tree->root->left = NULL;
+    tree->root->parent = NULL;
+
     return tree;
 }
 
@@ -32,23 +40,30 @@
                                  uint32_t key, uint32_t mask, uintptr_t value)
 {
     uint32_t           bit;
-    ngx_radix_node_t  *node, *new;
+    ngx_radix_node_t  *node, *next;
 
     bit = 0x80000000;
     node = tree->root;
+    next = NULL;
 
-    while (node && (bit & mask)) {
+    while (bit & mask) {
         if (key & bit) {
-            node = node->right;
+            next = node->right;
 
         } else {
-            node = node->left;
+            next = node->left;
         }
 
         bit >>= 1;
+
+        if (next == NULL) {
+            break;
+        }
+
+        node = next;
     }
 
-    if (node) {
+    if (next) {
         if (node->value) {
             return NGX_BUSY;
         }
@@ -58,64 +73,77 @@
     }
 
     while (bit & mask) {
-        if (!(new = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) {
+        if (!(next = ngx_radix_alloc(tree, sizeof(ngx_radix_node_t)))) {
             return NGX_ERROR;
         }
 
-        new->value = value;
-        new->right = NULL;
-        new->left = NULL;
+        next->value = value;
+        next->right = NULL;
+        next->left = NULL;
+        next->parent = node;
 
         if (key & bit) {
-            node->right = new;
+            node->right = next;
 
         } else {
-            node->left = new;
+            node->left = next;
         }
 
         bit >>= 1;
-        new = node;
+        node = next;
     }
 
     return NGX_OK;
 }
 
 
-void ngx_radix32tree_delete(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, **prev;
+    ngx_radix_node_t  *node;
 
     bit = 0x80000000;
     node = tree->root;
-    prev = NULL;
 
     while (node && (bit & mask)) {
         if (key & bit) {
-            prev = &node->right;;
             node = node->right;
 
         } else {
-            prev = &node->left;;
             node = node->left;
         }
 
         bit >>= 1;
     }
 
-    if (node) {
+    if (node == NULL) {
+        return NGX_ERROR;
+    }
 
-        /* the leaf nodes are moved to the free list only */
+    if (node->right || node->left) {
+        node->value = (uintptr_t) 0;
+        return NGX_OK;
+    }
 
-        if (node->right == NULL && node->left == NULL) {
-            *prev = NULL;
-            node->right = tree->free;
-            tree->free = node;
-
+    for ( ;; ) {
+        if (node->parent->right == node) {
+            node->parent->right = NULL;
         } else {
-            node->value = (uintptr_t) 0;
+            node->parent->left = NULL;
+        }
+
+        node->right = tree->free;
+        tree->free = node;
+
+        node = node->parent;
+
+        if (node->right || node->left || node->value || node->parent == NULL) {
+            break;
         }
     }
+
+    return NGX_OK;
 }
 
 

src/core/ngx_radix_tree.h

diff --git a/src/core/ngx_radix_tree.h b/src/core/ngx_radix_tree.h
index a177b6d..a5b8c62 100644
--- a/src/core/ngx_radix_tree.h
+++ b/src/core/ngx_radix_tree.h
@@ -9,9 +9,10 @@
 typedef struct ngx_radix_node_s  ngx_radix_node_t;
 
 struct ngx_radix_node_s {
-    uintptr_t          value;
     ngx_radix_node_t  *right;
     ngx_radix_node_t  *left;
+    ngx_radix_node_t  *parent;
+    uintptr_t          value;
 };
 
 
@@ -27,8 +28,8 @@
 ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool);
 ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree,
                                  uint32_t key, uint32_t mask, uintptr_t value);
-void ngx_radix32tree_delete(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);
 uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key);