Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 212:679f60139863

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx-0.0.1-2003-12-19-11:15:11 import
author Igor Sysoev <igor@sysoev.ru>
date Fri, 19 Dec 2003 08:15:11 +0000
parents 6e0fef527732
children f536f91e8e99
comparison
equal deleted inserted replaced
211:fd9fecc4193f 212:679f60139863
29 ngx_rbtree_t *temp; 29 ngx_rbtree_t *temp;
30 30
31 /* a binary tree insert */ 31 /* a binary tree insert */
32 32
33 if (*root == sentinel) { 33 if (*root == sentinel) {
34 node->parent = sentinel; 34 node->parent = NULL;
35 node->left = sentinel; 35 node->left = sentinel;
36 node->right = sentinel; 36 node->right = sentinel;
37 ngx_rbt_black(node); 37 ngx_rbt_black(node);
38 *root = node; 38 *root = node;
39 39
69 69
70 /* re-balance tree */ 70 /* re-balance tree */
71 71
72 ngx_rbt_red(node); 72 ngx_rbt_red(node);
73 73
74 while (node->parent && ngx_rbt_is_red(node->parent)) { 74 while (node != *root && ngx_rbt_is_red(node->parent)) {
75 75
76 if (node->parent == node->parent->parent->left) { 76 if (node->parent == node->parent->parent->left) {
77 temp = node->parent->parent->right; 77 temp = node->parent->parent->right;
78 78
79 if (ngx_rbt_is_red(temp)) { 79 if (ngx_rbt_is_red(temp)) {
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_rbtree_t *subst, *temp, *w; 127 ngx_rbtree_t *subst, *temp, *w;
127 128
128 /* a binary tree delete */ 129 /* a binary tree delete */
129 130
130 if (node->left == sentinel || node->right == sentinel) { 131 if (node->left == sentinel) {
132 temp = node->right;
131 subst = node; 133 subst = node;
132 134
133 } else { 135 } else if (node->right == sentinel) {
134 136 temp = node->left;
135 /* find a node successor */ 137 subst = node;
136 138
137 if (node->right == sentinel) { 139 } else {
138 temp = node; 140 subst = ngx_rbtree_min(node->right, sentinel);
139 subst = node->parent; 141
140 142 if (subst->left != sentinel) {
141 while (subst != sentinel && temp == subst->right) { 143 temp = subst->left;
142 temp = subst; 144 } else {
143 subst = subst->parent; 145 temp = subst->right;
144 } 146 }
145 147 }
146 } else { 148
147 subst = ngx_rbtree_min(node->right, sentinel); 149 if (subst == *root) {
148 } 150 /* it's the last node */
149 } 151 *root = sentinel;
150 152 return;
151 if (subst->left != sentinel) { 153 }
152 temp = subst->left; 154
153 } else { 155 red = ngx_rbt_is_red(subst);
154 temp = subst->right; 156
155 } 157 if (subst == subst->parent->left) {
156
157 temp->parent = subst->parent;
158
159 if (subst->parent == sentinel) {
160 *root = temp;
161
162 } else if (subst == subst->parent->left) {
163 subst->parent->left = temp; 158 subst->parent->left = temp;
164 159
165 } else { 160 } else {
166 subst->parent->right = temp; 161 subst->parent->right = temp;
167 } 162 }
168 163
169 if (subst != node) { 164 if (subst == node) {
170 node->key = subst->key; 165
171 node->color = subst->color; 166 temp->parent = subst->parent;
172 } 167
173 168 } else {
174 if (ngx_rbt_is_red(subst)) { 169
170 if (subst->parent == node) {
171 temp->parent = subst;
172
173 } else {
174 temp->parent = subst->parent;
175 }
176
177 subst->left = node->left;
178 subst->right = node->right;
179 subst->parent = node->parent;
180 ngx_rbt_copy_color(subst, node);
181
182 if (node == *root) {
183 *root = subst;
184
185 } else {
186 if (node == node->parent->left) {
187 node->parent->left = subst;
188 } else {
189 node->parent->right = subst;
190 }
191 }
192
193 if (subst->left != sentinel) {
194 subst->left->parent = subst;
195 }
196
197 if (subst->right != sentinel) {
198 subst->right->parent = subst;
199 }
200 }
201
202 if (red) {
175 return; 203 return;
176 } 204 }
177 205
178 /* a delete fixup */ 206 /* a delete fixup */
179 207
180 while (temp->parent != sentinel && ngx_rbt_is_black(temp)) { 208 while (temp != *root && ngx_rbt_is_black(temp)) {
209
181 if (temp == temp->parent->left) { 210 if (temp == temp->parent->left) {
182 w = temp->parent->right; 211 w = temp->parent->right;
183 212
184 if (ngx_rbt_is_red(w)) { 213 if (ngx_rbt_is_red(w)) {
185 ngx_rbt_black(w); 214 ngx_rbt_black(w);
255 temp->left->parent = node; 284 temp->left->parent = node;
256 } 285 }
257 286
258 temp->parent = node->parent; 287 temp->parent = node->parent;
259 288
260 if (node->parent == sentinel) { 289 if (node == *root) {
261 *root = temp; 290 *root = temp;
262 291
263 } else if (node == node->parent->left) { 292 } else if (node == node->parent->left) {
264 node->parent->left = temp; 293 node->parent->left = temp;
265 294
285 temp->right->parent = node; 314 temp->right->parent = node;
286 } 315 }
287 316
288 temp->parent = node->parent; 317 temp->parent = node->parent;
289 318
290 if (node->parent == sentinel) { 319 if (node == *root) {
291 *root = temp; 320 *root = temp;
292 321
293 } else if (node == node->parent->right) { 322 } else if (node == node->parent->right) {
294 node->parent->right = temp; 323 node->parent->right = temp;
295 324