Mercurial > hg > nginx
diff src/core/ngx_rbtree.c @ 826:4390fcad6628
undo the previous wrong commit
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Sat, 28 Oct 2006 14:32:39 +0000 |
parents | f9b9b84a8e18 |
children | 629b5e4f8931 |
line wrap: on
line diff
--- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -47,7 +47,48 @@ ngx_rbtree_insert(ngx_thread_volatile ng return; } - tree->insert(*root, node, sentinel); + /* + * 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; + /* re-balance tree */ @@ -95,6 +136,7 @@ ngx_rbtree_insert(ngx_thread_volatile ng ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); } } + } ngx_rbt_black(*root); @@ -102,47 +144,6 @@ ngx_rbtree_insert(ngx_thread_volatile ng 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; - continue; - } - - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; - } - - node->parent = temp; - node->left = sentinel; - node->right = sentinel; -} - - -void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_node_t *node) {