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