Re: [boost] Ion Gaztañaga's Intrusive Library

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-03-19 14:05:24

Howard Hinnant wrote:

> It always amuses me when Ion *knows* I'm lurking. :-)  Caught red- 
> handed again!

Something related to containers/move semantics/performance is just too 
attractive to ignore ;-)

> And I haven't been lurking quite closely enough to know if this  
> matters, but in both CodeWarrior and gcc the value_type is elided from  
> the embedded end node.  I.e. a node_base is actually embedded which  
> contains only the links, and node derives from node_base and adds the  
> value_type.

The same happens with Intrusive. The user derives or stores a hook to 
make the class intrusive-friendly. The hook contains a minimum generic 
node that just stores pointers. All the low-level (link, unlink, 
rebalance...) algorithms operate with these minimal nodes to avoid 
instantiating algorithms for all user types. The end node is a minimal 
node. When the user access to the real value (for example dereferencing 
an iterator), a downcasting or similar transformation is done to obtain 
the whole value from the minimal node.

> std::list<my_data, my_allocator<my_data>> l;
> char buffer[sizeof(my_node)] a_node;  // alignment magic...
> l.get_allocator().set_allocate(&a_node);
> l.push_back(a_node.data_);
> 
> or something along those lines (I'm going from memory).  It was very  
> low level and my_data_ was a pod, so I didn't have to worry about  
> double constructing and such.  It worked pretty well performance wise,  
> but was admittedly pretty ugly and I couldn't claim it was portable.   

<advertisement>
The philosophy behind Intrusive was to build something that would make 
building STL-like containers trivial. It's also a way to extract all the 
common code unrelated to object construction so that we could easily 
construct new value_types using copy construction, move construction or 
even in-place construction, reusing the same binary code to insert them 
in the container. As an experiment, I've implemented all Interprocess 
node containers using Intrusive, so I think Intrusive offers enough 
functions to do so.
</advertisement>

Regards,

Ion