From: Davidlohr Bueso <dave@xxxxxxxxxxxx> Subject: 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@xxxxxxxxxxxx Signed-off-by: Davidlohr Bueso <dbueso@xxxxxxx> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx> --- lib/rbtree.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff -puN lib/rbtree.c~rbtree-add-some-additional-comments-for-rebalancing-cases lib/rbtree.c --- a/lib/rbtree.c~rbtree-add-some-additional-comments-for-rebalancing-cases +++ a/lib/rbtree.c @@ -132,7 +132,7 @@ __rb_insert(struct rb_node *node, struct 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 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 } /* - * 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 * / \ / \ _ -- To unsubscribe from this list: send the line "unsubscribe mm-commits" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
