Mercurial > hg > nginx-ranges
view src/core/ngx_rbtree.c @ 34:aab2ea7c0458 NGINX_0_1_17
nginx 0.1.17
*) Change: the ngx_http_rewrite_module was rewritten from the scratch.
Now it is possible to redirect, to return the error codes, to check
the variables and referrers. The directives can be used inside
locations. The redirect directive was canceled.
*) Feature: the ngx_http_geo_module.
*) Feature: the proxy_set_x_var and fastcgi_set_var directives.
*) Bugfix: the location configuration with "=" modifier may be used in
another location.
*) Bugfix: the correct content type was set only for requests that use
small caps letters in extension.
*) Bugfix: if the proxy_pass or fastcgi_pass directives were set in the
location, and access was denied, and the error was redirected to a
static page, then the segmentation fault occurred.
*) Bugfix: if in a proxied "Location" header was a relative URL, then a
host name and a slash were added to them; bug appeared in 0.1.14.
*) Bugfix: the system error message was not logged on Linux.
| author | Igor Sysoev <http://sysoev.ru> |
|---|---|
| date | Thu, 03 Feb 2005 00:00:00 +0300 |
| parents | 74b1868dd3cd |
| children | 41ccba1aba45 |
line wrap: on
line source
/* * 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) static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, ngx_rbtree_t *node); static 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); } static 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; } static 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; }