1 ////////////////////////////////////////////////////////////////////////////// 2 // 3 // (C) Copyright Ion Gaztanaga 2008-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_POOLED_NODE_ALLOCATOR_HPP 12 #define BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_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 #include <boost/container/container_fwd.hpp> 25 #include <boost/container/throw_exception.hpp> 26 #include <boost/container/detail/node_pool.hpp> 27 #include <boost/container/detail/mpl.hpp> 28 #include <boost/container/detail/multiallocation_chain.hpp> 29 #include <boost/container/detail/dlmalloc.hpp> 30 #include <boost/container/detail/singleton.hpp> 31 32 #include <boost/assert.hpp> 33 #include <boost/static_assert.hpp> 34 #include <cstddef> 35 36 namespace boost { 37 namespace container { 38 39 //!An STL node allocator that uses a modified DlMalloc as memory 40 //!source. 41 //! 42 //!This node allocator shares a segregated storage between all instances 43 //!of node_allocator with equal sizeof(T). 44 //! 45 //!NodesPerBlock is the number of nodes allocated at once when the allocator 46 //!runs out of nodes 47 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED 48 template 49 < class T 50 , std::size_t NodesPerBlock = NodeAlloc_nodes_per_block> 51 #else 52 template 53 < class T 54 , std::size_t NodesPerBlock 55 , std::size_t Version> 56 #endif 57 class node_allocator 58 { 59 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 60 //! If Version is 1, the allocator is a STL conforming allocator. If Version is 2, 61 //! the allocator offers advanced expand in place and burst allocation capabilities. 62 public: 63 typedef unsigned int allocation_type; 64 typedef node_allocator<T, NodesPerBlock, Version> self_t; 65 66 static const std::size_t nodes_per_block = NodesPerBlock; 67 68 BOOST_STATIC_ASSERT((Version <=2)); 69 #endif 70 71 public: 72 //------- 73 typedef T value_type; 74 typedef T * pointer; 75 typedef const T * const_pointer; 76 typedef typename ::boost::container:: 77 dtl::unvoid_ref<T>::type reference; 78 typedef typename ::boost::container:: 79 dtl::unvoid_ref<const T>::type const_reference; 80 typedef std::size_t size_type; 81 typedef std::ptrdiff_t difference_type; 82 83 typedef boost::container::dtl:: 84 version_type<self_t, Version> version; 85 86 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 87 typedef boost::container::dtl:: 88 basic_multiallocation_chain<void*> multiallocation_chain_void; 89 typedef boost::container::dtl:: 90 transform_multiallocation_chain 91 <multiallocation_chain_void, T> multiallocation_chain; 92 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 93 94 //!Obtains node_allocator from 95 //!node_allocator 96 template<class T2> 97 struct rebind 98 { 99 typedef node_allocator< T2, NodesPerBlock 100 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 101 , Version 102 #endif 103 > other; 104 }; 105 106 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 107 private: 108 //!Not assignable from related node_allocator 109 template<class T2, std::size_t N2> 110 node_allocator& operator= 111 (const node_allocator<T2, N2>&); 112 #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 113 114 public: 115 116 //!Default constructor node_allocator()117 node_allocator() BOOST_NOEXCEPT_OR_NOTHROW 118 {} 119 120 //!Copy constructor from other node_allocator. node_allocator(const node_allocator &)121 node_allocator(const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW 122 {} 123 124 //!Copy constructor from related node_allocator. 125 template<class T2> node_allocator(const node_allocator<T2,NodesPerBlock,Version> &)126 node_allocator 127 (const node_allocator<T2, NodesPerBlock 128 #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED 129 , Version 130 #endif 131 > &) BOOST_NOEXCEPT_OR_NOTHROW 132 {} 133 134 //!Destructor ~node_allocator()135 ~node_allocator() BOOST_NOEXCEPT_OR_NOTHROW 136 {} 137 138 //!Returns the number of elements that could be allocated. 139 //!Never throws max_size() const140 size_type max_size() const 141 { return size_type(-1)/sizeof(T); } 142 143 //!Allocate memory for an array of count elements. 144 //!Throws std::bad_alloc if there is no enough memory allocate(size_type count,const void * =0)145 pointer allocate(size_type count, const void * = 0) 146 { 147 if(BOOST_UNLIKELY(count > this->max_size())) 148 boost::container::throw_bad_alloc(); 149 150 if(Version == 1 && count == 1){ 151 typedef dtl::shared_node_pool 152 <sizeof(T), NodesPerBlock> shared_pool_t; 153 typedef dtl::singleton_default<shared_pool_t> singleton_t; 154 return pointer(static_cast<T*>(singleton_t::instance().allocate_node())); 155 } 156 else{ 157 void *ret = dlmalloc_malloc(count*sizeof(T)); 158 if(BOOST_UNLIKELY(!ret)) 159 boost::container::throw_bad_alloc(); 160 return static_cast<pointer>(ret); 161 } 162 } 163 164 //!Deallocate allocated memory. 165 //!Never throws deallocate(const pointer & ptr,size_type count)166 void deallocate(const pointer &ptr, size_type count) BOOST_NOEXCEPT_OR_NOTHROW 167 { 168 (void)count; 169 if(Version == 1 && count == 1){ 170 typedef dtl::shared_node_pool 171 <sizeof(T), NodesPerBlock> shared_pool_t; 172 typedef dtl::singleton_default<shared_pool_t> singleton_t; 173 singleton_t::instance().deallocate_node(ptr); 174 } 175 else{ 176 dlmalloc_free(ptr); 177 } 178 } 179 180 //!Deallocates all free blocks of the pool deallocate_free_blocks()181 static void deallocate_free_blocks() BOOST_NOEXCEPT_OR_NOTHROW 182 { 183 typedef dtl::shared_node_pool 184 <sizeof(T), NodesPerBlock> shared_pool_t; 185 typedef dtl::singleton_default<shared_pool_t> singleton_t; 186 singleton_t::instance().deallocate_free_blocks(); 187 } 188 allocation_command(allocation_type command,size_type limit_size,size_type & prefer_in_recvd_out_size,pointer & reuse)189 pointer allocation_command 190 (allocation_type command, size_type limit_size, size_type &prefer_in_recvd_out_size, pointer &reuse) 191 { 192 BOOST_STATIC_ASSERT(( Version > 1 )); 193 pointer ret = this->priv_allocation_command(command, limit_size, prefer_in_recvd_out_size, reuse); 194 if(BOOST_UNLIKELY(!ret && !(command & BOOST_CONTAINER_NOTHROW_ALLOCATION))) 195 boost::container::throw_bad_alloc(); 196 return ret; 197 } 198 199 //!Returns maximum the number of objects the previously allocated memory 200 //!pointed by p can hold. size(pointer p) const201 size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW 202 { 203 BOOST_STATIC_ASSERT(( Version > 1 )); 204 return dlmalloc_size(p); 205 } 206 207 //!Allocates just one object. Memory allocated with this function 208 //!must be deallocated only with deallocate_one(). 209 //!Throws bad_alloc if there is no enough memory allocate_one()210 pointer allocate_one() 211 { 212 BOOST_STATIC_ASSERT(( Version > 1 )); 213 typedef dtl::shared_node_pool 214 <sizeof(T), NodesPerBlock> shared_pool_t; 215 typedef dtl::singleton_default<shared_pool_t> singleton_t; 216 return (pointer)singleton_t::instance().allocate_node(); 217 } 218 219 //!Allocates many elements of size == 1. 220 //!Elements must be individually deallocated with deallocate_one() allocate_individual(std::size_t num_elements,multiallocation_chain & chain)221 void allocate_individual(std::size_t num_elements, multiallocation_chain &chain) 222 { 223 BOOST_STATIC_ASSERT(( Version > 1 )); 224 typedef dtl::shared_node_pool 225 <sizeof(T), NodesPerBlock> shared_pool_t; 226 typedef dtl::singleton_default<shared_pool_t> singleton_t; 227 typename shared_pool_t::multiallocation_chain ch; 228 singleton_t::instance().allocate_nodes(num_elements, ch); 229 chain.incorporate_after(chain.before_begin(), (T*)&*ch.begin(), (T*)&*ch.last(), ch.size()); 230 } 231 232 //!Deallocates memory previously allocated with allocate_one(). 233 //!You should never use deallocate_one to deallocate memory allocated 234 //!with other functions different from allocate_one(). Never throws deallocate_one(pointer p)235 void deallocate_one(pointer p) BOOST_NOEXCEPT_OR_NOTHROW 236 { 237 BOOST_STATIC_ASSERT(( Version > 1 )); 238 typedef dtl::shared_node_pool 239 <sizeof(T), NodesPerBlock> shared_pool_t; 240 typedef dtl::singleton_default<shared_pool_t> singleton_t; 241 singleton_t::instance().deallocate_node(p); 242 } 243 deallocate_individual(multiallocation_chain & chain)244 void deallocate_individual(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW 245 { 246 BOOST_STATIC_ASSERT(( Version > 1 )); 247 typedef dtl::shared_node_pool 248 <sizeof(T), NodesPerBlock> shared_pool_t; 249 typedef dtl::singleton_default<shared_pool_t> singleton_t; 250 typename shared_pool_t::multiallocation_chain ch(&*chain.begin(), &*chain.last(), chain.size()); 251 singleton_t::instance().deallocate_nodes(ch); 252 } 253 254 //!Allocates many elements of size elem_size. 255 //!Elements must be individually deallocated with deallocate() allocate_many(size_type elem_size,std::size_t n_elements,multiallocation_chain & chain)256 void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain) 257 { 258 BOOST_STATIC_ASSERT(( Version > 1 )); 259 dlmalloc_memchain ch; 260 BOOST_CONTAINER_MEMCHAIN_INIT(&ch); 261 if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ 262 boost::container::throw_bad_alloc(); 263 } 264 chain.incorporate_after( chain.before_begin() 265 , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) 266 , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) 267 , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch)); 268 } 269 270 //!Allocates n_elements elements, each one of size elem_sizes[i] 271 //!Elements must be individually deallocated with deallocate() allocate_many(const size_type * elem_sizes,size_type n_elements,multiallocation_chain & chain)272 void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain) 273 { 274 BOOST_STATIC_ASSERT(( Version > 1 )); 275 dlmalloc_memchain ch; 276 dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), BOOST_CONTAINER_DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch); 277 if(BOOST_UNLIKELY(BOOST_CONTAINER_MEMCHAIN_EMPTY(&ch))){ 278 boost::container::throw_bad_alloc(); 279 } 280 chain.incorporate_after( chain.before_begin() 281 , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) 282 , (T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) 283 , BOOST_CONTAINER_MEMCHAIN_SIZE(&ch)); 284 } 285 deallocate_many(multiallocation_chain & chain)286 void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW 287 { 288 BOOST_STATIC_ASSERT(( Version > 1 )); 289 void *first = &*chain.begin(); 290 void *last = &*chain.last(); 291 size_t num = chain.size(); 292 dlmalloc_memchain ch; 293 BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, first, last, num); 294 dlmalloc_multidealloc(&ch); 295 } 296 297 //!Swaps allocators. Does not throw. If each allocator is placed in a 298 //!different memory segment, the result is undefined. swap(self_t &,self_t &)299 friend void swap(self_t &, self_t &) BOOST_NOEXCEPT_OR_NOTHROW 300 {} 301 302 //!An allocator always compares to true, as memory allocated with one 303 //!instance can be deallocated by another instance operator ==(const node_allocator &,const node_allocator &)304 friend bool operator==(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW 305 { return true; } 306 307 //!An allocator always compares to false, as memory allocated with one 308 //!instance can be deallocated by another instance operator !=(const node_allocator &,const node_allocator &)309 friend bool operator!=(const node_allocator &, const node_allocator &) BOOST_NOEXCEPT_OR_NOTHROW 310 { return false; } 311 312 private: priv_allocation_command(allocation_type command,std::size_t limit_size,size_type & prefer_in_recvd_out_size,pointer & reuse)313 pointer priv_allocation_command 314 (allocation_type command, std::size_t limit_size 315 ,size_type &prefer_in_recvd_out_size 316 ,pointer &reuse) 317 { 318 std::size_t const preferred_size = prefer_in_recvd_out_size; 319 dlmalloc_command_ret_t ret = {0 , 0}; 320 if((limit_size > this->max_size()) | (preferred_size > this->max_size())){ 321 return pointer(); 322 } 323 std::size_t l_size = limit_size*sizeof(T); 324 std::size_t p_size = preferred_size*sizeof(T); 325 std::size_t r_size; 326 { 327 void* reuse_ptr_void = reuse; 328 ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); 329 reuse = static_cast<T*>(reuse_ptr_void); 330 } 331 prefer_in_recvd_out_size = r_size/sizeof(T); 332 return (pointer)ret.first; 333 } 334 }; 335 336 } //namespace container { 337 } //namespace boost { 338 339 #include <boost/container/detail/config_end.hpp> 340 341 #endif //#ifndef BOOST_CONTAINER_POOLED_NODE_ALLOCATOR_HPP 342