nginx-0.0.1-2003-12-04-17:53:00 import

1 files changed, 296 insertions, 0 deletions

diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c
new file mode 100644
index 000000000..2bc4650f0
--- /dev/null
+++ b/src/core/ngx_rbtree.c
@@ -0,0 +1,296 @@
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+/*
+ * The code is based on the algorithm described in the "Introduction
+ * to Algorithms" by Cormen, Leiserson and Rivest.
+ */
+
+#define ngx_rbt_red(node)           ((uintptr_t) (node)->data |= 1)
+#define ngx_rbt_black(node)         ((uintptr_t) (node)->data &= ~1)
+#define ngx_rbt_is_red(node)        ((uintptr_t) (node)->data & 1)
+#define ngx_rbt_is_black(node)      (!ngx_rbt_is_red(node))
+#define ngx_rbt_copy_color(n1, n2)                                            \
+                         ((uintptr_t) (n1)->data |= (uintptr_t) (n2)->data & 1)
+
+
+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_rbtree_t  sentinel;
+
+
+void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+    ngx_rbtree_t  *temp;
+
+    /* a binary tree insert */
+
+    if (*root == &sentinel) {
+        node->parent = &sentinel;
+        node->left = &sentinel;
+        node->right = &sentinel;
+        ngx_rbt_black(node);
+        *root = node;
+
+        return;
+    }
+
+    temp = *root;
+
+    for ( ;; ) {
+        if (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;
+        continue;
+    }
+
+    node->parent = temp;
+    node->left = &sentinel;
+    node->right = &sentinel;
+
+
+    /* re-balance tree */
+
+    ngx_rbt_red(node);
+
+    while (node->parent && ngx_rbt_is_red(node->parent)) {
+
+        if (node->parent == node->parent->parent->left) {
+            temp = node->parent->parent->right;
+
+            if (ngx_rbt_is_red(temp)) {
+                ngx_rbt_black(node->parent);
+                ngx_rbt_black(temp);
+                ngx_rbt_red(node->parent->parent);
+                node = node->parent->parent;
+
+            } else {
+                if (node == node->parent->right) {
+                    node = node->parent;
+                    ngx_rbtree_left_rotate(root, node);
+                }
+
+                ngx_rbt_black(node->parent);
+                ngx_rbt_red(node->parent->parent);
+                ngx_rbtree_right_rotate(root, node->parent->parent);
+            }
+
+        } else {
+            temp = node->parent->parent->left;
+
+            if (ngx_rbt_is_red(temp)) {
+                ngx_rbt_black(node->parent);
+                ngx_rbt_black(temp);
+                ngx_rbt_red(node->parent->parent);
+                node = node->parent->parent;
+
+            } else {
+                if (node == node->parent->left) {
+                    node = node->parent;
+                    ngx_rbtree_right_rotate(root, node);
+                }
+
+                ngx_rbt_black(node->parent);
+                ngx_rbt_red(node->parent->parent);
+                ngx_rbtree_left_rotate(root, node->parent->parent);
+            }
+        }
+
+    }
+
+    ngx_rbt_black(*root);
+}
+
+
+void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+    ngx_rbtree_t  *subst, *temp, *w;
+
+    /* a binary tree delete */
+
+    if (node->left == &sentinel || node->right == &sentinel) {
+        subst = node;
+
+    } else {
+
+        /* find a node successor */
+
+        if (node->right == &sentinel) {
+            temp = node;
+            subst = node->parent;
+
+            while (subst != &sentinel && temp == subst->right) {
+                 temp = subst;
+                 subst = subst->parent;
+            }
+
+        } else {
+            subst = ngx_rbtree_min(node->right);
+        }
+    }
+
+    if (subst->left != &sentinel) {
+        temp = subst->left;
+    } else {
+        temp = subst->right;
+    }
+
+    temp->parent = subst->parent;
+
+    if (subst->parent == &sentinel) {
+        *root = temp;
+
+    } else if (subst == subst->parent->left) {
+        subst->parent->left = temp;
+
+    } else {
+        subst->parent->right = temp;
+    }
+
+    if (subst != node) {
+        node->key = subst->key;
+        node->data = subst->data;
+    }
+
+    if (ngx_rbt_is_red(subst)) {
+        return;
+    }
+
+    /* a delete fixup */
+
+    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);
+                w = temp->parent->right;
+            }
+
+            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
+                ngx_rbt_red(w);
+                temp = temp->parent;
+
+            } else {
+                if (ngx_rbt_is_black(w->right)) {
+                    ngx_rbt_black(w->left);
+                    ngx_rbt_red(w);
+                    ngx_rbtree_right_rotate(root, 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);
+                temp = *root;
+            }
+
+        } else {
+            w = temp->parent->left;
+
+            if (ngx_rbt_is_red(w)) {
+                ngx_rbt_black(w);
+                ngx_rbt_red(temp->parent);
+                ngx_rbtree_right_rotate(root, temp->parent);
+                w = temp->parent->left;
+            }
+
+            if (ngx_rbt_is_black(w->right) && ngx_rbt_is_black(w->left)) {
+                ngx_rbt_red(w);
+                temp = temp->parent;
+
+            } else {
+                if (ngx_rbt_is_black(w->left)) {
+                    ngx_rbt_black(w->right);
+                    ngx_rbt_red(w);
+                    ngx_rbtree_left_rotate(root, 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);
+                temp = *root;
+            }
+        }
+    }
+
+    ngx_rbt_black(temp);
+}
+
+
+ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+    ngx_rbtree_t  *temp;
+
+    temp = node->right;
+    node->right = temp->left;
+
+    if (temp->left != &sentinel) {
+        temp->left->parent = node;
+    }
+
+    temp->parent = node->parent;
+
+    if (node->parent == &sentinel) {
+        *root = temp;
+
+    } else if (node == node->parent->left) {
+        node->parent->left = temp;
+
+    } else {
+        node->parent->right = temp;
+    }
+
+    temp->left = node;
+    node->parent = temp;
+}
+
+
+ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+    ngx_rbtree_t  *temp;
+
+    temp = node->left;
+    node->left = temp->right;
+
+    if (temp->right != &sentinel) {
+        temp->right->parent = node;
+    }
+
+    temp->parent = node->parent;
+
+    if (node->parent == &sentinel) {
+        *root = temp;
+
+    } else if (node == node->parent->right) {
+        node->parent->right = temp;
+
+    } else {
+        node->parent->left = temp;
+    }
+
+    temp->right = node;
+    node->parent = temp;
+}