diff options
| author | Davidlohr Bueso <dave@stgolabs.net> | 2017-08-02 00:03:46 +0000 |
|---|---|---|
| committer | Johannes Weiner <hannes@cmpxchg.org> | 2017-08-02 00:03:46 +0000 |
| commit | c82e35e9ad55d7877459efb853256b5c3b07d982 (patch) | |
| tree | 33aff7fe5a612b5f9610593f093006e3801ac7f1 /lib | |
| parent | c662371c9569a51f4cb78fdb14893d8c38c2b1a7 (diff) | |
rbtree: add some additional comments for rebalancing cases
While overall the code is very nicely commented, it might not be
immediately obvious from the diagrams what is going on. Add a very brief
summary of each case. Opposite cases where the node is the left child are
left untouched.
Link: http://lkml.kernel.org/r/20170719014603.19029-4-dave@stgolabs.net
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/rbtree.c | 8 |
1 files changed, 5 insertions, 3 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index e7cce12f404f..ba4a9d165f1b 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -132,7 +132,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root, if (parent != tmp) { /* parent == gparent->rb_left */ if (tmp && rb_is_red(tmp)) { /* - * Case 1 - color flips + * Case 1 - node's uncle is red (color flips). * * G g * / \ / \ @@ -155,7 +155,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root, tmp = parent->rb_right; if (node == tmp) { /* - * Case 2 - left rotate at parent + * Case 2 - node's uncle is black and node is + * the parent's right child (left rotate at parent). * * G G * / \ / \ @@ -179,7 +180,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root, } /* - * Case 3 - right rotate at gparent + * Case 3 - node's uncle is black and node is + * the parent's left child (right rotate at gparent). * * G P * / \ / \ |