Mercurial > hg > nginx-mail
diff src/core/ngx_rbtree.c @ 0:f0b350454894 NGINX_0_1_0
nginx 0.1.0
*) The first public version.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Mon, 04 Oct 2004 00:00:00 +0400 |
parents | |
children | 74b1868dd3cd |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/src/core/ngx_rbtree.c @@ -0,0 +1,349 @@ + +/* + * Copyright (C) Igor Sysoev + */ + + +#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) ((node)->color = 1) +#define ngx_rbt_black(node) ((node)->color = 0) +#define ngx_rbt_is_red(node) ((node)->color) +#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) +#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 *sentinel, + ngx_rbtree_t *node); +ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, + ngx_rbtree_t *sentinel, + 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 = NULL; + 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 != *root && 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, sentinel, node); + } + + ngx_rbt_black(node->parent); + ngx_rbt_red(node->parent->parent); + ngx_rbtree_right_rotate(root, sentinel, 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, sentinel, node); + } + + ngx_rbt_black(node->parent); + ngx_rbt_red(node->parent->parent); + ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); + } + } + + } + + ngx_rbt_black(*root); +} + + +void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, + ngx_rbtree_t *node) +{ + ngx_int_t is_red; + ngx_rbtree_t *subst, *temp, *w; + + /* a binary tree delete */ + + if (node->left == sentinel) { + temp = node->right; + subst = node; + + } else if (node->right == sentinel) { + temp = node->left; + subst = node; + + } else { + subst = ngx_rbtree_min(node->right, sentinel); + + if (subst->left != sentinel) { + temp = subst->left; + } else { + temp = subst->right; + } + } + + if (subst == *root) { + *root = temp; + ngx_rbt_black(temp); + + /* DEBUG stuff */ + node->left = NULL; + node->right = NULL; + node->parent = NULL; + node->key = 0; + + return; + } + + is_red = ngx_rbt_is_red(subst); + + if (subst == subst->parent->left) { + subst->parent->left = temp; + + } else { + subst->parent->right = temp; + } + + if (subst == node) { + + temp->parent = subst->parent; + + } else { + + if (subst->parent == node) { + temp->parent = subst; + + } else { + temp->parent = subst->parent; + } + + subst->left = node->left; + subst->right = node->right; + subst->parent = node->parent; + ngx_rbt_copy_color(subst, node); + + if (node == *root) { + *root = subst; + + } else { + if (node == node->parent->left) { + node->parent->left = subst; + } else { + node->parent->right = subst; + } + } + + if (subst->left != sentinel) { + subst->left->parent = subst; + } + + if (subst->right != sentinel) { + subst->right->parent = subst; + } + + /* DEBUG stuff */ + node->left = NULL; + node->right = NULL; + node->parent = NULL; + node->key = 0; + } + + if (is_red) { + return; + } + + /* a delete fixup */ + + while (temp != *root && 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, sentinel, 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, 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, sentinel, 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, sentinel, temp->parent); + w = temp->parent->left; + } + + 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->left)) { + ngx_rbt_black(w->right); + ngx_rbt_red(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, sentinel, temp->parent); + temp = *root; + } + } + } + + ngx_rbt_black(temp); +} + + +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) { + temp->left->parent = node; + } + + temp->parent = node->parent; + + if (node == *root) { + *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 *sentinel, + 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 == *root) { + *root = temp; + + } else if (node == node->parent->right) { + node->parent->right = temp; + + } else { + node->parent->left = temp; + } + + temp->right = node; + node->parent = temp; +}