Boost logo

Boost :

From: Dan W. (danw_at_[hidden])
Date: 2003-12-29 19:55:01

Warning: un-tested. Might make a nice addition to the thread library. If
there's any interest in it, I could use some advice on how to test it properly.
In short, this is like a thread safe, alloc-free producer/consumer, shallow
but wide, two-way buffer. Should be very efficient and portable, since it does
not make use of locks or mutexes, and since it avoids
allocation/de-allocation by re-using the two same buffers. The buffer type
is generic (<T>).
Inherently portable, as it uses no platform specific threading mechanisms
Usage: Create a class for the buffer type wanted, inheriting from abstract
Call create_double_buffer<my_buff_t>( new my_buff_t, new my_buff_t ), to
allocate a double buffer on the heap. Optionally feed the returned address
to a smart pointer.
The producer can now call pmy_buff->checkout_buff(), and get a
shared_ptr<my_buff_t>. The producer can now write to this buffer via the
Once done, it simply lets the shared_ptr go out of scope. This triggers a
mechanism (via custom deleter calling double_buffer::operator()()) that moves
the buffer along from the producer checkout and makes it available to the
The consumer uses an exactly symetrical function 'checkout_data'.
There are two buffers moving around a 6-position 'ring'.
Anyways, the comments get pretty graphic towards the bottom of the file.
Sorry to just paste the code below, I have no web-space readily available;
specially now when everybody here is on holidays. Read on...



   Pattern "double buffer" is intended as a simple and
   fast inter-thread data exchange solution. It allows
   a producer and a consumer to exchange fixed-size data
   buffers. Two such buffers are managed such that the
   producer and consumer may simultaneously be working
   to/from either buffer, or such that that one buffer
   is being processed while the other waits, or such that
   both buffers are in waiting --whether one waiting
   for each thread, or the two waiting for one thread.
   Its speed stems from the fact that thread safety is
   achieved without the use of locks or mutexes, and
   from the fact that the buffers are re-used, rather
   than repeatedly allocated/de-allocated.
   Finally, the fact that it uses no platform-specific
   threading mechanisms, makes it inherently portable.
   Note also that since only pointer variables to the
   template type are instantiated, compiler optimization
   should reduce generated template instances to a single
   instance of the double_buffer class code.
   The free function 'create_double_buffer' allocates the
   instance on the heap and returns a pointer. This makes
   it convenient for assigning that pointer to shared_ptr
   objects held by the producer and consumer, such that
   when they go out of scope, their commonly owned double
   buffer is deallocated.
   Note that, although we speak of 'producer'/'consumer',
   the pattern is symmetrical: --i.e. the consumer can
   just as well write to the buffers it receives before
   returning them and the 'producer' may read them prior
   to writing to them.


#include <smart_ptr.hpp>

namespace boost
namespace dbf

//Class buffer allows polymorphic pointers to buffers;
//and prevents accidental deletion of the buffers by
//the delete shared_ptr<T>.get(). All you have to do is
//to derive your buffer from (abstract) buffer, e.g.:
// struct my_buff : public boost::dbf::buffer
// { char zzz[666];
// void erase(){ for(int i(666);i--;) zzz[i]=0; }
// }; //that's if you *want* to erase prior to producer
//checkout, each time; otherwise.. void erase(){}.
class buffer
     buffer( buffer const &); //no copying
     buffer & operator=( buffer const &);
     void erase(){ erase_(); }
     virtual void erase_() = 0;

//Class double_buffer<T> is the main one here. T is the type of
//of your buffer class, e.g.: my_buff, as per example above.
//The two "checkout" public functions are what matters to ya...
//The producer checks-out buffers and releases data; the con-
//sumer checks-out data and releases a buffer. Data is short
//for 'buffer with valid data', while Buffer means plain, raw
//buffer. The functions return empty shared_ptr<T>'s if data or
//buffers aren't available, respectively, at time of call.
template< typename T >
class double_buffer
     typedef shared_ptr<buffer> pbuff_t;
     pbuff_t checkout_data(){ return checkout_data_(); }
     pbuff_t checkout_buff(){ return checkout_buff_(); }
     virtual pbuff_t checkout_data_() = 0;
     virtual pbuff_t checkout_buff_() = 0;

//use this stand-alone function to create a double-buffer;
//you must allocate the buffers; double_buffer will delete
//them in its destructor.
template< typename T >
double_buffer<T> * create_double_buffer( T * pbuf1, T * pbuf2 );


//double_buffer's implementation:
template< typename T >
class db_impl : public double_buffer<T>
     db_impl & operator=(db_impl const &);
     db_impl(db_impl const &); db_impl();
     db_impl( T * pbuf1, T * pbuf2 );
     void operator()(T * released);
     void reset();
     pbuff_t checkout_data_();
     pbuff_t checkout_buff_();
     T * volatile arr[6];
     T * const pbuf1_;
     T * const pbuf2_;


