Re: RBTree implementation and thread structure

On Tue, Apr 15, 2008 at 5:20 AM, Salvatore Benedetto <[email protected]> wrote:
> To go back in topic, am I the only one who thinks that providing a RBTree class
>  would be a good idea?

I have one "already", based on the C version from Julienne Walker
(http://www.eternallyconfuzzled.com/). I mostly C++-ified it (turning
explicit passing of the tree pointer into implicit passing via
'this'). Needs some polishing (mostly renaming single-letter variables
to something more expressive and getting the code to conform to the
Haiku guidelines), and now that Julienne published a "librarified"
version of her implementation with comments, I guess I'm going to grab
her comments and paste it there. She also added a couple extra
functions, so that might be interesting to implement as well.

>  If no one has anything against it I'd like to implement one, unless
>  someone beats me
>  on time. Perhaps an easy ticket for students? :D Too late for that I guess...

Uhm... IMHO it's not worth it. OTOH, Julienne's implementation doesn't
use parent pointers, and in the scheduler there's a potential
performance boost if we do use parent pointers to backtrack on the
tree instead of starting over from the root node. So if you'd like to
cook up an implementation that uses parent pointers, I'd be glad. Just
a suggestion: just add parent pointer maintainance to the library
implementation found here:
http://www.eternallyconfuzzled.com/libs/jsw_rbtree.zip , and changing
the variables names to something more intelligible is a good idea too.
Or give me another week (and a half, perhaps; busy with an
assignment...) and I'll do it myself.


Cheers,
A.

-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference 
Don't miss this year's exciting event. There's still time to save $100. 
Use priority code J8TL2D2. 
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone