detail/foa/node_handle.hpp

0001 /* Copyright 2023 Christian Mazakas.
0002  * Copyright 2024 Joaquin M Lopez Munoz.
0003  * Distributed under the Boost Software License, Version 1.0.
0004  * (See accompanying file LICENSE_1_0.txt or copy at
0005  * http://www.boost.org/LICENSE_1_0.txt)
0006  *
0007  * See https://www.boost.org/libs/unordered for library home page.
0008  */
0009
0010 #ifndef BOOST_UNORDERED_DETAIL_FOA_NODE_HANDLE_HPP
0011 #define BOOST_UNORDERED_DETAIL_FOA_NODE_HANDLE_HPP
0012
0013 #include <boost/unordered/detail/opt_storage.hpp>
0014
0015 #include <boost/assert.hpp>
0016 #include <boost/config.hpp>
0017 #include <boost/config/workaround.hpp>
0018 #include <boost/core/allocator_access.hpp>
0019 #include <type_traits>
0020
0021 namespace boost{
0022 namespace unordered{
0023 namespace detail{
0024 namespace foa{
0025
0026 template <class Iterator,class NodeType>
0027 struct insert_return_type
0028 {
0029   Iterator position;
0030   bool     inserted;
0031   NodeType node;
0032 };
0033
0034 template <class NodeType>
0035 struct iteratorless_insert_return_type
0036 {
0037   bool     inserted;
0038   NodeType node;
0039 };
0040
0041 template <class TypePolicy,class Allocator>
0042 struct node_handle_base
0043 {
0044   protected:
0045     using type_policy=TypePolicy;
0046     using element_type=typename type_policy::element_type;
0047
0048   public:
0049     using allocator_type = Allocator;
0050
0051   private:
0052     using node_value_type=typename type_policy::value_type;
0053     element_type p_;
0054     BOOST_ATTRIBUTE_NO_UNIQUE_ADDRESS opt_storage<Allocator> a_;
0055
0056     friend struct node_handle_access;
0057
0058     template<bool B>
0059     void move_assign_allocator_if(node_handle_base&& nh)noexcept
0060     {
0061       move_assign_allocator_if(
0062         std::integral_constant<bool,B>{}, std::move(nh));
0063     }
0064
0065     void move_assign_allocator_if(
0066       std::true_type, node_handle_base&& nh)noexcept
0067     {
0068       al()=std::move(nh.al());
0069     }
0070
0071     void move_assign_allocator_if(
0072       std::false_type, node_handle_base&&)noexcept
0073     {
0074     }
0075
0076 protected:
0077     node_value_type& data()noexcept
0078     {
0079       return *(p_.p);
0080     }
0081
0082     node_value_type const& data()const noexcept
0083     {
0084       return *(p_.p);
0085     }
0086
0087     element_type& element()noexcept
0088     {
0089       BOOST_ASSERT(!empty());
0090       return p_;
0091     }
0092
0093     element_type const& element()const noexcept
0094     {
0095       BOOST_ASSERT(!empty());
0096       return p_;
0097     }
0098
0099     Allocator& al()noexcept
0100     {
0101       BOOST_ASSERT(!empty());
0102       return a_.t_;
0103     }
0104
0105     Allocator const& al()const noexcept
0106     {
0107       BOOST_ASSERT(!empty());
0108       return a_.t_;
0109     }
0110
0111     void emplace(element_type&& x,Allocator a)
0112     {
0113       BOOST_ASSERT(empty());
0114       auto* p=x.p;
0115       p_.p=p;
0116       new(&a_.t_)Allocator(a);
0117       x.p=nullptr;
0118     }
0119
0120     void reset()
0121     {
0122       a_.t_.~Allocator();
0123       p_.p=nullptr;
0124     }
0125
0126   public:
0127     constexpr node_handle_base()noexcept:p_{nullptr}{}
0128
0129     node_handle_base(node_handle_base&& nh) noexcept
0130     {
0131       p_.p = nullptr;
0132       if (!nh.empty()){
0133         emplace(std::move(nh.p_),nh.al());
0134         nh.reset();
0135       }
0136     }
0137
0138     node_handle_base& operator=(node_handle_base&& nh)noexcept
0139     {
0140       if(this!=&nh){
0141         if(empty()){
0142           if(nh.empty()){                      /* empty(),  nh.empty() */
0143             /* nothing to do */
0144           }else{                               /* empty(), !nh.empty() */
0145             emplace(std::move(nh.p_),std::move(nh.al()));
0146             nh.reset();
0147           }
0148         }else{
0149           if(nh.empty()){                      /* !empty(),  nh.empty() */
0150             type_policy::destroy(al(),&p_);
0151             reset();
0152           }else{                               /* !empty(), !nh.empty() */
0153             bool const pocma=
0154               boost::allocator_propagate_on_container_move_assignment<
0155                 Allocator>::type::value;
0156
0157             BOOST_ASSERT(pocma||al()==nh.al());
0158
0159             type_policy::destroy(al(),&p_);
0160             move_assign_allocator_if<pocma>(std::move(nh));
0161
0162             p_=std::move(nh.p_);
0163             nh.reset();
0164           }
0165         }
0166       }else{
0167         if(empty()){                           /* empty(),  nh.empty() */
0168           /* nothing to do */
0169         }else{                                 /* !empty(), !nh.empty() */
0170           type_policy::destroy(al(),&p_);
0171           reset();
0172         }
0173       }
0174       return *this;
0175     }
0176
0177     ~node_handle_base()
0178     {
0179       if(!empty()){
0180         type_policy::destroy(al(),&p_);
0181         reset();
0182       }
0183     }
0184
0185     allocator_type get_allocator()const
0186     {
0187 #if defined(BOOST_GCC)
0188       /* GCC lifetime analysis incorrectly warns about uninitialized
0189        * allocator object under some circumstances.
0190        */
0191       if(empty())__builtin_unreachable();
0192 #endif
0193       return al();
0194     }
0195
0196     explicit operator bool()const noexcept{ return !empty();}
0197     BOOST_ATTRIBUTE_NODISCARD bool empty()const noexcept{return p_.p==nullptr;}
0198
0199     void swap(node_handle_base& nh) noexcept(
0200       boost::allocator_is_always_equal<Allocator>::type::value||
0201       boost::allocator_propagate_on_container_swap<Allocator>::type::value)
0202     {
0203       if(this!=&nh){
0204         if(empty()){
0205           if(nh.empty()) {
0206             /* nothing to do here */
0207           } else {
0208             emplace(std::move(nh.p_), nh.al());
0209             nh.reset();
0210           }
0211         }else{
0212           if(nh.empty()){
0213             nh.emplace(std::move(p_),al());
0214             reset();
0215           }else{
0216             bool const pocs=
0217               boost::allocator_propagate_on_container_swap<
0218                 Allocator>::type::value;
0219
0220             BOOST_ASSERT(pocs || al()==nh.al());
0221
0222             using std::swap;
0223             p_.swap(nh.p_);
0224             if(pocs)swap(al(),nh.al());
0225           }
0226         }
0227       }
0228     }
0229
0230     friend
0231     void swap(node_handle_base& lhs,node_handle_base& rhs)
0232       noexcept(noexcept(lhs.swap(rhs)))
0233     {
0234       return lhs.swap(rhs);
0235     }
0236 };
0237
0238 // Internal usage of node_handle_base protected API
0239
0240 struct node_handle_access
0241 {
0242   template <class TypePolicy, class Allocator>
0243   using node_type = node_handle_base<TypePolicy, Allocator>;
0244
0245 #if BOOST_WORKAROUND(BOOST_CLANG_VERSION,<190000)
0246   // https://github.com/llvm/llvm-project/issues/25708
0247
0248   template <class TypePolicy, class Allocator>
0249   struct element_type_impl
0250   {
0251     using type = typename node_type<TypePolicy, Allocator>::element_type;
0252   };
0253   template <class TypePolicy, class Allocator>
0254   using element_type = typename element_type_impl<TypePolicy, Allocator>::type;
0255 #else
0256   template <class TypePolicy, class Allocator>
0257   using element_type = typename node_type<TypePolicy, Allocator>::element_type;
0258 #endif
0259
0260   template <class TypePolicy, class Allocator>
0261   static element_type<TypePolicy, Allocator>&
0262   element(node_type<TypePolicy, Allocator>& nh)noexcept
0263   {
0264     return nh.element();
0265   }
0266
0267   template <class TypePolicy, class Allocator>
0268   static element_type<TypePolicy, Allocator>
0269   const& element(node_type<TypePolicy, Allocator> const& nh)noexcept
0270   {
0271     return nh.element();
0272   }
0273
0274   template <class TypePolicy, class Allocator>
0275   static void emplace(
0276     node_type<TypePolicy, Allocator>& nh,
0277     element_type<TypePolicy, Allocator>&& x, Allocator a)
0278   {
0279     nh.emplace(std::move(x), a);
0280   }
0281
0282   template <class TypePolicy,class Allocator>
0283   static void reset(node_type<TypePolicy, Allocator>& nh)
0284   {
0285     nh.reset();
0286   }
0287 };
0288
0289 template <class TypePolicy, class Allocator>
0290 class node_handle_emplacer_class
0291 {
0292   using access = node_handle_access;
0293   using node_type = access::node_type<TypePolicy, Allocator>;
0294   using element_type = access::element_type<TypePolicy, Allocator>;
0295
0296   node_type & nh;
0297
0298 public:
0299   node_handle_emplacer_class(node_type& nh_): nh(nh_) {}
0300
0301   void operator()(element_type&& x,Allocator a)
0302   {
0303     access::emplace(nh, std::move(x), a);
0304   }
0305 };
0306
0307 template <class TypePolicy, class Allocator>
0308 node_handle_emplacer_class<TypePolicy, Allocator>
0309 node_handle_emplacer(node_handle_base<TypePolicy, Allocator>& nh)
0310 {
0311   return {nh};
0312 }
0313
0314 }
0315 }
0316 }
0317 }
0318
0319 #endif // BOOST_UNORDERED_DETAIL_FOA_NODE_HANDLE_HPP