Mercurial > hg > nginx
comparison src/core/ngx_string.c @ 3641:6802ba529ec4
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 *)) |