Program Listing for File RecSplit.h

↰ Return to documentation for file (ADS/dictionary/RecSplit.h)

/*--------------------------------------------------------------------------*/
/*---------------------------- File RecSplit.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/dictionary/FastHash.h"
#include "ADS/succinct/BitVector.h"

#if defined( __BMI2__ ) && defined( __x86_64__ )
 #include <immintrin.h>
#endif

#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <memory>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

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

namespace ADS {

namespace detail {

struct RecSplitTables {
 std::vector< std::uint8_t > rice;
 std::vector< std::uint32_t > low;
 std::vector< std::uint16_t > nodes;
 };

[[nodiscard]] int recSplitSelect( std::uint64_t x , int k );

class RecSplitSequence {
 public:
 RecSplitSequence( void ) = default;

 explicit RecSplitSequence( const std::vector< std::uint64_t > & x );

 [[nodiscard]] std::uint64_t access( std::size_t i ) const;

 [[nodiscard]] std::pair< std::uint64_t , std::uint64_t > pair(
                                                    std::size_t i ) const;

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

 private:
 [[nodiscard]] std::size_t select( std::size_t i ) const;

 [[nodiscard]] std::uint64_t low( std::size_t i ) const;

 int f_l = 0;
 std::vector< std::uint64_t > f_low;
 std::vector< std::uint64_t > f_high;
 std::vector< std::uint64_t > f_inv;
 };

}  // end( namespace detail )

/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS RecSplit -----------------------------*/
/*--------------------------------------------------------------------------*/

template< class T , unsigned L = 8 , class H = DefaultHash< T > >
class RecSplit {

 static_assert( ( L >= 1 ) && ( L <= 24 ) , "RecSplit: 1 <= L <= 24" );

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

 using Key = T;

 explicit RecSplit( const std::vector< T > & keys , std::size_t b = 100 ,
                    std::uint64_t seed = 1 , H h = H() );

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

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

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

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

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

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

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

 static constexpr std::size_t kMaxTrials = 100;
 static constexpr std::size_t kMaxBucket = 4096;
 static constexpr std::size_t kLower =
  std::max< std::size_t >( 2 , ( 35 * L + 50 + 99 ) / 100 ) * L;
 static constexpr std::size_t kUpper =
  ( L >= 7 ? ( 21 * L + 90 + 99 ) / 100 : 2 ) * kLower;

 [[nodiscard]] static const detail::RecSplitTables & tables( void );

 [[nodiscard]] static constexpr std::size_t left( std::size_t m );

 [[nodiscard]] static std::uint64_t node( std::uint64_t h ,
                                          std::uint64_t x , unsigned d );

 [[nodiscard]] static std::size_t remap( std::uint64_t g , std::size_t m );

 [[nodiscard]] std::uint64_t base( const T & k ) const;

 [[nodiscard]] std::uint64_t window( std::uint64_t at ) const;

 [[nodiscard]] std::uint64_t skipOnes( std::uint64_t at ,
                                       std::size_t c ) const;

 static void split( std::uint64_t * K , std::uint64_t * S , std::size_t m ,
                    unsigned d , std::vector< std::uint64_t > & seeds ,
                    std::vector< std::uint8_t > & rice );

 bool build( const std::vector< std::uint64_t > & B , std::size_t b );

 std::uint64_t f_seed;
 std::size_t f_n = 0;
 std::size_t f_nb = 0;
 std::vector< std::uint64_t > f_code;
 detail::RecSplitSequence f_keys;
 detail::RecSplitSequence f_place;
 std::uint64_t f_dk = 0;
 std::int64_t f_dp = 0;
 std::uint64_t f_beta = 0;
 const detail::RecSplitTables * f_t = nullptr;
 std::size_t f_trials = 0;
 H f_h;

 };  // end( class RecSplit )

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

}  // end( namespace ADS )

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

#include "ADS/dictionary/impl/RecSplit.tpp"

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

#endif  /* RecSplit.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File RecSplit.h ---------------------------*/
/*--------------------------------------------------------------------------*/