Commit | Line | Data |
---|---|---|
4b87898e JA |
1 | /* |
2 | Red Black Trees | |
3 | (C) 1999 Andrea Arcangeli <andrea@suse.de> | |
4 | (C) 2002 David Woodhouse <dwmw2@infradead.org> | |
5 | ||
6 | This program is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2 of the License, or | |
9 | (at your option) any later version. | |
10 | ||
11 | This program is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with this program; if not, write to the Free Software | |
fa07eaa6 | 18 | Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
4b87898e JA |
19 | |
20 | linux/lib/rbtree.c | |
21 | */ | |
22 | ||
23 | #include "rbtree.h" | |
24 | ||
e96c0125 | 25 | static void __rb_rotate_left(struct fio_rb_node *node, struct rb_root *root) |
4b87898e | 26 | { |
e96c0125 BVA |
27 | struct fio_rb_node *right = node->rb_right; |
28 | struct fio_rb_node *parent = rb_parent(node); | |
4b87898e JA |
29 | |
30 | if ((node->rb_right = right->rb_left)) | |
44b5374f | 31 | rb_set_parent(right->rb_left, node); |
4b87898e JA |
32 | right->rb_left = node; |
33 | ||
44b5374f JA |
34 | rb_set_parent(right, parent); |
35 | ||
36 | if (parent) | |
4b87898e | 37 | { |
44b5374f JA |
38 | if (node == parent->rb_left) |
39 | parent->rb_left = right; | |
4b87898e | 40 | else |
44b5374f | 41 | parent->rb_right = right; |
4b87898e JA |
42 | } |
43 | else | |
44 | root->rb_node = right; | |
44b5374f | 45 | rb_set_parent(node, right); |
4b87898e JA |
46 | } |
47 | ||
e96c0125 | 48 | static void __rb_rotate_right(struct fio_rb_node *node, struct rb_root *root) |
4b87898e | 49 | { |
e96c0125 BVA |
50 | struct fio_rb_node *left = node->rb_left; |
51 | struct fio_rb_node *parent = rb_parent(node); | |
4b87898e JA |
52 | |
53 | if ((node->rb_left = left->rb_right)) | |
44b5374f | 54 | rb_set_parent(left->rb_right, node); |
4b87898e JA |
55 | left->rb_right = node; |
56 | ||
44b5374f JA |
57 | rb_set_parent(left, parent); |
58 | ||
59 | if (parent) | |
4b87898e | 60 | { |
44b5374f JA |
61 | if (node == parent->rb_right) |
62 | parent->rb_right = left; | |
4b87898e | 63 | else |
44b5374f | 64 | parent->rb_left = left; |
4b87898e JA |
65 | } |
66 | else | |
67 | root->rb_node = left; | |
44b5374f | 68 | rb_set_parent(node, left); |
4b87898e JA |
69 | } |
70 | ||
e96c0125 | 71 | void rb_insert_color(struct fio_rb_node *node, struct rb_root *root) |
4b87898e | 72 | { |
e96c0125 | 73 | struct fio_rb_node *parent, *gparent; |
4b87898e | 74 | |
44b5374f | 75 | while ((parent = rb_parent(node)) && rb_is_red(parent)) |
4b87898e | 76 | { |
44b5374f | 77 | gparent = rb_parent(parent); |
4b87898e JA |
78 | |
79 | if (parent == gparent->rb_left) | |
80 | { | |
81 | { | |
e96c0125 | 82 | register struct fio_rb_node *uncle = gparent->rb_right; |
44b5374f | 83 | if (uncle && rb_is_red(uncle)) |
4b87898e | 84 | { |
44b5374f JA |
85 | rb_set_black(uncle); |
86 | rb_set_black(parent); | |
87 | rb_set_red(gparent); | |
4b87898e JA |
88 | node = gparent; |
89 | continue; | |
90 | } | |
91 | } | |
92 | ||
93 | if (parent->rb_right == node) | |
94 | { | |
e96c0125 | 95 | register struct fio_rb_node *tmp; |
4b87898e JA |
96 | __rb_rotate_left(parent, root); |
97 | tmp = parent; | |
98 | parent = node; | |
99 | node = tmp; | |
100 | } | |
101 | ||
44b5374f JA |
102 | rb_set_black(parent); |
103 | rb_set_red(gparent); | |
4b87898e JA |
104 | __rb_rotate_right(gparent, root); |
105 | } else { | |
106 | { | |
e96c0125 | 107 | register struct fio_rb_node *uncle = gparent->rb_left; |
44b5374f | 108 | if (uncle && rb_is_red(uncle)) |
4b87898e | 109 | { |
44b5374f JA |
110 | rb_set_black(uncle); |
111 | rb_set_black(parent); | |
112 | rb_set_red(gparent); | |
4b87898e JA |
113 | node = gparent; |
114 | continue; | |
115 | } | |
116 | } | |
117 | ||
118 | if (parent->rb_left == node) | |
119 | { | |
e96c0125 | 120 | register struct fio_rb_node *tmp; |
4b87898e JA |
121 | __rb_rotate_right(parent, root); |
122 | tmp = parent; | |
123 | parent = node; | |
124 | node = tmp; | |
125 | } | |
126 | ||
44b5374f JA |
127 | rb_set_black(parent); |
128 | rb_set_red(gparent); | |
4b87898e JA |
129 | __rb_rotate_left(gparent, root); |
130 | } | |
131 | } | |
132 | ||
44b5374f | 133 | rb_set_black(root->rb_node); |
4b87898e JA |
134 | } |
135 | ||
e96c0125 BVA |
136 | static void __rb_erase_color(struct fio_rb_node *node, |
137 | struct fio_rb_node *parent, | |
4b87898e JA |
138 | struct rb_root *root) |
139 | { | |
e96c0125 | 140 | struct fio_rb_node *other; |
4b87898e | 141 | |
44b5374f | 142 | while ((!node || rb_is_black(node)) && node != root->rb_node) |
4b87898e JA |
143 | { |
144 | if (parent->rb_left == node) | |
145 | { | |
146 | other = parent->rb_right; | |
44b5374f | 147 | if (rb_is_red(other)) |
4b87898e | 148 | { |
44b5374f JA |
149 | rb_set_black(other); |
150 | rb_set_red(parent); | |
4b87898e JA |
151 | __rb_rotate_left(parent, root); |
152 | other = parent->rb_right; | |
153 | } | |
44b5374f JA |
154 | if ((!other->rb_left || rb_is_black(other->rb_left)) && |
155 | (!other->rb_right || rb_is_black(other->rb_right))) | |
4b87898e | 156 | { |
44b5374f | 157 | rb_set_red(other); |
4b87898e | 158 | node = parent; |
44b5374f | 159 | parent = rb_parent(node); |
4b87898e JA |
160 | } |
161 | else | |
162 | { | |
44b5374f | 163 | if (!other->rb_right || rb_is_black(other->rb_right)) |
4b87898e | 164 | { |
e96c0125 | 165 | struct fio_rb_node *o_left; |
4b87898e | 166 | if ((o_left = other->rb_left)) |
44b5374f JA |
167 | rb_set_black(o_left); |
168 | rb_set_red(other); | |
4b87898e JA |
169 | __rb_rotate_right(other, root); |
170 | other = parent->rb_right; | |
171 | } | |
44b5374f JA |
172 | rb_set_color(other, rb_color(parent)); |
173 | rb_set_black(parent); | |
4b87898e | 174 | if (other->rb_right) |
44b5374f | 175 | rb_set_black(other->rb_right); |
4b87898e JA |
176 | __rb_rotate_left(parent, root); |
177 | node = root->rb_node; | |
178 | break; | |
179 | } | |
180 | } | |
181 | else | |
182 | { | |
183 | other = parent->rb_left; | |
44b5374f | 184 | if (rb_is_red(other)) |
4b87898e | 185 | { |
44b5374f JA |
186 | rb_set_black(other); |
187 | rb_set_red(parent); | |
4b87898e JA |
188 | __rb_rotate_right(parent, root); |
189 | other = parent->rb_left; | |
190 | } | |
44b5374f JA |
191 | if ((!other->rb_left || rb_is_black(other->rb_left)) && |
192 | (!other->rb_right || rb_is_black(other->rb_right))) | |
4b87898e | 193 | { |
44b5374f | 194 | rb_set_red(other); |
4b87898e | 195 | node = parent; |
44b5374f | 196 | parent = rb_parent(node); |
4b87898e JA |
197 | } |
198 | else | |
199 | { | |
44b5374f | 200 | if (!other->rb_left || rb_is_black(other->rb_left)) |
4b87898e | 201 | { |
e96c0125 | 202 | register struct fio_rb_node *o_right; |
4b87898e | 203 | if ((o_right = other->rb_right)) |
44b5374f JA |
204 | rb_set_black(o_right); |
205 | rb_set_red(other); | |
4b87898e JA |
206 | __rb_rotate_left(other, root); |
207 | other = parent->rb_left; | |
208 | } | |
44b5374f JA |
209 | rb_set_color(other, rb_color(parent)); |
210 | rb_set_black(parent); | |
4b87898e | 211 | if (other->rb_left) |
44b5374f | 212 | rb_set_black(other->rb_left); |
4b87898e JA |
213 | __rb_rotate_right(parent, root); |
214 | node = root->rb_node; | |
215 | break; | |
216 | } | |
217 | } | |
218 | } | |
219 | if (node) | |
44b5374f | 220 | rb_set_black(node); |
4b87898e JA |
221 | } |
222 | ||
e96c0125 | 223 | void rb_erase(struct fio_rb_node *node, struct rb_root *root) |
4b87898e | 224 | { |
e96c0125 | 225 | struct fio_rb_node *child, *parent; |
4b87898e JA |
226 | int color; |
227 | ||
228 | if (!node->rb_left) | |
229 | child = node->rb_right; | |
230 | else if (!node->rb_right) | |
231 | child = node->rb_left; | |
232 | else | |
233 | { | |
e96c0125 | 234 | struct fio_rb_node *old = node, *left; |
4b87898e JA |
235 | |
236 | node = node->rb_right; | |
237 | while ((left = node->rb_left) != NULL) | |
238 | node = left; | |
239 | child = node->rb_right; | |
44b5374f JA |
240 | parent = rb_parent(node); |
241 | color = rb_color(node); | |
4b87898e JA |
242 | |
243 | if (child) | |
44b5374f JA |
244 | rb_set_parent(child, parent); |
245 | if (parent == old) { | |
246 | parent->rb_right = child; | |
4b87898e | 247 | parent = node; |
44b5374f JA |
248 | } else |
249 | parent->rb_left = child; | |
250 | ||
251 | node->rb_parent_color = old->rb_parent_color; | |
4b87898e JA |
252 | node->rb_right = old->rb_right; |
253 | node->rb_left = old->rb_left; | |
254 | ||
44b5374f | 255 | if (rb_parent(old)) |
4b87898e | 256 | { |
44b5374f JA |
257 | if (rb_parent(old)->rb_left == old) |
258 | rb_parent(old)->rb_left = node; | |
4b87898e | 259 | else |
44b5374f | 260 | rb_parent(old)->rb_right = node; |
4b87898e JA |
261 | } else |
262 | root->rb_node = node; | |
263 | ||
44b5374f | 264 | rb_set_parent(old->rb_left, node); |
4b87898e | 265 | if (old->rb_right) |
44b5374f | 266 | rb_set_parent(old->rb_right, node); |
4b87898e JA |
267 | goto color; |
268 | } | |
269 | ||
44b5374f JA |
270 | parent = rb_parent(node); |
271 | color = rb_color(node); | |
4b87898e JA |
272 | |
273 | if (child) | |
44b5374f | 274 | rb_set_parent(child, parent); |
4b87898e JA |
275 | if (parent) |
276 | { | |
277 | if (parent->rb_left == node) | |
278 | parent->rb_left = child; | |
279 | else | |
280 | parent->rb_right = child; | |
281 | } | |
282 | else | |
283 | root->rb_node = child; | |
284 | ||
285 | color: | |
286 | if (color == RB_BLACK) | |
287 | __rb_erase_color(child, parent, root); | |
288 | } | |
289 | ||
290 | /* | |
291 | * This function returns the first node (in sort order) of the tree. | |
292 | */ | |
e96c0125 | 293 | struct fio_rb_node *rb_first(struct rb_root *root) |
4b87898e | 294 | { |
e96c0125 | 295 | struct fio_rb_node *n; |
4b87898e JA |
296 | |
297 | n = root->rb_node; | |
298 | if (!n) | |
299 | return NULL; | |
300 | while (n->rb_left) | |
301 | n = n->rb_left; | |
302 | return n; | |
303 | } | |
8f2b1374 | 304 | |
e96c0125 | 305 | struct fio_rb_node *rb_next(const struct fio_rb_node *node) |
8f2b1374 | 306 | { |
e96c0125 | 307 | struct fio_rb_node *parent; |
8f2b1374 JA |
308 | |
309 | if (RB_EMPTY_NODE(node)) | |
310 | return NULL; | |
311 | ||
312 | /* | |
313 | * If we have a right-hand child, go down and then left as far | |
314 | * as we can. | |
315 | */ | |
316 | if (node->rb_right) { | |
317 | node = node->rb_right; | |
318 | while (node->rb_left) | |
319 | node=node->rb_left; | |
e96c0125 | 320 | return (struct fio_rb_node *)node; |
8f2b1374 JA |
321 | } |
322 | ||
323 | /* | |
324 | * No right-hand children. Everything down and left is smaller than us, | |
325 | * so any 'next' node must be in the general direction of our parent. | |
326 | * Go up the tree; any time the ancestor is a right-hand child of its | |
327 | * parent, keep going up. First time it's a left-hand child of its | |
328 | * parent, said parent is our 'next' node. | |
329 | */ | |
330 | while ((parent = rb_parent(node)) && node == parent->rb_right) | |
331 | node = parent; | |
332 | ||
333 | return parent; | |
334 | } |