Statically wrapping a library's polymorphic iterator without exposing the library to the user

Question

I am currently integrating a datastore library into my application. I need to be able to mock this datastore (which is I/O intensive) for my unit tests, therefore creating a wrapper around that library's interface.

Unfortunately, in its interface, this library returns iterators as pointers and not as values, because they are polymorphic at runtime.

My issue is that because of the layer of polymorphism I am adding, it seems unavoidable to add iterators that are polymorphic at runtime, therefore incurring a new level of indirection and some more dynamic allocation...

// Library code
class LibIterator
{
    // pure virtual methods
};

class LibDataStore
{
    LibIterator* getIt();
};

// My interface
class IMyIterator{
    // pure virtual methods
};

class MyLibIterator : public IMyIterator
{
    std::unique_ptr<LibIterator> m_iterator;
};

class MyIterator
{
    std::unique_ptr<MyLibIterator> m_iterator;
};

class IMyDataStore
{
    MyIterator getIt();
};

That is an awful lot of pointers to dereference, of virtual dispatch on each use of any method of the iterator, plus at least 2 dynamic allocations (the lib iterator + mine) for each iterator creation...

I was thinking of using CRTP to help with this, but I can't figure out a way to prevent code using IMyDataStore to see the concrete implementation of the iterator bleeding through MyIterator's type.

Is there any trick I might have missed?

Answer 1

template<class T, std::size_t sz, std::size_t algn>
struct poly {

if you are not afraid yet you should be

  poly_vtable<T> const* vtable=0;
  std::aligned_storage_t<sz, algn> data;

we can cover the vtable later.

  T* get() { return vtable->get(&data); }
  T const* get() const { return vtable->get((void*)&data); }

example use of vtable. Here is setup:

  template<class U, class...Args>
  U* emplace(Args&&...args){
    static_assert(sizeof(U)<=sz && alignof(U)<=algn, "type too large");
    clear();
    U* r = ::new((void*)&data) U(std::forward<Args>(args)...);
    vtable = get_poly_vtable<T,U>();
    return r;
  }

copy:

  poly(poly const& o){
    if (!o.vtable) return;
    o.vtable->copy( &data, &o.data );
    vtable=o.vtable;
  }
  poly(poly&& o){
    if (!o.vtable) return;
    o.vtable->move( &data, &o.data );
    vtable=o.vtable;
  }
  poly& operator=(poly const& rhs) {
    if (this == &rhs) return *this;
    clear();
    if (!rhs.vtable) return *this;
    rhs.vtable->copy( &data, &rhs.data );
    vtable = rhs.vtable;
    return *this;
  }
  poly& operator=(poly&& rhs) {
    if (this == &rhs) return *this;
    clear();
    if (!rhs.vtable) return *this;
    rhs.vtable->move( &data, &rhs.data );
    vtable = rhs.vtable;
    return *this;
  }

destruction:

  void clear(){
    if (!vtable) return;
    vtable->dtor(&data);
    vtable=nullptr;
  }
  ~poly(){clear();}

pointer like operations:

  explicit operator bool()const{return vtable;}
  T& operator*(){ return *get();}
  T const& operator*() const{ return *get();}
  T* operator->(){ return get();}
  T const* operator->() const{ return get();}

construct from a type derived from T:

  template<class U,
    class dU=std::decay_t<U>,
    class=std::enable_if_t<!std::is_same<dU, poly>{}>,
    class=std::enable_if_t<std::is_base_of<T, dU>{}>
  >
  poly(U&& u) {
    emplace<std::decay_t<U>>( std::forward<U>(u) );
  }
};

note that this type when const refers to a const value.

The idea is that poly<T> is a polymorphic value of type T. It has size limits.

You can use the T* vtable to arrange for polymorphism of other operations.

template<class T>
struct poly_vtable{
  T*(*get)(void*)=0;
  void(*copy)(void*,void const*)=0;
  void(*move)(void*,void*)=0;
  void(*dtor)(void*)=0;
};

template<class T, class U>
poly_vtable<T> make_poly_vtable() {
    return {
        [](void* ptr)->T*{ return static_cast<U*>(ptr); },
        [](void* dest, void const* src){ ::new(dest) U(*static_cast<U const*>(src)); },
        [](void* dest, void* src){ ::new(dest) U(std::move(*static_cast<U*>(src))); },
        [](void* ptr){ static_cast<U*>(ptr)->~U(); }
    };
}
template<class T, class U>
poly_vtable<T> const* get_poly_vtable() {
    static const auto r = make_poly_vtable<T,U>();
    return &r;
}

get_poly_vtable<T,U>() returns a pointer to a static local poly_vtable<T> with each operation implemented.

Live example.

Now you can have a vtable based polymorphic value type.

The same technique can be extended to more operations; simply cast-to-base and using real vtables is easier.

Using this, you store a poly<IMyIterator, 64, alignof(IMyIterator)>. This is a value type containing some buffer of 64 bytes.

---

Another approach to reduce indirection would be to replace the concept of per-item visitation with possibly repeated range visitation.

If you visit a range of 10 items at once per callback, then the overhead of invoking virtual methods is up to 10 times less than one per callback.

You can create input iterators with a range object that has a buffer for up to 10 items in it and who automatically rebuild it when you reach the end, if there are more available, getting the data in batches.