Mercurial > hg > nginx
comparison src/core/ngx_rbtree.c @ 212:679f60139863
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 |