nginx-0.0.1-2003-12-05-20:07:27 import

1 files changed, 43 insertions, 36 deletions

diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c
index ea78e2254..3e6025f12 100644
--- a/src/core/ngx_rbtree.c
+++ b/src/core/ngx_rbtree.c
@@ -15,23 +15,25 @@
 #define ngx_rbt_copy_color(n1, n2)  (n1->color = n2->color)
 
 
-ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node);
+ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root,
+                                       ngx_rbtree_t *sentinel,
+                                       ngx_rbtree_t *node);
 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root,
+                                        ngx_rbtree_t *sentinel,
                                         ngx_rbtree_t *node);
 
-ngx_rbtree_t  sentinel;
 
-
-void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
+void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel,
+                       ngx_rbtree_t *node)
 {
     ngx_rbtree_t  *temp;
 
     /* a binary tree insert */
 
-    if (*root == &sentinel) {
-        node->parent = &sentinel;
-        node->left = &sentinel;
-        node->right = &sentinel;
+    if (*root == sentinel) {
+        node->parent = sentinel;
+        node->left = sentinel;
+        node->right = sentinel;
         ngx_rbt_black(node);
         *root = node;
 
@@ -42,7 +44,7 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
 
     for ( ;; ) {
         if (node->key < temp->key) {
-            if (temp->left == &sentinel) {
+            if (temp->left == sentinel) {
                 temp->left = node;
                 break;
             }
@@ -51,7 +53,7 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
             continue;
         }
 
-        if (temp->right == &sentinel) {
+        if (temp->right == sentinel) {
             temp->right = node;
             break;
         }
@@ -61,8 +63,8 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
     }
 
     node->parent = temp;
-    node->left = &sentinel;
-    node->right = &sentinel;
+    node->left = sentinel;
+    node->right = sentinel;
 
 
     /* re-balance tree */
@@ -83,12 +85,12 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
             } else {
                 if (node == node->parent->right) {
                     node = node->parent;
-                    ngx_rbtree_left_rotate(root, node);
+                    ngx_rbtree_left_rotate(root, sentinel, node);
                 }
 
                 ngx_rbt_black(node->parent);
                 ngx_rbt_red(node->parent->parent);
-                ngx_rbtree_right_rotate(root, node->parent->parent);
+                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
             }
 
         } else {
@@ -103,12 +105,12 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
             } else {
                 if (node == node->parent->left) {
                     node = node->parent;
-                    ngx_rbtree_right_rotate(root, node);
+                    ngx_rbtree_right_rotate(root, sentinel, node);
                 }
 
                 ngx_rbt_black(node->parent);
                 ngx_rbt_red(node->parent->parent);
-                ngx_rbtree_left_rotate(root, node->parent->parent);
+                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
             }
         }
 
@@ -118,34 +120,35 @@ void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
 }
 
 
-void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
+void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel,
+                       ngx_rbtree_t *node)
 {
     ngx_rbtree_t  *subst, *temp, *w;
 
     /* a binary tree delete */
 
-    if (node->left == &sentinel || node->right == &sentinel) {
+    if (node->left == sentinel || node->right == sentinel) {
         subst = node;
 
     } else {
 
         /* find a node successor */
 
-        if (node->right == &sentinel) {
+        if (node->right == sentinel) {
             temp = node;
             subst = node->parent;
 
-            while (subst != &sentinel && temp == subst->right) {
+            while (subst != sentinel && temp == subst->right) {
                  temp = subst;
                  subst = subst->parent;
             }
 
         } else {
-            subst = ngx_rbtree_min(node->right);
+            subst = ngx_rbtree_min(node->right, sentinel);
         }
     }
 
-    if (subst->left != &sentinel) {
+    if (subst->left != sentinel) {
         temp = subst->left;
     } else {
         temp = subst->right;
@@ -153,7 +156,7 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
 
     temp->parent = subst->parent;
 
-    if (subst->parent == &sentinel) {
+    if (subst->parent == sentinel) {
         *root = temp;
 
     } else if (subst == subst->parent->left) {
@@ -174,14 +177,14 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
 
     /* a delete fixup */
 
-    while (temp->parent != &sentinel && ngx_rbt_is_black(temp)) {
+    while (temp->parent != sentinel && ngx_rbt_is_black(temp)) {
         if (temp == temp->parent->left) {
             w = temp->parent->right;
 
             if (ngx_rbt_is_red(w)) {
                 ngx_rbt_black(w);
                 ngx_rbt_red(temp->parent);
-                ngx_rbtree_left_rotate(root, temp->parent);
+                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                 w = temp->parent->right;
             }
 
@@ -193,14 +196,14 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
                 if (ngx_rbt_is_black(w->right)) {
                     ngx_rbt_black(w->left);
                     ngx_rbt_red(w);
-                    ngx_rbtree_right_rotate(root, w);
+                    ngx_rbtree_right_rotate(root, sentinel, w);
                     w = temp->parent->right;
                 }
 
                 ngx_rbt_copy_color(w, temp->parent);
                 ngx_rbt_black(temp->parent);
                 ngx_rbt_black(w->right);
-                ngx_rbtree_left_rotate(root, temp->parent);
+                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                 temp = *root;
             }
 
@@ -210,7 +213,7 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
             if (ngx_rbt_is_red(w)) {
                 ngx_rbt_black(w);
                 ngx_rbt_red(temp->parent);
-                ngx_rbtree_right_rotate(root, temp->parent);
+                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                 w = temp->parent->left;
             }
 
@@ -222,14 +225,14 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
                 if (ngx_rbt_is_black(w->left)) {
                     ngx_rbt_black(w->right);
                     ngx_rbt_red(w);
-                    ngx_rbtree_left_rotate(root, w);
+                    ngx_rbtree_left_rotate(root, sentinel, w);
                     w = temp->parent->left;
                 }
 
                 ngx_rbt_copy_color(w, temp->parent);
                 ngx_rbt_black(temp->parent);
                 ngx_rbt_black(w->left);
-                ngx_rbtree_right_rotate(root, temp->parent);
+                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
                 temp = *root;
             }
         }
@@ -239,20 +242,22 @@ void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
 }
 
 
-ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
+ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root,
+                                       ngx_rbtree_t *sentinel,
+                                       ngx_rbtree_t *node)
 {
     ngx_rbtree_t  *temp;
 
     temp = node->right;
     node->right = temp->left;
 
-    if (temp->left != &sentinel) {
+    if (temp->left != sentinel) {
         temp->left->parent = node;
     }
 
     temp->parent = node->parent;
 
-    if (node->parent == &sentinel) {
+    if (node->parent == sentinel) {
         *root = temp;
 
     } else if (node == node->parent->left) {
@@ -267,20 +272,22 @@ ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
 }
 
 
-ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
+ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root,
+                                        ngx_rbtree_t *sentinel,
+                                        ngx_rbtree_t *node)
 {
     ngx_rbtree_t  *temp;
 
     temp = node->left;
     node->left = temp->right;
 
-    if (temp->right != &sentinel) {
+    if (temp->right != sentinel) {
         temp->right->parent = node;
     }
 
     temp->parent = node->parent;
 
-    if (node->parent == &sentinel) {
+    if (node->parent == sentinel) {
         *root = temp;
 
     } else if (node == node->parent->right) {