linux-kernel - Re: [PATCH 00/13] rbtree updates

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1342102376.28010.7.camel@twins>
Date:	Thu, 12 Jul 2012 16:12:56 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Michel Lespinasse <walken@...gle.com>
Cc:	aarcange@...hat.com, dwmw2@...radead.org, riel@...hat.com,
	daniel.santos@...ox.com, axboe@...nel.dk, ebiederm@...ssion.com,
	linux-mm@...ck.org, akpm@...ux-foundation.org,
	linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org
Subject: Re: [PATCH 00/13] rbtree updates

On Wed, 2012-07-11 at 18:12 -0700, Michel Lespinasse wrote:
> 
> In __rb_erase_color(), some of the cases are more complicated than you drew however, because some node colors aren't known.

Right, the wikipedia article draws them blank, I couldn't come up with a
3rd case, although maybe we can annotate them like (P) to mean blank..


> 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
> +                        */ 


Yes, very nice.. someday when I'm bored I might expand the comments with
the reason why we're doing the given operation.

Also, I was sorely tempted to rename your tmp1,tmp2 variables to sl and
sr.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/