Mercurial > hg > nginx
diff src/http/ngx_http_variables.c @ 2333:f267d23868fc
variable value rbtree support
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Sat, 22 Nov 2008 20:42:01 +0000 |
parents | 4b98aa04ee24 |
children | 4fee4ebbfb0b |
line wrap: on
line diff
--- a/src/http/ngx_http_variables.c Sat Nov 22 20:38:45 2008 +0000 +++ b/src/http/ngx_http_variables.c Sat Nov 22 20:42:01 2008 +0000 @@ -1633,3 +1633,87 @@ return NGX_OK; } + + +void +ngx_http_variable_value_rbtree_insert(ngx_rbtree_node_t *temp, + ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) +{ + ngx_rbtree_node_t **p; + ngx_http_variable_value_node_t *vvn, *vvt; + + for ( ;; ) { + + vvn = (ngx_http_variable_value_node_t *) node; + vvt = (ngx_http_variable_value_node_t *) temp; + + if (node->key != temp->key) { + + p = (node->key < temp->key) ? &temp->left : &temp->right; + + } else if (vvn->len != vvt->len) { + + p = (vvn->len < vvt->len) ? &temp->left : &temp->right; + + } else { + p = (ngx_memcmp(vvn->value->data, vvt->value->data, vvn->len) < 0) + ? &temp->left : &temp->right; + } + + if (*p == sentinel) { + break; + } + + temp = *p; + } + + *p = node; + node->parent = temp; + node->left = sentinel; + node->right = sentinel; + ngx_rbt_red(node); +} + + +ngx_http_variable_value_t * +ngx_http_variable_value_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, + uint32_t hash) +{ + ngx_int_t rc; + ngx_rbtree_node_t *node, *sentinel; + ngx_http_variable_value_node_t *vvn; + + node = rbtree->root; + sentinel = rbtree->sentinel; + + while (node != sentinel) { + + vvn = (ngx_http_variable_value_node_t *) node; + + if (hash != node->key) { + node = (hash < node->key) ? node->left : node->right; + continue; + } + + if (val->len != vvn->len) { + node = (val->len < vvn->len) ? node->left : node->right; + continue; + } + + rc = ngx_memcmp(val->data, vvn->value->data, val->len); + + if (rc < 0) { + node = node->left; + continue; + } + + if (rc > 0) { + node = node->right; + continue; + } + + return vvn->value; + } + + return NULL; +}