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

   1 /* Copyright 2003-2015 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/detail/no_exceptions_support.hpp>
  19 #include <boost/multi_index/detail/auto_space.hpp>
  20 #include <boost/multi_index/detail/raw_ptr.hpp>
  21 #include <boost/noncopyable.hpp>
  22 #include <cstddef>
  23 #include <functional>
  24
  25 namespace boost{
  26
  27 namespace multi_index{
  28
  29 namespace detail{
  30
  31 /* copy_map is used as an auxiliary structure during copy_() operations.
  32  * When a container with n nodes is replicated, node_map holds the pairings
  33  * between original and copied nodes, and provides a fast way to find a
  34  * copied node from an original one.
  35  * The semantics of the class are not simple, and no attempt has been made
  36  * to enforce it: multi_index_container handles it right. On the other hand,
  37  * the const interface, which is the one provided to index implementations,
  38  * only allows for:
  39  *   - Enumeration of pairs of (original,copied) nodes (excluding the headers),
  40  *   - fast retrieval of copied nodes (including the headers.)
  41  */
  42
  43 template <typename Node>
  44 struct copy_map_entry
  45 {
  46   copy_map_entry(Node* f,Node* s):first(f),second(s){}
  47
  48   Node* first;
  49   Node* second;
  50
  51   bool operator<(const copy_map_entry<Node>& x)const
  52   {
  53     return std::less<Node*>()(first,x.first);
  54   }
  55 };
  56
  57 template <typename Node,typename Allocator>
  58 class copy_map:private noncopyable
  59 {
  60 public:
  61   typedef const copy_map_entry<Node>* const_iterator;
  62
  63   copy_map(
  64     const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy):
  65     al_(al),size_(size),spc(al_,size_),n(0),
  66     header_org_(header_org),header_cpy_(header_cpy),released(false)
  67   {}
  68
  69   ~copy_map()
  70   {
  71     if(!released){
  72       for(std::size_t i=0;i<n;++i){
  73         boost::detail::allocator::destroy(&(spc.data()+i)->second->value());
  74         deallocate((spc.data()+i)->second);
  75       }
  76     }
  77   }
  78
  79   const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
  80   const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}
  81
  82   void clone(Node* node)
  83   {
  84     (spc.data()+n)->first=node;
  85     (spc.data()+n)->second=raw_ptr<Node*>(al_.allocate(1));
  86     BOOST_TRY{
  87       boost::detail::allocator::construct(
  88         &(spc.data()+n)->second->value(),node->value());
  89     }
  90     BOOST_CATCH(...){
  91       deallocate((spc.data()+n)->second);
  92       BOOST_RETHROW;
  93     }
  94     BOOST_CATCH_END
  95     ++n;
  96
  97     if(n==size_){
  98       std::sort(
  99         raw_ptr<copy_map_entry<Node>*>(spc.data()),
 100         raw_ptr<copy_map_entry<Node>*>(spc.data())+size_);
 101     }
 102   }
 103
 104   Node* find(Node* node)const
 105   {
 106     if(node==header_org_)return header_cpy_;
 107     return std::lower_bound(
 108       begin(),end(),copy_map_entry<Node>(node,0))->second;
 109   }
 110
 111   void release()
 112   {
 113     released=true;
 114   }
 115
 116 private:
 117   typedef typename boost::detail::allocator::rebind_to<
 118     Allocator,Node
 119   >::type                                               allocator_type;
 120   typedef typename allocator_type::pointer              allocator_pointer;
 121
 122   allocator_type                                        al_;
 123   std::size_t                                           size_;
 124   auto_space<copy_map_entry<Node>,Allocator>            spc;
 125   std::size_t                                           n;
 126   Node*                                                 header_org_;
 127   Node*                                                 header_cpy_;
 128   bool                                                  released;
 129
 130   void deallocate(Node* node)
 131   {
 132     al_.deallocate(static_cast<allocator_pointer>(node),1);
 133   }
 134 };
 135
 136 } /* namespace multi_index::detail */
 137
 138 } /* namespace multi_index */
 139
 140 } /* namespace boost */
 141
 142 #endif