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