Re: [boost] Re: Boost Array: read/write access to entire data

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2002-11-06 09:52:21

----- Original Message -----
From: "Gennaro Prota" <gennaro_prota_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Wednesday, November 06, 2002 8:13 AM
Subject: [boost] Re: Boost Array: read/write access to entire data

> On Tue, 5 Nov 2002 18:22:22 -0300, "Fernando Cacciola"
> <fernando_cacciola_at_[hidden]> wrote:
>
> >I also think it is useful for the case when you have more than one object
> >and you don't know how to perform a (no throw) move/swap of those
objects.
> >That is, if you have:
> >
> >T[0]
> >T[1]
> >...
> >
> >How do you implement no-throw swapping without a transacted approach (so
> >that you can rollback state in case of an exception)?
> >
> >The double buffer would allow you to have no-throw swap in the array even
if
> >you don't have it in the objects themselves.
>
>
> Well, I'm not sure what you are trying to say. BTW I couldn't find the
> details of construct_as. Are you saying that it doesn't use the copy
> constructor? Otherwise I don't see how the tecnique achieves a
> *no-throw* swap: either the copy constructor is nothrow itself and
> thus the tecnique is not needed, or it throws and the tecnique only
> gives you the strong guarantee. Or am I missing something?
>
> Genny.
>
OK. I'll try to explain it better.

The double buffer technique allows you to skip the expensive save/restore
mechanism required for the rollback of a 'traditional'
no-throw/strong-guarantee implementation. That is:
In our case, we have an array of fixed size which is not allocated in the
heap, so we can't use the address of the memory block used by the array
itself for swapping.
Schematically, this would be something like the following (showing only the
relevant parts):

// [UNTESTED CODE BELOW]
template<class T, size_t N>
struct FixedArray
{
  FixedArray() : p_(storage_.address()) {}

  void swap(FixedArray&);

  typedef aligned_storage<sizeof(T)*N> storage_t ;
  storage_t storage_ ;
  T* p_ ;
} ;

Now, let's consider a swap() with strong guarantee (not a no-throw swap,
yet)

template<class T, size_t N>
FixedArray<T,N>::swap ( FixedArray<T,N>& rhs )
{
   save_a_copy_of_the_current_state_without_throwing();
   try
   {
     using std::swap ;
     for ( size_t i = 0 ; i < N ; ++ i )
       swap(p_[i],rhs.p_[i]); // THIS MAY THROW
   }
   catch(...)
   {
      restore_previous_state_without_throwing();
      throw;
   }
}

A no-throw swap would be essentially the same except that exception possibly
thrown by the T's swap are eaten.

Do we agree that the above is the minimun 'traditional' implementation?

Now, let's see how the double buffer could be used:

// [UNTESTED CODE BELOW]

template<class T, size_t N>
struct FixedArray
{
  FixedArray() : idx_(0) {
storage_initialized_[0]=storage_initialized_[1]=false;}

  void swap(FixedArray&);

  T* data() const { return storage_[idx_].address() ; }

  typedef aligned_storage<sizeof(T)*N> storage_t ;
  storage_t storage_[2] ;
  bool storage_initialized_[2];
  int idx_ ;
} ;

template<class T, size_t N>
FixedArray<T,N>::swap ( FixedArray<T,N>& rhs )
{
   // NO NEED FOR SAVING STATE BEFORE.
   try
   {
     // (1) Copy active storage in rhs to mirror storage here
     int mirror_idx = (idx_+1)%2;
     T* lhs_mirror  = storage_[mirror_idx].address() ;
     T* rhs_source = rhs.storage_[rhs.idx_].address() ;
     for ( size_t i = 0 ; i < N ; ++ i )
     {
       if ( storage_initialized_[mirror_idx] )
         lhs_mirror->~T();
       new(lhs_mirror++) T(*rhs_source++); // THIS MAY THROW
     }

    // (2) Copy active storage in here to mirror storage in rhs
     int rhs_mirror_idx = (rhs.idx_+1)%2;
     T* rhs_mirror  = rhs.storage_[rhs_mirror_idx].address() ;
     T* lhs_source = storage_[idx_].address() ;
     for ( size_t i = 0 ; i < N ; ++ i )
    {
       if ( rhs.storage_initialized_[rhs_mirror_idx] )
         rhs_mirror->~T();
       new(rhs_mirror++) T(*lhs_source++); // THIS MAY THROW
     }

    // (3) Swaps active storages (commit changes)
    ++ idx_ ;
    ++ rhs.idx_ ;

   }
   catch(...)
   {
      // NO NEED TO RESTORE PREVIOUS STATE.
      throw;
   }
}

So, the basic idea is essentially the same as in Anthony's code. We copy to
a mirror buffer so that if exceptions are thrown the original state is
preserved. If no exceptions are thrown, we activate the mirror buffer in
order to 'commit' the changes. In the end, we avoided the expensive
save/restore_state.

Unfortunately, one drawback of this scheme which I just realized while I was
typing the code above (which was out the top of my head, btw), is that T's
are not really 'swapped', using T's swap, but copy constructed in an
uninitialized storage, which is uninitialized because it is previously
destroyed using T's destructor (if applicable).

Fernando Cacciola