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/container/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 container_detail { 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::container_detail::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*>(container_detail::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 (container_detail::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 std::pair<void_pointer, void_pointer> ret 175 (slist_impl_.begin().operator->() 176 ,slist_impl_.last().operator->()); 177 slist_impl_.clear(); 178 return ret; 179 } 180 }; 181 182 template<class T> 183 struct cast_functor 184 { 185 typedef typename container_detail::add_reference<T>::type result_type; 186 template<class U> operator ()boost::container::container_detail::cast_functor187 result_type operator()(U &ptr) const 188 { return *static_cast<T*>(static_cast<void*>(&ptr)); } 189 }; 190 191 template<class MultiallocationChain, class T> 192 class transform_multiallocation_chain 193 : public MultiallocationChain 194 { 195 private: 196 BOOST_MOVABLE_BUT_NOT_COPYABLE(transform_multiallocation_chain) 197 //transform_multiallocation_chain(const transform_multiallocation_chain &); 198 //transform_multiallocation_chain & operator=(const transform_multiallocation_chain &); 199 200 typedef typename MultiallocationChain::void_pointer void_pointer; 201 typedef typename boost::intrusive::pointer_traits 202 <void_pointer> void_pointer_traits; 203 typedef typename void_pointer_traits::template 204 rebind_pointer<T>::type pointer; 205 typedef typename boost::intrusive::pointer_traits 206 <pointer> pointer_traits; 207 cast(const void_pointer & p)208 static pointer cast(const void_pointer &p) 209 { return pointer_traits::static_cast_from(p); } 210 211 public: 212 typedef transform_iterator 213 < typename MultiallocationChain::iterator 214 , container_detail::cast_functor <T> > iterator; 215 typedef typename MultiallocationChain::size_type size_type; 216 transform_multiallocation_chain()217 transform_multiallocation_chain() 218 : MultiallocationChain() 219 {} 220 transform_multiallocation_chain(BOOST_RV_REF (transform_multiallocation_chain)other)221 transform_multiallocation_chain(BOOST_RV_REF(transform_multiallocation_chain) other) 222 : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other))) 223 {} 224 transform_multiallocation_chain(BOOST_RV_REF (MultiallocationChain)other)225 transform_multiallocation_chain(BOOST_RV_REF(MultiallocationChain) other) 226 : MultiallocationChain(::boost::move(static_cast<MultiallocationChain&>(other))) 227 {} 228 operator =(BOOST_RV_REF (transform_multiallocation_chain)other)229 transform_multiallocation_chain& operator=(BOOST_RV_REF(transform_multiallocation_chain) other) 230 { 231 return static_cast<MultiallocationChain&> 232 (this->MultiallocationChain::operator=(::boost::move(static_cast<MultiallocationChain&>(other)))); 233 } 234 /* 235 void push_front(const pointer &mem) 236 { holder_.push_front(mem); } 237 238 void push_back(const pointer &mem) 239 { return holder_.push_back(mem); } 240 241 void swap(transform_multiallocation_chain &other_chain) 242 { holder_.swap(other_chain.holder_); } 243 244 void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_b, iterator before_e, size_type n) 245 { holder_.splice_after(after_this.base(), x.holder_, before_b.base(), before_e.base(), n); } 246 247 void incorporate_after(iterator after_this, pointer b, pointer before_e, size_type n) 248 { holder_.incorporate_after(after_this.base(), b, before_e, n); } 249 */ pop_front()250 pointer pop_front() 251 { return cast(this->MultiallocationChain::pop_front()); } 252 /* 253 bool empty() const 254 { return holder_.empty(); } 255 256 iterator before_begin() 257 { return iterator(holder_.before_begin()); } 258 */ begin()259 iterator begin() 260 { return iterator(this->MultiallocationChain::begin()); } 261 /* 262 iterator end() 263 { return iterator(holder_.end()); } 264 265 iterator last() 266 { return iterator(holder_.last()); } 267 268 size_type size() const 269 { return holder_.size(); } 270 271 void clear() 272 { holder_.clear(); } 273 */ insert_after(iterator it,pointer m)274 iterator insert_after(iterator it, pointer m) 275 { return iterator(this->MultiallocationChain::insert_after(it.base(), m)); } 276 iterator_to(const pointer & p)277 static iterator iterator_to(const pointer &p) 278 { return iterator(MultiallocationChain::iterator_to(p)); } 279 extract_data()280 std::pair<pointer, pointer> extract_data() 281 { 282 std::pair<void_pointer, void_pointer> data(this->MultiallocationChain::extract_data()); 283 return std::pair<pointer, pointer>(cast(data.first), cast(data.second)); 284 } 285 /* 286 MultiallocationChain &extract_multiallocation_chain() 287 { return holder_; }*/ 288 }; 289 290 }}} 291 292 // namespace container_detail { 293 // namespace container { 294 // namespace boost { 295 296 #include <boost/container/detail/config_end.hpp> 297 298 #endif //BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP 299