From eaf536856d05cfca2259b8e7c0fe77cb8fc1c439 Mon Sep 17 00:00:00 2001
From: Richard Braun <rbraun@sceen.net>
Date: Sun, 22 Apr 2012 17:33:36 +0200
Subject: Update comments.

Literature about red-black trees vary concerning the cases numbering,
and the implementation doesn't make all of them clearly appear. Remove
cases numbering references to avoid confusion.
---
 kern/rbtree.c | 26 ++++++++++++--------------
 1 file changed, 12 insertions(+), 14 deletions(-)

diff --git a/kern/rbtree.c b/kern/rbtree.c
index f6b89bc4..0f5eb9ae 100644
--- a/kern/rbtree.c
+++ b/kern/rbtree.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2010 Richard Braun.
+ * Copyright (c) 2010, 2012 Richard Braun.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -180,7 +180,7 @@ void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
         uncle = grand_parent->children[right];
 
         /*
-         * Case 1: uncle is red. Flip colors and repeat at grand parent.
+         * Uncle is red. Flip colors and repeat at grand parent.
          */
         if ((uncle != NULL) && rbtree_is_red(uncle)) {
             rbtree_set_black(uncle);
@@ -192,8 +192,7 @@ void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
         }
 
         /*
-         * Case 2: node is the right child of its parent. Rotate left at parent
-         * to reduce to case 3.
+         * Node is the right child of its parent. Rotate left at parent.
          */
         if (parent->children[right] == node) {
             rbtree_rotate(tree, parent, left);
@@ -203,8 +202,8 @@ void rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent,
         }
 
         /*
-         * Case 3: node is the left child of its parent. Handle colors, rotate
-         * right at grand parent, and leave.
+         * Node is the left child of its parent. Handle colors, rotate right
+         * at grand parent, and leave.
          */
         rbtree_set_black(parent);
         rbtree_set_red(grand_parent);
@@ -306,8 +305,8 @@ update_color:
         brother = parent->children[right];
 
         /*
-         * Case 1: brother is red. Recolor and rotate left at parent so that
-         * brother becomes black.
+         * Brother is red. Recolor and rotate left at parent so that brother
+         * becomes black.
          */
         if (rbtree_is_red(brother)) {
             rbtree_set_black(brother);
@@ -317,7 +316,7 @@ update_color:
         }
 
         /*
-         * Case 2: brother has no red child. Recolor and repeat at parent.
+         * Brother has no red child. Recolor and repeat at parent.
          */
         if (((brother->children[RBTREE_LEFT] == NULL)
              || rbtree_is_black(brother->children[RBTREE_LEFT]))
@@ -330,8 +329,7 @@ update_color:
         }
 
         /*
-         * Case 3: brother's right child is black. Recolor and rotate right
-         * at brother to reduce to case 4.
+         * Brother's right child is black. Recolor and rotate right at brother.
          */
         if ((brother->children[right] == NULL)
             || rbtree_is_black(brother->children[right])) {
@@ -342,9 +340,9 @@ update_color:
         }
 
         /*
-         * Case 4: brother's left child is black. Exchange parent and brother
-         * colors (we already know brother is black), set brother's right child
-         * black, rotate left at parent and leave.
+         * Brother's left child is black. Exchange parent and brother colors
+         * (we already know brother is black), set brother's right child black,
+         * rotate left at parent and leave.
          */
         rbtree_set_color(brother, rbtree_color(parent));
         rbtree_set_black(parent);
-- 
cgit v1.2.3