diff src/core/ngx_rbtree.c @ 826:4390fcad6628

undo the previous wrong commit
author Igor Sysoev <igor@sysoev.ru>
date Sat, 28 Oct 2006 14:32:39 +0000
parents f9b9b84a8e18
children 629b5e4f8931
line wrap: on
line diff
--- a/src/core/ngx_rbtree.c
+++ b/src/core/ngx_rbtree.c
@@ -47,7 +47,48 @@ ngx_rbtree_insert(ngx_thread_volatile ng
         return;
     }
 
-    tree->insert(*root, node, sentinel);
+    /*
+     * The rbtree is currently used by event timers only.  Timer values
+     * 1) are spread in small range, usually several minutes,
+     * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
+     * The below comparison takes into account that overflow.
+     *
+     * If there will be a necessity to use the rbtree for values with
+     * other comparison rules, then a whole "for ( ;; )" loop should
+     * be made as tree->insert() function.
+     */
+
+    temp = *root;
+
+    for ( ;; ) {
+
+        /*  node->key < temp->key */
+
+        if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
+            < 0)
+        {
+            if (temp->left == sentinel) {
+                temp->left = node;
+                break;
+            }
+
+            temp = temp->left;
+            continue;
+        }
+
+        if (temp->right == sentinel) {
+            temp->right = node;
+            break;
+        }
+
+        temp = temp->right;
+        continue;
+    }
+
+    node->parent = temp;
+    node->left = sentinel;
+    node->right = sentinel;
+
 
     /* re-balance tree */
 
@@ -95,6 +136,7 @@ ngx_rbtree_insert(ngx_thread_volatile ng
                 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
             }
         }
+
     }
 
     ngx_rbt_black(*root);
@@ -102,47 +144,6 @@ ngx_rbtree_insert(ngx_thread_volatile ng
 
 
 void
-ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
-    ngx_rbtree_node_t *sentinel)
-{
-    for ( ;; ) {
-
-        /*
-         * Timer values
-         * 1) are spread in small range, usually several minutes,
-         * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
-         * The comparison takes into account that overflow.
-         */
-
-        if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
-            < 0)
-        {
-            /*  node->key < temp->key */
-
-            if (temp->left == sentinel) {
-                temp->left = node;
-                break;
-            }
-
-            temp = temp->left;
-            continue;
-        }
-
-        if (temp->right == sentinel) {
-            temp->right = node;
-            break;
-        }
-
-        temp = temp->right;
-    }
-
-    node->parent = temp;
-    node->left = sentinel;
-    node->right = sentinel;
-}
-
-
-void
 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
     ngx_rbtree_node_t *node)
 {