Program Listing for File WorkStealingDeque.h

↰ Return to documentation for file (ADS/concurrent/WorkStealingDeque.h)

/*--------------------------------------------------------------------------*/
/*------------------------ File WorkStealingDeque.h ------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_WorkStealingDeque
 #define __ADS_WorkStealingDeque
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"

#include <atomic>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <optional>
#include <type_traits>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS WorkStealingDeque -------------------------*/
/*--------------------------------------------------------------------------*/

template< class T >
class WorkStealingDeque {
 static_assert( std::is_trivially_copyable_v< T > ,
                "the items are copied through atomics" );

 struct Ring {
  std::int64_t mask;
  std::unique_ptr< std::atomic< T >[] > place;
  explicit Ring( std::int64_t c )
   : mask( c - 1 ) , place( new std::atomic< T >[ std::size_t( c ) ] ) {}
  [[nodiscard]] T get( std::int64_t i ) const {
   return( place[ std::size_t( i & mask ) ].load(
                                            std::memory_order_relaxed ) );
   }
  void put( std::int64_t i , T x ) {
   place[ std::size_t( i & mask ) ].store( x , std::memory_order_relaxed );
   }
  };

/*--------------------------------------------------------------------------*/
 public:

 using Item = T;

 explicit WorkStealingDeque( std::size_t capacity = 1024 );
 WorkStealingDeque( const WorkStealingDeque & ) = delete;
 WorkStealingDeque & operator=( const WorkStealingDeque & ) = delete;

 void push( T x );

 std::optional< T > take( void );

 bool steal( T & x );

 [[nodiscard]] std::size_t size( void ) const;

 [[nodiscard]] bool empty( void ) const { return( size() == 0 ); }

 [[nodiscard]] std::size_t capacity( void ) const {
  return( std::size_t( f_ring.load( std::memory_order_relaxed )->mask +
                       1 ) );
  }

/*--------------------------------------------------------------------------*/
 private:

 static constexpr std::size_t line = 64;

 alignas( 2 * line ) std::atomic< std::int64_t > f_top{ 0 };
 alignas( 2 * line ) std::atomic< std::int64_t > f_bottom{ 0 };
 std::atomic< Ring * > f_ring;
 std::vector< std::unique_ptr< Ring > > f_rings;
 };  // end( class WorkStealingDeque )

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/concurrent/impl/WorkStealingDeque.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* WorkStealingDeque.h included */

/*--------------------------------------------------------------------------*/
/*---------------------- End File WorkStealingDeque.h ----------------------*/
/*--------------------------------------------------------------------------*/