container/detail/multiallocation_chain.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010
0011 #ifndef BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
0012 #define BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
0013
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017
0018 #if defined(BOOST_HAS_PRAGMA_ONCE)
0019 #  pragma once
0020 #endif
0021
0022 #include <boost/container/detail/config_begin.hpp>
0023 #include <boost/container/detail/workaround.hpp>
0024 // container
0025 #include <boost/container/container_fwd.hpp>
0026 // container/detail
0027 #include <boost/move/detail/to_raw_pointer.hpp>
0028 #include <boost/container/detail/transform_iterator.hpp>
0029 #include <boost/container/detail/type_traits.hpp>
0030 #include <boost/container/detail/placement_new.hpp>
0031 // intrusive
0032 #include <boost/intrusive/slist.hpp>
0033 #include <boost/intrusive/pointer_traits.hpp>
0034 #include <boost/intrusive/detail/twin.hpp>
0035 // move
0036 #include <boost/move/utility_core.hpp>
0037
0038 namespace boost {
0039 namespace container {
0040 namespace dtl {
0041
0042 template<class VoidPointer>
0043 class basic_multiallocation_chain
0044 {
0045    private:
0046    typedef bi::slist_base_hook<bi::void_pointer<VoidPointer>
0047                         ,bi::link_mode<bi::normal_link>
0048                         > node;
0049
0050    typedef typename boost::intrusive::pointer_traits
0051       <VoidPointer>::template rebind_pointer<char>::type    char_ptr;
0052    typedef typename boost::intrusive::
0053       pointer_traits<char_ptr>::difference_type             difference_type;
0054
0055    typedef bi::slist< node
0056                     , bi::linear<true>
0057                     , bi::cache_last<true>
0058                     , bi::size_type<typename boost::container::dtl::make_unsigned<difference_type>::type>
0059                     > slist_impl_t;
0060    slist_impl_t slist_impl_;
0061
0062    typedef typename boost::intrusive::pointer_traits
0063       <VoidPointer>::template rebind_pointer<node>::type    node_ptr;
0064    typedef typename boost::intrusive::
0065       pointer_traits<node_ptr>                              node_ptr_traits;
0066
0067    static node & to_node(const VoidPointer &p)
0068    {  return *static_cast<node*>(static_cast<void*>(boost::movelib::to_raw_pointer(p)));  }
0069
0070    static VoidPointer from_node(node &n)
0071    {  return node_ptr_traits::pointer_to(n);  }
0072
0073    static node_ptr to_node_ptr(const VoidPointer &p)
0074    {  return node_ptr_traits::static_cast_from(p);   }
0075
0076    BOOST_MOVABLE_BUT_NOT_COPYABLE(basic_multiallocation_chain)
0077
0078    public:
0079
0080    typedef VoidPointer                       void_pointer;
0081    typedef typename slist_impl_t::iterator   iterator;
0082    typedef typename slist_impl_t::size_type  size_type;
0083    typedef boost::intrusive::twin<void_pointer> pointer_pair;
0084
0085    basic_multiallocation_chain()
0086       :  slist_impl_()
0087    {}
0088
0089    basic_multiallocation_chain(const void_pointer &b, const void_pointer &before_e, size_type n)
0090       :  slist_impl_(to_node_ptr(b), to_node_ptr(before_e), n)
0091    {}
0092
0093    basic_multiallocation_chain(BOOST_RV_REF(basic_multiallocation_chain) other)
0094       :  slist_impl_(::boost::move(other.slist_impl_))
0095    {}
0096
0097    basic_multiallocation_chain& operator=(BOOST_RV_REF(basic_multiallocation_chain) other)
0098    {
0099       slist_impl_ = ::boost::move(other.slist_impl_);
0100       return *this;
0101    }
0102
0103    bool empty() const
0104    {  return slist_impl_.empty(); }
0105
0106    size_type size() const
0107    {  return slist_impl_.size();  }
0108
0109    iterator before_begin()
0110    {  return slist_impl_.before_begin(); }
0111
0112    iterator begin()
0113    {  return slist_impl_.begin(); }
0114
0115    iterator end()
0116    {  return slist_impl_.end(); }
0117
0118    iterator last()
0119    {  return slist_impl_.last(); }
0120
0121    void clear()
0122    {  slist_impl_.clear(); }
0123
0124    iterator insert_after(iterator it, void_pointer m)
0125    {  return slist_impl_.insert_after(it, to_node(m));   }
0126
0127    void push_front(const void_pointer &m)
0128    {  return slist_impl_.push_front(to_node(m));  }
0129
0130    void push_back(const void_pointer &m)
0131    {  return slist_impl_.push_back(to_node(m));   }
0132
0133    void_pointer pop_front()
0134    {
0135       node & n = slist_impl_.front();
0136       void_pointer ret = from_node(n);
0137       slist_impl_.pop_front();
0138       return ret;
0139    }
0140
0141    void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n)
0142    {  slist_impl_.splice_after(after_this, x.slist_impl_, before_b, before_e, n);   }
0143
0144    void splice_after(iterator after_this, basic_multiallocation_chain &x)
0145    {  slist_impl_.splice_after(after_this, x.slist_impl_);   }
0146
0147    void erase_after(iterator before_b, iterator e, size_type n)
0148    {  slist_impl_.erase_after(before_b, e, n);   }
0149
0150    void_pointer incorporate_after(iterator after_this, const void_pointer &b, size_type unit_bytes, size_type num_units)
0151    {
0152       typedef typename boost::intrusive::pointer_traits<char_ptr> char_pointer_traits;
0153       char_ptr elem = char_pointer_traits::static_cast_from(b);
0154       if(num_units){
0155          char_ptr prev_elem = elem;
0156          elem += difference_type(unit_bytes);
0157          for(size_type i = 0; i != num_units-1u; ++i, elem += difference_type(unit_bytes)){
0158             ::new (boost::movelib::to_raw_pointer(prev_elem), boost_container_new_t()) void_pointer(elem);
0159             prev_elem = elem;
0160          }
0161          slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(prev_elem), num_units);
0162       }
0163       return elem;
0164    }
0165
0166    void incorporate_after(iterator after_this, void_pointer b, void_pointer before_e, size_type n)
0167    {  slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(before_e), n);   }
0168
0169    void swap(basic_multiallocation_chain &x)
0170    {  slist_impl_.swap(x.slist_impl_);   }
0171
0172    static iterator iterator_to(const void_pointer &p)
0173    {  return slist_impl_t::s_iterator_to(to_node(p));   }
0174
0175    pointer_pair extract_data()
0176    {
0177       if(BOOST_LIKELY(!slist_impl_.empty())){
0178          pointer_pair ret
0179             (slist_impl_.begin().operator->()
0180             ,slist_impl_.last().operator->());
0181          slist_impl_.clear();
0182          return ret;
0183       }
0184       else {
0185          return pointer_pair();
0186       }
0187    }
0188 };
0189
0190 template<class T>
0191 struct cast_functor
0192 {
0193    typedef typename dtl::add_reference<T>::type result_type;
0194    template<class U>
0195    result_type operator()(U &ptr) const
0196    {  return *static_cast<T*>(static_cast<void*>(&ptr));  }
0197 };
0198
0199 template<class MultiallocationChain, class T>
0200 class transform_multiallocation_chain
0201    : public MultiallocationChain
0202 {
0203    private:
0204    BOOST_MOVABLE_BUT_NOT_COPYABLE(transform_multiallocation_chain)
0205    //transform_multiallocation_chain(const transform_multiallocation_chain &);
0206    //transform_multiallocation_chain & operator=(const transform_multiallocation_chain &);
0207
0208    typedef typename MultiallocationChain::void_pointer   void_pointer;
0209    typedef typename boost::intrusive::pointer_traits
0210       <void_pointer>                                     void_pointer_traits;
0211    typedef typename void_pointer_traits::template
0212       rebind_pointer<T>::type                            pointer;
0213    typedef typename boost::intrusive::pointer_traits
0214       <pointer>                                          pointer_traits;
0215
0216    static pointer cast(const void_pointer &p)
0217    {  return pointer_traits::static_cast_from(p);  }
0218
0219    public:
0220    typedef transform_iterator
0221       < typename MultiallocationChain::iterator
0222       , dtl::cast_functor <T> >                          iterator;
0223    typedef typename MultiallocationChain::size_type      size_type;
0224    typedef boost::intrusive::twin<pointer>               pointer_pair;
0225
0226    transform_multiallocation_chain()
0227       : MultiallocationChain()
0228    {}
0229
0230    transform_multiallocation_chain(BOOST_RV_REF(transform_multiallocation_chain) other)
0231       : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other)))
0232    {}
0233
0234    transform_multiallocation_chain(BOOST_RV_REF(MultiallocationChain) other)
0235       : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other)))
0236    {}
0237
0238    transform_multiallocation_chain& operator=(BOOST_RV_REF(transform_multiallocation_chain) other)
0239    {
0240       return static_cast<MultiallocationChain&>
0241          (this->MultiallocationChain::operator=(::boost::move(static_cast<MultiallocationChain&>(other))));
0242    }
0243
0244    void push_front(const pointer &mem)
0245    {   this->MultiallocationChain::push_front(mem);  }
0246
0247    void push_back(const pointer &mem)
0248    {  return this->MultiallocationChain::push_back(mem);   }
0249
0250    void swap(transform_multiallocation_chain &other_chain)
0251    {  this->MultiallocationChain::swap(other_chain); }
0252
0253    void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n)
0254    {  this->MultiallocationChain::splice_after(after_this.base(), x, before_b.base(), before_e.base(), n);  }
0255
0256    void incorporate_after(iterator after_this, pointer b, pointer before_e, size_type n)
0257    {  this->MultiallocationChain::incorporate_after(after_this.base(), b, before_e, n);  }
0258
0259    pointer pop_front()
0260    {  return cast(this->MultiallocationChain::pop_front());  }
0261
0262    bool empty() const
0263    {  return this->MultiallocationChain::empty(); }
0264
0265    iterator before_begin()
0266    {  return iterator(this->MultiallocationChain::before_begin());   }
0267
0268    iterator begin()
0269    {  return iterator(this->MultiallocationChain::begin());   }
0270
0271    iterator last()
0272    {  return iterator(this->MultiallocationChain::last());  }
0273
0274    iterator end()
0275    {  return iterator(this->MultiallocationChain::end());   }
0276
0277    size_type size() const
0278    {  return this->MultiallocationChain::size();  }
0279
0280    void clear()
0281    {  this->MultiallocationChain::clear(); }
0282
0283    iterator insert_after(iterator it, pointer m)
0284    {  return iterator(this->MultiallocationChain::insert_after(it.base(), m)); }
0285
0286    static iterator iterator_to(const pointer &p)
0287    {  return iterator(MultiallocationChain::iterator_to(p));  }
0288
0289    pointer_pair extract_data()
0290    {
0291       typename MultiallocationChain::pointer_pair data(this->MultiallocationChain::extract_data());
0292       return pointer_pair(cast(data.first), cast(data.second));
0293    }
0294 /*
0295    MultiallocationChain &extract_multiallocation_chain()
0296    {  return holder_;  }*/
0297 };
0298
0299 }}}
0300
0301 // namespace dtl {
0302 // namespace container {
0303 // namespace boost {
0304
0305 #include <boost/container/detail/config_end.hpp>
0306
0307 #endif   //BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP