diff options
author | Igor Sysoev <igor@sysoev.ru> | 2006-10-28 18:20:13 +0400 |
---|---|---|
committer | Igor Sysoev <igor@sysoev.ru> | 2006-10-28 18:20:13 +0400 |
commit | e6d99d831cf7a8eac1f554bf0a07d67664a3bb92 (patch) | |
tree | 960850c99895082be62bbd3ce1faf4cf69b055c0 /src/core/ngx_rbtree.c | |
parent | a994bd0ae2a2b7f268f050c70e281e3081916d22 (diff) |
bad commit
Diffstat (limited to 'src/core/ngx_rbtree.c')
-rw-r--r-- | src/core/ngx_rbtree.c | 85 |
1 files changed, 42 insertions, 43 deletions
diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c index 3c42be402..11db4c5c7 100644 --- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -47,48 +47,7 @@ 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 */ @@ -136,7 +95,6 @@ ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); } } - } ngx_rbt_black(*root); @@ -144,6 +102,47 @@ ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, 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) { |