variable value rbtree support

1 files changed, 84 insertions, 0 deletions

diff --git a/src/http/ngx_http_variables.c b/src/http/ngx_http_variables.c
index 69900b073..aad541e81 100644
--- 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 *cf)
 
     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;
+}