detail/foa/table.hpp

0001 /* Fast open-addressing hash table.
0002  *
0003  * Copyright 2022-2023 Joaquin M Lopez Munoz.
0004  * Copyright 2023 Christian Mazakas.
0005  * Distributed under the Boost Software License, Version 1.0.
0006  * (See accompanying file LICENSE_1_0.txt or copy at
0007  * http://www.boost.org/LICENSE_1_0.txt)
0008  *
0009  * See https://www.boost.org/libs/unordered for library home page.
0010  */
0011
0012 #ifndef BOOST_UNORDERED_DETAIL_FOA_TABLE_HPP
0013 #define BOOST_UNORDERED_DETAIL_FOA_TABLE_HPP
0014
0015 #include <boost/assert.hpp>
0016 #include <boost/config.hpp>
0017 #include <boost/config/workaround.hpp>
0018 #include <boost/core/serialization.hpp>
0019 #include <boost/unordered/detail/foa/core.hpp>
0020 #include <boost/unordered/detail/serialize_tracked_address.hpp>
0021 #include <cstddef>
0022 #include <iterator>
0023 #include <memory>
0024 #include <type_traits>
0025 #include <utility>
0026
0027 namespace boost{
0028 namespace unordered{
0029 namespace detail{
0030 namespace foa{
0031
0032 /* use plain integrals for group metadata storage */
0033
0034 template<typename Integral>
0035 struct plain_integral
0036 {
0037   operator Integral()const{return n;}
0038   void operator=(Integral m){n=m;}
0039
0040 #if BOOST_WORKAROUND(BOOST_GCC,>=50000 && BOOST_GCC<60000)
0041   void operator|=(Integral m){n=static_cast<Integral>(n|m);}
0042   void operator&=(Integral m){n=static_cast<Integral>(n&m);}
0043 #else
0044   void operator|=(Integral m){n|=m;}
0045   void operator&=(Integral m){n&=m;}
0046 #endif
0047
0048   Integral n;
0049 };
0050
0051 struct plain_size_control
0052 {
0053   std::size_t ml;
0054   std::size_t size;
0055 };
0056
0057 template<typename,typename,typename,typename>
0058 class table;
0059
0060 /* table_iterator keeps two pointers:
0061  *
0062  *   - A pointer p to the element slot.
0063  *   - A pointer pc to the n-th byte of the associated group metadata, where n
0064  *     is the position of the element in the group.
0065  *
0066  * A simpler solution would have been to keep a pointer p to the element, a
0067  * pointer pg to the group, and the position n, but that would increase
0068  * sizeof(table_iterator) by 4/8 bytes. In order to make this compact
0069  * representation feasible, it is required that group objects are aligned
0070  * to their size, so that we can recover pg and n as
0071  *
0072  *   - n = pc%sizeof(group)
0073  *   - pg = pc-n
0074  *
0075  * (for explanatory purposes pg and pc are treated above as if they were memory
0076  * addresses rather than pointers).
0077  *
0078  * p = nullptr is conventionally used to mark end() iterators.
0079  */
0080
0081 /* internal conversion from const_iterator to iterator */
0082 struct const_iterator_cast_tag{};
0083
0084 template<typename TypePolicy,typename GroupPtr,bool Const>
0085 class table_iterator
0086 {
0087   using group_pointer_traits=boost::pointer_traits<GroupPtr>;
0088   using type_policy=TypePolicy;
0089   using table_element_type=typename type_policy::element_type;
0090   using group_type=typename group_pointer_traits::element_type;
0091   using table_element_pointer=
0092     typename group_pointer_traits::template rebind<table_element_type>;
0093   using char_pointer=
0094     typename group_pointer_traits::template rebind<unsigned char>;
0095   static constexpr auto N=group_type::N;
0096   static constexpr auto regular_layout=group_type::regular_layout;
0097
0098 public:
0099   using difference_type=std::ptrdiff_t;
0100   using value_type=typename type_policy::value_type;
0101   using pointer=
0102     typename std::conditional<Const,value_type const*,value_type*>::type;
0103   using reference=
0104     typename std::conditional<Const,value_type const&,value_type&>::type;
0105   using iterator_category=std::forward_iterator_tag;
0106   using element_type=
0107     typename std::conditional<Const,value_type const,value_type>::type;
0108
0109   table_iterator():pc_{nullptr},p_{nullptr}{};
0110   template<bool Const2,typename std::enable_if<!Const2>::type* =nullptr>
0111   table_iterator(const table_iterator<TypePolicy,GroupPtr,Const2>& x):
0112     pc_{x.pc_},p_{x.p_}{}
0113   table_iterator(
0114     const_iterator_cast_tag, const table_iterator<TypePolicy,GroupPtr,true>& x):
0115     pc_{x.pc_},p_{x.p_}{}
0116
0117   inline reference operator*()const noexcept
0118     {return type_policy::value_from(*p());}
0119   inline pointer operator->()const noexcept
0120     {return std::addressof(type_policy::value_from(*p()));}
0121   inline table_iterator& operator++()noexcept{increment();return *this;}
0122   inline table_iterator operator++(int)noexcept
0123     {auto x=*this;increment();return x;}
0124   friend inline bool operator==(
0125     const table_iterator& x,const table_iterator& y)
0126     {return x.p()==y.p();}
0127   friend inline bool operator!=(
0128     const table_iterator& x,const table_iterator& y)
0129     {return !(x==y);}
0130
0131 private:
0132   template<typename,typename,bool> friend class table_iterator;
0133   template<typename> friend class table_erase_return_type;
0134   template<typename,typename,typename,typename> friend class table;
0135
0136   table_iterator(group_type* pg,std::size_t n,const table_element_type* ptet):
0137     pc_{to_pointer<char_pointer>(
0138       reinterpret_cast<unsigned char*>(const_cast<group_type*>(pg))+n)},
0139     p_{to_pointer<table_element_pointer>(const_cast<table_element_type*>(ptet))}
0140   {}
0141
0142   unsigned char* pc()const noexcept{return boost::to_address(pc_);}
0143   table_element_type* p()const noexcept{return boost::to_address(p_);}
0144
0145   inline void increment()noexcept
0146   {
0147     BOOST_ASSERT(p()!=nullptr);
0148     increment(std::integral_constant<bool,regular_layout>{});
0149   }
0150
0151   inline void increment(std::true_type /* regular layout */)noexcept
0152   {
0153     using diff_type=
0154       typename boost::pointer_traits<char_pointer>::difference_type;
0155
0156     for(;;){
0157       ++p_;
0158       if(reinterpret_cast<uintptr_t>(pc())%sizeof(group_type)==N-1){
0159         pc_+=static_cast<diff_type>(sizeof(group_type)-(N-1));
0160         break;
0161       }
0162       ++pc_;
0163       if(!group_type::is_occupied(pc()))continue;
0164       if(BOOST_UNLIKELY(group_type::is_sentinel(pc())))p_=nullptr;
0165       return;
0166     }
0167
0168     for(;;){
0169       int mask=reinterpret_cast<group_type*>(pc())->match_occupied();
0170       if(mask!=0){
0171         auto n=unchecked_countr_zero(mask);
0172         if(BOOST_UNLIKELY(reinterpret_cast<group_type*>(pc())->is_sentinel(n))){
0173           p_=nullptr;
0174         }
0175         else{
0176           pc_+=static_cast<diff_type>(n);
0177           p_+=static_cast<diff_type>(n);
0178         }
0179         return;
0180       }
0181       pc_+=static_cast<diff_type>(sizeof(group_type));
0182       p_+=static_cast<diff_type>(N);
0183     }
0184   }
0185
0186   inline void increment(std::false_type /* interleaved */)noexcept
0187   {
0188     using diff_type=
0189       typename boost::pointer_traits<char_pointer>::difference_type;
0190
0191     std::size_t n0=reinterpret_cast<uintptr_t>(pc())%sizeof(group_type);
0192     pc_-=static_cast<diff_type>(n0);
0193
0194     int mask=(
0195       reinterpret_cast<group_type*>(pc())->match_occupied()>>(n0+1))<<(n0+1);
0196     if(!mask){
0197       do{
0198         pc_+=sizeof(group_type);
0199         p_+=N;
0200       }
0201       while((mask=reinterpret_cast<group_type*>(pc())->match_occupied())==0);
0202     }
0203
0204     auto n=unchecked_countr_zero(mask);
0205     if(BOOST_UNLIKELY(reinterpret_cast<group_type*>(pc())->is_sentinel(n))){
0206       p_=nullptr;
0207     }
0208     else{
0209       pc_+=static_cast<diff_type>(n);
0210       p_-=static_cast<diff_type>(n0);
0211       p_+=static_cast<diff_type>(n);
0212     }
0213   }
0214
0215   template<typename Archive>
0216   friend void serialization_track(Archive& ar,const table_iterator& x)
0217   {
0218     if(x.p()){
0219       track_address(ar,x.pc_);
0220       track_address(ar,x.p_);
0221     }
0222   }
0223
0224   friend class boost::serialization::access;
0225
0226   template<typename Archive>
0227   void serialize(Archive& ar,unsigned int)
0228   {
0229     if(!p())pc_=nullptr;
0230     serialize_tracked_address(ar,pc_);
0231     serialize_tracked_address(ar,p_);
0232   }
0233
0234   char_pointer          pc_=nullptr;
0235   table_element_pointer  p_=nullptr;
0236 };
0237
0238 /* Returned by table::erase([const_]iterator) to avoid iterator increment
0239  * if discarded.
0240  */
0241
0242 template<typename Iterator>
0243 class table_erase_return_type;
0244
0245 template<typename TypePolicy,typename GroupPtr,bool Const>
0246 class table_erase_return_type<table_iterator<TypePolicy,GroupPtr,Const>>
0247 {
0248   using iterator=table_iterator<TypePolicy,GroupPtr,Const>;
0249   using const_iterator=table_iterator<TypePolicy,GroupPtr,true>;
0250
0251 public:
0252   /* can't delete it because VS in pre-C++17 mode needs to see it for RVO */
0253   table_erase_return_type(const table_erase_return_type&);
0254
0255   operator iterator()const noexcept
0256   {
0257     auto it=pos;
0258     it.increment(); /* valid even if *it was erased */
0259     return iterator(const_iterator_cast_tag{},it);
0260   }
0261
0262   template<
0263     bool dependent_value=false,
0264     typename std::enable_if<!Const||dependent_value>::type* =nullptr
0265   >
0266   operator const_iterator()const noexcept{return this->operator iterator();}
0267
0268 private:
0269   template<typename,typename,typename,typename> friend class table;
0270
0271   table_erase_return_type(const_iterator pos_):pos{pos_}{}
0272   table_erase_return_type& operator=(const table_erase_return_type&)=delete;
0273
0274   const_iterator pos;
0275 };
0276
0277 /* foa::table interface departs in a number of ways from that of C++ unordered
0278  * associative containers because it's not for end-user consumption
0279  * (boost::unordered_(flat|node)_(map|set) wrappers complete it as
0280  * appropriate).
0281  *
0282  * The table supports two main modes of operation: flat and node-based. In the
0283  * flat case, buckets directly store elements. For node-based, buckets store
0284  * pointers to individually heap-allocated elements.
0285  *
0286  * For both flat and node-based:
0287  *
0288  *   - begin() is not O(1).
0289  *   - No bucket API.
0290  *   - Load factor is fixed and can't be set by the user.
0291  *
0292  * For flat only:
0293  *
0294  *   - value_type must be moveable.
0295  *   - Pointer stability is not kept under rehashing.
0296  *   - No extract API.
0297  *
0298  * try_emplace, erase and find support heterogeneous lookup by default,
0299  * that is, without checking for any ::is_transparent typedefs --the
0300  * checking is done by boost::unordered_(flat|node)_(map|set).
0301  */
0302
0303 template<typename,typename,typename,typename>
0304 class concurrent_table; /* concurrent/non-concurrent interop */
0305
0306 template <typename TypePolicy,typename Hash,typename Pred,typename Allocator>
0307 using table_core_impl=
0308   table_core<TypePolicy,group15<plain_integral>,table_arrays,
0309   plain_size_control,Hash,Pred,Allocator>;
0310
0311 #include <boost/unordered/detail/foa/ignore_wshadow.hpp>
0312
0313 #if defined(BOOST_MSVC)
0314 #pragma warning(push)
0315 #pragma warning(disable:4714) /* marked as __forceinline not inlined */
0316 #endif
0317
0318 template<typename TypePolicy,typename Hash,typename Pred,typename Allocator>
0319 class table:table_core_impl<TypePolicy,Hash,Pred,Allocator>
0320 {
0321   using super=table_core_impl<TypePolicy,Hash,Pred,Allocator>;
0322   using type_policy=typename super::type_policy;
0323   using group_type=typename super::group_type;
0324   using super::N;
0325   using prober=typename super::prober;
0326   using arrays_type=typename super::arrays_type;
0327   using size_ctrl_type=typename super::size_ctrl_type;
0328   using locator=typename super::locator;
0329   using compatible_concurrent_table=
0330     concurrent_table<TypePolicy,Hash,Pred,Allocator>;
0331   using group_type_pointer=typename boost::pointer_traits<
0332     typename boost::allocator_pointer<Allocator>::type
0333   >::template rebind<group_type>;
0334   friend compatible_concurrent_table;
0335
0336 public:
0337   using key_type=typename super::key_type;
0338   using init_type=typename super::init_type;
0339   using value_type=typename super::value_type;
0340   using element_type=typename super::element_type;
0341
0342 private:
0343   static constexpr bool has_mutable_iterator=
0344     !std::is_same<key_type,value_type>::value;
0345 public:
0346   using hasher=typename super::hasher;
0347   using key_equal=typename super::key_equal;
0348   using allocator_type=typename super::allocator_type;
0349   using pointer=typename super::pointer;
0350   using const_pointer=typename super::const_pointer;
0351   using reference=typename super::reference;
0352   using const_reference=typename super::const_reference;
0353   using size_type=typename super::size_type;
0354   using difference_type=typename super::difference_type;
0355   using const_iterator=table_iterator<type_policy,group_type_pointer,true>;
0356   using iterator=typename std::conditional<
0357     has_mutable_iterator,
0358     table_iterator<type_policy,group_type_pointer,false>,
0359     const_iterator>::type;
0360   using erase_return_type=table_erase_return_type<iterator>;
0361
0362   table(
0363     std::size_t n=default_bucket_count,const Hash& h_=Hash(),
0364     const Pred& pred_=Pred(),const Allocator& al_=Allocator()):
0365     super{n,h_,pred_,al_}
0366     {}
0367
0368   table(const table& x)=default;
0369   table(table&& x)=default;
0370   table(const table& x,const Allocator& al_):super{x,al_}{}
0371   table(table&& x,const Allocator& al_):super{std::move(x),al_}{}
0372   table(compatible_concurrent_table&& x):
0373     table(std::move(x),x.exclusive_access()){}
0374   ~table()=default;
0375
0376   table& operator=(const table& x)=default;
0377   table& operator=(table&& x)=default;
0378
0379   using super::get_allocator;
0380
0381   iterator begin()noexcept
0382   {
0383     iterator it{this->arrays.groups(),0,this->arrays.elements()};
0384     if(this->arrays.elements()&&
0385        !(this->arrays.groups()[0].match_occupied()&0x1))++it;
0386     return it;
0387   }
0388
0389   const_iterator begin()const noexcept
0390                    {return const_cast<table*>(this)->begin();}
0391   iterator       end()noexcept{return {};}
0392   const_iterator end()const noexcept{return const_cast<table*>(this)->end();}
0393   const_iterator cbegin()const noexcept{return begin();}
0394   const_iterator cend()const noexcept{return end();}
0395
0396   using super::empty;
0397   using super::size;
0398   using super::max_size;
0399
0400   template<typename... Args>
0401   BOOST_FORCEINLINE std::pair<iterator,bool> emplace(Args&&... args)
0402   {
0403     auto x=alloc_make_insert_type<type_policy>(
0404       this->al(),std::forward<Args>(args)...);
0405     return emplace_impl(type_policy::move(x.value()));
0406   }
0407
0408   template<typename Key,typename... Args>
0409   BOOST_FORCEINLINE std::pair<iterator,bool> try_emplace(
0410     Key&& x,Args&&... args)
0411   {
0412     return emplace_impl(
0413       try_emplace_args_t{},std::forward<Key>(x),std::forward<Args>(args)...);
0414   }
0415
0416   BOOST_FORCEINLINE std::pair<iterator,bool>
0417   insert(const init_type& x){return emplace_impl(x);}
0418
0419   BOOST_FORCEINLINE std::pair<iterator,bool>
0420   insert(init_type&& x){return emplace_impl(std::move(x));}
0421
0422   /* template<typename=void> tilts call ambiguities in favor of init_type */
0423
0424   template<typename=void>
0425   BOOST_FORCEINLINE std::pair<iterator,bool>
0426   insert(const value_type& x){return emplace_impl(x);}
0427
0428   template<typename=void>
0429   BOOST_FORCEINLINE std::pair<iterator,bool>
0430   insert(value_type&& x){return emplace_impl(std::move(x));}
0431
0432   template<typename T=element_type>
0433   BOOST_FORCEINLINE
0434   typename std::enable_if<
0435     !std::is_same<T,value_type>::value,
0436     std::pair<iterator,bool>
0437   >::type
0438   insert(element_type&& x){return emplace_impl(std::move(x));}
0439
0440   template<
0441     bool dependent_value=false,
0442     typename std::enable_if<
0443       has_mutable_iterator||dependent_value>::type* =nullptr
0444   >
0445   erase_return_type erase(iterator pos)noexcept
0446   {return erase(const_iterator(pos));}
0447
0448   BOOST_FORCEINLINE
0449   erase_return_type erase(const_iterator pos)noexcept
0450   {
0451     super::erase(pos.pc(),pos.p());
0452     return {pos};
0453   }
0454
0455   template<typename Key>
0456   BOOST_FORCEINLINE
0457   auto erase(Key&& x) -> typename std::enable_if<
0458     !std::is_convertible<Key,iterator>::value&&
0459     !std::is_convertible<Key,const_iterator>::value, std::size_t>::type
0460   {
0461     auto it=find(x);
0462     if(it!=end()){
0463       erase(it);
0464       return 1;
0465     }
0466     else return 0;
0467   }
0468
0469   void swap(table& x)
0470     noexcept(noexcept(std::declval<super&>().swap(std::declval<super&>())))
0471   {
0472     super::swap(x);
0473   }
0474
0475   using super::clear;
0476
0477   element_type extract(const_iterator pos)
0478   {
0479     BOOST_ASSERT(pos!=end());
0480     erase_on_exit e{*this,pos};
0481     (void)e;
0482     return std::move(*pos.p());
0483   }
0484
0485   // TODO: should we accept different allocator too?
0486   template<typename Hash2,typename Pred2>
0487   void merge(table<TypePolicy,Hash2,Pred2,Allocator>& x)
0488   {
0489     x.for_all_elements([&,this](group_type* pg,unsigned int n,element_type* p){
0490       erase_on_exit e{x,{pg,n,p}};
0491       if(!emplace_impl(type_policy::move(*p)).second)e.rollback();
0492     });
0493   }
0494
0495   template<typename Hash2,typename Pred2>
0496   void merge(table<TypePolicy,Hash2,Pred2,Allocator>&& x){merge(x);}
0497
0498   using super::hash_function;
0499   using super::key_eq;
0500
0501   template<typename Key>
0502   BOOST_FORCEINLINE iterator find(const Key& x)
0503   {
0504     return make_iterator(super::find(x));
0505   }
0506
0507   template<typename Key>
0508   BOOST_FORCEINLINE const_iterator find(const Key& x)const
0509   {
0510     return const_cast<table*>(this)->find(x);
0511   }
0512
0513   using super::capacity;
0514   using super::load_factor;
0515   using super::max_load_factor;
0516   using super::max_load;
0517   using super::rehash;
0518   using super::reserve;
0519
0520   template<typename Predicate>
0521   friend std::size_t erase_if(table& x,Predicate& pr)
0522   {
0523     using value_reference=typename std::conditional<
0524       std::is_same<key_type,value_type>::value,
0525       const_reference,
0526       reference
0527     >::type;
0528
0529     std::size_t s=x.size();
0530     x.for_all_elements(
0531       [&](group_type* pg,unsigned int n,element_type* p){
0532         if(pr(const_cast<value_reference>(type_policy::value_from(*p)))){
0533           x.super::erase(pg,n,p);
0534         }
0535       });
0536     return std::size_t(s-x.size());
0537   }
0538
0539   friend bool operator==(const table& x,const table& y)
0540   {
0541     return static_cast<const super&>(x)==static_cast<const super&>(y);
0542   }
0543
0544   friend bool operator!=(const table& x,const table& y){return !(x==y);}
0545
0546 private:
0547   template<typename ArraysType>
0548   table(compatible_concurrent_table&& x,arrays_holder<ArraysType,Allocator>&& ah):
0549     super{
0550       std::move(x.h()),std::move(x.pred()),std::move(x.al()),
0551       [&x]{return arrays_type{
0552         x.arrays.groups_size_index,x.arrays.groups_size_mask,
0553         to_pointer<group_type_pointer>(
0554           reinterpret_cast<group_type*>(x.arrays.groups())),
0555         x.arrays.elements_};},
0556       size_ctrl_type{x.size_ctrl.ml,x.size_ctrl.size}}
0557   {
0558     compatible_concurrent_table::arrays_type::delete_group_access(x.al(),x.arrays);
0559     x.arrays=ah.release();
0560     x.size_ctrl.ml=x.initial_max_load();
0561     x.size_ctrl.size=0;
0562   }
0563
0564   template<typename ExclusiveLockGuard>
0565   table(compatible_concurrent_table&& x,ExclusiveLockGuard):
0566     table(std::move(x),x.make_empty_arrays())
0567   {}
0568
0569   struct erase_on_exit
0570   {
0571     erase_on_exit(table& x_,const_iterator it_):x(x_),it(it_){}
0572     ~erase_on_exit(){if(!rollback_)x.erase(it);}
0573
0574     void rollback(){rollback_=true;}
0575
0576     table&         x;
0577     const_iterator it;
0578     bool           rollback_=false;
0579   };
0580
0581   static inline iterator make_iterator(const locator& l)noexcept
0582   {
0583     return {l.pg,l.n,l.p};
0584   }
0585
0586   template<typename... Args>
0587   BOOST_FORCEINLINE std::pair<iterator,bool> emplace_impl(Args&&... args)
0588   {
0589     const auto &k=this->key_from(std::forward<Args>(args)...);
0590     auto        hash=this->hash_for(k);
0591     auto        pos0=this->position_for(hash);
0592     auto        loc=super::find(k,pos0,hash);
0593
0594     if(loc){
0595       return {make_iterator(loc),false};
0596     }
0597     if(BOOST_LIKELY(this->size_ctrl.size<this->size_ctrl.ml)){
0598       return {
0599         make_iterator(
0600           this->unchecked_emplace_at(pos0,hash,std::forward<Args>(args)...)),
0601         true
0602       };
0603     }
0604     else{
0605       return {
0606         make_iterator(
0607           this->unchecked_emplace_with_rehash(
0608             hash,std::forward<Args>(args)...)),
0609         true
0610       };
0611     }
0612   }
0613 };
0614
0615 #if defined(BOOST_MSVC)
0616 #pragma warning(pop) /* C4714 */
0617 #endif
0618
0619 #include <boost/unordered/detail/foa/restore_wshadow.hpp>
0620
0621 } /* namespace foa */
0622 } /* namespace detail */
0623 } /* namespace unordered */
0624 } /* namespace boost */
0625
0626 #endif