diff options
Diffstat (limited to 'app/nginx/src/core/ngx_rbtree.c')
-rw-r--r-- | app/nginx/src/core/ngx_rbtree.c | 409 |
1 files changed, 0 insertions, 409 deletions
diff --git a/app/nginx/src/core/ngx_rbtree.c b/app/nginx/src/core/ngx_rbtree.c deleted file mode 100644 index 969d549..0000000 --- a/app/nginx/src/core/ngx_rbtree.c +++ /dev/null @@ -1,409 +0,0 @@ - -/* - * Copyright (C) Igor Sysoev - * Copyright (C) Nginx, Inc. - */ - - -#include <ngx_config.h> -#include <ngx_core.h> - - -/* - * The red-black tree code is based on the algorithm described in - * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. - */ - - -static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, - ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); -static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, - ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); - - -void -ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) -{ - ngx_rbtree_node_t **root, *temp, *sentinel; - - /* a binary tree insert */ - - root = &tree->root; - sentinel = tree->sentinel; - - if (*root == sentinel) { - node->parent = NULL; - node->left = sentinel; - node->right = sentinel; - ngx_rbt_black(node); - *root = node; - - return; - } - - tree->insert(*root, node, sentinel); - - /* re-balance tree */ - - 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_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, - ngx_rbtree_node_t *sentinel) -{ - ngx_rbtree_node_t **p; - - for ( ;; ) { - - p = (node->key < temp->key) ? &temp->left : &temp->right; - - if (*p == sentinel) { - break; - } - - temp = *p; - } - - *p = node; - node->parent = temp; - node->left = sentinel; - node->right = sentinel; - ngx_rbt_red(node); -} - - -void -ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, - ngx_rbtree_node_t *sentinel) -{ - ngx_rbtree_node_t **p; - - 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. - */ - - /* node->key < temp->key */ - - p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0) - ? &temp->left : &temp->right; - - if (*p == sentinel) { - break; - } - - temp = *p; - } - - *p = node; - node->parent = temp; - node->left = sentinel; - node->right = sentinel; - ngx_rbt_red(node); -} - - -void -ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) -{ - ngx_uint_t red; - ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; - - /* a binary tree delete */ - - root = &tree->root; - sentinel = tree->sentinel; - - 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; - } - - 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 (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); -} - - -static ngx_inline void -ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, - ngx_rbtree_node_t *node) -{ - ngx_rbtree_node_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; -} - - -static ngx_inline void -ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, - ngx_rbtree_node_t *node) -{ - ngx_rbtree_node_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; -} - - -ngx_rbtree_node_t * -ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node) -{ - ngx_rbtree_node_t *root, *sentinel, *parent; - - sentinel = tree->sentinel; - - if (node->right != sentinel) { - return ngx_rbtree_min(node->right, sentinel); - } - - root = tree->root; - - for ( ;; ) { - parent = node->parent; - - if (node == root) { - return NULL; - } - - if (node == parent->left) { - return parent; - } - - node = parent; - } -} |