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