Program Listing for File StaticSearch.h

↰ Return to documentation for file (ADS/search/StaticSearch.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File StaticSearch.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/memory/HugePageAllocator.h"
#include "ADS/search/CountLess.h"

#include <algorithm>
#include <cstddef>
#include <functional>
#include <limits>
#include <memory>
#include <new>
#include <type_traits>
#include <vector>


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

namespace ADS {

template< class T , class C = std::less<> >
std::size_t branchlessLowerBound( const std::vector< T > & A , const T & v ,
                                  C less = C() );

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS SPlusTree ------------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , class Less = std::less< T > , std::size_t Bytes = 64 >
 requires std::is_trivially_copyable_v< T >
class SPlusTree {

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

 using Item = T;

 static constexpr std::size_t B = sizeof( T ) <= Bytes ?
  std::max< std::size_t >( Bytes / sizeof( T ) , 2 ) : 2;

 SPlusTree( void ) = default;

 explicit SPlusTree( const std::vector< T > & A , Less less = Less() );

 SPlusTree( const SPlusTree & o );

 SPlusTree( SPlusTree && o ) noexcept = default;

 SPlusTree & operator=( SPlusTree o ) noexcept;

 [[nodiscard]] std::size_t lowerBound( const T & v ) const;

 [[nodiscard]] std::size_t upperBound( const T & v ) const;

 [[nodiscard]] bool contains( const T & v ) const;

 [[nodiscard]] const T & operator[]( std::size_t i ) const;

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

 [[nodiscard]] bool empty( void ) const;

 [[nodiscard]] int height( void ) const;

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

 static constexpr bool FAST = std::is_arithmetic_v< T > &&
  ( std::is_same_v< Less , std::less< T > > ||
    std::is_same_v< Less , std::less<> > );

 [[nodiscard]] static constexpr T pad( void ) {
  if constexpr( std::numeric_limits< T >::has_infinity )
   return( std::numeric_limits< T >::infinity() );
  else
   return( std::numeric_limits< T >::max() );
  }

 [[nodiscard]] static T * allocate( std::size_t n );

 struct Free {
  std::size_t n = 0;
  void operator()( T * p ) const noexcept {
   if( n * sizeof( T ) >= HUGE_BYTES )
    HugePageAllocator< T >().deallocate( p , n );
   else
    ::operator delete( p , std::align_val_t( 64 ) );
   }
  };

 static constexpr std::size_t HUGE_BYTES = std::size_t( 1 ) << 21;

 template< bool Up >
 [[nodiscard]] std::size_t count( const T * a , const T & v ,
                                  std::size_t m ) const;

 template< bool Up >
 [[nodiscard]] std::size_t search( const T & v ) const;

 void layout( const std::vector< T > & A );

 std::vector< std::size_t > f_size;

 std::unique_ptr< T[] , Free > f_a;
 std::vector< std::size_t > f_off;
 std::size_t f_items = 0;
 std::size_t f_n = 0;
 [[no_unique_address]] Less f_less;

 };  // end( class SPlusTree )

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

}  // end( namespace ADS )

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

#include "ADS/search/impl/StaticSearch.tpp"

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

#endif  /* StaticSearch.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File StaticSearch.h -------------------------*/
/*--------------------------------------------------------------------------*/