Mercurial > hg > nginx
diff src/core/ngx_rbtree.c @ 1743:4fc402c3ec73
optimize rbtree initialization and insert
| author | Igor Sysoev <igor@sysoev.ru> |
|---|---|
| date | Mon, 17 Dec 2007 08:52:00 +0000 |
| parents | 68cc5e2e1a5d |
| children | 3c0b44825071 |
line wrap: on
line diff
--- a/src/core/ngx_rbtree.c +++ b/src/core/ngx_rbtree.c @@ -97,28 +97,20 @@ void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { + ngx_rbtree_node_t **p; + for ( ;; ) { - if (node->key < temp->key) { - - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; + p = (node->key < temp->key) ? &temp->left : &temp->right; - } else { + if (*p == sentinel) { + break; + } - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; - } + temp = *p; } + *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; @@ -130,6 +122,8 @@ void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { + ngx_rbtree_node_t **p; + for ( ;; ) { /* @@ -139,29 +133,20 @@ ngx_rbtree_insert_timer_value(ngx_rbtree * 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 */ + /* node->key < temp->key */ - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; + p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key + < 0) + ? &temp->left : &temp->right; - } else { + if (*p == sentinel) { + break; + } - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; - } + temp = *p; } - + + *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel;