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

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2007-08-08 20:15:17

Ion Gaztañaga wrote:
> Tobias Schwinger wrote:
>> However, I've been wondering whether it would be possible to make the 
>> "hook interface" easier to use and less demanding in terms of names that 
>> are injected into client code. So I started experimenting a bit and the 
>> attachment is what I came up with. I believe that scheme might actually 
>> work (not sure, though)...
>  >
>> [code]
>  >
> 
> Very interesting, although I don't fully understand the goal. If the 
> goal is to avoid name injection, I could rework hooks to group all the 
> name definitions in a single internal structure and avoid code bloat.

Maybe because there were two goals:

1. Get rid of the syntactic bloat currently needed to make a class 
Intrusive-ready.
2. Reduce the probability of name clashes with arbitrary existing client 
code.

Here is a second take of the code hopefully addressing the issues you 
pointed me to.

> What I found interesting is the non-intrusive Intrusive version (nice 
> definition ;-)). Using ADL, there is a way to obtain the hook from the 
> value. However, Intrusive uses a two level architecture, where node 
> algorithms only know about nodes (which in the singly linked list case 
> is just an structure holding a single pointer) and containers know also 
> about values (values hold nodes/hooks as base or members).

Well, it was a "waste product" trying to preserve flexibility, they 
might as well be replaced with function objects, as you suggested below.

> This guarantees that template bloat is minimized, because instantiated 
> algorithms are the same for all values using the same hook. Containers 
> transform nodes to values and the inverse (using static_cast for base 
> hooks or calculating the offset of the hook in the value in member hooks).

Ah, I see! So the "syntactic bloat" sorta just fell into place 
minimizing the "machine language bloat" some misguided compilers' code 
generation stages produce (not recognizing the that X<T> and X<U> are 
equivalent for something like

      template<class T>
      class X
      {
          T* x;
          T* y;
        public:
          /* ...member functions that work on x and y ... */
      };

).

I noticed the two-level architecture, but didn't quite understand what 
it's for. Now that I know, I see my sample introduced an undesirable 
type dependency.

> 
> Although your example is not directly applicable to current Intrusive 
> code, you suggest a very nice possibility: storing nodes(hooks) 
> independently from values. The programmer could just offer a way to get 
> the node from the value and the inverse when not using any base or 
> member hook.
> 
> In the two-level Intrusive architecture your example would need two maps 
> (we could just use boost::bimap) to transform independently stored nodes 
> (slist_node_mgmt_data in your example) to values and the inverse operation.

... or extended the node structure with a back pointer like the attached 
code. I didn't notice boost::bimap is checked-in already, until now.

<snip>

> A lot of questions, but I think it's a fresh, great idea. Thanks!

Glad you like it.

Regards,
Tobias


#include <boost/pointee.hpp>
#include <boost/noncopyable.hpp>

namespace intrusive
{
// ---- node with policies

    // management data for one node
    template< class Policies = void >
    class slist_node_mgmt_data
    {
        template< typename U, class Tr > friend class slist;
        slist_node_mgmt_data* ptr_next;

      public:
        slist_node_mgmt_data() { }
    };

    // ADL extension points to allow Boost.Intrusive to work with custom 
    // members or even non-intrusively (using some external, bidirectional
    // mapping).
    // The default implementations assume the hook a base of the value.
    template< class Policies >
    slist_node_mgmt_data<Policies>& value_to_hook(
        slist_node_mgmt_data<Policies>& value)
    {
        return value;
    }

    // Note: Raw pointers will probably be enough, here...
    template< typename NodePointer, class Policies >
    void hook_to_value( NodePointer& result,
        slist_node_mgmt_data<Policies>& node)
    {
        // ... (using Smart Pointer - capable implementation just in case).
        // If not, Smart Pointers must provide support for boost::pointee
        // (e.g. an 'element_type' member).

        result = NodePointer( static_cast<
            typename boost::pointee<NodePointer>::type* >(& node) );
    }

// ---- container 

    // traits for customization
    template< typename T >
    struct slist_node_traits
    {
        typedef T  value_type;
        typedef T* pointer_type;
        typedef T& reference;

        // not sure it belongs here, move elsewhere at will
        typedef void policies; 

        // ...
    };

    // single-linked list (incomplete for illustration) 
    template< typename T, class Traits = slist_node_traits<T> >
    class slist : boost::noncopyable
    {
        typedef Traits traits;
      public:
        typedef typename traits::value_type value_type;
        typedef typename traits::pointer_type pointer_type;
        typedef typename traits::reference reference;
 
        typedef typename traits::policies policies;

        // ...

        slist_node_mgmt_data<policies>* ptr_first;
      public:

        // Note: Algorithms can work without depending on the value type
        // (except for casting or mapping for input and output, which will
        // always be there in some form).

        void push_front(reference x)
        {
            slist_node_mgmt_data<policies>& node = value_to_hook(x);
            node.ptr_next = this->ptr_first;
            this->ptr_first = & node;
        }

        void pop_front()
        {
            this->ptr_first = value_to_hook(* this->ptr_first).ptr_next;
        }

        reference front()
        {
            pointer_type result;
            hook_to_value(result, *this->ptr_first);
            return *result;
        }

        // ...
    };
}

#include <boost/detail/lightweight_test.hpp>
#include <map>

class foo
  : public intrusive::slist_node_mgmt_data<> 
// Note: Base class does not insert any names
{
    int val_data;
  public:

    foo(int data)
      : val_data(data)
    { }

    int data() const
    { return this->val_data; }

    // Note: No "member hook" 
};

void foo_test()
{
    intrusive::slist<foo> my_list;

    foo foo1(1); my_list.push_front(foo1);
    foo foo2(2); my_list.push_front(foo2);

    BOOST_TEST( my_list.front().data() == 2 );
    my_list.pop_front();
    BOOST_TEST( my_list.front().data() == 1 );
    my_list.pop_front();
}   

// Ok, let's try non-intrusive Intrusive ;-)

class bar
// Note: No base class
{
    int val_data;
  public:

    bar(int data)
      : val_data(data)
    { }

    int data() const
    { return this->val_data; }

    // Note: No "member hook" 
};

// External management facility

struct mgmt_data : intrusive::slist_node_mgmt_data<>
// adds a back pointer for bidi mapping
{
    bar* ptr_value;
};

std::map<bar*,mgmt_data> bar_mgmt_map;

intrusive::slist_node_mgmt_data<>& value_to_hook(bar& that)
{
    mgmt_data& result = bar_mgmt_map[& that];
    result.ptr_value = & that; // set back pointer
    return result;
}

void hook_to_value(bar*& result, intrusive::slist_node_mgmt_data<>& that)
{
    // downcast to access the back pointer
    result = static_cast<mgmt_data&>(that).ptr_value;
}

void bar_test()
{
    intrusive::slist<bar> my_list;

    bar bar1(1); my_list.push_front(bar1);
    bar bar2(2); my_list.push_front(bar2);

    BOOST_TEST( my_list.front().data() == 2 );
    my_list.pop_front();
    BOOST_TEST( my_list.front().data() == 1 );
    my_list.pop_front();
}

// Run the tests...

int main()
{ 
    foo_test();
    bar_test();

    return boost::report_errors();
}