Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 206:9aa426375256

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx-0.0.1-2003-12-05-10:11:46 import
author Igor Sysoev <igor@sysoev.ru>
date Fri, 05 Dec 2003 07:11:46 +0000
parents 4a9a2b1dd6fa
children 6e0fef527732
comparison
equal deleted inserted replaced
205:4a9a2b1dd6fa 206:9aa426375256
6 /* 6 /*
7 * The code is based on the algorithm described in the "Introduction 7 * The code is based on the algorithm described in the "Introduction
8 * to Algorithms" by Cormen, Leiserson and Rivest. 8 * to Algorithms" by Cormen, Leiserson and Rivest.
9 */ 9 */
10 10
11 #define ngx_rbt_red(node) ((uintptr_t) (node)->data |= 1) 11 #define ngx_rbt_red(node) ((node)->color = 1)
12 #define ngx_rbt_black(node) ((uintptr_t) (node)->data &= ~1) 12 #define ngx_rbt_black(node) ((node)->color = 0)
13 #define ngx_rbt_is_red(node) ((uintptr_t) (node)->data & 1) 13 #define ngx_rbt_is_red(node) ((node)->color)
14 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) 14 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
15 #define ngx_rbt_copy_color(n1, n2) \ 15 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
16 ((uintptr_t) (n1)->data |= (uintptr_t) (n2)->data & 1)
17 16
18 17
19 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node); 18 ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node);
20 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, 19 ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root,
21 ngx_rbtree_t *node); 20 ngx_rbtree_t *node);
164 subst->parent->right = temp; 163 subst->parent->right = temp;
165 } 164 }
166 165
167 if (subst != node) { 166 if (subst != node) {
168 node->key = subst->key; 167 node->key = subst->key;
169 node->data = subst->data; 168 node->color = subst->color;
170 } 169 }
171 170
172 if (ngx_rbt_is_red(subst)) { 171 if (ngx_rbt_is_red(subst)) {
173 return; 172 return;
174 } 173 }