[rust-dev] purely function red-black tree

Patrick Walton pwalton at mozilla.com
Sat Dec 15 19:15:50 PST 2012


On 12/15/12 4:38 PM, Steve Jenson wrote:
> I could use advice here. Is it possible for me to write a single trait
> that can be used by both users that want to use managed boxes and people
> who wish otherwise? IOW, what is the best way to abstract away the @sign
> in this trait?

It depends on how you implement the red-black tree. With your current 
implementation, I think you're probably going to have to expose the GC 
to the user, because that implementation of red-black trees doesn't do 
manual memory management. There's no real way to abstract over methods 
of automatic storage reclamation in general (and adding such a mechanism 
would be pretty complex).

If you're OK with having get() copy out the value instead of returning a 
reference to it, then you could avoid exposing the GC to the user, at 
the cost of copying every value you put in (which is not as bad as it 
sounds, since the cost of a copy of an @ box is practically zero). 
However, if you modify the algorithm to use unique pointers throughout, 
then your methods like get() can probably return a borrowed pointer instead.

> What is the rationale for making this impossible?

You can put private methods on the anonymous trait associated with the 
type instead. Say `impl<K:Copy Eq Ord, V:Copy> RBMap<K,V> { ... }` (i.e. 
leave off the trait) to put methods in the anonymous trait.

Patrick



More information about the Rust-dev mailing list