boost/bloom/filter.hpp

0001 /* Configurable Bloom filter.
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_FILTER_HPP
0012 #define BOOST_BLOOM_FILTER_HPP
0013
0014 #include <boost/bloom/block.hpp>
0015 #include <boost/bloom/detail/bloom_printers.hpp>
0016 #include <boost/bloom/detail/core.hpp>
0017 #include <boost/bloom/detail/mulx64.hpp>
0018 #include <boost/bloom/detail/type_traits.hpp>
0019 #include <boost/config.hpp>
0020 #include <boost/container_hash/hash.hpp>
0021 #include <boost/container_hash/hash_is_avalanching.hpp>
0022 #include <boost/core/allocator_traits.hpp>
0023 #include <boost/core/empty_value.hpp>
0024 #include <cstdint>
0025 #include <initializer_list>
0026 #include <iterator>
0027 #include <memory>
0028 #include <type_traits>
0029 #include <utility>
0030
0031 namespace boost{
0032 namespace bloom{
0033 namespace detail{
0034
0035 /* Mixing policies: no_mix_policy is the identity function, and
0036  * mulx64_mix_policy uses the mulx64 function from
0037  * <boost/bloom/detail/mulx64.hpp>.
0038  *
0039  * filter mixes hash results with mulx64 if the hash is not marked as
0040  * avalanching, i.e. it's not of good quality (see
0041  * <boost/unordered/hash_traits.hpp>), or if std::size_t is less than 64 bits
0042  * (mixing policies promote to std::uint64_t).
0043  */
0044
0045 struct no_mix_policy
0046 {
0047   template<typename Hash,typename T>
0048   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0049   static inline std::uint64_t mix(const Hash& h,const T& x)
0050   {
0051     return (std::uint64_t)h(x);
0052   }
0053 };
0054
0055 struct mulx64_mix_policy
0056 {
0057   template<typename Hash,typename T>
0058   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0059   static inline std::uint64_t mix(const Hash& h,const T& x)
0060   {
0061     return mulx64((std::uint64_t)h(x));
0062   }
0063 };
0064
0065 } /* namespace detail */
0066
0067 #if defined(BOOST_MSVC)
0068 #pragma warning(push)
0069 #pragma warning(disable:4714) /* marked as __forceinline not inlined */
0070 #endif
0071
0072 template<
0073   typename T,std::size_t K,
0074   typename Subfilter=block<unsigned char,1>,std::size_t Stride=0,
0075   typename Hash=boost::hash<T>,typename Allocator=std::allocator<unsigned char>
0076 >
0077 class
0078
0079 #if defined(_MSC_VER)&&_MSC_FULL_VER>=190023918
0080 __declspec(empty_bases) /* activate EBO with multiple inheritance */
0081 #endif
0082
0083 filter:
0084   detail::filter_core<
0085     K,Subfilter,Stride,allocator_rebind_t<Allocator,unsigned char>
0086   >,
0087   empty_value<Hash,0>
0088 {
0089   BOOST_BLOOM_STATIC_ASSERT_IS_CV_UNQUALIFIED_OBJECT(T);
0090   static_assert(
0091     std::is_same<unsigned char,allocator_value_type_t<Allocator>>::value,
0092     "Allocator's value_type must be unsigned char");
0093   using super=detail::filter_core<K,Subfilter,Stride,Allocator>;
0094   using mix_policy=typename std::conditional<
0095     boost::hash_is_avalanching<Hash>::value&&
0096     sizeof(std::size_t)>=sizeof(std::uint64_t),
0097     detail::no_mix_policy,
0098     detail::mulx64_mix_policy
0099   >::type;
0100
0101 public:
0102   using value_type=T;
0103   using super::k;
0104   using subfilter=typename super::subfilter;
0105   using super::stride;
0106   using hasher=Hash;
0107   using allocator_type=Allocator;
0108   using size_type=typename super::size_type;
0109   using difference_type=typename super::difference_type;
0110   using reference=value_type&;
0111   using const_reference=const value_type&;
0112   using pointer=value_type*;
0113   using const_pointer=const value_type*;
0114   static constexpr std::size_t bulk_insert_size=super::bulk_insert_size;
0115   static constexpr std::size_t bulk_may_contain_size=
0116     super::bulk_may_contain_size;
0117
0118   filter()=default;
0119
0120   explicit filter(
0121     std::size_t m,const hasher& h=hasher(),
0122     const allocator_type& al=allocator_type()):
0123     super{m,al},hash_base{empty_init,h}{}
0124
0125   filter(
0126     std::size_t n,double fpr,const hasher& h=hasher(),
0127     const allocator_type& al=allocator_type()):
0128     super{n,fpr,al},hash_base{empty_init,h}{}
0129
0130   template<typename InputIterator>
0131   filter(
0132     InputIterator first,InputIterator last,
0133     std::size_t m,const hasher& h=hasher(),
0134     const allocator_type& al=allocator_type()):
0135     filter{m,h,al}
0136   {
0137     insert(first,last);
0138   }
0139
0140   template<typename InputIterator>
0141   filter(
0142     InputIterator first,InputIterator last,
0143     std::size_t n,double fpr,const hasher& h=hasher(),
0144     const allocator_type& al=allocator_type()):
0145     filter{n,fpr,h,al}
0146   {
0147     insert(first,last);
0148   }
0149
0150   filter(const filter&)=default;
0151   filter(filter&&)=default;
0152
0153   template<typename InputIterator>
0154   filter(
0155     InputIterator first,InputIterator last,
0156     std::size_t m,const allocator_type& al):
0157     filter{first,last,m,hasher(),al}{}
0158
0159   template<typename InputIterator>
0160   filter(
0161     InputIterator first,InputIterator last,
0162     std::size_t n,double fpr,const allocator_type& al):
0163     filter{first,last,n,fpr,hasher(),al}{}
0164
0165   explicit filter(const allocator_type& al):filter{0,al}{}
0166
0167   filter(const filter& x,const allocator_type& al):
0168     super{x,al},hash_base{empty_init,x.h()}{}
0169
0170   filter(filter&& x,const allocator_type& al):
0171     super{std::move(x),al},hash_base{empty_init,std::move(x.h())}{}
0172
0173   filter(
0174     std::initializer_list<value_type> il,
0175     std::size_t m,const hasher& h=hasher(),
0176     const allocator_type& al=allocator_type()):
0177     filter{il.begin(),il.end(),m,h,al}{}
0178
0179   filter(
0180     std::initializer_list<value_type> il,
0181     std::size_t n,double fpr,const hasher& h=hasher(),
0182     const allocator_type& al=allocator_type()):
0183     filter{il.begin(),il.end(),n,fpr,h,al}{}
0184
0185   filter(std::size_t m,const allocator_type& al):
0186     filter{m,hasher(),al}{}
0187
0188   filter(std::size_t n,double fpr,const allocator_type& al):
0189     filter{n,fpr,hasher(),al}{}
0190
0191   filter(
0192     std::initializer_list<value_type> il,
0193     std::size_t m,const allocator_type& al):
0194     filter{il.begin(),il.end(),m,hasher(),al}{}
0195
0196   filter(
0197     std::initializer_list<value_type> il,
0198     std::size_t n,double fpr,const allocator_type& al):
0199     filter{il.begin(),il.end(),n,fpr,hasher(),al}{}
0200
0201   filter& operator=(const filter& x)
0202   {
0203     BOOST_BLOOM_STATIC_ASSERT_IS_NOTHROW_SWAPPABLE(Hash);
0204     using std::swap;
0205
0206     auto x_h=x.h();
0207     super::operator=(x);
0208     swap(h(),x_h);
0209     return *this;
0210   }
0211
0212   filter& operator=(filter&& x)
0213     noexcept(noexcept(std::declval<super&>()=(std::declval<super&&>())))
0214   {
0215     BOOST_BLOOM_STATIC_ASSERT_IS_NOTHROW_SWAPPABLE(Hash);
0216     using std::swap;
0217
0218     super::operator=(std::move(x));
0219     swap(h(),x.h());
0220     return *this;
0221   }
0222
0223   filter& operator=(std::initializer_list<value_type> il)
0224   {
0225     clear();
0226     insert(il);
0227     return *this;
0228   }
0229
0230   using super::get_allocator;
0231   using super::capacity;
0232   using super::capacity_for;
0233   using super::fpr_for;
0234   using super::array;
0235
0236   BOOST_FORCEINLINE void insert(const T& x)
0237   {
0238     super::insert(hash_for(x));
0239   }
0240
0241   template<
0242     typename U,
0243     typename H=hasher,detail::enable_if_transparent_t<H>* =nullptr
0244   >
0245   BOOST_FORCEINLINE void insert(const U& x)
0246   {
0247     super::insert(hash_for(x));
0248   }
0249
0250   template<typename InputIterator>
0251   void insert(InputIterator first,InputIterator last)
0252   {
0253     insert_impl(
0254       first,last,
0255       std::integral_constant<
0256         bool,detail::is_forward_iterator<InputIterator>::value>{});
0257   }
0258
0259   void insert(std::initializer_list<value_type> il)
0260   {
0261     insert(il.begin(),il.end());
0262   }
0263
0264   void swap(filter& x)
0265     noexcept(noexcept(std::declval<super&>().swap(std::declval<super&>())))
0266   {
0267     BOOST_BLOOM_STATIC_ASSERT_IS_NOTHROW_SWAPPABLE(Hash);
0268     using std::swap;
0269
0270     super::swap(x);
0271     swap(h(),x.h());
0272   }
0273
0274   using super::clear;
0275   using super::reset;
0276
0277   filter& operator&=(const filter& x)
0278   {
0279     super::operator&=(x);
0280     return *this;
0281   }
0282
0283   filter& operator|=(const filter& x)
0284   {
0285     super::operator|=(x);
0286     return *this;
0287   }
0288
0289   hasher hash_function()const
0290   {
0291     return h();
0292   }
0293
0294   BOOST_FORCEINLINE bool may_contain(const T& x)const
0295   {
0296     return super::may_contain(hash_for(x));
0297   }
0298
0299   template<
0300     typename U,
0301     typename H=hasher,detail::enable_if_transparent_t<H>* =nullptr
0302   >
0303   BOOST_FORCEINLINE bool may_contain(const U& x)const
0304   {
0305     return super::may_contain(hash_for(x));
0306   }
0307
0308   template<typename ForwardIterator,typename F>
0309   void may_contain(
0310     ForwardIterator first,ForwardIterator last,F f)const
0311   {
0312     BOOST_BLOOM_STATIC_ASSERT_IS_FORWARD_ITERATOR(ForwardIterator);
0313
0314     super::bulk_may_contain(
0315       [this,first]()mutable{return promoting_hash_for(*first++);},
0316       static_cast<std::size_t>(std::distance(first,last)),
0317       [&f,first](bool res)mutable{f(*first++,res);});
0318   }
0319
0320 private:
0321   template<
0322     typename T1,std::size_t K1,typename SF,std::size_t S,typename H,typename A
0323   >
0324   bool friend operator==(
0325     const filter<T1,K1,SF,S,H,A>& x,const filter<T1,K1,SF,S,H,A>& y);
0326
0327   using hash_base=empty_value<Hash,0>;
0328
0329   const Hash& h()const{return hash_base::get();}
0330   Hash& h(){return hash_base::get();}
0331
0332   template<typename U>
0333   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0334   inline std::uint64_t hash_for(const U& x)const
0335   {
0336     return mix_policy::mix(h(),x);
0337   }
0338
0339   /* promoting_hash_for forces conversion to value_type unless Hash
0340    * is transparent.
0341    */
0342
0343   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0344   inline std::uint64_t promoting_hash_for(const T& x)const
0345   {
0346     return hash_for(x);
0347   }
0348
0349   template<
0350     typename U,
0351     typename H=hasher,detail::enable_if_transparent_t<H>* =nullptr
0352   >
0353   /* NOLINTNEXTLINE(readability-redundant-inline-specifier) */
0354   inline std::uint64_t promoting_hash_for(const U& x)const
0355   {
0356     return hash_for(x);
0357   }
0358
0359   template<typename Iterator>
0360   void insert_impl(
0361     Iterator first,Iterator last,std::false_type /* input iterator */)
0362   {
0363     while(first!=last)insert(*first++);
0364   }
0365
0366   template<typename Iterator>
0367   void insert_impl(
0368     Iterator first,Iterator last,std::true_type /* forward iterator */)
0369   {
0370     super::bulk_insert(
0371       [this,first]()mutable{return promoting_hash_for(*first++);},
0372       static_cast<std::size_t>(std::distance(first,last)));
0373   }
0374 };
0375
0376 template<
0377   typename T,std::size_t K,typename SF,std::size_t S,typename H,typename A
0378 >
0379 bool operator==(const filter<T,K,SF,S,H,A>& x,const filter<T,K,SF,S,H,A>& y)
0380 {
0381   using super=typename filter<T,K,SF,S,H,A>::super;
0382   return static_cast<const super&>(x)==static_cast<const super&>(y);
0383 }
0384
0385 template<
0386   typename T,std::size_t K,typename SF,std::size_t S,typename H,typename A
0387 >
0388 bool operator!=(const filter<T,K,SF,S,H,A>& x,const filter<T,K,SF,S,H,A>& y)
0389 {
0390   return !(x==y);
0391 }
0392
0393 template<
0394   typename T,std::size_t K,typename SF,std::size_t S,typename H,typename A
0395 >
0396 void swap(filter<T,K,SF,S,H,A>& x,filter<T,K,SF,S,H,A>& y)
0397   noexcept(noexcept(x.swap(y)))
0398 {
0399   x.swap(y);
0400 }
0401
0402 #if defined(BOOST_MSVC)
0403 #pragma warning(pop) /* C4714 */
0404 #endif
0405
0406 } /* namespace bloom */
0407 } /* namespace boost */
0408 #endif