commit a20b6e64c1dcfcf5ef7a586586496bc9cb67051f
author Igor Sysoev <igor@sysoev.ru> Wed May 26 15:30:12 2004 +0000
committer Igor Sysoev <igor@sysoev.ru> Wed May 26 15:30:12 2004 +0000
tree 8c50ceadb4f6975c2f0e5f75be28dd2e75fe71fa
parent 822834e2274e6b2946ee758981ba0c261cedc69e

nginx-0.0.3-2004-05-26-19:30:12 import

src/core/ngx_radix_tree.c

diff --git a/src/core/ngx_radix_tree.c b/src/core/ngx_radix_tree.c
index d2716e1..0933fa4 100644
--- a/src/core/ngx_radix_tree.c
+++ b/src/core/ngx_radix_tree.c
@@ -21,6 +21,7 @@
     tree->root = NULL;
     tree->pool = pool;
     tree->free = NULL;
+    tree->start = NULL;
     tree->size = 0;
 
     return tree;
@@ -62,6 +63,8 @@
         }
 
         new->value = value;
+        new->right = NULL;
+        new->left = NULL;
 
         if (key & bit) {
             node->right = new;
@@ -81,16 +84,19 @@
 void ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
 {
     uint32_t           bit;
-    ngx_radix_node_t  *node;
+    ngx_radix_node_t  *node, **prev;
 
     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;
         }
 
@@ -98,7 +104,17 @@
     }
 
     if (node) {
-        node->value = (uintptr_t) 0;
+
+        /* the leaf nodes are moved to the free list only */
+
+        if (node->right == NULL && node->left == NULL) {
+            *prev = NULL;
+            node->right = tree->free;
+            tree->free = node;
+
+        } else {
+            node->value = (uintptr_t) 0;
+        }
     }
 }
 
@@ -110,7 +126,7 @@
     ngx_radix_node_t  *node;
 
     bit = 0x80000000;
-    value = NULL;
+    value = (uintptr_t) 0;
     node = tree->root;
 
     while (node) {
@@ -136,16 +152,22 @@
 {
     char  *p;
 
+    if (tree->free) {
+        p = (char *) tree->free;
+        tree->free = tree->free->right;
+        return p;
+    }
+
     if (tree->size < size) {
-        if (!(tree->free = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) {
+        if (!(tree->start = ngx_palloc(tree->pool, NGX_RADIX_TREE_POOL_SIZE))) {
             return NULL;
         }
 
         tree->size = NGX_RADIX_TREE_POOL_SIZE;
     }
 
-    p = tree->free;
-    tree->free += size;
+    p = tree->start;
+    tree->start += size;
     tree->size -= size;
 
     return p;

src/core/ngx_radix_tree.h

diff --git a/src/core/ngx_radix_tree.h b/src/core/ngx_radix_tree.h
index 6fe574b..a177b6d 100644
--- a/src/core/ngx_radix_tree.h
+++ b/src/core/ngx_radix_tree.h
@@ -18,7 +18,8 @@
 typedef struct {
     ngx_radix_node_t  *root;
     ngx_pool_t        *pool;
-    char              *free;
+    ngx_radix_node_t  *free;
+    char              *start;
     size_t             size;
 } ngx_radix_tree_t;