diff options
author | Igor Sysoev <igor@sysoev.ru> | 2007-12-17 11:52:00 +0300 |
---|---|---|
committer | Igor Sysoev <igor@sysoev.ru> | 2007-12-17 11:52:00 +0300 |
commit | 7912e4ba5d699da3de6643a99c3076c660742f88 (patch) | |
tree | 6ab51590f3a1b9a38aa070ae680ab8275dc74744 /src/core/ngx_rbtree.c | |
parent | c0cadf1f347440ee57c00527e3ba8d274dff27ff (diff) |
optimize rbtree initialization and insert
Diffstat (limited to 'src/core/ngx_rbtree.c')
-rw-r--r-- | src/core/ngx_rbtree.c | 55 |
1 files changed, 20 insertions, 35 deletions
diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c index 0a5753cdf..7ee0036ec 100644 --- 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) { - for ( ;; ) { - - if (node->key < temp->key) { - - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; + ngx_rbtree_node_t **p; - } else { + for ( ;; ) { - if (temp->right == sentinel) { - temp->right = node; - break; - } + p = (node->key < temp->key) ? &temp->left : &temp->right; - temp = temp->right; + if (*p == sentinel) { + break; } + + 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_node_t *temp, ngx_rbtree_node_t *node, * 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; - } + /* node->key < temp->key */ - temp = temp->left; - - } else { + p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key + < 0) + ? &temp->left : &temp->right; - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; + if (*p == sentinel) { + break; } - } + temp = *p; + } + + *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel; |