On Thu, 2008-02-21 at 15:37 +0530, Balbir Singh wrote: > You use the empty pointer (missing right child), so why do we need a list. May > be I am missing something.
A fully threaded tree also has back-pointer to traverse backwards through the ordered elements. That said, overloading the right child pointer might not be the best thing for the linux kernel, as it will impact all the rb-tree lookups which are open-coded and often performance critical (this is the reason the colour isn't bit encoded in either of the child pointers either). But if you only want a uni directional thread, I guess we can stick it in the unsigned long we use for the node colour. Still, perhaps it's worth it to grow rb_node to 4 words and do the fully threaded thing as there are also a lot of rb_prev() users in the kernel. Who knows.. Anyway, I agree that improving rb_next() is worth looking into for the scheduler. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
