Re: [boost] [Intrusive] - Adapting existing intrusive classes

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2007-03-19 14:31:06

On 3/19/07, Ion Gaztañaga <igaztanaga_at_[hidden]> wrote:
> The same happens with Intrusive. The user derives or stores a hook to
> make the class intrusive-friendly. The hook contains a minimum generic
> node that just stores pointers. All the low-level (link, unlink,
> rebalance...) algorithms operate with these minimal nodes to avoid
> instantiating algorithms for all user types.

Ion, does this version of Intrusive have functionality that would
allow me to adapt existing classes (i.e. a non-intrusive way to
provide Boost.Intrusive functionality)?  I think this could be
accomplished using a mechanism similar to iterator traits classes.  A
user would simply need to specialize a
boost::intrusive::list::node_traits class.  This was how I went about
it when I coded an intrusive n-ary tree.  It looked something like
(simplified):

template <typename T>
struct nary_treenode_traits
{
        static T *&parent(T &node);
        static T *&prev(T &node);
        static T *&next(T &node);
        static T *&first_child(T &node);
        static T *&last_child(T &node);
        // const versions too...
};

And then all of my node operations went through the traits class.  E.g.

template <typename T>
T *&parent_node(T &node)
{
        typedef nary_treenode_traits<T> traits_type;
        return traits_type::parent(node);
}

This allows implementations where the user takes advantage of platform
specific knowledge to store extra information within one pointer
(linked list with next/prev pointer in the same pointer with xor to
extract), as well as more commonly, existing pointers that might
simply be named something different than what the generic algorithm
expected.

It appears that my implementation, yours, and the Generic Tree GSoC
project from last year all had similar goals in trying to provide
generic algorithms that only rely on certain capabilities of the input
type (e.g. must have next/prev to be used as a linked list node, or
must have parent to be a tree node).

--Michael Fawcett