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