diff options
| author | Richard Braun <rbraun@sceen.net> | 2012-04-22 17:33:36 +0200 |
|---|---|---|
| committer | Richard Braun <rbraun@sceen.net> | 2012-04-22 17:40:28 +0200 |
| commit | eaf536856d05cfca2259b8e7c0fe77cb8fc1c439 (patch) | |
| tree | b3c32489f6ed0f64e51232cd04a37d42877bfd39 /kern | |
| parent | d518d34ce0794da016d223a6a4f1b5a69825ede8 (diff) | |
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.
Diffstat (limited to 'kern')
| -rw-r--r-- | kern/rbtree.c | 26 |
1 files changed, 12 insertions, 14 deletions
diff --git a/kern/rbtree.c b/kern/rbtree.c index f6b89bc..0f5eb9a 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); |