aboutsummaryrefslogtreecommitdiffstats
path: root/lib/rbtree.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 19:30:57 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 03:22:35 -0400
commit6280d2356fd8ad0936a63c10dc1e6accf48d0c61 (patch)
tree867b959cc5441f5af443965acc60d2e78dc7fec0 /lib/rbtree.c
parente125d1471a4f8f1bf7ea9a83deb8d23cb40bd712 (diff)
rbtree: low level optimizations in __rb_erase_color()
In __rb_erase_color(), we often already have pointers to the nodes being rotated and/or know what their colors must be, so we can generate more efficient code than the generic __rb_rotate_left() and __rb_rotate_right() functions. Also when the current node is red or when flipping the sibling's color, the parent is already known so we can use the more efficient rb_set_parent_color() function to set the desired color. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Acked-by: David Woodhouse <David.Woodhouse@intel.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Daniel Santos <daniel.santos@pobox.com> Cc: Jens Axboe <axboe@kernel.dk> Cc: "Eric W. Biederman" <ebiederm@xmission.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/rbtree.c')
-rw-r--r--lib/rbtree.c208
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
54static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 53static 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}
58static 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
63static inline void rb_set_parent_color(struct rb_node *rb, 58static 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
74static 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
97static 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);
257static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, 206static 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 }
generated by cgit v1.2.2 (git 2.25.0) at 2024-09-22 11:31:19 -0400