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

From: Gennaro Prota (gennaro_prota_at_[hidden])
Date: 2002-11-06 12:36:53

On Wed, 6 Nov 2002 11:52:21 -0300, "Fernando Cacciola"
<fernando_cacciola_at_[hidden]> wrote:

>
>----- 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.

It's better that I explain it better too :-) I was commenting on your
phrase "would allow you to have a _no-throw_ swap". The original code
I've seen is:

   void swap(StrongStorage& other)
   {
     using std::swap;

     if(other.cacheInitialized) {
       getOtherCache().template
                construct_as<value_type>(other.value());
     }
     try {
               ...
     }
     catch(...) {

                ...
     }
            
            etc..
   }

Now, as I said, I DO NOT have the code of construct_as () because I
haven't found it in any place, but if it uses copy construction (as I
suppose) and if the copy may throw then that swap cannot provide the
nothrow guarantee. We agree on that, I think. Now let us see other
points:

>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();

How do you do that? Do you use memcpy? If so you are in UB land
(though it will usually work)

>   try
>   {
>     using std::swap ;
>     for ( size_t i = 0 ; i < N ; ++ i )
>       swap(p_[i],rhs.p_[i]); // THIS MAY THROW

This must be just an oversight. Weren't you thinking to p_ as the
pointer to the array in the free store case?

>   }
>   catch(...)
>   {
>      restore_previous_state_without_throwing();

Same note, of course.

>      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?

It depends. Don't make me say that :-) Once you are in the catch and
you have swapped N/2 objects...

>
>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;

Yep :-) I commented that you could have written

      int mirror_idx = 1 - idx;

but then I saw your pre-increments below and I understood.

>     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();

Who says you that you can invoke the destructor on all the N elements?
I think the destruction must be done at the moment you know you have
constructed, say, i elements and the construction of the (i+1)-th
failed. In that case you call the destructor on the first i.

>       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.

I understand that. But, as you showed, if

  new(lhs_mirror++) T(*rhs_source++);

does throw then swap throws too. Which was my point.

Genny.