bloom/detail/core.hpp

0001 /* Common base for all boost::bloom::filter instantiations.
0002  *
0003  * Copyright 2025 Joaquin M Lopez Munoz.
0004  * Distributed under the Boost Software License, Version 1.0.
0005  * (See accompanying file LICENSE_1_0.txt or copy at
0006  * http://www.boost.org/LICENSE_1_0.txt)
0007  *
0008  * See https://www.boost.org/libs/bloom for library home page.
0009  */
0010
0011 #ifndef BOOST_BLOOM_DETAIL_CORE_HPP
0012 #define BOOST_BLOOM_DETAIL_CORE_HPP
0013
0014 #include <algorithm>
0015 #include <boost/assert.hpp>
0016 #include <boost/bloom/detail/mulx64.hpp>
0017 #include <boost/bloom/detail/sse2.hpp>
0018 #include <boost/config.hpp>
0019 #include <boost/core/allocator_traits.hpp>
0020 #include <boost/core/bit.hpp>
0021 #include <boost/core/empty_value.hpp>
0022 #include <boost/core/span.hpp>
0023 #include <boost/throw_exception.hpp>
0024 #include <climits>
0025 #include <cmath>
0026 #include <cstdint>
0027 #include <cstring>
0028 #include <limits>
0029 #include <memory>
0030 #include <stdexcept>
0031 #include <tuple>
0032 #include <type_traits>
0033 #include <utility>
0034
0035 #ifdef __has_builtin
0036 #define BOOST_BLOOM_HAS_BUILTIN(x) __has_builtin(x)
0037 #else
0038 #define BOOST_BLOOM_HAS_BUILTIN(x) 0
0039 #endif
0040
0041 #if !defined(NDEBUG)
0042 #define BOOST_BLOOM_ASSUME(cond) BOOST_ASSERT(cond)
0043 #elif BOOST_BLOOM_HAS_BUILTIN(__builtin_assume)
0044 #define BOOST_BLOOM_ASSUME(cond) __builtin_assume(cond)
0045 #elif defined(__GNUC__) || BOOST_BLOOM_HAS_BUILTIN(__builtin_unreachable)
0046 #define BOOST_BLOOM_ASSUME(cond)    \
0047   do{                                   \
0048     if(!(cond))__builtin_unreachable(); \
0049   }while(0)
0050 #elif defined(_MSC_VER)
0051 #define BOOST_BLOOM_ASSUME(cond) __assume(cond)
0052 #else
0053 #define BOOST_BLOOM_ASSUME(cond)  \
0054   do{                                 \
0055     static_cast<void>(false&&(cond)); \
0056   }while(0)
0057 #endif
0058
0059  /* We use BOOST_BLOOM_PREFETCH[_WRITE] macros rather than proper
0060  * functions because of https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109985
0061  */
0062
0063 #if defined(BOOST_GCC)||defined(BOOST_CLANG)
0064 #define BOOST_BLOOM_PREFETCH(p) __builtin_prefetch((const char*)(p))
0065 #define BOOST_BLOOM_PREFETCH_WRITE(p) __builtin_prefetch((const char*)(p),1)
0066 #elif defined(BOOST_BLOOM_SSE2)
0067 #define BOOST_BLOOM_PREFETCH(p) _mm_prefetch((const char*)(p),_MM_HINT_T0)
0068 #if defined(_MM_HINT_ET0)
0069 #define BOOST_BLOOM_PREFETCH_WRITE(p) \
0070 _mm_prefetch((const char*)(p),_MM_HINT_ET0)
0071 #else
0072 #define BOOST_BLOOM_PREFETCH_WRITE(p) \
0073 _mm_prefetch((const char*)(p),_MM_HINT_T0)
0074 #endif
0075 #else
0076 #define BOOST_BLOOM_PREFETCH(p) ((void)(p))
0077 #define BOOST_BLOOM_PREFETCH_WRITE(p) ((void)(p))
0078 #endif
0079
0080 namespace boost{
0081 namespace bloom{
0082 namespace detail{
0083
0084 #if defined(BOOST_MSVC)
0085 #pragma warning(push)
0086 #pragma warning(disable:4714) /* marked as __forceinline not inlined */
0087 #endif
0088
0089 /* fastrange_and_mcg produces (pos,hash') from hash as follows:
0090  *   - pos=high(mulx64(hash,range))
0091  *   - hash'=c*m
0092  * pos is uniformly distributed in [0,range) (see Lemire 2018
0093  * https://arxiv.org/pdf/1805.10941), whereas hash'<-hash is a multiplicative
0094  * congruential generator using well-behaved multipliers c from Steele and
0095  * Vigna 2021 https://arxiv.org/pdf/2001.05304 . To ensure the MCG generates
0096  * long cycles the initial value of hash is adjusted to be odd, which implies
0097  * that the least significant of hash' is always one. In general, the low bits
0098  * of MCG-produced values are of low quality and we don't use them downstream.
0099  */
0100
0101 struct fastrange_and_mcg
0102 {
0103   constexpr fastrange_and_mcg(std::size_t m)noexcept:rng{m}{}
0104
0105   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0106   inline constexpr std::size_t range()const noexcept{return (std::size_t)rng;}
0107
0108   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0109   inline void prepare_hash(std::uint64_t& hash)const noexcept
0110   {
0111     hash|=1u;
0112   }
0113
0114   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0115   inline std::size_t next_position(std::uint64_t& hash)const noexcept
0116   {
0117     boost::uint64_t hi;
0118     umul128(hash,rng,hi);
0119
0120 #if ((((SIZE_MAX>>16)>>16)>>16)>>15)!=0 /* 64-bit mode (or higher) */
0121     hash*=0xf1357aea2e62a9c5ull;
0122 #else /* 32-bit mode */
0123     hash*=0xe817fb2d;
0124 #endif
0125     return (std::size_t)hi;
0126   }
0127
0128   std::uint64_t rng;
0129 };
0130
0131 /* used_value_size<Subfilter>::value is Subfilter::used_value_size if it
0132  * exists, or sizeof(Subfilter::value_type) otherwise. This covers the
0133  * case where a subfilter only operates on the first bytes of its entire
0134  * value_type (e.g. fast_multiblock32<K> with K<8).
0135  */
0136
0137 template<typename Subfilter,typename=void>
0138 struct used_value_size
0139 {
0140   static constexpr std::size_t value=sizeof(typename Subfilter::value_type);
0141 };
0142
0143 template<typename Subfilter>
0144 struct used_value_size<
0145   Subfilter,
0146   typename std::enable_if<Subfilter::used_value_size!=0>::type
0147 >
0148 {
0149   static constexpr std::size_t value=Subfilter::used_value_size;
0150 };
0151
0152 /* GCD with x,p > 1, p a power of two */
0153
0154 constexpr std::size_t gcd_pow2(std::size_t x,std::size_t p)
0155 {
0156   /* x&-x: maximum power of two dividing x */
0157   return (x&(0-x))<p?(x&(0-x)):p;
0158 }
0159
0160 /* std::ldexp is not constexpr in C++11 */
0161
0162 constexpr double constexpr_ldexp_1_positive(int exp)
0163 {
0164   return exp==0?1.0:2.0*constexpr_ldexp_1_positive(exp-1);
0165 }
0166
0167 inline unsigned int unchecked_countr_zero(std::uint64_t x)
0168 {
0169 #if defined(BOOST_MSVC)&&(defined(_M_X64)||defined(_M_ARM64))
0170   unsigned long r;
0171   _BitScanForward64(&r,x);
0172   return (unsigned int)r;
0173 #elif defined(BOOST_GCC)||defined(BOOST_CLANG)
0174   return (unsigned int)__builtin_ctzll(x);
0175 #else
0176   BOOST_BLOOM_ASSUME(x!=0);
0177   return (unsigned int)boost::core::countr_zero(x);
0178 #endif
0179 }
0180
0181 struct filter_array
0182 {
0183   unsigned char* data;
0184   unsigned char* array; /* adjusted from data for proper alignment */
0185 };
0186
0187 struct if_constexpr_void_else{void operator()()const{}};
0188
0189 template<bool B,typename F,typename G=if_constexpr_void_else>
0190 void if_constexpr(F f,G g={})
0191 {
0192   std::get<B?0:1>(std::forward_as_tuple(f,g))();
0193 }
0194
0195 template<bool B,typename T,typename std::enable_if<B>::type* =nullptr>
0196 void copy_assign_if(T& x,const T& y){x=y;}
0197
0198 template<bool B,typename T,typename std::enable_if<!B>::type* =nullptr>
0199 void copy_assign_if(T&,const T&){}
0200
0201 template<bool B,typename T,typename std::enable_if<B>::type* =nullptr>
0202 void move_assign_if(T& x,T& y){x=std::move(y);}
0203
0204 template<bool B,typename T,typename std::enable_if<!B>::type* =nullptr>
0205 void move_assign_if(T&,T&){}
0206
0207 template<bool B,typename T,typename std::enable_if<B>::type* =nullptr>
0208 void swap_if(T& x,T& y){using std::swap; swap(x,y);}
0209
0210 template<bool B,typename T,typename std::enable_if<!B>::type* =nullptr>
0211 void swap_if(T&,T&){}
0212
0213 template<
0214   std::size_t K,typename Subfilter,std::size_t Stride,typename Allocator
0215 >
0216 class filter_core:empty_value<Allocator,0>
0217 {
0218   static_assert(K>0,"K must be >= 1");
0219   static_assert(
0220     std::is_same<allocator_value_type_t<Allocator>,unsigned char>::value,
0221     "Allocator value_type must be unsigned char");
0222
0223 public:
0224   static constexpr std::size_t k=K;
0225   using subfilter=Subfilter;
0226
0227 private:
0228   static constexpr std::size_t kp=subfilter::k;
0229   static constexpr std::size_t k_total=k*kp;
0230   using block_type=typename subfilter::value_type;
0231   static constexpr std::size_t block_size=sizeof(block_type);
0232   static constexpr std::size_t used_value_size=
0233     detail::used_value_size<subfilter>::value;
0234
0235 public:
0236   static constexpr std::size_t stride=Stride?Stride:used_value_size;
0237   static_assert(
0238     stride<=used_value_size,"Stride can't exceed the block size");
0239
0240 private:
0241   static constexpr std::size_t tail_size=sizeof(block_type)-stride;
0242   static constexpr bool are_blocks_aligned=
0243     (stride%alignof(block_type)==0);
0244   static constexpr std::size_t cacheline=64; /* unknown at compile time */
0245   static constexpr std::size_t initial_alignment=
0246     are_blocks_aligned?
0247       alignof(block_type)>cacheline?alignof(block_type):cacheline:
0248       1;
0249   static constexpr std::size_t prefetched_cachelines=
0250     1+(block_size+cacheline-1-gcd_pow2(stride,cacheline))/cacheline;
0251   using hash_strategy=detail::fastrange_and_mcg;
0252
0253 public:
0254   using allocator_type=Allocator;
0255   using size_type=std::size_t;
0256   using difference_type=std::ptrdiff_t;
0257   using pointer=unsigned char*;
0258   using const_pointer=const unsigned char*;
0259   static constexpr std::size_t bulk_insert_size=
0260     (64+prefetched_cachelines-1)/prefetched_cachelines;
0261   static constexpr std::size_t bulk_may_contain_size=
0262     (64+prefetched_cachelines-1)/prefetched_cachelines;
0263   static_assert(
0264     bulk_may_contain_size<=64, /* see results in bulk_may_contain */
0265     "internal check, bulk_may_contain_size must be <= 64");
0266
0267   explicit filter_core(std::size_t m=0):filter_core{m,allocator_type{}}{}
0268
0269   filter_core(std::size_t m,const allocator_type& al_):
0270     allocator_base{empty_init,al_},
0271     hs{requested_range(m)},
0272     ar(new_array(al(),m?hs.range():0))
0273   {
0274     clear_bytes();
0275   }
0276
0277   filter_core(std::size_t n,double fpr,const allocator_type& al_):
0278     filter_core(unadjusted_capacity_for(n,fpr),al_){}
0279
0280   filter_core(const filter_core& x):
0281     filter_core{x,allocator_select_on_container_copy_construction(x.al())}{}
0282
0283   filter_core(filter_core&& x)noexcept:
0284     filter_core{std::move(x),allocator_type(std::move(x.al()))}{}
0285
0286   filter_core(const filter_core& x,const allocator_type& al_):
0287     allocator_base{empty_init,al_},
0288     hs{x.hs},
0289     ar(new_array(al(),x.range()))
0290   {
0291     copy_bytes(x);
0292   }
0293
0294   filter_core(filter_core&& x,const allocator_type& al_):
0295     allocator_base{empty_init,al_},
0296     hs{x.hs}
0297   {
0298     auto empty_ar=new_array(x.al(),0); /* we're relying on this not throwing */
0299     if(al()==x.al()){
0300       ar=x.ar;
0301     }
0302     else{
0303       ar=new_array(al(),x.range());
0304       copy_bytes(x);
0305       x.delete_array();
0306     }
0307     x.hs=hash_strategy{0};
0308     x.ar=empty_ar;
0309   }
0310
0311   ~filter_core()noexcept
0312   {
0313     delete_array();
0314   }
0315
0316   filter_core& operator=(const filter_core& x)
0317   {
0318     static constexpr auto pocca=
0319       allocator_propagate_on_container_copy_assignment_t<allocator_type>::
0320         value;
0321
0322     if(this!=&x){
0323       if_constexpr<pocca>([&,this]{
0324         if(al()!=x.al()||range()!=x.range()){
0325           auto x_al=x.al();
0326           auto new_ar=new_array(x_al,x.range());
0327           delete_array();
0328           hs=x.hs;
0329           ar=new_ar;
0330         }
0331         copy_assign_if<pocca>(al(),x.al());
0332       },
0333       [&,this]{ /* else */
0334         if(range()!=x.range()){
0335           auto new_ar=new_array(al(),x.range());
0336           delete_array();
0337           hs=x.hs;
0338           ar=new_ar;
0339         }
0340       });
0341       copy_bytes(x);
0342     }
0343     return *this;
0344   }
0345
0346 #if defined(BOOST_MSVC)
0347 #pragma warning(push)
0348 #pragma warning(disable:4127) /* conditional expression is constant */
0349 #endif
0350
0351   filter_core& operator=(filter_core&& x)noexcept(
0352     allocator_propagate_on_container_move_assignment_t<allocator_type>::value||
0353     allocator_is_always_equal_t<allocator_type>::value)
0354   {
0355     static constexpr auto pocma=
0356       allocator_propagate_on_container_move_assignment_t<allocator_type>::
0357         value;
0358
0359     if(this!=&x){
0360       auto empty_ar=new_array(x.al(),0); /* relying on this not throwing */
0361       if(pocma||al()==x.al()){
0362         delete_array();
0363         move_assign_if<pocma>(al(),x.al());
0364         hs=x.hs;
0365         ar=x.ar;
0366       }
0367       else{
0368         if(range()!=x.range()){
0369           auto new_ar=new_array(al(),x.range());
0370           delete_array();
0371           hs=x.hs;
0372           ar=new_ar;
0373         }
0374         copy_bytes(x);
0375         x.delete_array();
0376       }
0377       x.hs=hash_strategy{0};
0378       x.ar=empty_ar;
0379     }
0380     return *this;
0381   }
0382
0383 #if defined(BOOST_MSVC)
0384 #pragma warning(pop) /* C4127 */
0385 #endif
0386
0387   allocator_type get_allocator()const noexcept
0388   {
0389     return al();
0390   }
0391
0392   std::size_t capacity()const noexcept
0393   {
0394     return used_array_size()*CHAR_BIT;
0395   }
0396
0397   static std::size_t capacity_for(std::size_t n,double fpr)
0398   {
0399     auto m=unadjusted_capacity_for(n,fpr);
0400     if(m==0)return 0;
0401     auto rng=hash_strategy{requested_range(m)}.range();
0402     return used_array_size(rng)*CHAR_BIT;
0403   }
0404
0405   static double fpr_for(std::size_t n,std::size_t m)
0406   {
0407     return m==0?1.0:n==0?0.0:fpr_for_c((double)m/n);
0408   }
0409
0410   boost::span<unsigned char> array()noexcept
0411   {
0412     return {ar.data?ar.array:nullptr,capacity()/CHAR_BIT};
0413   }
0414
0415   boost::span<const unsigned char> array()const noexcept
0416   {
0417     return {ar.data?ar.array:nullptr,capacity()/CHAR_BIT};
0418   }
0419
0420   BOOST_FORCEINLINE void insert(std::uint64_t hash)
0421   {
0422     hs.prepare_hash(hash);
0423     for(auto n=k;n--;){
0424       auto p=next_element(hash); /* modifies h */
0425       /* We do the unhappy-path null check here rather than at the beginning
0426        * of the function because prefetch completion wait gives us free CPU
0427        * cycles to spare.
0428        */
0429       if(BOOST_UNLIKELY(n==k-1&&ar.data==nullptr))return;
0430
0431       set(p,hash);
0432     }
0433   }
0434
0435   template<typename HashStream>
0436   void bulk_insert(HashStream h,std::size_t n)
0437   {
0438     std::uint64_t  hashes[bulk_insert_size];
0439     unsigned char* positions[bulk_insert_size];
0440
0441     if(n>=2*bulk_insert_size){
0442       for(auto i=bulk_insert_size;i--;){
0443         auto& hash=hashes[i]=h();
0444         auto& p=positions[i];
0445         hs.prepare_hash(hash);
0446         p=next_element(hash);
0447       }
0448       if(BOOST_UNLIKELY(ar.data==nullptr))return;
0449       do{
0450         for(auto j=k-1;j--;){
0451           for(auto i=bulk_insert_size;i--;){
0452             auto& hash=hashes[i];
0453             auto& p=positions[i];
0454             auto  hash0=hash;
0455             auto  p0=p;
0456             p=next_element(hash);
0457             set(p0,hash0);
0458           }
0459         }
0460         for(auto i=bulk_insert_size;i--;){
0461           auto& hash=hashes[i];
0462           auto& p=positions[i];
0463           auto  hash0=hash;
0464           auto  p0=p;
0465           hash=h();
0466           hs.prepare_hash(hash);
0467           p=next_element(hash);
0468           set(p0,hash0);
0469         }
0470         n-=bulk_insert_size;
0471       }while(n>=2*bulk_insert_size);
0472       for(auto j=k-1;j--;){
0473         for(auto i=bulk_insert_size;i--;){
0474           auto& hash=hashes[i];
0475           auto& p=positions[i];
0476           auto  hash0=hash;
0477           auto  p0=p;
0478           p=next_element(hash);
0479           set(p0,hash0);
0480         }
0481       }
0482       for(auto i=bulk_insert_size;i--;){
0483         auto& hash=hashes[i];
0484         auto& p=positions[i];
0485         set(p,hash);
0486       }
0487       n-=bulk_insert_size;
0488     }
0489     while(n--)insert(h());
0490   }
0491
0492   void swap(filter_core& x)noexcept(
0493     allocator_propagate_on_container_swap_t<allocator_type>::value||
0494     allocator_is_always_equal_t<allocator_type>::value)
0495   {
0496     static constexpr auto pocs=
0497       allocator_propagate_on_container_swap_t<allocator_type>::value;
0498
0499     if_constexpr<pocs>([&,this]{
0500       swap_if<pocs>(al(),x.al());
0501     },
0502     [&,this]{ /* else */
0503       BOOST_ASSERT(al()==x.al());
0504       (void)this; /* makes sure captured this is used */
0505     });
0506     std::swap(hs,x.hs);
0507     std::swap(ar,x.ar);
0508   }
0509
0510   void clear()noexcept
0511   {
0512     clear_bytes();
0513   }
0514
0515   void reset(std::size_t m=0)
0516   {
0517     hash_strategy new_hs{requested_range(m)};
0518     std::size_t   rng=m?new_hs.range():0;
0519     if(rng!=range()){
0520       auto new_ar=new_array(al(),rng);
0521       delete_array();
0522       hs=new_hs;
0523       ar=new_ar;
0524     }
0525     clear_bytes();
0526   }
0527
0528   void reset(std::size_t n,double fpr)
0529   {
0530     reset(capacity_for(n,fpr));
0531   }
0532
0533   filter_core& operator&=(const filter_core& x)
0534   {
0535     combine(x,[](unsigned char& a,unsigned char b){a&=b;});
0536     return *this;
0537   }
0538
0539   filter_core& operator|=(const filter_core& x)
0540   {
0541     combine(x,[](unsigned char& a,unsigned char b){a|=b;});
0542     return *this;
0543   }
0544
0545   BOOST_FORCEINLINE bool may_contain(std::uint64_t hash)const
0546   {
0547     hs.prepare_hash(hash);
0548 #if 1
0549     auto p0=next_element(hash);
0550     for(std::size_t n=k-1;n--;){
0551       auto p=p0;
0552       auto hash0=hash;
0553       p0=next_element(hash);
0554       if(!get(p,hash0))return false;
0555     }
0556     if(!get(p0,hash))return false;
0557     return true;
0558 #else
0559     for(auto n=k;n--;){
0560       auto p=next_element(hash); /* modifies hash */
0561       if(!get(p,hash))return false;
0562     }
0563     return true;
0564 #endif
0565   }
0566
0567   template<typename HashStream,typename F>
0568   void bulk_may_contain(HashStream h,std::size_t n,F f)const
0569   {
0570     if(k==1){
0571       std::uint64_t        hashes[bulk_may_contain_size];
0572       const unsigned char* positions[bulk_may_contain_size];
0573
0574       if(n>=2*bulk_may_contain_size){
0575         for(auto i=bulk_may_contain_size;i--;){
0576           auto& hash=hashes[i]=h();
0577           auto& p=positions[i];
0578           hs.prepare_hash(hash);
0579           p=next_element(hash);
0580         }
0581         do{
0582           for(auto i=bulk_may_contain_size;i--;){
0583             auto& hash=hashes[i];
0584             auto& p=positions[i];
0585             auto  hash0=hash;
0586             auto  p0=p;
0587             hash=h();
0588             hs.prepare_hash(hash);
0589             p=next_element(hash);
0590             f(get(p0,hash0));
0591           }
0592           n-=bulk_may_contain_size;
0593         }while(n>=2*bulk_may_contain_size);
0594
0595         for(auto i=bulk_may_contain_size;i--;){
0596           auto& hash=hashes[i];
0597           auto& p=positions[i];
0598           f(get(p,hash));
0599         }
0600         n-=bulk_may_contain_size;
0601       }
0602
0603       while(n--)f(may_contain(h()));
0604     }
0605     else{
0606       static constexpr std::uint64_t initial_result_mask=
0607         ((std::uint64_t(1)<<(bulk_may_contain_size/2))<<
0608           ((bulk_may_contain_size+1)/2))-1;
0609
0610       std::uint64_t        hashes[bulk_may_contain_size];
0611       const unsigned char* positions[bulk_may_contain_size];
0612       std::uint64_t        results=initial_result_mask;
0613
0614       if(n>=2*bulk_may_contain_size){
0615         for(std::size_t i=0;i<bulk_may_contain_size;++i){
0616           auto& hash=hashes[i]=h();
0617           auto& p=positions[i];
0618           hs.prepare_hash(hash);
0619           p=next_element(hash);
0620         }
0621         do{
0622           for(auto j=k;j--;){
0623             auto mask=results;
0624             if(!mask)break;
0625             do{
0626               auto i=unchecked_countr_zero(mask);
0627               auto& hash=hashes[i];
0628               auto& p=positions[i];
0629               auto  b=get(p,hash);
0630               p=next_element(hash);
0631               results&=~(std::uint64_t(!b)<<i);
0632               mask&=mask-1;
0633             }while(mask);
0634           }
0635           for(std::size_t i=0;i<bulk_may_contain_size;++i){
0636             auto& hash=hashes[i];
0637             auto& p=positions[i];
0638             hash=h();
0639             hs.prepare_hash(hash);
0640             p=next_element(hash);
0641             f(results&1);
0642             results>>=1;
0643           }
0644           results=initial_result_mask;
0645           n-=bulk_may_contain_size;
0646         }while(n>=2*bulk_may_contain_size);
0647
0648         for(auto j=k;j--;){
0649           auto mask=results;
0650           if(!mask)break;
0651           do{
0652             auto i=unchecked_countr_zero(mask);
0653             auto& hash=hashes[i];
0654             auto& p=positions[i];
0655             auto  b=get(p,hash);
0656             p=next_element(hash);
0657             results&=~(std::uint64_t(!b)<<i);
0658             mask&=mask-1;
0659           }while(mask);
0660         }
0661         for(std::size_t i=0;i<bulk_may_contain_size;++i){
0662           f(results&1);
0663           results>>=1;
0664         }
0665         n-=bulk_may_contain_size;
0666       }
0667
0668       while(n--)f(may_contain(h()));
0669     }
0670   }
0671
0672   friend bool operator==(const filter_core& x,const filter_core& y)
0673   {
0674     if(x.range()!=y.range())return false;
0675     else if(!x.ar.data)return true;
0676     else return std::memcmp(x.ar.array,y.ar.array,x.used_array_size())==0;
0677   }
0678
0679 private:
0680   using allocator_base=empty_value<Allocator,0>;
0681
0682   const Allocator& al()const{return allocator_base::get();}
0683   Allocator& al(){return allocator_base::get();}
0684
0685   static std::size_t requested_range(std::size_t m)
0686   {
0687     if(m>(used_value_size-stride)*CHAR_BIT){
0688       /* ensures filter_core{f.capacity()}.capacity()==f.capacity() */
0689       m-=(used_value_size-stride)*CHAR_BIT;
0690     }
0691     return
0692       (std::numeric_limits<std::size_t>::max)()-m>=stride*CHAR_BIT-1?
0693       (m+stride*CHAR_BIT-1)/(stride*CHAR_BIT):
0694       m/(stride*CHAR_BIT);
0695   }
0696
0697   static filter_array new_array(allocator_type& al,std::size_t rng)
0698   {
0699     if(rng){
0700       auto p=allocator_allocate(al,space_for(rng));
0701       return {p,array_for(p)};
0702     }
0703     else{
0704       /* To avoid dynamic allocation for zero capacity or moved-from filters,
0705        * we point array to a statically allocated dummy array with all bits
0706        * set to one. This is good for read operations but not so for write
0707        * operations, where we need to resort to a null check on
0708        * filter_array::data.
0709        */
0710
0711       static struct {unsigned char x=-1;}
0712       dummy[space_for(hash_strategy{0}.range())];
0713
0714       return {nullptr,array_for(reinterpret_cast<unsigned char*>(&dummy))};
0715     }
0716   }
0717
0718   void delete_array()noexcept
0719   {
0720     if(ar.data)allocator_deallocate(al(),ar.data,space_for(range()));
0721   }
0722
0723   void clear_bytes()noexcept
0724   {
0725     std::memset(ar.array,0,used_array_size());
0726   }
0727
0728   void copy_bytes(const filter_core& x)
0729   {
0730     BOOST_ASSERT(range()==x.range());
0731     std::memcpy(ar.array,x.ar.array,used_array_size());
0732   }
0733
0734   std::size_t range()const noexcept
0735   {
0736     return ar.data?hs.range():0;
0737   }
0738
0739   static constexpr std::size_t space_for(std::size_t rng)noexcept
0740   {
0741     return (initial_alignment-1)+rng*stride+tail_size;
0742   }
0743
0744   static unsigned char* array_for(unsigned char* p)noexcept
0745   {
0746     return p+
0747       (std::uintptr_t(initial_alignment)-
0748        std::uintptr_t(p))%initial_alignment;
0749   }
0750
0751   std::size_t used_array_size()const noexcept
0752   {
0753     return used_array_size(range());
0754   }
0755
0756   static std::size_t used_array_size(std::size_t rng)noexcept
0757   {
0758     return rng?rng*stride+(used_value_size-stride):0;
0759   }
0760
0761   static std::size_t unadjusted_capacity_for(std::size_t n,double fpr)
0762   {
0763     using size_t_limits=std::numeric_limits<std::size_t>;
0764     using double_limits=std::numeric_limits<double>;
0765
0766     BOOST_ASSERT(fpr>=0.0&&fpr<=1.0);
0767     if(n==0)return fpr==1.0?0:1;
0768
0769     constexpr double eps=1.0/(double)(size_t_limits::max)();
0770     constexpr double max_size_t_as_double=
0771       size_t_limits::digits<=double_limits::digits?
0772       (double)(size_t_limits::max)():
0773       (double)(size_t_limits::max)()
0774         /* ensure value is portably castable back to std::size_t */
0775         -constexpr_ldexp_1_positive(
0776           size_t_limits::digits-double_limits::digits);
0777
0778     const double c_max=max_size_t_as_double/n;
0779
0780     /* Capacity of a classical Bloom filter as a lower bound:
0781      * c = k / -log(1 - fpr^(1/k)).
0782      */
0783
0784     double d=1.0-std::pow(fpr,1.0/k_total);
0785     if(std::fpclassify(d)==FP_ZERO)return 0; /* fpr ~ 1 */
0786     double l=std::log(d);
0787     if(std::fpclassify(l)==FP_ZERO)return (std::size_t)(c_max*n); /* fpr ~ 0 */
0788     double c0=(std::min)(k_total/-l,c_max);
0789
0790     /* bracket target fpr between c0 and c1 */
0791
0792     double c1=c0;
0793     if(fpr_for_c(c1)>fpr){ /* expected case */
0794       do{
0795         double cn=c1*1.5;
0796         if(cn>c_max)return (std::size_t)(c_max*n);
0797         c0=c1;
0798         c1=cn;
0799       }while(fpr_for_c(c1)>fpr);
0800     }
0801     else{ /* c0 shouldn't overshoot ever, just in case */
0802       do{
0803         double cn=c0/1.5;
0804         c1=c0;
0805         c0=cn;
0806       }while(fpr_for_c(c0)<fpr);
0807     }
0808
0809     /* bisect */
0810
0811     double cm;
0812     while((cm=c0+(c1-c0)/2)>c0 && cm<c1 && c1-c0>=eps){
0813       if(fpr_for_c(cm)>fpr)c0=cm;
0814       else                 c1=cm;
0815     }
0816     return (std::size_t)(cm*n);
0817   }
0818
0819   static double fpr_for_c(double c)
0820   {
0821     constexpr std::size_t w=(2*used_value_size-stride)*CHAR_BIT;
0822     const double          lambda=w*k/c;
0823     const double          loglambda=std::log(lambda);
0824     double                res=0.0;
0825     double                deltap=0.0;
0826     for(int i=0;i<1000;++i){
0827       double poisson=std::exp(i*loglambda-lambda-std::lgamma(i+1));
0828       double delta=poisson*subfilter::fpr(i,w);
0829       double resn=res+delta;
0830
0831       /* The terms of this summation are unimodal, so we check we're on the
0832        * descending slope before stopping.
0833        */
0834
0835       if(delta<deltap&&resn==res)break;
0836       deltap=delta;
0837       res=resn;
0838     }
0839
0840     /* For small values of c (high values of lambda), truncation errors,loop
0841      * exhaustion and the use of Poisson instead of binomial may result in a
0842      * calculated value less than the classical Bloom filter formula, which we
0843      * know is always the minimum attainable.
0844      */
0845
0846     return (std::max)(
0847       std::pow((double)res,(double)k),
0848       std::pow(1.0-std::exp(-(double)k_total/c),(double)k_total));
0849   }
0850
0851   BOOST_FORCEINLINE bool get(const unsigned char* p,std::uint64_t hash)const
0852   {
0853     return get(p,hash,std::integral_constant<bool,are_blocks_aligned>{});
0854   }
0855
0856   BOOST_FORCEINLINE bool get(
0857     const unsigned char* p,std::uint64_t hash,
0858     std::true_type /* blocks aligned */)const
0859   {
0860     return subfilter::check(*reinterpret_cast<const block_type*>(p),hash);
0861   }
0862
0863   BOOST_FORCEINLINE bool get(
0864     const unsigned char* p,std::uint64_t hash,
0865     std::false_type /* blocks not aligned */)const
0866   {
0867     block_type x;
0868     std::memcpy(&x,p,block_size);
0869     return subfilter::check(x,hash);
0870   }
0871
0872   BOOST_FORCEINLINE void set(unsigned char* p,std::uint64_t hash)
0873   {
0874     return set(p,hash,std::integral_constant<bool,are_blocks_aligned>{});
0875   }
0876
0877   BOOST_FORCEINLINE void set(
0878     unsigned char* p,std::uint64_t hash,
0879     std::true_type /* blocks aligned */)
0880   {
0881     subfilter::mark(*reinterpret_cast<block_type*>(p),hash);
0882   }
0883
0884   BOOST_FORCEINLINE void set(
0885     unsigned char* p,std::uint64_t hash,
0886     std::false_type /* blocks not aligned */)
0887   {
0888     block_type x;
0889     std::memcpy(&x,p,block_size);
0890     subfilter::mark(x,hash);
0891     std::memcpy(p,&x,block_size);
0892   }
0893
0894   BOOST_FORCEINLINE
0895   unsigned char* next_element(std::uint64_t& h)noexcept
0896   {
0897     auto p=ar.array+hs.next_position(h)*stride;
0898     for(std::size_t i=0;i<prefetched_cachelines;++i){
0899       BOOST_BLOOM_PREFETCH_WRITE((unsigned char*)p+i*cacheline);
0900     }
0901     return p;
0902   }
0903
0904   BOOST_FORCEINLINE
0905   const unsigned char* next_element(std::uint64_t& h)const noexcept
0906   {
0907     auto p=ar.array+hs.next_position(h)*stride;
0908     for(std::size_t i=0;i<prefetched_cachelines;++i){
0909       BOOST_BLOOM_PREFETCH((unsigned char*)p+i*cacheline);
0910     }
0911     return p;
0912   }
0913
0914   template<typename F>
0915   void combine(const filter_core& x,F f)
0916   {
0917     if(range()!=x.range()){
0918       BOOST_THROW_EXCEPTION(std::invalid_argument("incompatible filters"));
0919     }
0920     auto first0=ar.array,
0921          last0=first0+used_array_size(),
0922          first1=x.ar.array;
0923     while(first0!=last0)f(*first0++,*first1++);
0924   }
0925
0926   hash_strategy hs;
0927   filter_array  ar;
0928 };
0929
0930 #if defined(BOOST_MSVC)
0931 #pragma warning(pop) /* C4714 */
0932 #endif
0933
0934 } /* namespace detail */
0935 } /* namespace bloom */
0936 } /* namespace boost */
0937 #endif