Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752744AbdGSBqt (ORCPT ); Tue, 18 Jul 2017 21:46:49 -0400 Received: from smtp2.provo.novell.com ([137.65.250.81]:45613 "EHLO smtp2.provo.novell.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751906AbdGSBqq (ORCPT ); Tue, 18 Jul 2017 21:46:46 -0400 From: Davidlohr Bueso To: akpm@linux-foundation.org Cc: mingo@kernel.org, peterz@infradead.org, jack@suse.cz, torvalds@linux-foundation.org, kirill.shutemov@linux.intel.com, hch@infradead.org, ldufour@linux.vnet.ibm.com, mhocko@suse.com, mgorman@techsingularity.net, dave@stgolabs.net, linux-kernel@vger.kernel.org, Davidlohr Bueso Subject: [PATCH 03/17] rbtree: add some additional comments for rebalancing cases Date: Tue, 18 Jul 2017 18:45:49 -0700 Message-Id: <20170719014603.19029-4-dave@stgolabs.net> X-Mailer: git-send-email 2.12.0 In-Reply-To: <20170719014603.19029-1-dave@stgolabs.net> References: <20170719014603.19029-1-dave@stgolabs.net> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1463 Lines: 45 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. Signed-off-by: Davidlohr Bueso --- lib/rbtree.c | 8 +++++--- 1 file 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 * / \ / \ -- 2.12.0