optimize rbtree initialization and insert
diff --git a/src/core/ngx_open_file_cache.c b/src/core/ngx_open_file_cache.c
index dab98b3..d518f4b 100644
--- a/src/core/ngx_open_file_cache.c
+++ b/src/core/ngx_open_file_cache.c
@@ -53,11 +53,8 @@
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;
diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c
index 0a5753c..7ee0036 100644
--- a/src/core/ngx_rbtree.c
+++ b/src/core/ngx_rbtree.c
@@ -97,28 +97,20 @@
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) {
+ p = (node->key < temp->key) ? &temp->left : &temp->right;
- if (temp->left == sentinel) {
- temp->left = node;
- break;
- }
-
- temp = temp->left;
-
- } else {
-
- 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;
@@ -130,6 +122,8 @@
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 @@
* 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;
- }
+ p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
+ < 0)
+ ? &temp->left : &temp->right;
- temp = temp->left;
-
- } else {
-
- 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;
diff --git a/src/event/ngx_event_openssl.c b/src/event/ngx_event_openssl.c
index be24d9c..bd539c9 100644
--- a/src/event/ngx_event_openssl.c
+++ b/src/event/ngx_event_openssl.c
@@ -1241,11 +1241,8 @@
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 @@
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;
diff --git a/src/event/ngx_event_timer.c b/src/event/ngx_event_timer.c
index 589de6d..2931a9f 100644
--- a/src/event/ngx_event_timer.c
+++ b/src/event/ngx_event_timer.c
@@ -26,9 +26,8 @@
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)
diff --git a/src/http/modules/ngx_http_limit_zone_module.c b/src/http/modules/ngx_http_limit_zone_module.c
index a0be6f1..c7a3753 100644
--- a/src/http/modules/ngx_http_limit_zone_module.c
+++ b/src/http/modules/ngx_http_limit_zone_module.c
@@ -239,54 +239,36 @@
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;
-
- } else {
-
- if (temp->right == sentinel) {
- temp->right = node;
- break;
- }
-
- temp = temp->right;
- }
+ p = (ngx_memn2cmp(lzn->data, lznt->data, lzn->len, lznt->len) < 0)
+ ? &temp->left : &temp->right;
}
+
+ if (*p == sentinel) {
+ break;
+ }
+
+ temp = *p;
}
+ *p = node;
node->parent = temp;
node->left = sentinel;
node->right = sentinel;
@@ -362,11 +344,8 @@
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;
}
