Mercurial > hg > nginx
changeset 1743:4fc402c3ec73
optimize rbtree initialization and insert
| author | Igor Sysoev <igor@sysoev.ru> |
|---|---|
| date | Mon, 17 Dec 2007 08:52:00 +0000 |
| parents | 268b81386fe4 |
| children | d65172100f6b |
| files | src/core/ngx_open_file_cache.c src/core/ngx_rbtree.c src/event/ngx_event_openssl.c src/event/ngx_event_timer.c src/http/modules/ngx_http_limit_zone_module.c |
| diffstat | 5 files changed, 54 insertions(+), 116 deletions(-) [+] |
line wrap: on
line diff
--- a/src/core/ngx_open_file_cache.c +++ b/src/core/ngx_open_file_cache.c @@ -53,11 +53,8 @@ ngx_open_file_cache_init(ngx_pool_t *poo return NULL; } - ngx_rbtree_sentinel_init(sentinel); - - cache->rbtree.root = sentinel; - cache->rbtree.sentinel = sentinel; - cache->rbtree.insert = ngx_open_file_cache_rbtree_insert_value; + ngx_rbtree_init(&cache->rbtree, sentinel, + ngx_open_file_cache_rbtree_insert_value); cache->current = 0; cache->max = max;
--- 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;
--- a/src/event/ngx_event_openssl.c +++ b/src/event/ngx_event_openssl.c @@ -1241,11 +1241,8 @@ ngx_ssl_session_cache_init(ngx_shm_zone_ return NGX_ERROR; } - ngx_rbtree_sentinel_init(sentinel); - - cache->session_rbtree->root = sentinel; - cache->session_rbtree->sentinel = sentinel; - cache->session_rbtree->insert = ngx_ssl_session_rbtree_insert_value; + ngx_rbtree_init(cache->session_rbtree, sentinel, + ngx_ssl_session_rbtree_insert_value); shm_zone->data = cache; @@ -1625,56 +1622,37 @@ static void ngx_ssl_session_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { - ngx_ssl_sess_id_t *sess_id, *sess_id_temp; + ngx_rbtree_node_t **p; + ngx_ssl_sess_id_t *sess_id, *sess_id_temp; for ( ;; ) { if (node->key < temp->key) { - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; + p = &temp->left; } else if (node->key > temp->key) { - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; + p = &temp->right; } else { /* node->key == temp->key */ sess_id = (ngx_ssl_sess_id_t *) node; sess_id_temp = (ngx_ssl_sess_id_t *) temp; - if (ngx_memn2cmp(sess_id->id, sess_id_temp->id, - (size_t) node->data, (size_t) temp->data) - < 0) - { - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; - - } else { - - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; - } + p = (ngx_memn2cmp(sess_id->id, sess_id_temp->id, + (size_t) node->data, (size_t) temp->data) + < 0) ? &temp->left : &temp->right; } + + if (*p == sentinel) { + break; + } + + temp = *p; } + *p = node; node->parent = temp; node->left = sentinel; node->right = sentinel;
--- a/src/event/ngx_event_timer.c +++ b/src/event/ngx_event_timer.c @@ -26,9 +26,8 @@ static ngx_rbtree_node_t ngx_ev ngx_int_t ngx_event_timer_init(ngx_log_t *log) { - ngx_event_timer_rbtree.root = &ngx_event_timer_sentinel; - ngx_event_timer_rbtree.sentinel = &ngx_event_timer_sentinel; - ngx_event_timer_rbtree.insert = ngx_rbtree_insert_timer_value; + ngx_rbtree_init(&ngx_event_timer_rbtree, &ngx_event_timer_sentinel, + ngx_rbtree_insert_timer_value); #if (NGX_THREADS)
--- a/src/http/modules/ngx_http_limit_zone_module.c +++ b/src/http/modules/ngx_http_limit_zone_module.c @@ -239,54 +239,36 @@ static void ngx_http_limit_zone_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) { - ngx_http_limit_zone_node_t *lzn, *lznt; + ngx_rbtree_node_t **p; + ngx_http_limit_zone_node_t *lzn, *lznt; for ( ;; ) { if (node->key < temp->key) { - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; + p = &temp->left; } else if (node->key > temp->key) { - if (temp->right == sentinel) { - temp->right = node; - break; - } - - temp = temp->right; + p = &temp->right; } else { /* node->key == temp->key */ lzn = (ngx_http_limit_zone_node_t *) &node->color; lznt = (ngx_http_limit_zone_node_t *) &temp->color; - if (ngx_memn2cmp(lzn->data, lznt->data, lzn->len, lznt->len) < 0) { - - if (temp->left == sentinel) { - temp->left = node; - break; - } - - temp = temp->left; + p = (ngx_memn2cmp(lzn->data, lznt->data, lzn->len, lznt->len) < 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; @@ -362,11 +344,8 @@ ngx_http_limit_zone_init_zone(ngx_shm_zo return NGX_ERROR; } - ngx_rbtree_sentinel_init(sentinel); - - ctx->rbtree->root = sentinel; - ctx->rbtree->sentinel = sentinel; - ctx->rbtree->insert = ngx_http_limit_zone_rbtree_insert_value; + ngx_rbtree_init(ctx->rbtree, sentinel, + ngx_http_limit_zone_rbtree_insert_value); return NGX_OK; }