Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 213:f536f91e8e99

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx-0.0.1-2003-12-19-15:45:27 import
author Igor Sysoev <igor@sysoev.ru>
date Fri, 19 Dec 2003 12:45:27 +0000
parents 679f60139863
children ce6b72fe33fe
comparison
equal deleted inserted replaced
212:679f60139863 213:f536f91e8e99
121 121
122 122
123 void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, 123 void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel,
124 ngx_rbtree_t *node) 124 ngx_rbtree_t *node)
125 { 125 {
126 ngx_int_t red; 126 ngx_int_t is_red;
127 ngx_rbtree_t *subst, *temp, *w; 127 ngx_rbtree_t *subst, *temp, *w;
128 128
129 /* a binary tree delete */ 129 /* a binary tree delete */
130 130
131 if (node->left == sentinel) { 131 if (node->left == sentinel) {
150 /* it's the last node */ 150 /* it's the last node */
151 *root = sentinel; 151 *root = sentinel;
152 return; 152 return;
153 } 153 }
154 154
155 red = ngx_rbt_is_red(subst); 155 is_red = ngx_rbt_is_red(subst);
156 156
157 if (subst == subst->parent->left) { 157 if (subst == subst->parent->left) {
158 subst->parent->left = temp; 158 subst->parent->left = temp;
159 159
160 } else { 160 } else {
197 if (subst->right != sentinel) { 197 if (subst->right != sentinel) {
198 subst->right->parent = subst; 198 subst->right->parent = subst;
199 } 199 }
200 } 200 }
201 201
202 if (red) { 202 if (is_red) {
203 return; 203 return;
204 } 204 }
205 205
206 /* a delete fixup */ 206 /* a delete fixup */
207 207
244 ngx_rbt_red(temp->parent); 244 ngx_rbt_red(temp->parent);
245 ngx_rbtree_right_rotate(root, sentinel, temp->parent); 245 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
246 w = temp->parent->left; 246 w = temp->parent->left;
247 } 247 }
248 248
249 if (ngx_rbt_is_black(w->right) && ngx_rbt_is_black(w->left)) { 249 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
250 ngx_rbt_red(w); 250 ngx_rbt_red(w);
251 temp = temp->parent; 251 temp = temp->parent;
252 252
253 } else { 253 } else {
254 if (ngx_rbt_is_black(w->left)) { 254 if (ngx_rbt_is_black(w->left)) {