Mercurial > hg > nginx

comparison src/core/ngx_string.c @ 3641:6802ba529ec4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change ngx_http_variable_value_node_t to more generic ngx_str_node_t
author Igor Sysoev <igor@sysoev.ru>
date Wed, 23 Jun 2010 15:31:33 +0000
parents 76d252724db5
children 4954530db2af
comparison
equal deleted inserted replaced
3640:6a767188e365 3641:6802ba529ec4
1636 1636
1637 return (uintptr_t) dst; 1637 return (uintptr_t) dst;
1638 } 1638 }
1639 1639
1640 1640
1641 void
1642 ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
1643 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
1644 {
1645 ngx_str_node_t *n, *t;
1646 ngx_rbtree_node_t **p;
1647
1648 for ( ;; ) {
1649
1650 n = (ngx_str_node_t *) node;
1651 t = (ngx_str_node_t *) temp;
1652
1653 if (node->key != temp->key) {
1654
1655 p = (node->key < temp->key) ? &temp->left : &temp->right;
1656
1657 } else if (n->str.len != t->str.len) {
1658
1659 p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
1660
1661 } else {
1662 p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
1663 ? &temp->left : &temp->right;
1664 }
1665
1666 if (*p == sentinel) {
1667 break;
1668 }
1669
1670 temp = *p;
1671 }
1672
1673 *p = node;
1674 node->parent = temp;
1675 node->left = sentinel;
1676 node->right = sentinel;
1677 ngx_rbt_red(node);
1678 }
1679
1680
1681 ngx_str_node_t *
1682 ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, uint32_t hash)
1683 {
1684 ngx_int_t rc;
1685 ngx_str_node_t *n;
1686 ngx_rbtree_node_t *node, *sentinel;
1687
1688 node = rbtree->root;
1689 sentinel = rbtree->sentinel;
1690
1691 while (node != sentinel) {
1692
1693 n = (ngx_str_node_t *) node;
1694
1695 if (hash != node->key) {
1696 node = (hash < node->key) ? node->left : node->right;
1697 continue;
1698 }
1699
1700 if (val->len != n->str.len) {
1701 node = (val->len < n->str.len) ? node->left : node->right;
1702 continue;
1703 }
1704
1705 rc = ngx_memcmp(val->data, n->str.data, val->len);
1706
1707 if (rc < 0) {
1708 node = node->left;
1709 continue;
1710 }
1711
1712 if (rc > 0) {
1713 node = node->right;
1714 continue;
1715 }
1716
1717 return n;
1718 }
1719
1720 return NULL;
1721 }
1722
1723
1641 /* ngx_sort() is implemented as insertion sort because we need stable sort */ 1724 /* ngx_sort() is implemented as insertion sort because we need stable sort */
1642 1725
1643 void 1726 void
1644 ngx_sort(void *base, size_t n, size_t size, 1727 ngx_sort(void *base, size_t n, size_t size,
1645 ngx_int_t (*cmp)(const void *, const void *)) 1728 ngx_int_t (*cmp)(const void *, const void *))