Re: [boost] [intrusive] Interface for hooking into client code improvable?

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-08-09 21:35:37

Ion Gaztañaga wrote:
> Tobias Schwinger wrote:
>> As already admitted (in my reply to Ion), stateful function objects 
>> would be more flexible for the non-intrusive stuff.
> 
> I think a custom ValueTraits class just offers the necessary tools to 
> build the stateless (or using global variables) non-intrusive approach. 
> An alternative would be store a copy of ValueTraits inside the 
> container, yielding to a stateful function object. Container 
> constructors should take an additional ValueTraits parameter, 
> guaranteeing that the internal ValueTraits will be copy constructor. If 
> no ValueTraits object is provided a default constructed one might be 
> used. If EBO is used there wouldn't be any size overhead for the default 
> case (member or base ValueTraits).
> 
>> There are two much template parameters, already, and it seems that 
>> applying Boost.Parameter (to the template parameters of containers) 
>> would suit that library well:
> 
> The fact is that containers could accept an arbitrary number of options 
> For example: slist could just also store a pointer to the last element, 
> so that more functions are now constant-time functions.
> 
> As mentioned, the bucket management could be more customizable. There is 
> no logical requirement to have a bucket array. Buckets can be 
> represented with a ramdom access iterator and a size, so that buckets 
> can be implemented with a deque or any other container that might be 
> more suitable for an application.
> 
>> Positional template parameters whose meaning isn't immediately obvious 
>> (such as e.g. the non-type boolean ConstantTimeSize used by the 
>> Intrusive containers) tend make interfaces unintuitive, because readers 
>> of client code without in-depth knowledge of the library have to figure 
>> out what the arguments refer to. Named arguments OTOH lead to 
>> self-explanatory code.
> 
> I don't know much about Boost.Parameter but my goal is maintain 
> Boost.Intrusive independent of heavy template-metaprogramming machinery, 
> because the library is adequate for embedded systems and I wouldn't want 
> the executable to grow with type-info information/increased compilation 
> time created by meta-programming (I might absolutely wrong with this 
> sentence, so please feel free to correct).
> I want to maintain the library *simple*. 

Policy mixing (what is basically what named arguments is all about) is 
very simple to implement (just traits and inheritance) and requires no 
meta-programming machinery at all.

I'm certain that an interface, similar to what Boost.Parameter provides 
for template arguments, can be implemented with zero overhead. Not sure 
whether that's what Boost.Parameter does, however.

Type information is only emitted if 'typeid' is used or for polymorphic 
classes (IOW classes with virtual functions). Further, you can just 
globally disable RTTI with a compiler option and templates will keep 
working (well, unless they attempt to use 'typeid' or 'dynamic_cast', of 
course).

The only potential problem I see is that

     container< a_policy, another_policy >

and

     container< another_policy, a_policy >

are distinct types and some compiler might not factor out redundant code 
properly. It can be dealt with in two ways:

a) Add a note to the docs and leave it up to the user's self discipline 
to pick an order and to stick with it, or
b) enforce some canonical order before instantiating functions.

I think that a) is the way to go if you want to keep things simple.

> But I agree that so many options might confuse users. 
> Maybe a configuration structure might be better:
> 
> struct options
> {
>    //If not present, defaults to true
>    static const bool contant_time_size = true;
> 
>    //If not present, defaults to std::size_t
>    typedef unsigned short size_type;
> 
>    //...
> };
> 
> list<T, options>

Yes, much better.

It also allows to say:

      struct options : default_options
      {
          // just set one option
          static const bool constant_time_size = false;
      };

> 
>> I'd also like to see a 'T' parameter for straightforwardness
>>
>>       template< class T, // [...]
>>       class container;
>>
>> so one could just say
>>
>>       container<T>
>>
>> given 'T' has appropriate hooks installed. That "nested 'value_traits' 
>> business" feels pretty clumsy (much more than having the hooks inject 
>> public names) and it was my main motivation to look for something better.
> 
> One option would be to detect if the passed value parameter is a 
> value_traits class. If not, a base hook is supposed.

