Program Listing for File StringSearch.h

↰ Return to documentation for file (ADS/string/StringSearch.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File StringSearch.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"
#include "ADS/string/StringMatching.h"

#include <cstddef>
#include <array>
#include <cstdint>
#include <iterator>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

#ifndef ADS_SEARCH_SIMD
 #if defined( __AVX512BW__ )
  #define ADS_SEARCH_SIMD 3
 #elif defined( __AVX2__ )
  #define ADS_SEARCH_SIMD 2
 #elif defined( __SSE2__ ) || defined( _M_X64 )
  #define ADS_SEARCH_SIMD 1
 #else
  #define ADS_SEARCH_SIMD 0
 #endif
#endif

#if ADS_SEARCH_SIMD > 0
 #include <immintrin.h>
#endif

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------- CLASS StringSearcher ---------------------------*/
/*--------------------------------------------------------------------------*/

class StringSearcher {

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

 static constexpr std::size_t npos = std::string_view::npos;

 static constexpr std::size_t kSkip = 64;

 StringSearcher( void ) : StringSearcher( std::string_view() ) {}

 explicit StringSearcher( std::string_view P );

 [[nodiscard]] std::size_t find( std::string_view T ,
                                 std::size_t from = 0 ) const;

 [[nodiscard]] std::vector< std::size_t > findAll( std::string_view T ) const;

 [[nodiscard]] std::size_t count( std::string_view T ) const;

 template< std::contiguous_iterator I >
  requires( sizeof( std::iter_value_t< I > ) == 1 )
 [[nodiscard]] std::pair< I , I > operator()( I first , I last ) const {
  const std::string_view T( reinterpret_cast< const char * >(
                             std::to_address( first ) ) ,
                            std::size_t( last - first ) );
  const std::size_t s = find( T );
  if( s == npos ) return( std::pair( last , last ) );
  return( std::pair( first + std::ptrdiff_t( s ) ,
                     first + std::ptrdiff_t( s + f_P.size() ) ) );
  }

 [[nodiscard]] std::string_view pattern( void ) const { return( f_P ); }

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

 template< class F >
 std::size_t scan( std::string_view T , std::size_t from ,
                   F && report ) const;

 template< int k , int W , class F >
 std::size_t filter( const unsigned char * T , std::size_t n ,
                     std::size_t from , F && report ) const;

 template< class F >
 std::size_t filterBytes( const unsigned char * T , std::size_t n ,
                          std::size_t from , F && report ) const;

 template< class F >
 std::size_t skip( const unsigned char * T , std::size_t n ,
                   std::size_t from , F && report ) const;

 template< class F >
 std::size_t skipPair( const unsigned char * T , std::size_t n ,
                       std::size_t from , F && report ) const;

 [[nodiscard]] std::size_t gram( const unsigned char * p ) const;

 template< class F >
 std::size_t twoWay( const unsigned char * T , std::size_t n ,
                     std::size_t from , F && report ) const;

 std::string f_P;
 std::size_t f_off[ 4 ] = { 0 , 0 , 0 , 0 };
 unsigned char f_byte[ 4 ] = { 0 , 0 , 0 , 0 };
 int f_probes = 0;
 std::size_t f_q = 0;
 std::uint64_t f_qmask = 0;
 std::array< std::uint8_t , 4096 > f_shift;
 std::size_t f_shift0 = 1;

 };  // end( class StringSearcher )

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

[[nodiscard]] inline std::size_t findFirst( std::string_view T ,
                                            std::string_view P ,
                                            std::size_t from = 0 );

[[nodiscard]] inline std::vector< std::size_t > findAll( std::string_view T ,
                                                    std::string_view P );

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

}  // end( namespace ADS )

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

#include "ADS/string/impl/StringSearch.tpp"

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

#endif  /* StringSearch.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File StringSearch.h -------------------------*/
/*--------------------------------------------------------------------------*/