Mercurial > hg > nginx
comparison 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 |
comparison
equal
deleted
inserted
replaced
2332:8f77ba626ead | 2333:f267d23868fc |
---|---|
1631 | 1631 |
1632 cmcf->variables_keys = NULL; | 1632 cmcf->variables_keys = NULL; |
1633 | 1633 |
1634 return NGX_OK; | 1634 return NGX_OK; |
1635 } | 1635 } |
1636 | |
1637 | |
1638 void | |
1639 ngx_http_variable_value_rbtree_insert(ngx_rbtree_node_t *temp, | |
1640 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) | |
1641 { | |
1642 ngx_rbtree_node_t **p; | |
1643 ngx_http_variable_value_node_t *vvn, *vvt; | |
1644 | |
1645 for ( ;; ) { | |
1646 | |
1647 vvn = (ngx_http_variable_value_node_t *) node; | |
1648 vvt = (ngx_http_variable_value_node_t *) temp; | |
1649 | |
1650 if (node->key != temp->key) { | |
1651 | |
1652 p = (node->key < temp->key) ? &temp->left : &temp->right; | |
1653 | |
1654 } else if (vvn->len != vvt->len) { | |
1655 | |
1656 p = (vvn->len < vvt->len) ? &temp->left : &temp->right; | |
1657 | |
1658 } else { | |
1659 p = (ngx_memcmp(vvn->value->data, vvt->value->data, vvn->len) < 0) | |
1660 ? &temp->left : &temp->right; | |
1661 } | |
1662 | |
1663 if (*p == sentinel) { | |
1664 break; | |
1665 } | |
1666 | |
1667 temp = *p; | |
1668 } | |
1669 | |
1670 *p = node; | |
1671 node->parent = temp; | |
1672 node->left = sentinel; | |
1673 node->right = sentinel; | |
1674 ngx_rbt_red(node); | |
1675 } | |
1676 | |
1677 | |
1678 ngx_http_variable_value_t * | |
1679 ngx_http_variable_value_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, | |
1680 uint32_t hash) | |
1681 { | |
1682 ngx_int_t rc; | |
1683 ngx_rbtree_node_t *node, *sentinel; | |
1684 ngx_http_variable_value_node_t *vvn; | |
1685 | |
1686 node = rbtree->root; | |
1687 sentinel = rbtree->sentinel; | |
1688 | |
1689 while (node != sentinel) { | |
1690 | |
1691 vvn = (ngx_http_variable_value_node_t *) node; | |
1692 | |
1693 if (hash != node->key) { | |
1694 node = (hash < node->key) ? node->left : node->right; | |
1695 continue; | |
1696 } | |
1697 | |
1698 if (val->len != vvn->len) { | |
1699 node = (val->len < vvn->len) ? node->left : node->right; | |
1700 continue; | |
1701 } | |
1702 | |
1703 rc = ngx_memcmp(val->data, vvn->value->data, val->len); | |
1704 | |
1705 if (rc < 0) { | |
1706 node = node->left; | |
1707 continue; | |
1708 } | |
1709 | |
1710 if (rc > 0) { | |
1711 node = node->right; | |
1712 continue; | |
1713 } | |
1714 | |
1715 return vvn->value; | |
1716 } | |
1717 | |
1718 return NULL; | |
1719 } |