Mercurial > hg > nginx-ranges
diff src/core/ngx_rbtree.c @ 108:cf3d6edb3ad6 NGINX_0_3_1
nginx 0.3.1
*) Bugfix: the segmentation fault occurred when the signal queue
overflowed if the "rtsig" method was used; bug appeared in 0.2.0.
*) Change: correct handling of the "\\", "\"", "\'", and "\$" pairs in
SSI.
| author | Igor Sysoev <http://sysoev.ru> |
|---|---|
| date | Mon, 10 Oct 2005 00:00:00 +0400 |
| parents | 45f7329b4bd0 |
| children | 6ae1357b7b7c |
line wrap: on
line diff
--- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -9,8 +9,8 @@ /* - * The code is based on the algorithm described in the "Introduction - * to Algorithms" by Cormen, Leiserson and Rivest. + * The red-black tree 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) @@ -20,20 +20,23 @@ #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); +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 **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, + ngx_rbtree_node_t *node) { - ngx_rbtree_t *temp; + ngx_rbtree_node_t **root, *temp, *sentinel; /* a binary tree insert */ + root = (ngx_rbtree_node_t **) &tree->root; + sentinel = tree->sentinel; + if (*root == sentinel) { node->parent = NULL; node->left = sentinel; @@ -44,6 +47,17 @@ ngx_rbtree_insert(ngx_rbtree_t **root, n return; } + /* + * The rbtree is currently used by event timers only. 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 below comparison takes into account that overflow. + * + * If there will be a necessity to use the rbtree for values with + * other comparison rules, then a whole "for ( ;; )" loop should + * be made as tree->insert() function. + */ + temp = *root; for ( ;; ) { @@ -130,14 +144,17 @@ ngx_rbtree_insert(ngx_rbtree_t **root, n void -ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, + ngx_rbtree_node_t *node) { - ngx_int_t is_red; - ngx_rbtree_t *subst, *temp, *w; + ngx_int_t is_red; + ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ + root = (ngx_rbtree_node_t **) &tree->root; + sentinel = tree->sentinel; + if (node->left == sentinel) { temp = node->right; subst = node; @@ -295,10 +312,10 @@ ngx_rbtree_delete(ngx_rbtree_t **root, n static ngx_inline void -ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, + ngx_rbtree_node_t *node) { - ngx_rbtree_t *temp; + ngx_rbtree_node_t *temp; temp = node->right; node->right = temp->left; @@ -325,10 +342,10 @@ ngx_rbtree_left_rotate(ngx_rbtree_t **ro static ngx_inline void -ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, - ngx_rbtree_t *node) +ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, + ngx_rbtree_node_t *node) { - ngx_rbtree_t *temp; + ngx_rbtree_node_t *temp; temp = node->left; node->left = temp->right;