Chris@101: /* Copyright 2003-2013 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <algorithm>
Chris@16: #include <boost/detail/no_exceptions_support.hpp>
Chris@16: #include <boost/multi_index/detail/auto_space.hpp>
Chris@16: #include <boost/noncopyable.hpp>
Chris@16: #include <cstddef>
Chris@16: #include <functional>
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@16: /* copy_map is used as an auxiliary structure during copy_() operations.
Chris@16:  * When a container with n nodes is replicated, node_map holds the pairings
Chris@16:  * between original and copied nodes, and provides a fast way to find a
Chris@16:  * copied node from an original one.
Chris@16:  * The semantics of the class are not simple, and no attempt has been made
Chris@16:  * to enforce it: multi_index_container handles it right. On the other hand,
Chris@16:  * the const interface, which is the one provided to index implementations,
Chris@16:  * only allows for:
Chris@16:  *   - Enumeration of pairs of (original,copied) nodes (excluding the headers),
Chris@16:  *   - fast retrieval of copied nodes (including the headers.)
Chris@16:  */
Chris@16: 
Chris@16: template <typename Node>
Chris@16: struct copy_map_entry
Chris@16: {
Chris@16:   copy_map_entry(Node* f,Node* s):first(f),second(s){}
Chris@16: 
Chris@16:   Node* first;
Chris@16:   Node* second;
Chris@16: 
Chris@16:   bool operator<(const copy_map_entry<Node>& x)const
Chris@16:   {
Chris@16:     return std::less<Node*>()(first,x.first);
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: template <typename Node,typename Allocator>
Chris@16: class copy_map:private noncopyable
Chris@16: {
Chris@16: public:
Chris@16:   typedef const copy_map_entry<Node>* const_iterator;
Chris@16: 
Chris@16:   copy_map(
Chris@16:     const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy):
Chris@16:     al_(al),size_(size),spc(al_,size_),n(0),
Chris@16:     header_org_(header_org),header_cpy_(header_cpy),released(false)
Chris@16:   {}
Chris@16: 
Chris@16:   ~copy_map()
Chris@16:   {
Chris@16:     if(!released){
Chris@16:       for(std::size_t i=0;i<n;++i){
Chris@16:         boost::detail::allocator::destroy(&(spc.data()+i)->second->value());
Chris@16:         deallocate((spc.data()+i)->second);
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   const_iterator begin()const{return &*spc.data();}
Chris@16:   const_iterator end()const{return &*(spc.data()+n);}
Chris@16: 
Chris@16:   void clone(Node* node)
Chris@16:   {
Chris@16:     (spc.data()+n)->first=node;
Chris@16:     (spc.data()+n)->second=&*al_.allocate(1);
Chris@16:     BOOST_TRY{
Chris@16:       boost::detail::allocator::construct(
Chris@16:         &(spc.data()+n)->second->value(),node->value());
Chris@16:     }
Chris@16:     BOOST_CATCH(...){
Chris@16:       deallocate((spc.data()+n)->second);
Chris@16:       BOOST_RETHROW;
Chris@16:     }
Chris@16:     BOOST_CATCH_END
Chris@16:     ++n;
Chris@16: 
Chris@16:     if(n==size_)std::sort(&*spc.data(),&*spc.data()+size_);
Chris@16:   }
Chris@16: 
Chris@16:   Node* find(Node* node)const
Chris@16:   {
Chris@16:     if(node==header_org_)return header_cpy_;
Chris@16:     return std::lower_bound(
Chris@16:       begin(),end(),copy_map_entry<Node>(node,0))->second;
Chris@16:   }
Chris@16: 
Chris@16:   void release()
Chris@16:   {
Chris@16:     released=true;
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@101:   typedef typename boost::detail::allocator::rebind_to<
Chris@101:     Allocator,Node
Chris@101:   >::type                                               allocator_type;
Chris@101:   typedef typename allocator_type::pointer              allocator_pointer;
Chris@16: 
Chris@101:   allocator_type                                        al_;
Chris@101:   std::size_t                                           size_;
Chris@101:   auto_space<copy_map_entry<Node>,Allocator>            spc;
Chris@101:   std::size_t                                           n;
Chris@101:   Node*                                                 header_org_;
Chris@101:   Node*                                                 header_cpy_;
Chris@101:   bool                                                  released;
Chris@16: 
Chris@16:   void deallocate(Node* node)
Chris@16:   {
Chris@16:     al_.deallocate(static_cast<allocator_pointer>(node),1);
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif