summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavidlohr Bueso <dave@stgolabs.net>2017-09-08 16:14:42 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2017-09-08 18:26:48 -0700
commit35dc67d7d922b2c9a1adb006c7a0f370eeb5c114 (patch)
tree5f9f7154581152b4557d7cf7e64179fccbc02209
parent2aadf7fc7df9e70c99786ffb8452ccdd83d49e59 (diff)
downloadlinux-35dc67d7d922b2c9a1adb006c7a0f370eeb5c114.tar.bz2
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> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
-rw-r--r--lib/rbtree.c8
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
* / \ / \