diff options
| author | Jonathan Corbet <corbet@lwn.net> | 2016-12-27 12:53:44 -0700 |
|---|---|---|
| committer | Jonathan Corbet <corbet@lwn.net> | 2016-12-27 12:53:44 -0700 |
| commit | 54ab6db0909061ab7ee07233d3cab86d29f86e6c (patch) | |
| tree | a7650ab5c0fa3a6a3841de8e8693041b3e009054 /lib/rbtree.c | |
| parent | 217e2bfab22e740227df09f22165e834cddd8a3b (diff) | |
| parent | 7ce7d89f48834cefece7804d38fc5d85382edf77 (diff) | |
Merge tag 'v4.10-rc1' into docs-next
Linux 4.10-rc1
Diffstat (limited to 'lib/rbtree.c')
| -rw-r--r-- | lib/rbtree.c | 23 |
1 files changed, 19 insertions, 4 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index eb8a19fee110..1f8b112a7c35 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -296,11 +296,26 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root, * * (p) (p) * / \ / \ - * N S --> N Sl + * N S --> N sl * / \ \ - * sl Sr s + * sl Sr S * \ * Sr + * + * Note: p might be red, and then both + * p and sl are red after rotation(which + * breaks property 4). This is fixed in + * Case 4 (in __rb_rotate_set_parents() + * which set sl the color of p + * and set p RB_BLACK) + * + * (p) (sl) + * / \ / \ + * N sl --> P S + * \ / \ + * S N Sr + * \ + * Sr */ tmp1 = tmp2->rb_right; WRITE_ONCE(sibling->rb_left, tmp1); @@ -365,7 +380,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root, } break; } - /* Case 3 - right rotate at sibling */ + /* Case 3 - left rotate at sibling */ tmp1 = tmp2->rb_left; WRITE_ONCE(sibling->rb_right, tmp1); WRITE_ONCE(tmp2->rb_left, sibling); @@ -377,7 +392,7 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root, tmp1 = sibling; sibling = tmp2; } - /* Case 4 - left rotate at parent + color flips */ + /* Case 4 - right rotate at parent + color flips */ tmp2 = sibling->rb_right; WRITE_ONCE(parent->rb_left, tmp2); WRITE_ONCE(sibling->rb_right, parent); |