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 -- 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>