Re: [PATCH 02/13] rbtree: empty nodes have no color

[Daniel Santos <danielfsantos@att.net>]

On 07/09/2012 06:35 PM, Michel Lespinasse wrote:
> Empty nodes have no color.  We can make use of this property to
> simplify the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE
> macros.  Also, we can get rid of the rb_init_node function which had
> been introduced by commit 88d19cf37952a7e1e38b2bf87a00f0e857e63180
> to avoid some issue with the empty node's color not being initialized.
Oh sweet, very glad to see this.  I'm addressing a fairly large scope of
things in my patches and I didn't want to address this yet, so I'm glad
somebody has. :)  I *hoped* that gcc would figure out some of the
excesses of rb_init_node and and just set rb_parent_color directly to
the node address, but better to have actually fixed.  As far as
RB_EMPTY_NODE, I am using that in my test code (which I haven't posted
yet) since I'm testing the actual integrity of a tree and a set of
objects after performing insertions & such on it.  I'm also using it in
some new CONFIG_RBTREE_DEBUG-enabled code.
> I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next()
> are doing there, though. axboe introduced them in commit 10fd48f2376d.
> The way I see it, the 'empty node' abstraction is only used by rbtree
> users to flag nodes that they haven't inserted in any rbtree, so asking
> the predecessor or successor of such nodes doesn't make any sense.
>
> One final rb_init_node() caller was recently added in sysctl code
> to implement faster sysctl name lookups. This code doesn't make use
> of RB_EMPTY_NODE at all, and from what I could see it only called
> rb_init_node() under the mistaken assumption that such initialization
> was required before node insertion.
That was one of the problems with rb_init_node().  Not being documented,
one would assume it's needed unless you study the code more closely.

BTW, the current revision of my patches adds some doc comments to struct
rb_node since the actual function of rb_parent_color isn't very clear
without a lot of study.

/**
 * struct rb_node
 * @rb_parent_color: Contains the color in the lower 2 bits (although
only bit
 *              zero is currently used) and the address of the parent in
 *              the rest (lower 2 bits of address should always be zero on
 *              any arch supported).  If the node is initialized and not a
 *              member of any tree, the parent point to its self.  If the
 *              node belongs to a tree, but is the root element, the
 *              parent will be NULL.  Otherwise, parent will always
 *              point to the parent node in the tree.
 * @rb_right:        Pointer to the right element.
 * @rb_left:         Pointer to the left element.
 */

That said, there's an extra bit in the rb_parent_color that can be used
for some future purpose.

Daniel