Re: [PATCH 00/13] rbtree updates
From: Michel Lespinasse <hidden>
Date: 2012-07-12 01:12:14
Also in:
lkml
On Wed, Jul 11, 2012 at 6:23 AM, Peter Zijlstra [off-list ref] 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.
quoted hunk ↗ jump to hunk
@@ -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@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>