lkml.org 
[lkml]   [2012]   [Jul]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 00/13] rbtree updates
On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra <peterz@infradead.org> 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.


\
 
 \ /
  Last update: 2012-07-12 04:01    [W:0.145 / U:0.060 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site