Mercurial > hg > nginx-quic
changeset 2333:f267d23868fc
variable value rbtree support
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Sat, 22 Nov 2008 20:42:01 +0000 |
parents | 8f77ba626ead |
children | 6e30d64f919b |
files | src/http/ngx_http_variables.c src/http/ngx_http_variables.h |
diffstat | 2 files changed, 97 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- a/src/http/ngx_http_variables.c +++ b/src/http/ngx_http_variables.c @@ -1633,3 +1633,87 @@ ngx_http_variables_init_vars(ngx_conf_t 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; +}
--- a/src/http/ngx_http_variables.h +++ b/src/http/ngx_http_variables.h @@ -63,6 +63,19 @@ ngx_int_t ngx_http_variables_add_core_va ngx_int_t ngx_http_variables_init_vars(ngx_conf_t *cf); +typedef struct { + ngx_rbtree_node_t node; + size_t len; + ngx_http_variable_value_t *value; +} ngx_http_variable_value_node_t; + + +void ngx_http_variable_value_rbtree_insert(ngx_rbtree_node_t *temp, + ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel); +ngx_http_variable_value_t *ngx_http_variable_value_lookup(ngx_rbtree_t *rbtree, + ngx_str_t *name, uint32_t hash); + + extern ngx_http_variable_value_t ngx_http_variable_null_value; extern ngx_http_variable_value_t ngx_http_variable_true_value;