From 03789a0a1c208ac62bee429497b9f6a46c0aa5ff Mon Sep 17 00:00:00 2001 From: Igor Sysoev Date: Mon, 27 Nov 2006 11:18:50 +0000 Subject: Changes with nginx 0.4.14 27 Nov 2006 *) Feature: the "proxy_pass_error_message" directive in IMAP/POP3 proxy. *) Bugfix: ngx_http_perl_module did nto work with perl built with the threads support; bug appeared in 0.3.38. *) Bugfix: !!!!!!!!!! segfault perl. *) Bugfix: !!!!!!!!!! recursive perl. *) Bugfix: nginx ignored a host name in an request line. *) Bugfix: !!!!!!!!!! endless loop when too many FastCGI sent too many to stderr *) Bugfix: !!!!!!!! negative upstream response time *) Bugfix: the "Auth-Login-Attempt" parameter was not sent to IMAP/POP3 proxy authentication server when POP3 was used. *) Bugfix: a segmentation fault might occur if connect to IMAP/POP3 proxy authentication server failed. --- src/core/ngx_rbtree.c | 128 +++++++++++++++++++++++++++++++------------------- 1 file changed, 80 insertions(+), 48 deletions(-) (limited to 'src/core/ngx_rbtree.c') diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c index 3c42be402..a9d630520 100644 --- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -47,53 +47,10 @@ ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, 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 ( ;; ) { - - /* node->key < temp->key */ - - if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key - < 0) - { - 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; - + tree->insert(*root, node, sentinel); /* re-balance tree */ - ngx_rbt_red(node); - while (node != *root && ngx_rbt_is_red(node->parent)) { if (node->parent == node->parent->parent->left) { @@ -136,18 +93,93 @@ ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, 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) +{ + for ( ;; ) { + + if (node->key < temp->key) { + + if (temp->left == sentinel) { + temp->left = node; + break; + } + + temp = temp->left; + + } else { + + if (temp->right == sentinel) { + temp->right = node; + break; + } + + temp = temp->right; + } + } + + 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) +{ + 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. + */ + + if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key + < 0) + { + /* node->key < temp->key */ + + if (temp->left == sentinel) { + temp->left = node; + break; + } + + temp = temp->left; + + } else { + + if (temp->right == sentinel) { + temp->right = node; + break; + } + + temp = temp->right; + } + } + + node->parent = temp; + node->left = sentinel; + node->right = sentinel; + ngx_rbt_red(node); +} + + void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node) { - ngx_int_t is_red; + ngx_uint_t red; ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; /* a binary tree delete */ @@ -186,7 +218,7 @@ ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, return; } - is_red = ngx_rbt_is_red(subst); + red = ngx_rbt_is_red(subst); if (subst == subst->parent->left) { subst->parent->left = temp; @@ -239,7 +271,7 @@ ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, node->key = 0; } - if (is_red) { + if (red) { return; } -- cgit v1.2.1