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

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2007-03-18 19:55:33

On Mar 18, 2007, at 8:10 AM, Ion Gaztañaga wrote:

> //Imagine list allocates the "end" node using the allocator
> std::list<MyObject> list;
>
> //If we want list to be usable after being moved
> //we must COPY the allocator and ALLOCATE a new
> //end node. Both operations might throw!
> std::list<MyObject> list2(std::move(list));
>
> Howard can correct me if I'm wrong but I think the Metrowerks/ 
> Freescale
> implementation of std containers using move semantics store the end  
> node
> inside the container to achieve no throw guarantee in default
> construction and move operations in node containers.

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

Yes, the CodeWarrior Freescale list, map, multimap, set, multiset use  
the embedded end-node technique.  And it is possible this issue is  
about to come to a head, not sure.  Fwiw, gcc 4.x also uses the same  
technique (but I claim CodeWarrior was there first :-)).  And yes, I  
think this design for node-based STL containers is far superior to the  
heap-allocated end node.

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.

<aside>
I once did an intrusive std::list, using the CodeWarrior std::list  
implementation by using a custom allocator.  I told the allocator  
where to allocate the next node and it just did so.  The allocator had  
to have knowledge of the node layout for the std::list, making it not  
really officially portable.  But how many node layouts could there be  
in practice?

struct my_node
{
     my_node* prev_;
     my_node* next_;
     my_data_ data_;
};

...

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.   
Fwiw, the application was malloc/free (never actually shipped).  I  
managed the memory blocks in the malloc heap using std::list -  
intrusively, one list node per memory block.
</aside>

-Howard