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

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-08-24 17:10:39

Hi to all,

  First of all, thanks to all who participated in recent threads
about Boost.Intrusive options and extended configurability discussions. 
These days I've been experimenting a bit with this option and also with 
stateful value_traits (those who could allow non-intrusive hooks).

-----------------------------------------
-----------------------------------------
Passing policies to hooks and containers
-----------------------------------------
------------------------------------------

As you know, one of my main concerns is that a container explicitly set
with some options, should have the same type as another container
defined with the same options in a different order. I meant:

  list<T, base_hook<my_base_hook>, constant_time_size<false> >

should have the same type as:

  list<T, constant_time_size<false>, base_hook<my_base_hook> > l;

My preferred alternative is the more verbose:

typedef list_options
  < base_hook<my_base_hook>
  , constant_time_size<false>
  >::type options_t;

list<T, options_t> l;

that guarantees the same type for the same options.

1) Implemented interface:

I've implemented all current container options using this approach. I've
chosen a different options configurer "list_options", "slist_options"...
because otherwise, I couldn't set defaults that could lead to the
correct types.

The default hooks is the base hook so a user can just say:

class my_type
   : public list_base_hook<>
{}

list<my_type> l;

Some options must not be set in the container *but in the hook*, since
options affect both the hook and the container. Examples: void pointer
definition, the linking policy. I think hook options can be unified so I
have:

typedef hook_options
    < void_pointer<offset_ptr<void> >
    , link<normal_link>
    , tag<my_tag>
    >::type hook_options_t;

class my_type
   : public list_base_hook<hook_options_t>
{
    typedef list_base_hook<hook_options_t> my_hook_t;
}

typedef list_options
  < base_hook<my_hook_t>
  , size_type<std::size_t>
  >::type options_t;

list<T, options_t> l;

As you can see, specifying options can be quite verbose (comparing it to
the old way, but as new options are added (for example, custom buckets
definition in hash containers) users don't have put arguments in order
and can change only the options they want to change from the default.

2) Declaration of new classes:

template<class T, class ListOptions>
class list;

template<class T, class SlistOptions>
class slist;

template<class T, class Pred, class SetOptions>
class set;

template<class T, class Hash, class Equal, class UsetOptions>
class unordered_set;

So the declaration of intrusive containers would be exactly the same as
the STL containers plus an options argument.

3) Problem: Definition of member hooks is very long

class my_type
{
    list_member_hook member_hook_;
}

typedef list_options
   < member_hook<my_type, list_member_hook, &my_type::member_hook_>
   >::type options;

list<my_type, options> l;

Why? Because I can't make C++ deduce a pointer to member value in a
single template parameter passed to a class. It would be nice that C++
could deduce my_type and list_member_hook from the value directly
yielding to:

typedef list_options
   //Deduce my_type and list_member_hook automatically
   < member_hook<&my_type::member_hook_>
   >::type options;

If anyone can correct me, I would be *really* glad.

4) Custom value_traits

Current interface takes a value_traits class as the first parameter in
containers:

template<class ValueTraits, bool...>
class list;

ValueTraits concept is very powerful because allows separating the
concepts of a Node and a Value. The node is the minimal structure that
is need to form a group of nodes (group of pointers to form a list, a
tree...) and the Value is the whole user type that is somehow related to 
the node (via inheritance, membership, or other).

Intrusive documentation offers examples of custom ValueTraits to reuse
nodes for different containers or to deal with non modifiable ABI of old 
code. This is still possible specifying
the value_traits instead of the hook:

typedef list_options
   < value_traits<my_value_traits>
   >::type options;

list<T, my_value_traits> l;

---------------------------------------------------------
---------------------------------------------------------
Stateful value_traits (aka allowing extrusive containers)
---------------------------------------------------------
---------------------------------------------------------

I've started experimenting with stateful value_traits, while trying to 
keep zero overhead when ValueTraits is an empty class. There are some 
problems though:

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.

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.

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.

However if the external bucket implementation is very near to the 
container (said, it's a member of the same structure or whatever), it's 
possible to obtain the address of the the external resource based on the 
address of the container or the internal traits instance included in the 
container.

Rei Thiessen was requesting that when he explained the customized bucket 
info structure.

template< unsigned n >
struct bucket_info_size_n
{
    /* appropriate constructors... */
    bucket_ptr  buckets_;
    template<class T> bucket_ptr buckets( T* container ) const { return
buckets_; }
    size_type buckets_len() const { return 1<<n; }
}

So based on the address of the container, the user can find the resource 
(in this case, the bucket array) obtaining zero size overhead (the 
internal traits is empty). This logic can be extended to every traits 
class of the container, but specially to ValueTraits.

But this would require passing the address of the container to every 
function the traits class implements. Users not wanting this composition 
hack surely don't want to change their signatures to just support this 
extremely advance practice:

before

class my_value_traits
{
    node_ptr to_node_ptr(value_type &val)
    //...
};

after

class my_value_traits
{
    template<class Container>
    node_ptr to_node_ptr(value_type &val, const Container& cont)
    //...
};

So if there is any metaprogramming hack (if increases compilation time 
too much, forget it ;-) ) I would like to receive suggestions. 
Otherwise, a member static const bool saying "pass container address" in 
value traits might be useful, so that the container changes the calls to 
the traits with another equivalent one passing the address of the container.

I haven't still experimented this composition hack so I'm really open to 
all suggestions from advanced users. My point is that this should be 
really optional and should not affect users not using these advanced 
features.

As Rei said (inflating my ego): "These intrusive containers are so close 
to perfect that it's painful to have to modify them."

So let's make them perfect ;-)

Regards,

Ion