ConcurrentClosed.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------------ File ConcurrentClosed.h -------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_ads_ConcurrentClosed
 #define __PBeFS_ads_ConcurrentClosed
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <atomic>
 
#include <cstddef>
 
#include <cstdint>
 
#include <memory>
 
#include <mutex>
 
#include <variant>
 
#include "ADS/concurrent/ConcurrentFlatTable.h"
 
#include "PBeFS/astar/Domain.h"
 
#include "PBeFS/astar/Node.h"
 
#include "PBeFS/core/SearchUtils.h"
 
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------- CLASS ConcurrentClosed -------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D , class Lock >
class ConcurrentClosed {
 
 public:
 
 using State = state_t< D >;                       
 using Cost = cost_t< D >;                         
 using NodeT = Node< State , Cost >;               
 
 static_assert( alignof( Cost ) >=
                std::atomic_ref< Cost >::required_alignment );

 struct Local {
  NodePool< NodeT > pool;                         
  NodeT * spare = nullptr;                        

  [[nodiscard]] std::size_t stored( void ) const {
   return( pool.size() - ( spare ? 1 : 0 ) );
   }
  };

 struct Successor {
  State state;                                    
  Cost g;                                         
  Cost h;                                         
  std::uint64_t hash;                             
  std::uint8_t op = no_op;                        
  };

 
 explicit ConcurrentClosed( const D & domain )
  : f_domain( domain ) , f_table( 0 , ByState{ &domain } ) {}

 
 Lock & lock( const NodeT * n ) {
  const auto a = std::uint64_t( reinterpret_cast< std::uintptr_t >( n ) );
  return( f_stripes[ ( ( a >> 4 ) * 0x9E3779B97F4A7C15ULL ) >> 56 ].lock );
  }

 
 void prefetch( std::uint64_t hash ) const { f_table.prefetch( hash ); }

 
 NodeT * update( const State & t , std::uint64_t hash , Cost g , Cost h ,
                 NodeT * parent , std::uint8_t op , Local & local ,
                 std::uint64_t & duplicates ) {
  if( ! local.spare )
   local.spare = local.pool.allocate();
  *local.spare = NodeT{ t , g , h , parent , false , false , op };
  const auto [ x , fresh ] = f_table.findOrInsertKey( local.spare , hash );
  if( fresh ) {
   local.spare = nullptr;
   return( x );
   }
  if( g < std::atomic_ref< Cost >( x->g ).load(
           std::memory_order_relaxed ) ) {
   std::lock_guard< Lock > guard( lock( x ) );
   if( g < x->g ) {
    std::atomic_ref< Cost >( x->g ).store( g , std::memory_order_relaxed );
    x->parent = parent;
    x->op = op;
    x->closed = false;
    return( x );
    }
   }
  ++duplicates;
  return( nullptr );
  }
 
 private:
 
 // the hash of the state of a node, well spread by the Domain
 struct ByState {
  using is_avalanching = void;
  const D * d;
  std::uint64_t operator()( const NodeT * n ) const {
   return( d->hash( n->state ) );
   }
  };
 
 // the equality of the states of two nodes
 struct SameState {
  bool operator()( const NodeT * a , const NodeT * b ) const {
   return( a->state == b->state );
   }
  };
 
 static constexpr unsigned c_stripes = 256;        
 
 // a lock on a line of its own
 struct alignas( cache_line ) Stripe {
  Lock lock;
  };
 
 using Table = ADS::ConcurrentFlatTable< NodeT * , std::monostate , ByState ,
                                         SameState >;
 static_assert( Table::packed );
 
 const D & f_domain;                               
 Table f_table;                                    
 std::unique_ptr< Stripe[] > f_stripes{ new Stripe[ c_stripes ] }; 
 
 };  // end( class( ConcurrentClosed ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_ads_ConcurrentClosed */
 
/*--------------------------------------------------------------------------*/
/*---------------------- End File ConcurrentClosed.h -----------------------*/
/*--------------------------------------------------------------------------*/