On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:
> 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.
Do you mean the case you marked XXX ? it is actually parent that is
red, which we know because we tested that a few lines earlier.
> @@ -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);
See :)
> 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.
> + */
I like these diagrams - I initially didn't think they'd work well, given the need for colors etc, but I now see that it's workable.
In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.
This is what I ended up with:
* 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.
+ * nodes will be lowercase. Unknown color nodes shall be drawn as red with
+ * some accompanying text comment.
*/
+ /*
+ * Case 2 - sibling color flip
+ * (p could be either color here)
+ *
+ * p p
+ * / \ / \
+ * N S --> N s
+ * / \ / \
+ * Sl Sr Sl Sr
+ *
+ * This leaves us violating 5), so
+ * recurse at p. If p is red, the
+ * recursion will just flip it to black
+ * and exit. If coming from Case 1,
+ * p is known to be red.
+ */
+ /*
+ * Case 3 - right rotate at sibling
+ * (p could be either color here)
+ *
+ * p p
+ * / \ / \
+ * N S --> N Sl
+ * / \ \
+ * sl Sr s
+ * \
+ * Sr
+ */
+ /*
+ * Case 4 - left rotate at parent + color flips
+ * (p and sl could be either color here.
+ * After rotation, p becomes black, s acquires
+ * p's color, and sl keeps its color)
+ *
+ * p s
+ * / \ / \
+ * N S --> P Sr
+ * / \ / \
+ * sl sr N sl
+ */
--
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>