1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10 
11 #ifndef BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
12 #define BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
13 
14 #ifndef BOOST_CONFIG_HPP
15 #  include <boost/config.hpp>
16 #endif
17 
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
19 #  pragma once
20 #endif
21 
22 #include <boost/container/detail/config_begin.hpp>
23 #include <boost/container/detail/workaround.hpp>
24 // container
25 #include <boost/container/container_fwd.hpp>
26 // container/detail
27 #include <boost/move/detail/to_raw_pointer.hpp>
28 #include <boost/container/detail/transform_iterator.hpp>
29 #include <boost/container/detail/type_traits.hpp>
30 // intrusive
31 #include <boost/intrusive/slist.hpp>
32 #include <boost/intrusive/pointer_traits.hpp>
33 // move
34 #include <boost/move/utility_core.hpp>
35 
36 namespace boost {
37 namespace container {
38 namespace dtl {
39 
40 template<class VoidPointer>
41 class basic_multiallocation_chain
42 {
43    private:
44    typedef bi::slist_base_hook<bi::void_pointer<VoidPointer>
45                         ,bi::link_mode<bi::normal_link>
46                         > node;
47 
48    typedef typename boost::intrusive::pointer_traits
49       <VoidPointer>::template rebind_pointer<char>::type    char_ptr;
50    typedef typename boost::intrusive::
51       pointer_traits<char_ptr>::difference_type             difference_type;
52 
53    typedef bi::slist< node
54                     , bi::linear<true>
55                     , bi::cache_last<true>
56                     , bi::size_type<typename boost::container::dtl::make_unsigned<difference_type>::type>
57                     > slist_impl_t;
58    slist_impl_t slist_impl_;
59 
60    typedef typename boost::intrusive::pointer_traits
61       <VoidPointer>::template rebind_pointer<node>::type    node_ptr;
62    typedef typename boost::intrusive::
63       pointer_traits<node_ptr>                              node_ptr_traits;
64 
to_node(const VoidPointer & p)65    static node & to_node(const VoidPointer &p)
66    {  return *static_cast<node*>(static_cast<void*>(boost::movelib::to_raw_pointer(p)));  }
67 
from_node(node & n)68    static VoidPointer from_node(node &n)
69    {  return node_ptr_traits::pointer_to(n);  }
70 
to_node_ptr(const VoidPointer & p)71    static node_ptr to_node_ptr(const VoidPointer &p)
72    {  return node_ptr_traits::static_cast_from(p);   }
73 
74    BOOST_MOVABLE_BUT_NOT_COPYABLE(basic_multiallocation_chain)
75 
76    public:
77 
78    typedef VoidPointer                       void_pointer;
79    typedef typename slist_impl_t::iterator   iterator;
80    typedef typename slist_impl_t::size_type  size_type;
81 
basic_multiallocation_chain()82    basic_multiallocation_chain()
83       :  slist_impl_()
84    {}
85 
basic_multiallocation_chain(const void_pointer & b,const void_pointer & before_e,size_type n)86    basic_multiallocation_chain(const void_pointer &b, const void_pointer &before_e, size_type n)
87       :  slist_impl_(to_node_ptr(b), to_node_ptr(before_e), n)
88    {}
89 
basic_multiallocation_chain(BOOST_RV_REF (basic_multiallocation_chain)other)90    basic_multiallocation_chain(BOOST_RV_REF(basic_multiallocation_chain) other)
91       :  slist_impl_(::boost::move(other.slist_impl_))
92    {}
93 
operator =(BOOST_RV_REF (basic_multiallocation_chain)other)94    basic_multiallocation_chain& operator=(BOOST_RV_REF(basic_multiallocation_chain) other)
95    {
96       slist_impl_ = ::boost::move(other.slist_impl_);
97       return *this;
98    }
99 
empty() const100    bool empty() const
101    {  return slist_impl_.empty(); }
102 
size() const103    size_type size() const
104    {  return slist_impl_.size();  }
105 
before_begin()106    iterator before_begin()
107    {  return slist_impl_.before_begin(); }
108 
begin()109    iterator begin()
110    {  return slist_impl_.begin(); }
111 
end()112    iterator end()
113    {  return slist_impl_.end(); }
114 
last()115    iterator last()
116    {  return slist_impl_.last(); }
117 
clear()118    void clear()
119    {  slist_impl_.clear(); }
120 
insert_after(iterator it,void_pointer m)121    iterator insert_after(iterator it, void_pointer m)
122    {  return slist_impl_.insert_after(it, to_node(m));   }
123 
push_front(const void_pointer & m)124    void push_front(const void_pointer &m)
125    {  return slist_impl_.push_front(to_node(m));  }
126 
push_back(const void_pointer & m)127    void push_back(const void_pointer &m)
128    {  return slist_impl_.push_back(to_node(m));   }
129 
pop_front()130    void_pointer pop_front()
131    {
132       node & n = slist_impl_.front();
133       void_pointer ret = from_node(n);
134       slist_impl_.pop_front();
135       return ret;
136    }
137 
splice_after(iterator after_this,basic_multiallocation_chain & x,iterator before_b,iterator before_e,size_type n)138    void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n)
139    {  slist_impl_.splice_after(after_this, x.slist_impl_, before_b, before_e, n);   }
140 
splice_after(iterator after_this,basic_multiallocation_chain & x)141    void splice_after(iterator after_this, basic_multiallocation_chain &x)
142    {  slist_impl_.splice_after(after_this, x.slist_impl_);   }
143 
erase_after(iterator before_b,iterator e,size_type n)144    void erase_after(iterator before_b, iterator e, size_type n)
145    {  slist_impl_.erase_after(before_b, e, n);   }
146 
incorporate_after(iterator after_this,const void_pointer & b,size_type unit_bytes,size_type num_units)147    void_pointer incorporate_after(iterator after_this, const void_pointer &b, size_type unit_bytes, size_type num_units)
148    {
149       typedef typename boost::intrusive::pointer_traits<char_ptr> char_pointer_traits;
150       char_ptr elem = char_pointer_traits::static_cast_from(b);
151       if(num_units){
152          char_ptr prev_elem = elem;
153          elem += unit_bytes;
154          for(size_type i = 0; i != num_units-1; ++i, elem += unit_bytes){
155             ::new (boost::movelib::to_raw_pointer(prev_elem)) void_pointer(elem);
156             prev_elem = elem;
157          }
158          slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(prev_elem), num_units);
159       }
160       return elem;
161    }
162 
incorporate_after(iterator after_this,void_pointer b,void_pointer before_e,size_type n)163    void incorporate_after(iterator after_this, void_pointer b, void_pointer before_e, size_type n)
164    {  slist_impl_.incorporate_after(after_this, to_node_ptr(b), to_node_ptr(before_e), n);   }
165 
swap(basic_multiallocation_chain & x)166    void swap(basic_multiallocation_chain &x)
167    {  slist_impl_.swap(x.slist_impl_);   }
168 
iterator_to(const void_pointer & p)169    static iterator iterator_to(const void_pointer &p)
170    {  return slist_impl_t::s_iterator_to(to_node(p));   }
171 
extract_data()172    std::pair<void_pointer, void_pointer> extract_data()
173    {
174       if(BOOST_LIKELY(!slist_impl_.empty())){
175          std::pair<void_pointer, void_pointer> ret
176             (slist_impl_.begin().operator->()
177             ,slist_impl_.last().operator->());
178          slist_impl_.clear();
179          return ret;
180       }
181       else {
182          return std::pair<void_pointer, void_pointer>();
183       }
184    }
185 };
186 
187 template<class T>
188 struct cast_functor
189 {
190    typedef typename dtl::add_reference<T>::type result_type;
191    template<class U>
operator ()boost::container::dtl::cast_functor192    result_type operator()(U &ptr) const
193    {  return *static_cast<T*>(static_cast<void*>(&ptr));  }
194 };
195 
196 template<class MultiallocationChain, class T>
197 class transform_multiallocation_chain
198    : public MultiallocationChain
199 {
200    private:
201    BOOST_MOVABLE_BUT_NOT_COPYABLE(transform_multiallocation_chain)
202    //transform_multiallocation_chain(const transform_multiallocation_chain &);
203    //transform_multiallocation_chain & operator=(const transform_multiallocation_chain &);
204 
205    typedef typename MultiallocationChain::void_pointer   void_pointer;
206    typedef typename boost::intrusive::pointer_traits
207       <void_pointer>                                     void_pointer_traits;
208    typedef typename void_pointer_traits::template
209       rebind_pointer<T>::type                            pointer;
210    typedef typename boost::intrusive::pointer_traits
211       <pointer>                                          pointer_traits;
212 
cast(const void_pointer & p)213    static pointer cast(const void_pointer &p)
214    {  return pointer_traits::static_cast_from(p);  }
215 
216    public:
217    typedef transform_iterator
218       < typename MultiallocationChain::iterator
219       , dtl::cast_functor <T> >             iterator;
220    typedef typename MultiallocationChain::size_type      size_type;
221 
transform_multiallocation_chain()222    transform_multiallocation_chain()
223       : MultiallocationChain()
224    {}
225 
transform_multiallocation_chain(BOOST_RV_REF (transform_multiallocation_chain)other)226    transform_multiallocation_chain(BOOST_RV_REF(transform_multiallocation_chain) other)
227       : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other)))
228    {}
229 
transform_multiallocation_chain(BOOST_RV_REF (MultiallocationChain)other)230    transform_multiallocation_chain(BOOST_RV_REF(MultiallocationChain) other)
231       : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other)))
232    {}
233 
operator =(BOOST_RV_REF (transform_multiallocation_chain)other)234    transform_multiallocation_chain& operator=(BOOST_RV_REF(transform_multiallocation_chain) other)
235    {
236       return static_cast<MultiallocationChain&>
237          (this->MultiallocationChain::operator=(::boost::move(static_cast<MultiallocationChain&>(other))));
238    }
239 
push_front(const pointer & mem)240    void push_front(const pointer &mem)
241    {   this->MultiallocationChain::push_front(mem);  }
242 
push_back(const pointer & mem)243    void push_back(const pointer &mem)
244    {  return this->MultiallocationChain::push_back(mem);   }
245 
swap(transform_multiallocation_chain & other_chain)246    void swap(transform_multiallocation_chain &other_chain)
247    {  this->MultiallocationChain::swap(other_chain); }
248 
splice_after(iterator after_this,transform_multiallocation_chain & x,iterator before_b,iterator before_e,size_type n)249    void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n)
250    {  this->MultiallocationChain::splice_after(after_this.base(), x, before_b.base(), before_e.base(), n);  }
251 
incorporate_after(iterator after_this,pointer b,pointer before_e,size_type n)252    void incorporate_after(iterator after_this, pointer b, pointer before_e, size_type n)
253    {  this->MultiallocationChain::incorporate_after(after_this.base(), b, before_e, n);  }
254 
pop_front()255    pointer pop_front()
256    {  return cast(this->MultiallocationChain::pop_front());  }
257 
empty() const258    bool empty() const
259    {  return this->MultiallocationChain::empty(); }
260 
before_begin()261    iterator before_begin()
262    {  return iterator(this->MultiallocationChain::before_begin());   }
263 
begin()264    iterator begin()
265    {  return iterator(this->MultiallocationChain::begin());   }
266 
last()267    iterator last()
268    {  return iterator(this->MultiallocationChain::last());  }
269 
end()270    iterator end()
271    {  return iterator(this->MultiallocationChain::end());   }
272 
size() const273    size_type size() const
274    {  return this->MultiallocationChain::size();  }
275 
clear()276    void clear()
277    {  this->MultiallocationChain::clear(); }
278 
insert_after(iterator it,pointer m)279    iterator insert_after(iterator it, pointer m)
280    {  return iterator(this->MultiallocationChain::insert_after(it.base(), m)); }
281 
iterator_to(const pointer & p)282    static iterator iterator_to(const pointer &p)
283    {  return iterator(MultiallocationChain::iterator_to(p));  }
284 
extract_data()285    std::pair<pointer, pointer> extract_data()
286    {
287       std::pair<void_pointer, void_pointer> data(this->MultiallocationChain::extract_data());
288       return std::pair<pointer, pointer>(cast(data.first), cast(data.second));
289    }
290 /*
291    MultiallocationChain &extract_multiallocation_chain()
292    {  return holder_;  }*/
293 };
294 
295 }}}
296 
297 // namespace dtl {
298 // namespace container {
299 // namespace boost {
300 
301 #include <boost/container/detail/config_end.hpp>
302 
303 #endif   //BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP
304