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/type_traits.hpp>
0029 #include <boost/container/detail/placement_new.hpp>
0030 #include <boost/container/detail/iterator.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 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0038
0039
0040 namespace boost {
0041 namespace container {
0042 namespace dtl {
0043
0044 template<class VoidPointer>
0045 class basic_multiallocation_chain
0046 {
0047    private:
0048    typedef bi::slist_base_hook<bi::void_pointer<VoidPointer>
0049                         ,bi::link_mode<bi::normal_link>
0050                         > node;
0051
0052    typedef typename boost::intrusive::pointer_traits
0053       <VoidPointer>::template rebind_pointer<char>::type    char_ptr;
0054    typedef typename boost::intrusive::
0055       pointer_traits<char_ptr>::difference_type             difference_type;
0056
0057    typedef bi::slist< node
0058                     , bi::linear<true>
0059                     , bi::cache_last<true>
0060                     , bi::size_type<typename boost::container::dtl::make_unsigned<difference_type>::type>
0061                     > slist_impl_t;
0062    slist_impl_t slist_impl_;
0063
0064    typedef typename boost::intrusive::pointer_traits
0065       <VoidPointer>::template rebind_pointer<node>::type    node_ptr;
0066    typedef typename boost::intrusive::
0067       pointer_traits<node_ptr>                              node_ptr_traits;
0068
0069    static node & to_node(const VoidPointer &p)
0070    {  return *static_cast<node*>(static_cast<void*>(boost::movelib::to_raw_pointer(p)));  }
0071
0072    static VoidPointer from_node(node &n)
0073    {  return node_ptr_traits::pointer_to(n);  }
0074
0075    static node_ptr to_node_ptr(const VoidPointer &p)
0076    {  return node_ptr_traits::static_cast_from(p);   }
0077
0078    BOOST_MOVABLE_BUT_NOT_COPYABLE(basic_multiallocation_chain)
0079
0080    public:
0081
0082    typedef VoidPointer                       void_pointer;
0083    typedef typename slist_impl_t::iterator   iterator;
0084    typedef typename slist_impl_t::size_type  size_type;
0085    typedef boost::intrusive::twin<void_pointer> pointer_pair;
0086
0087    basic_multiallocation_chain()
0088       :  slist_impl_()
0089    {}
0090
0091    basic_multiallocation_chain(const void_pointer &b, const void_pointer &before_e, size_type n)
0092       :  slist_impl_(to_node_ptr(b), to_node_ptr(before_e), n)
0093    {}
0094
0095    basic_multiallocation_chain(BOOST_RV_REF(basic_multiallocation_chain) other)
0096       :  slist_impl_(::boost::move(other.slist_impl_))
0097    {}
0098
0099    basic_multiallocation_chain& operator=(BOOST_RV_REF(basic_multiallocation_chain) other)
0100    {
0101       slist_impl_ = ::boost::move(other.slist_impl_);
0102       return *this;
0103    }
0104
0105    bool empty() const
0106    {  return slist_impl_.empty(); }
0107
0108    size_type size() const
0109    {  return slist_impl_.size();  }
0110
0111    iterator before_begin()
0112    {  return slist_impl_.before_begin(); }
0113
0114    iterator begin()
0115    {  return slist_impl_.begin(); }
0116
0117    iterator end()
0118    {  return slist_impl_.end(); }
0119
0120    iterator last()
0121    {  return slist_impl_.last(); }
0122
0123    void clear()
0124    {  slist_impl_.clear(); }
0125
0126    iterator insert_after(iterator it, void_pointer m)
0127    {  return slist_impl_.insert_after(it, to_node(m));   }
0128
0129    void push_front(const void_pointer &m)
0130    {  return slist_impl_.push_front(to_node(m));  }
0131
0132    void push_back(const void_pointer &m)
0133    {  return slist_impl_.push_back(to_node(m));   }
0134
0135    void_pointer pop_front()
0136    {
0137       node & n = slist_impl_.front();
0138       void_pointer ret = from_node(n);
0139       slist_impl_.pop_front();
0140       return ret;
0141    }
0142
0143    void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n)
0144    {  slist_impl_.splice_after(after_this, x.slist_impl_, before_b, before_e, n);   }
0145
0146    void splice_after(iterator after_this, basic_multiallocation_chain &x)
0147    {  slist_impl_.splice_after(after_this, x.slist_impl_);   }
0148
0149    void erase_after(iterator before_b, iterator e, size_type n)
0150    {  slist_impl_.erase_after(before_b, e, n);   }
0151
0152    void_pointer incorporate_after(iterator after_this, const void_pointer &b, size_type unit_bytes, size_type num_units)
0153    {
0154       typedef typename boost::intrusive::pointer_traits<char_ptr> char_pointer_traits;
0155       char_ptr elem = char_pointer_traits::static_cast_from(b);
0156       if(num_units){
0157          char_ptr prev_elem = elem;
0158          elem += difference_type(unit_bytes);
0159          for(size_type i = 0; i != num_units-1u; ++i, elem += difference_type(unit_bytes)){
0160             ::new (boost::movelib::to_raw_pointer(prev_elem), boost_container_new_t()) void_pointer(elem);
0161             prev_elem = elem;
0162          }
0163          slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(prev_elem), num_units);
0164       }
0165       return elem;
0166    }
0167
0168    void incorporate_after(iterator after_this, void_pointer b, void_pointer before_e, size_type n)
0169    {  slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(before_e), n);   }
0170
0171    void swap(basic_multiallocation_chain &x)
0172    {  slist_impl_.swap(x.slist_impl_);   }
0173
0174    static iterator iterator_to(const void_pointer &p)
0175    {  return slist_impl_t::s_iterator_to(to_node(p));   }
0176
0177    pointer_pair extract_data()
0178    {
0179       if(BOOST_LIKELY(!slist_impl_.empty())){
0180          pointer_pair ret
0181             (slist_impl_.begin().operator->()
0182             ,slist_impl_.last().operator->());
0183          slist_impl_.clear();
0184          return ret;
0185       }
0186       else {
0187          return pointer_pair();
0188       }
0189    }
0190 };
0191
0192 template <class Iterator, class T>
0193 class multialloc_iterator
0194    : public boost::container::iterator
0195       < typename Iterator::iterator_category
0196       , T
0197       , typename Iterator::difference_type
0198       , T*
0199       , T&
0200       >
0201 {
0202    public:
0203    inline explicit multialloc_iterator(const Iterator &it)
0204       :  m_it(it)
0205    {}
0206
0207    inline explicit multialloc_iterator()
0208       :  m_it()
0209    {}
0210
0211    //Constructors
0212    inline multialloc_iterator& operator++()
0213    { increment();   return *this;   }
0214
0215       inline multialloc_iterator operator++(int)
0216    {
0217       multialloc_iterator result (*this);
0218       increment();
0219       return result;
0220    }
0221
0222    inline friend bool operator== (const multialloc_iterator& i, const multialloc_iterator& i2)
0223    { return i.equal(i2); }
0224
0225    inline friend bool operator!= (const multialloc_iterator& i, const multialloc_iterator& i2)
0226    { return !(i == i2); }
0227
0228    inline friend typename Iterator::difference_type operator- (const multialloc_iterator& i, const multialloc_iterator& i2)
0229    { return i2.distance_to(i); }
0230
0231    //Arithmetic
0232    inline multialloc_iterator& operator+=(typename Iterator::difference_type off)
0233    {  this->advance(off); return *this;   }
0234
0235    inline multialloc_iterator operator+(typename Iterator::difference_type off) const
0236    {
0237       multialloc_iterator other(*this);
0238       other.advance(off);
0239       return other;
0240    }
0241
0242    inline friend multialloc_iterator operator+(typename Iterator::difference_type off, const multialloc_iterator& right)
0243    {  return right + off; }
0244
0245    inline multialloc_iterator& operator-=(typename Iterator::difference_type off)
0246    {  this->advance(-off); return *this;   }
0247
0248    inline multialloc_iterator operator-(typename Iterator::difference_type off) const
0249    {  return *this + (-off);  }
0250
0251    inline T& operator*() const
0252    { return *this->operator->(); }
0253
0254    inline T* operator->() const
0255    {  return static_cast<T*>(static_cast<void*>(boost::movelib::iterator_to_raw_pointer(m_it)));   }
0256
0257    inline Iterator & base()
0258    {  return m_it;   }
0259
0260    inline const Iterator & base() const
0261    {  return m_it;   }
0262
0263    private:
0264    Iterator m_it;
0265
0266    inline void increment()
0267    { ++m_it; }
0268
0269    inline void decrement()
0270    { --m_it; }
0271
0272    inline bool equal(const multialloc_iterator &other) const
0273    {  return m_it == other.m_it;   }
0274
0275    inline bool less(const multialloc_iterator &other) const
0276    {  return other.m_it < m_it;   }
0277
0278    inline void advance(typename Iterator::difference_type n)
0279    {  boost::container::iterator_advance(m_it, n); }
0280
0281    inline typename Iterator::difference_type distance_to(const multialloc_iterator &other)const
0282    {  return boost::container::iterator_distance(other.m_it, m_it); }
0283 };
0284
0285
0286 template<class MultiallocationChain, class T>
0287 class transform_multiallocation_chain
0288    : public MultiallocationChain
0289 {
0290    private:
0291    BOOST_MOVABLE_BUT_NOT_COPYABLE(transform_multiallocation_chain)
0292    //transform_multiallocation_chain(const transform_multiallocation_chain &);
0293    //transform_multiallocation_chain & operator=(const transform_multiallocation_chain &);
0294
0295    typedef typename MultiallocationChain::void_pointer   void_pointer;
0296    typedef typename boost::intrusive::pointer_traits
0297       <void_pointer>                                     void_pointer_traits;
0298    typedef typename void_pointer_traits::template
0299       rebind_pointer<T>::type                            pointer;
0300    typedef typename boost::intrusive::pointer_traits
0301       <pointer>                                          pointer_traits;
0302
0303    static pointer cast(const void_pointer &p)
0304    {  return pointer_traits::static_cast_from(p);  }
0305
0306    public:
0307    typedef multialloc_iterator
0308       <typename MultiallocationChain::iterator, T>       iterator;
0309    typedef typename MultiallocationChain::size_type      size_type;
0310    typedef boost::intrusive::twin<pointer>               pointer_pair;
0311
0312    transform_multiallocation_chain()
0313       : MultiallocationChain()
0314    {}
0315
0316    transform_multiallocation_chain(BOOST_RV_REF(transform_multiallocation_chain) other)
0317       : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other)))
0318    {}
0319
0320    transform_multiallocation_chain(BOOST_RV_REF(MultiallocationChain) other)
0321       : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other)))
0322    {}
0323
0324    transform_multiallocation_chain& operator=(BOOST_RV_REF(transform_multiallocation_chain) other)
0325    {
0326       return static_cast<MultiallocationChain&>
0327          (this->MultiallocationChain::operator=(::boost::move(static_cast<MultiallocationChain&>(other))));
0328    }
0329
0330    void push_front(const pointer &mem)
0331    {   this->MultiallocationChain::push_front(mem);  }
0332
0333    void push_back(const pointer &mem)
0334    {  return this->MultiallocationChain::push_back(mem);   }
0335
0336    void swap(transform_multiallocation_chain &other_chain)
0337    {  this->MultiallocationChain::swap(other_chain); }
0338
0339    void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n)
0340    {  this->MultiallocationChain::splice_after(after_this.base(), x, before_b.base(), before_e.base(), n);  }
0341
0342    void incorporate_after(iterator after_this, pointer b, pointer before_e, size_type n)
0343    {  this->MultiallocationChain::incorporate_after(after_this.base(), b, before_e, n);  }
0344
0345    pointer pop_front()
0346    {  return cast(this->MultiallocationChain::pop_front());  }
0347
0348    bool empty() const
0349    {  return this->MultiallocationChain::empty(); }
0350
0351    iterator before_begin()
0352    {  return iterator(this->MultiallocationChain::before_begin());   }
0353
0354    iterator begin()
0355    {  return iterator(this->MultiallocationChain::begin());   }
0356
0357    iterator last()
0358    {  return iterator(this->MultiallocationChain::last());  }
0359
0360    iterator end()
0361    {  return iterator(this->MultiallocationChain::end());   }
0362
0363    size_type size() const
0364    {  return this->MultiallocationChain::size();  }
0365
0366    void clear()
0367    {  this->MultiallocationChain::clear(); }
0368
0369    iterator insert_after(iterator it, pointer m)
0370    {  return iterator(this->MultiallocationChain::insert_after(it.base(), m)); }
0371
0372    static iterator iterator_to(const pointer &p)
0373    {  return iterator(MultiallocationChain::iterator_to(p));  }
0374
0375    pointer_pair extract_data()
0376    {
0377       typename MultiallocationChain::pointer_pair data(this->MultiallocationChain::extract_data());
0378       return pointer_pair(cast(data.first), cast(data.second));
0379    }
0380 /*
0381    MultiallocationChain &extract_multiallocation_chain()
0382    {  return holder_;  }*/
0383 };
0384
0385 }}}
0386
0387 // namespace dtl {
0388 // namespace container {
0389 // namespace boost {
0390
0391 #include <boost/container/detail/config_end.hpp>
0392
0393 #endif   //BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP