Program Listing for File ConcurrentUnionFind.h

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

/*--------------------------------------------------------------------------*/
/*------------------------ File ConcurrentUnionFind.h ----------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <atomic>
#include <cstddef>
#include <cstdint>
#include <memory>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------ CLASS ConcurrentUnionFind -----------------------*/
/*--------------------------------------------------------------------------*/

class ConcurrentUnionFind {

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

 explicit ConcurrentUnionFind( std::size_t n )
  : f_n( n ) , f_p( new std::atomic< std::int32_t >[ n ] ) {
  ADS_PRE( n < ( std::size_t( 1 ) << 31 ) );
  for( std::size_t x = 0 ; x < n ; ++x )
   f_p[ x ].store( std::int32_t( x ) , std::memory_order_relaxed );
  }

 ConcurrentUnionFind( const ConcurrentUnionFind & ) = delete;
 ConcurrentUnionFind & operator=( const ConcurrentUnionFind & ) = delete;

 [[nodiscard]] std::size_t size( void ) const { return( f_n ); }

 [[nodiscard]] std::int32_t find( std::int32_t x ) {
  ADS_PRE( ( x >= 0 ) && ( std::size_t( x ) < f_n ) );
  for( ;; ) {
   std::int32_t p = f_p[ x ].load( std::memory_order_acquire );
   const std::int32_t g = f_p[ p ].load( std::memory_order_acquire );
   if( p == g )
    return( p );
   f_p[ x ].compare_exchange_weak( p , g , std::memory_order_release ,
                                   std::memory_order_relaxed );
   x = p;
   }
  }

 [[nodiscard]] std::int32_t parent( std::int32_t x ) const {
  return( f_p[ x ].load( std::memory_order_acquire ) );
  }

 void compress( std::int32_t x ) {
  std::int32_t p = f_p[ x ].load( std::memory_order_acquire );
  if( p == x )
   return;
  const std::int32_t r = find( p );
  if( r != p )
   f_p[ x ].compare_exchange_strong( p , r , std::memory_order_release ,
                                     std::memory_order_relaxed );
  }

 bool unite( std::int32_t x , std::int32_t y ) {
  for( ;; ) {
   x = find( x );
   y = find( y );
   if( x == y )
    return( false );
   if( x < y )
    std::swap( x , y );                     // hook x, the larger root
   std::int32_t r = x;
   if( f_p[ x ].compare_exchange_strong( r , y , std::memory_order_acq_rel ,
                                         std::memory_order_relaxed ) )
    return( true );
   }
  }

 [[nodiscard]] bool sameSet( std::int32_t x , std::int32_t y ) {
  for( ;; ) {
   x = find( x );
   y = find( y );
   if( x == y )
    return( true );
   if( f_p[ x ].load( std::memory_order_acquire ) == x )
    return( false );                        // x was a root after y found
   }
  }

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

 std::size_t f_n;
 std::unique_ptr< std::atomic< std::int32_t >[] > f_p;
 };  // end( class ConcurrentUnionFind )

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

}  // end( namespace ADS )

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

#endif  /* ConcurrentUnionFind.h included */

/*--------------------------------------------------------------------------*/
/*--------------------- End File ConcurrentUnionFind.h ---------------------*/
/*--------------------------------------------------------------------------*/