Looks nice.. How about something like the below on top.. I couldn't immediately find a sane reason for the grand-parent to always be red in the insertion case.
--- --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -23,6 +23,25 @@ #include <linux/rbtree.h> #include <linux/export.h> +/* + * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree + * + * 1) A node is either red or black + * 2) The root is black + * 3) All leaves (NULL) are black + * 4) Both children of every red node are black + * 5) Every simple path from a given node to any of its descendant leaves + * contains the same number of black nodes. + * + * 4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two + * consecutive red nodes in a path and every red node is therefore followed by + * a black. So if B is the number of black nodes on every simple path (as per + * 5), then the longest possible path due to 4 is 2B. + * + * We shall indicate color with case, where black nodes are uppercase and red + * nodes will be lowercase. + */ + #define RB_RED 0 #define RB_BLACK 1 @@ -85,12 +104,27 @@ void rb_insert_color(struct rb_node *nod } else if (rb_is_black(parent)) break; + /* + * XXX + */ gparent = rb_red_parent(parent); if (parent == gparent->rb_left) { tmp = gparent->rb_right; if (tmp && rb_is_red(tmp)) { - /* Case 1 - color flips */ + /* + * Case 1 - color flips + * + * G g + * / \ / \ + * p u --> P U + * / / + * n N + * + * However, since g's parent might be red, and + * 4) does not allow this, we need to recurse + * at g. + */ rb_set_parent_color(tmp, gparent, RB_BLACK); rb_set_parent_color(parent, gparent, RB_BLACK); node = gparent; @@ -100,17 +134,35 @@ void rb_insert_color(struct rb_node *nod } if (parent->rb_right == node) { - /* Case 2 - left rotate at parent */ + /* + * Case 2 - left rotate at parent + * + * G G + * / \ / \ + * p U --> n U + * \ / + * n p + * + * This still leaves us in violation of 4), the + * continuation into Case 3 will fix that. + */ parent->rb_right = tmp = node->rb_left; node->rb_left = parent; if (tmp) - rb_set_parent_color(tmp, parent, - RB_BLACK); + rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); parent = node; } - /* Case 3 - right rotate at gparent */ + /* + * Case 3 - right rotate at gparent + * + * G P + * / \ / \ + * p U --> n g + * / \ + * n U + */ gparent->rb_left = tmp = parent->rb_right; parent->rb_right = gparent; if (tmp) @@ -134,8 +186,7 @@ void rb_insert_color(struct rb_node *nod parent->rb_left = tmp = node->rb_right; node->rb_right = parent; if (tmp) - rb_set_parent_color(tmp, parent, - RB_BLACK); + rb_set_parent_color(tmp, parent, RB_BLACK); rb_set_parent_color(parent, node, RB_RED); parent = node; } @@ -175,43 +226,75 @@ static void __rb_erase_color(struct rb_n } else if (parent->rb_left == node) { sibling = parent->rb_right; if (rb_is_red(sibling)) { - /* Case 1 - left rotate at parent */ + /* + * Case 1 - left rotate at parent + * + * P S + * / \ / \ + * N s --> p Sr + * / \ / \ + * Sl Sr N Sl + */ parent->rb_right = tmp1 = sibling->rb_left; sibling->rb_left = parent; rb_set_parent_color(tmp1, parent, RB_BLACK); - __rb_rotate_set_parents(parent, sibling, root, - RB_RED); + __rb_rotate_set_parents(parent, sibling, root, RB_RED); sibling = tmp1; } tmp1 = sibling->rb_right; if (!tmp1 || rb_is_black(tmp1)) { tmp2 = sibling->rb_left; if (!tmp2 || rb_is_black(tmp2)) { - /* Case 2 - sibling color flip */ - rb_set_parent_color(sibling, parent, - RB_RED); + /* + * Case 2 - sibling color flip + * + * P P + * / \ / \ + * N S --> N s + * / \ / \ + * Sl Sr Sl Sr + * + * This leaves us violating 5), recurse at p. + */ + rb_set_parent_color(sibling, parent, RB_RED); node = parent; parent = rb_parent(node); continue; } - /* Case 3 - right rotate at sibling */ + /* + * Case 3 - right rotate at sibling + * + * P P + * / \ / \ + * N S --> N sl + * / \ / \ + * sl Sr 1 S + * / \ / \ + * 1 2 2 Sr + */ sibling->rb_left = tmp1 = tmp2->rb_right; tmp2->rb_right = sibling; parent->rb_right = tmp2; if (tmp1) - rb_set_parent_color(tmp1, sibling, - RB_BLACK); + rb_set_parent_color(tmp1, sibling, RB_BLACK); tmp1 = sibling; sibling = tmp2; } - /* Case 4 - left rotate at parent + color flips */ + /* + * Case 4 - left rotate at parent + color flips + * + * P S + * / \ / \ + * N S --> P Sr + * / \ / \ + * Sl Sr N Sl + */ parent->rb_right = tmp2 = sibling->rb_left; sibling->rb_left = parent; rb_set_parent_color(tmp1, sibling, RB_BLACK); if (tmp2) rb_set_parent(tmp2, parent); - __rb_rotate_set_parents(parent, sibling, root, - RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); break; } else { sibling = parent->rb_left; @@ -220,8 +303,7 @@ static void __rb_erase_color(struct rb_n parent->rb_left = tmp1 = sibling->rb_right; sibling->rb_right = parent; rb_set_parent_color(tmp1, parent, RB_BLACK); - __rb_rotate_set_parents(parent, sibling, root, - RB_RED); + __rb_rotate_set_parents(parent, sibling, root, RB_RED); sibling = tmp1; } tmp1 = sibling->rb_left; @@ -229,8 +311,7 @@ static void __rb_erase_color(struct rb_n tmp2 = sibling->rb_right; if (!tmp2 || rb_is_black(tmp2)) { /* Case 2 - sibling color flip */ - rb_set_parent_color(sibling, parent, - RB_RED); + rb_set_parent_color(sibling, parent, RB_RED); node = parent; parent = rb_parent(node); continue; @@ -240,8 +321,7 @@ static void __rb_erase_color(struct rb_n tmp2->rb_left = sibling; parent->rb_left = tmp2; if (tmp1) - rb_set_parent_color(tmp1, sibling, - RB_BLACK); + rb_set_parent_color(tmp1, sibling, RB_BLACK); tmp1 = sibling; sibling = tmp2; } @@ -251,8 +331,7 @@ static void __rb_erase_color(struct rb_n rb_set_parent_color(tmp1, sibling, RB_BLACK); if (tmp2) rb_set_parent(tmp2, parent); - __rb_rotate_set_parents(parent, sibling, root, - RB_BLACK); + __rb_rotate_set_parents(parent, sibling, root, RB_BLACK); break; } } @@ -267,8 +346,7 @@ void rb_erase(struct rb_node *node, stru child = node->rb_right; else if (!node->rb_right) child = node->rb_left; - else - { + else { struct rb_node *old = node, *left; node = node->rb_right; @@ -310,17 +388,15 @@ void rb_erase(struct rb_node *node, stru if (child) rb_set_parent(child, parent); - if (parent) - { + if (parent) { if (parent->rb_left == node) parent->rb_left = child; else parent->rb_right = child; - } - else + } else root->rb_node = child; - color: +color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); } @@ -433,8 +509,10 @@ struct rb_node *rb_next(const struct rb_ if (RB_EMPTY_NODE(node)) return NULL; - /* If we have a right-hand child, go down and then left as far - as we can. */ + /* + * If we have a right-hand child, go down and then left as far as we + * can. + */ if (node->rb_right) { node = node->rb_right; while (node->rb_left) @@ -442,12 +520,13 @@ struct rb_node *rb_next(const struct rb_ return (struct rb_node *)node; } - /* No right-hand children. Everything down and left is - smaller than us, so any 'next' node must be in the general - direction of our parent. Go up the tree; any time the - ancestor is a right-hand child of its parent, keep going - up. First time it's a left-hand child of its parent, said - parent is our 'next' node. */ + /* + * No right-hand children. Everything down and left is smaller than + * us, so any 'next' node must be in the general direction of our + * parent. Go up the tree; any time the ancestor is a right-hand child + * of its parent, keep going up. First time it's a left-hand child of + * its parent, said parent is our 'next' node. + */ while ((parent = rb_parent(node)) && node == parent->rb_right) node = parent; @@ -462,8 +541,10 @@ struct rb_node *rb_prev(const struct rb_ if (RB_EMPTY_NODE(node)) return NULL; - /* If we have a left-hand child, go down and then right as far - as we can. */ + /* + * If we have a left-hand child, go down and then right as far as we + * can. + */ if (node->rb_left) { node = node->rb_left; while (node->rb_right) @@ -471,8 +552,10 @@ struct rb_node *rb_prev(const struct rb_ return (struct rb_node *)node; } - /* No left-hand children. Go up till we find an ancestor which - is a right-hand child of its parent */ + /* + * No left-hand children. Go up till we find an ancestor which is a + * right-hand child of its parent + */ while ((parent = rb_parent(node)) && node == parent->rb_left) node = parent; -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