template< typename T > //free-standing create f'n
double_buffer<T> * create_double_buffer( T * pbuf1, T * pbuf2 )
     return new db_impl<T>( pbuf1, pbuf2 );


template< typename T > //reset
void db_impl<T>::reset()
     for(int i = 0; i < 6; ++i) arr[i] = 0;
     arr[5] = pbuf2_;
     arr[0] = pbuf1_;
     if( arr[0] == 0 ) //see notes below
         arr[0] = pbuf2_;
         arr[5] = 0;

template< typename T > //ctor
   T * pbuf1,
   T * pbuf2
: arr()
, pbuf1_(pbuf1)
, pbuf2_(pbuf2)
     assert( pbuf1_ && pbuf2_ );

template< typename T > //dtor
     assert( arr[1]==0 && arr[4]==0 );
     delete pbuf2_;
     delete pbuf1_;

/* checkout_buff_(), checkout_data_(), and operator()()
    constitute the core functionality and implement all
    the thread-safety tricks. Two 'tokens' (pointers) are
    moved around T * arr[6]: a ruby-shaped circuit where
    two of the positions are checkout positions, and the
    other four are 'waiting' positions, as follows:

                 [0] [5]
           Buffer waiting Buffer waiting

        [1] [4]
Producer checkout Consumer checkout

                 [2] [3]
            Data waiting Data waiting

    The tokens circulate counter-clock-wise. The producer
    can copy a token from positions 0 or 5 to position 1,
    and can clear positions 0 or 5, but not set them.
    Once it has moved a token to position 1, it can use
    the buffer it points to. When finished, the token in
    1 is moved to 3, if 3 is clear, or to 2 otherwise.
    The producer can set, but not clear, positions 2 and
    and 3; unless 3 is free on second check. The consumer
    can copy a token from positions 3 or 2 to position 4,
    and can clear positions 3 or 2, but not set them.
    Once it has moved a token to position 4, it can use
    the data it points to. When finished, the token in
    4 is moved to 0, if 0 is clear, or to 5 otherwise.
    The consumer can set, but not clear, positions 5 and
    and 0; unless 0 is free on second check, in which
    rare case it will move 5 to 0 and clear 5, very, very
    carefully... Some of the conditionals may appear to
    be redundant; --they have to be so to be thread-safe.
    Almost forgot, when consumer is done with data, it
    first calls user function erase() on it.
    Note that the checkout functions return shared_ptr<>
    objects, which it initializes with "this" in ctor's
    second argument...
    When the client (producer or consumer) is done with
    the buffer (shared_ptr<>'s go out of scope) the last
    shared_ptr calls this->operator()(T*), like a custom
    deleter. Operator()(), rather than free the memory,
    simply moves the token along the circuit. At first it
    does not know whether it's a return of a data-filled
    buffer, or a used buffer. It finds out by comparing
    the address released to those present in positions 1
    and 4. This is safe to do.


template< typename T > //producer checkout
double_buffer<T>::pbuff_t db_impl<T>::checkout_buff_()
     T * the_buffer = 0;
     assert( ! arr[1] );
     if( ! arr[2] )
         arr[1] = arr[0];
         the_buffer = arr[1];
         if( arr[0] && arr[5] )
             arr[0] = arr[5];
             arr[5] = 0;
             arr[0] = 0;
     return pbuff_t( the_buffer, this );
template< typename T > //consumer checkout
double_buffer<T>::pbuff_t db_impl<T>::checkout_data_()
     T * the_buffer = 0;
     assert( ! arr[4] );
     if( ! arr[5] )
         arr[4] = arr[3];
         the_buffer = arr[4];
         if( arr[3] && arr[2] )
             arr[3] = arr[2];
             arr[2] = 0;
             arr[3] = 0;
     return pbuff_t( the_buffer, this );
template< typename T > //"deleter" (moves token along)
void db_impl<T>::operator()(T * released)
     assert( released );
     if( released == arr[1] ) //if a producer release
         if( arr[3] )
           arr[2] = released;
         else arr[3] = released;
         if( !arr[3] && arr[2] )
             arr[2] = 0;
             arr[3] = released;
         arr[1] = 0;
     else //ought to be a consumer release (arr[4])
         assert( released == arr[4] );
         arr[4]->erase(); //clears buffer
         if( arr[0] ) arr[5] = released;
         else arr[0] = released;
         if( !arr[0] && arr[5] )
             arr[5] = 0;
             arr[0] = released;
         arr[4] = 0;



Boost list run by bdawes at, gregod at, cpdaniel at, john at