Re: [boost] Interest in a "Heterogenous Container" system?

Subject: Re: [boost] Interest in a "Heterogenous Container" system?
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-08-04 16:15:43

On Wed, Aug 5, 2009 at 4:30 AM, Mathias Gaunard <
mathias.gaunard_at_[hidden]> wrote:

> Frank Mori Hess wrote:
>
>  I wasn't following the thread too closely, but I assumed the benefit of
>> using size+alignment instead of type would be that you could reuse the same
>> allocator with different types (as long as they had the same size and
>> alignment).  But since a type's size+alignment varies across platforms, you
>> wouldn't be able to portably reuse such an allocator with different types
>> (hence no portable benefit).
>>
>
> The size + alignment wouldn't be part of the type of the allocator, it
> would be part of the arguments it receives to perform a given allocation.
> (i.e., like posix_memalign).
>
>
This is basically what Cloneable does. I'll try to make this as short as
possible: basically, there are four levels. At the bottom (most general),
there is abstract_base<Base>, where Base is the user-supplied base class for
a type hierarchy. abstract_base<> provides an abstract interface. Using that
is mixin<Derived, Base> : abstract_base<Base>, which implements much of the
interface required by abstract_base, excluding what is implemented by
base<Derived,Base,Construction> which deals with types that are not default
constructable. At the top is YourType : base<YourType,YourBase>.

Allocation is performed by an abstract_allocator, which is adapted from a
type that models a std::allocator. This is necessary because the system uses
the one allocator to make objects of different types.

///
/// required interface for typeless allocation
///
struct abstract_allocator
{
     typedef char *pointer;
     virtual pointer allocate_bytes(size_t num_bytes, size_t alignment) = 0;
     virtual void deallocate_bytes(pointer, size_t alignment) = 0;
     static size_t calc_padding(pointer ptr, size_t alignment);
};

///
/// adapt a std::allocator to provide abstract_allocator interface
///
template <class Allocator>
struct make_clone_allocator { typedef ... type; }

///
/// base for cloneable hierarchy given user-supplied base
/// same for all objects that share the same base
///
template <class Base>
struct abstract_base : Base
{
    virtual this_type *allocate(abstract_allocator &alloc) const = 0;
    // and deallocate(), clone(), create(), etc

     template <class Alloc>
     this_type *allocate(Alloc &al) const
     {
          make_clone_allocator<Alloc>::type al;
          return allocate(al);
     }
};

///
/// mixin for a specific derived/base pair. note that derived could have
different bases
///
template <class Derived, class Base>
struct mixin : abstract_base<Base>
{
     static const size_t alignment =
boost::aligned_storage<sizeof(Derived)>::alignment;
     virtual this_type *allocate(abstract_allocator &alloc) const //
covariant virtual method
     {
         return reinterpret_cast<Derived
*>(alloc.allocate_bytes(sizeof(derived_type), alignment));
     }
     // clone(), clone_as<T>(), etc elided...
};

///
/// interface to the system for clients; they derive from this
///
template <class Derived, class Base, class HasDefaultCtor =
has_default_ctor>
struct base : mixin<Derived, Base>
{
     /// ... details
};

///////////////////////////////////////

struct MyBase { };

struct MyDerived : cloneable::base<MyDerived, MyBase> { };

int main()
{
     // clone using default allocator
     MyBase *base = new MyDerived;
     MyDerived *derived = base->clone();

     // create and clone using a custom allocator
     std::allocator<myDerived> alloc;
     MyDerived *d2 = alloc.allocate(1);
     new (d2) MyDerived;
     MyDerived *clone = d2->clone(alloc);
}

/////////////////////////////////////

This scheme, with some slight mods to ptr_container to pass the containers'
allocator to the clone site, allows for correct deep cloning of containers
of pointers. The alignment is not incorrect. It works for all types, and it
is portable. Free functions are provided so non-cloneable types can be used
as well. The default clone operation, implemented using copy-construction,
can be overridden by simply providing a `Derived *clone(abstract_allocator
&) const` method in your derived class.

There are some outstanding issues, mostly to do with the containers that are
built using this system and based on ptr_container. These 'heterogenous'
containers entirely use emplace semantics  (the containers create the
objects). The main issues are method names, some semantic issues, and
dealing correctly with multiple inheritance. Also, what to do with various
almost-pointers like heterogenous::vector<shared_ptr<Base>> is unresolved.

That said, it is the closest I've seen yet to a general way to make
cloneable objects, and thereby providing true heterogenous containers with
real value semantics. For example:

// the user-supplied base, with comparison operator
struct B { int n; B(int N = 0) : n(N) { } bool operator<(B q) { return n <
q.n; } };

// derived types
struct A : cloneable::base<A,B> { A(int N = 0) : B(N) { } };
struct C : cloneable::base<C,B,cloneable::no_default_construct> { C(int N) :
B(N) { } };

typedef heterogenous::list<B> List;
List list;
list.push_back<A>(1); // emplace
list.push_back<C>(2);
List list2 = list;
assert(typeid(list2.back()) == typeid(C));

typedef my_magic_allocator<B> Alloc;
typedef heterogenous::set<B, Alloc> Set;
Set set;
set.insert<A>(1); // emplace
set.insert<C>(2);
Set set2 = set; // deep copy using correct allocator
assert(set2.find<C>(2) != set2.end()); // find an instance
assert(set2.find<A>(2) == set2.end());
assert(set2.find<B>(1) != set2.end()); // search for any type that matches
assert(set2.find<B>(2) != set2.end());

Similarly for map, vector etc. Map has the interesting case of:

typedef heterogenous::iso_map<B> Map;
Map map;
map.key<A>(1).value<C>(2);

However, so far I have only implemented map<Key, Base> (map of value-type to
pointer), not iso_map<Base> (map of pointer to pointer). This is due to how
ptr_map<> is implemented, but the implementation of iso_map<Base> is obvious
if technically tedious.

Regards,
Christian.