ceph/src/boost/boost/multi_index/detail/copy_map.hpp

   1 /* Copyright 2003-2018 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/core/addressof.hpp>
  19 #include <boost/detail/no_exceptions_support.hpp>
  20 #include <boost/multi_index/detail/auto_space.hpp>
  21 #include <boost/multi_index/detail/raw_ptr.hpp>
  22 #include <boost/noncopyable.hpp>
  23 #include <cstddef>
  24 #include <functional>
  25 #include <memory>
  26
  27 namespace boost{
  28
  29 namespace multi_index{
  30
  31 namespace detail{
  32
  33 /* copy_map is used as an auxiliary structure during copy_() operations.
  34  * When a container with n nodes is replicated, node_map holds the pairings
  35  * between original and copied nodes, and provides a fast way to find a
  36  * copied node from an original one.
  37  * The semantics of the class are not simple, and no attempt has been made
  38  * to enforce it: multi_index_container handles it right. On the other hand,
  39  * the const interface, which is the one provided to index implementations,
  40  * only allows for:
  41  *   - Enumeration of pairs of (original,copied) nodes (excluding the headers),
  42  *   - fast retrieval of copied nodes (including the headers.)
  43  */
  44
  45 template <typename Node>
  46 struct copy_map_entry
  47 {
  48   copy_map_entry(Node* f,Node* s):first(f),second(s){}
  49
  50   Node* first;
  51   Node* second;
  52
  53   bool operator<(const copy_map_entry<Node>& x)const
  54   {
  55     return std::less<Node*>()(first,x.first);
  56   }
  57 };
  58
  59 template <typename Node,typename Allocator>
  60 class copy_map:private noncopyable
  61 {
  62 public:
  63   typedef const copy_map_entry<Node>* const_iterator;
  64
  65   copy_map(
  66     const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy):
  67     al_(al),size_(size),spc(al_,size_),n(0),
  68     header_org_(header_org),header_cpy_(header_cpy),released(false)
  69   {}
  70
  71   ~copy_map()
  72   {
  73     if(!released){
  74       for(std::size_t i=0;i<n;++i){
  75         boost::detail::allocator::destroy(
  76           boost::addressof((spc.data()+i)->second->value()));
  77         deallocate((spc.data()+i)->second);
  78       }
  79     }
  80   }
  81
  82   const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
  83   const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}
  84
  85   void clone(Node* node)
  86   {
  87     (spc.data()+n)->first=node;
  88     (spc.data()+n)->second=raw_ptr<Node*>(allocate());
  89     BOOST_TRY{
  90       boost::detail::allocator::construct(
  91         boost::addressof((spc.data()+n)->second->value()),node->value());
  92     }
  93     BOOST_CATCH(...){
  94       deallocate((spc.data()+n)->second);
  95       BOOST_RETHROW;
  96     }
  97     BOOST_CATCH_END
  98     ++n;
  99
 100     if(n==size_){
 101       std::sort(
 102         raw_ptr<copy_map_entry<Node>*>(spc.data()),
 103         raw_ptr<copy_map_entry<Node>*>(spc.data())+size_);
 104     }
 105   }
 106
 107   Node* find(Node* node)const
 108   {
 109     if(node==header_org_)return header_cpy_;
 110     return std::lower_bound(
 111       begin(),end(),copy_map_entry<Node>(node,0))->second;
 112   }
 113
 114   void release()
 115   {
 116     released=true;
 117   }
 118
 119 private:
 120   typedef typename boost::detail::allocator::rebind_to<
 121     Allocator,Node
 122   >::type                                               allocator_type;
 123 #ifdef BOOST_NO_CXX11_ALLOCATOR
 124   typedef typename allocator_type::pointer              allocator_pointer;
 125 #else
 126   typedef std::allocator_traits<allocator_type>         allocator_traits;
 127   typedef typename allocator_traits::pointer            allocator_pointer;
 128 #endif
 129
 130   allocator_type                                        al_;
 131   std::size_t                                           size_;
 132   auto_space<copy_map_entry<Node>,Allocator>            spc;
 133   std::size_t                                           n;
 134   Node*                                                 header_org_;
 135   Node*                                                 header_cpy_;
 136   bool                                                  released;
 137
 138   allocator_pointer allocate()
 139   {
 140 #ifdef BOOST_NO_CXX11_ALLOCATOR
 141     return al_.allocate(1);
 142 #else
 143     return allocator_traits::allocate(al_,1);
 144 #endif
 145   }
 146
 147   void deallocate(Node* node)
 148   {
 149 #ifdef BOOST_NO_CXX11_ALLOCATOR
 150     al_.deallocate(static_cast<allocator_pointer>(node),1);
 151 #else
 152     allocator_traits::deallocate(al_,static_cast<allocator_pointer>(node),1);
 153 #endif
 154   }
 155 };
 156
 157 } /* namespace multi_index::detail */
 158
 159 } /* namespace multi_index */
 160
 161 } /* namespace boost */
 162
 163 #endif