Mercurial > hg > nginx
diff src/core/ngx_rbtree.c @ 205:4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Thu, 04 Dec 2003 14:53:00 +0000 |
parents | |
children | 9aa426375256 |
line wrap: on
line diff
new file mode 100644 --- /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; +}