diff options
-rw-r--r-- | lib/rbtree.c | 208 |
1 files changed, 115 insertions, 93 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index eb823a31099c..a38e473d8fe7 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c | |||
@@ -39,7 +39,8 @@ | |||
39 | * 5), then the longest possible path due to 4 is 2B. | 39 | * 5), then the longest possible path due to 4 is 2B. |
40 | * | 40 | * |
41 | * We shall indicate color with case, where black nodes are uppercase and red | 41 | * We shall indicate color with case, where black nodes are uppercase and red |
42 | * nodes will be lowercase. | 42 | * nodes will be lowercase. Unknown color nodes shall be drawn as red within |
43 | * parentheses and have some accompanying text comment. | ||
43 | */ | 44 | */ |
44 | 45 | ||
45 | #define RB_RED 0 | 46 | #define RB_RED 0 |
@@ -48,17 +49,11 @@ | |||
48 | #define rb_color(r) ((r)->__rb_parent_color & 1) | 49 | #define rb_color(r) ((r)->__rb_parent_color & 1) |
49 | #define rb_is_red(r) (!rb_color(r)) | 50 | #define rb_is_red(r) (!rb_color(r)) |
50 | #define rb_is_black(r) rb_color(r) | 51 | #define rb_is_black(r) rb_color(r) |
51 | #define rb_set_red(r) do { (r)->__rb_parent_color &= ~1; } while (0) | ||
52 | #define rb_set_black(r) do { (r)->__rb_parent_color |= 1; } while (0) | ||
53 | 52 | ||
54 | static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) | 53 | static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) |
55 | { | 54 | { |
56 | rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; | 55 | rb->__rb_parent_color = rb_color(rb) | (unsigned long)p; |
57 | } | 56 | } |
58 | static inline void rb_set_color(struct rb_node *rb, int color) | ||
59 | { | ||
60 | rb->__rb_parent_color = (rb->__rb_parent_color & ~1) | color; | ||
61 | } | ||
62 | 57 | ||
63 | static inline void rb_set_parent_color(struct rb_node *rb, | 58 | static inline void rb_set_parent_color(struct rb_node *rb, |
64 | struct rb_node *p, int color) | 59 | struct rb_node *p, int color) |
@@ -71,52 +66,6 @@ static inline struct rb_node *rb_red_parent(struct rb_node *red) | |||
71 | return (struct rb_node *)red->__rb_parent_color; | 66 | return (struct rb_node *)red->__rb_parent_color; |
72 | } | 67 | } |
73 | 68 | ||
74 | static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) | ||
75 | { | ||
76 | struct rb_node *right = node->rb_right; | ||
77 | struct rb_node *parent = rb_parent(node); | ||
78 | |||
79 | if ((node->rb_right = right->rb_left)) | ||
80 | rb_set_parent(right->rb_left, node); | ||
81 | right->rb_left = node; | ||
82 | |||
83 | rb_set_parent(right, parent); | ||
84 | |||
85 | if (parent) | ||
86 | { | ||
87 | if (node == parent->rb_left) | ||
88 | parent->rb_left = right; | ||
89 | else | ||
90 | parent->rb_right = right; | ||
91 | } | ||
92 | else | ||
93 | root->rb_node = right; | ||
94 | rb_set_parent(node, right); | ||
95 | } | ||
96 | |||
97 | static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) | ||
98 | { | ||
99 | struct rb_node *left = node->rb_left; | ||
100 | struct rb_node *parent = rb_parent(node); | ||
101 | |||
102 | if ((node->rb_left = left->rb_right)) | ||
103 | rb_set_parent(left->rb_right, node); | ||
104 | left->rb_right = node; | ||
105 | |||
106 | rb_set_parent(left, parent); | ||
107 | |||
108 | if (parent) | ||
109 | { | ||
110 | if (node == parent->rb_right) | ||
111 | parent->rb_right = left; | ||
112 | else | ||
113 | parent->rb_left = left; | ||
114 | } | ||
115 | else | ||
116 | root->rb_node = left; | ||
117 | rb_set_parent(node, left); | ||
118 | } | ||
119 | |||
120 | /* | 69 | /* |
121 | * Helper function for rotations: | 70 | * Helper function for rotations: |
122 | * - old's parent and color get assigned to new | 71 | * - old's parent and color get assigned to new |
@@ -257,7 +206,7 @@ EXPORT_SYMBOL(rb_insert_color); | |||
257 | static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, | 206 | static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, |
258 | struct rb_root *root) | 207 | struct rb_root *root) |
259 | { | 208 | { |
260 | struct rb_node *other; | 209 | struct rb_node *sibling, *tmp1, *tmp2; |
261 | 210 | ||
262 | while (true) { | 211 | while (true) { |
263 | /* | 212 | /* |
@@ -270,63 +219,136 @@ static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, | |||
270 | * and tree rotations as per one of the 4 cases below. | 219 | * and tree rotations as per one of the 4 cases below. |
271 | */ | 220 | */ |
272 | if (node && rb_is_red(node)) { | 221 | if (node && rb_is_red(node)) { |
273 | rb_set_black(node); | 222 | rb_set_parent_color(node, parent, RB_BLACK); |
274 | break; | 223 | break; |
275 | } else if (!parent) { | 224 | } else if (!parent) { |
276 | break; | 225 | break; |
277 | } else if (parent->rb_left == node) { | 226 | } else if (parent->rb_left == node) { |
278 | other = parent->rb_right; | 227 | sibling = parent->rb_right; |
279 | if (rb_is_red(other)) | 228 | if (rb_is_red(sibling)) { |
280 | { | 229 | /* |
281 | rb_set_black(other); | 230 | * Case 1 - left rotate at parent |
282 | rb_set_red(parent); | 231 | * |
283 | __rb_rotate_left(parent, root); | 232 | * P S |
284 | other = parent->rb_right; | 233 | * / \ / \ |
234 | * N s --> p Sr | ||
235 | * / \ / \ | ||
236 | * Sl Sr N Sl | ||
237 | */ | ||
238 | parent->rb_right = tmp1 = sibling->rb_left; | ||
239 | sibling->rb_left = parent; | ||
240 | rb_set_parent_color(tmp1, parent, RB_BLACK); | ||
241 | __rb_rotate_set_parents(parent, sibling, root, | ||
242 | RB_RED); | ||
243 | sibling = tmp1; | ||
285 | } | 244 | } |
286 | if (!other->rb_right || rb_is_black(other->rb_right)) { | 245 | tmp1 = sibling->rb_right; |
287 | if (!other->rb_left || | 246 | if (!tmp1 || rb_is_black(tmp1)) { |
288 | rb_is_black(other->rb_left)) { | 247 | tmp2 = sibling->rb_left; |
289 | rb_set_red(other); | 248 | if (!tmp2 || rb_is_black(tmp2)) { |
249 | /* | ||
250 | * Case 2 - sibling color flip | ||
251 | * (p could be either color here) | ||
252 | * | ||
253 | * (p) (p) | ||
254 | * / \ / \ | ||
255 | * N S --> N s | ||
256 | * / \ / \ | ||
257 | * Sl Sr Sl Sr | ||
258 | * | ||
259 | * This leaves us violating 5), so | ||
260 | * recurse at p. If p is red, the | ||
261 | * recursion will just flip it to black | ||
262 | * and exit. If coming from Case 1, | ||
263 | * p is known to be red. | ||
264 | */ | ||
265 | rb_set_parent_color(sibling, parent, | ||
266 | RB_RED); | ||
290 | node = parent; | 267 | node = parent; |
291 | parent = rb_parent(node); | 268 | parent = rb_parent(node); |
292 | continue; | 269 | continue; |
293 | } | 270 | } |
294 | rb_set_black(other->rb_left); | 271 | /* |
295 | rb_set_red(other); | 272 | * Case 3 - right rotate at sibling |
296 | __rb_rotate_right(other, root); | 273 | * (p could be either color here) |
297 | other = parent->rb_right; | 274 | * |
275 | * (p) (p) | ||
276 | * / \ / \ | ||
277 | * N S --> N Sl | ||
278 | * / \ \ | ||
279 | * sl Sr s | ||
280 | * \ | ||
281 | * Sr | ||
282 | */ | ||
283 | sibling->rb_left = tmp1 = tmp2->rb_right; | ||
284 | tmp2->rb_right = sibling; | ||
285 | parent->rb_right = tmp2; | ||
286 | if (tmp1) | ||
287 | rb_set_parent_color(tmp1, sibling, | ||
288 | RB_BLACK); | ||
289 | tmp1 = sibling; | ||
290 | sibling = tmp2; | ||
298 | } | 291 | } |
299 | rb_set_color(other, rb_color(parent)); | 292 | /* |
300 | rb_set_black(parent); | 293 | * Case 4 - left rotate at parent + color flips |
301 | rb_set_black(other->rb_right); | 294 | * (p and sl could be either color here. |
302 | __rb_rotate_left(parent, root); | 295 | * After rotation, p becomes black, s acquires |
296 | * p's color, and sl keeps its color) | ||
297 | * | ||
298 | * (p) (s) | ||
299 | * / \ / \ | ||
300 | * N S --> P Sr | ||
301 | * / \ / \ | ||
302 | * (sl) sr N (sl) | ||
303 | */ | ||
304 | parent->rb_right = tmp2 = sibling->rb_left; | ||
305 | sibling->rb_left = parent; | ||
306 | rb_set_parent_color(tmp1, sibling, RB_BLACK); | ||
307 | if (tmp2) | ||
308 | rb_set_parent(tmp2, parent); | ||
309 | __rb_rotate_set_parents(parent, sibling, root, | ||
310 | RB_BLACK); | ||
303 | break; | 311 | break; |
304 | } else { | 312 | } else { |
305 | other = parent->rb_left; | 313 | sibling = parent->rb_left; |
306 | if (rb_is_red(other)) | 314 | if (rb_is_red(sibling)) { |
307 | { | 315 | /* Case 1 - right rotate at parent */ |
308 | rb_set_black(other); | 316 | parent->rb_left = tmp1 = sibling->rb_right; |
309 | rb_set_red(parent); | 317 | sibling->rb_right = parent; |
310 | __rb_rotate_right(parent, root); | 318 | rb_set_parent_color(tmp1, parent, RB_BLACK); |
311 | other = parent->rb_left; | 319 | __rb_rotate_set_parents(parent, sibling, root, |
320 | RB_RED); | ||
321 | sibling = tmp1; | ||
312 | } | 322 | } |
313 | if (!other->rb_left || rb_is_black(other->rb_left)) { | 323 | tmp1 = sibling->rb_left; |
314 | if (!other->rb_right || | 324 | if (!tmp1 || rb_is_black(tmp1)) { |
315 | rb_is_black(other->rb_right)) { | 325 | tmp2 = sibling->rb_right; |
316 | rb_set_red(other); | 326 | if (!tmp2 || rb_is_black(tmp2)) { |
327 | /* Case 2 - sibling color flip */ | ||
328 | rb_set_parent_color(sibling, parent, | ||
329 | RB_RED); | ||
317 | node = parent; | 330 | node = parent; |
318 | parent = rb_parent(node); | 331 | parent = rb_parent(node); |
319 | continue; | 332 | continue; |
320 | } | 333 | } |
321 | rb_set_black(other->rb_right); | 334 | /* Case 3 - right rotate at sibling */ |
322 | rb_set_red(other); | 335 | sibling->rb_right = tmp1 = tmp2->rb_left; |
323 | __rb_rotate_left(other, root); | 336 | tmp2->rb_left = sibling; |
324 | other = parent->rb_left; | 337 | parent->rb_left = tmp2; |
338 | if (tmp1) | ||
339 | rb_set_parent_color(tmp1, sibling, | ||
340 | RB_BLACK); | ||
341 | tmp1 = sibling; | ||
342 | sibling = tmp2; | ||
325 | } | 343 | } |
326 | rb_set_color(other, rb_color(parent)); | 344 | /* Case 4 - left rotate at parent + color flips */ |
327 | rb_set_black(parent); | 345 | parent->rb_left = tmp2 = sibling->rb_right; |
328 | rb_set_black(other->rb_left); | 346 | sibling->rb_right = parent; |
329 | __rb_rotate_right(parent, root); | 347 | rb_set_parent_color(tmp1, sibling, RB_BLACK); |
348 | if (tmp2) | ||
349 | rb_set_parent(tmp2, parent); | ||
350 | __rb_rotate_set_parents(parent, sibling, root, | ||
351 | RB_BLACK); | ||
330 | break; | 352 | break; |
331 | } | 353 | } |
332 | } | 354 | } |