Re: [boost] [intrusive] Comments on interface changes and stateful value_traits (long)

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-08-26 04:08:28

Ion Gaztañaga wrote:
> 1) Iterators
> 
> Iterators containa pointer to node and they use ValueTraits to obtain 
> the user value from the node. If an stateful ValueTraits is used, we 
> also need to store a pointer to the value traits stored in the 
> container. If I want zero overhead when using hooks or just value traits 
> with static functions I have to avoid storing the pointer when the 
> iterator is stateless.
> 
> How do we know if an allocator is stateless? One possibility is to check 
> if the ValueTraits is empty, that is, has no members. However, this does 
> not guarantee that ValuetTraits will define static functions so that no 
> pointer to ValueTraits is needed to convert from a node to a container. 
> I think it's a good aproximation or I could also define a traits or 
> internal constant to say "this ValueTraits is stateless/stateful". For 
> the moment, my current option is to consider an empty ValueTratis 
> stateless, so it must define conversion functions as static members.

Boost.TypeTraits defines boost::is_stateless, which would be the
appropriate extension point. Some compilers even provide intrinsics for
this traits template to work automatically.

> 2) Losing static functions
> 
> Some member functions of intrusive containers are static, so that there 
> is no need to have a reference to the container. This sometimes is very 
> useful (e.g. list::iterator_to) but this can't be achieved if stateful 
> value traits are used. I can think 3 options:
> 
> -> Convert static functions in non-static (losing some advantages)
> -> Offer static and non-static versions. Static versions won't compile 
> with stateful allocators (via BOOST_STATIC_ASSERT).
> -> Someone knows have to make a function static or not depending on a 
> compile-time boolean.

As we're talking about inline functions you can just pass a (possibly
null) pointer to the state into a static functions and the additional
argument will get optimized out.

> 3) Stateless, but taking advantage of composition
> 
> In a recent discussion about adding custom bucket traits to unordered 
> containers a booster wanted to have the bucket outside the class (for 
> example, to reuse that with other containers). With stateful allocators 
> this can be possible if bucket traits are stateful an contain a pointer 
> to the real bucket traits instance. But this increases the size of your 
> intrusive container.

Overhead of this kind can always be optional using EBCO (like compressed
pair does).

Regards,
Tobias