One could put the 'value_traits' template into 'options' (which is then 
used with 'T'). Alternatively we'd have 'options<T>'.

> But note that if 
> several base hooks are used, you *must* tell the container which hook 
> you want to use:
> 
> struct tag1;
> struct tag2;
> 
> struct my_type
>    : public list_hook<tag1>
>    , public list_hook<tag2>
> {};

And the tag would go into 'options' as well...

> No automatic detection will work here. 

BTW: Given a typeof operator it can in some cases (not the one above, 
however, because deduction would be ambiguous).

> T is the same for slist, but the 
> hook to be used is different. What I could do, is to simplify the most 
> common case (simple base hook).

And provide "'options' classes or templates" for common combinations of 
settings (e.g. with 'value_traits' using 'offset_ptr' or a template that 
sets a custom tag)...

Now recognize that it's still imperfect and that what we actually want 
is named template arguments ;-)...

>> Hope I haven't complained too much... The library is great; I have the 
>> impression that a lot of care went into the implementation -- its 
>> interface just /deserves/ some polishing ;-).
> 
> I agree. It's just that I haven't found a better interface that 
> preserves all the possibilities of the library. But I'm pretty sure that 
> interface exists ;-)

...here's some code for the taste of it (plain, without using 
Boost.Parameter).

Regards,
Tobias


// Defaults

struct container_xyz_defaults
{
    static bool const constant_time_size = true;

    typedef void tag;

    template<typename T>
    struct value_traits
    {
        typedef T* pointer_type;
        typedef T& reference;
        // ...
    };
    // ...
};

// Setters

template<bool Enabled>
struct constant_time_size
{
    template<class Base>
    struct apply_options : Base
    {
        static bool const constant_time_size = Enabled;
    };
};

template<typename T>
struct tag
{
    template<class Base>
    struct apply_options : Base
    {
        typedef T tag;
    };
};

template<typename T>
struct offset_ptr {}; // just pretend it's there...

struct offset_ptr_storage
{
    template<class Base>
    struct apply_options : Base
    {
        template<typename T>
        struct value_traits
        {
            typedef offset_ptr<T> pointer_type;
            typedef T& reference;
            // ...
        };
    };
};

struct none_specified
{
    template<class Base>
    struct apply_options : Base
    { };
};

// ...

template<typename T, class Policy1 = none_specified, 
    class Policy2 = none_specified, class Policy3 = none_specified,
    class Policy4 = none_specified >
class container_xyz
{
    typedef
        typename Policy4::template apply_options<
            typename Policy3::template apply_options<
                typename Policy2::template apply_options<
                    typename Policy1::template apply_options<
                        container_xyz_defaults
        >   >   >   > policies;

  public:
    typedef typename policies::template value_traits<T> value_traits;

    typedef typename policies::tag tag;
    typedef typename value_traits::pointer_type pointer_type;
    static bool const constant_time_size = policies::constant_time_size;

    // ...
};

// Demonstrate it

#include <iostream>
#include <typeinfo>

template<class C>
void show_config(char const * name)
{
    std::cout << 
    name << ":" << std::endl <<
    "  tag: " << typeid( typename C::tag ).name() << std::endl <<
    "  pointer_type: " << typeid( typename C::pointer_type ).name() << std::endl <<
    "  constant_time_size: " << C::constant_time_size << std::endl <<
    std::endl;
}

int main()
{
    show_config<   container_xyz< int, constant_time_size<false> >   >
                 ("container_xyz< int, constant_time_size<false> >");

    show_config<   container_xyz< int, offset_ptr_storage >   >
                 ("container_xyz< int, offset_ptr_storage >");

    show_config<   container_xyz< int, offset_ptr_storage, tag<int> >   >
                 ("container_xyz< int, offset_ptr_storage, tag<int> >");

    return 0;
}