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_ADAPTIVE_NODE_POOL_IMPL_HPP
12 #define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_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
25 // container
26 #include <boost/container/container_fwd.hpp>
27 #include <boost/container/throw_exception.hpp>
28 // container/detail
29 #include <boost/container/detail/pool_common.hpp>
30 #include <boost/container/detail/iterator.hpp>
31 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
32 #include <boost/container/detail/math_functions.hpp>
33 #include <boost/container/detail/mpl.hpp>
34 #include <boost/move/detail/to_raw_pointer.hpp>
35 #include <boost/container/detail/type_traits.hpp>
36 // intrusive
37 #include <boost/intrusive/pointer_traits.hpp>
38 #include <boost/intrusive/set.hpp>
39 #include <boost/intrusive/list.hpp>
40 #include <boost/intrusive/slist.hpp>
41 // other
42 #include <boost/assert.hpp>
43 #include <boost/core/no_exceptions_support.hpp>
44 #include <cstddef>
45
46 namespace boost {
47 namespace container {
48
49 namespace adaptive_pool_flag {
50
51 static const unsigned int none = 0u;
52 static const unsigned int align_only = 1u << 0u;
53 static const unsigned int size_ordered = 1u << 1u;
54 static const unsigned int address_ordered = 1u << 2u;
55
56 } //namespace adaptive_pool_flag{
57
58 namespace dtl {
59
60 template<class size_type>
61 struct hdr_offset_holder_t
62 {
hdr_offset_holder_tboost::container::dtl::hdr_offset_holder_t63 hdr_offset_holder_t(size_type offset = 0)
64 : hdr_offset(offset)
65 {}
66 size_type hdr_offset;
67 };
68
69 template<class SizeType, unsigned int Flags>
70 struct less_func;
71
72 template<class SizeType>
73 struct less_func<SizeType, adaptive_pool_flag::none>
74 {
lessboost::container::dtl::less_func75 static bool less(SizeType, SizeType, const void *, const void *)
76 { return true; }
77 };
78
79 template<class SizeType>
80 struct less_func<SizeType, adaptive_pool_flag::size_ordered>
81 {
lessboost::container::dtl::less_func82 static bool less(SizeType ls, SizeType rs, const void *, const void *)
83 { return ls < rs; }
84 };
85
86 template<class SizeType>
87 struct less_func<SizeType, adaptive_pool_flag::address_ordered>
88 {
lessboost::container::dtl::less_func89 static bool less(SizeType, SizeType, const void *la, const void *ra)
90 { return la < ra; }
91 };
92
93 template<class SizeType>
94 struct less_func<SizeType, adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered>
95 {
lessboost::container::dtl::less_func96 static bool less(SizeType ls, SizeType rs, const void *la, const void *ra)
97 { return (ls < rs) || ((ls == rs) && (la < ra)); }
98 };
99
100 template<class VoidPointer, class SizeType, unsigned OrderFlags>
101 struct block_container_traits
102 {
103 typedef typename bi::make_set_base_hook
104 < bi::void_pointer<VoidPointer>
105 , bi::optimize_size<true>
106 , bi::link_mode<bi::normal_link> >::type hook_t;
107
108 template<class T>
109 struct container
110 {
111 typedef typename bi::make_multiset
112 <T, bi::base_hook<hook_t>, bi::size_type<SizeType> >::type type;
113 };
114
115 template<class Container>
reinsert_was_usedboost::container::dtl::block_container_traits116 static void reinsert_was_used(Container &container, typename Container::reference v, bool)
117 {
118 typedef typename Container::const_iterator const_block_iterator;
119 typedef typename Container::iterator block_iterator;
120 typedef typename Container::value_compare value_compare;
121
122 const block_iterator this_block(Container::s_iterator_to(v));
123 const const_block_iterator cendit(container.cend());
124 block_iterator next_block(this_block);
125
126 if(++next_block != cendit && value_compare()(*next_block, v)){
127 const_block_iterator next2_block(next_block);
128 //Test if v should be swapped with next (optimization)
129 if(++next2_block == cendit || !value_compare()(*next2_block, v)){
130 v.swap_nodes(*next_block);
131 BOOST_ASSERT(++next_block == this_block);
132 }
133 else{
134 container.erase(this_block);
135 container.insert(v);
136 }
137 }
138 }
139
140 template<class Container>
insert_was_emptyboost::container::dtl::block_container_traits141 static void insert_was_empty(Container &container, typename Container::value_type &v, bool)
142 {
143 container.insert(v);
144 }
145
146 template<class Container>
erase_firstboost::container::dtl::block_container_traits147 static void erase_first(Container &container)
148 {
149 container.erase(container.cbegin());
150 }
151
152 template<class Container>
erase_lastboost::container::dtl::block_container_traits153 static void erase_last(Container &container)
154 {
155 container.erase(--container.cend());
156 }
157 };
158
159 template<class VoidPointer, class SizeType>
160 struct block_container_traits<VoidPointer, SizeType, 0u>
161 {
162 typedef typename bi::make_list_base_hook
163 < bi::void_pointer<VoidPointer>
164 , bi::link_mode<bi::normal_link> >::type hook_t;
165
166 template<class T>
167 struct container
168 {
169 typedef typename bi::make_list
170 <T, bi::base_hook<hook_t>, bi::size_type<SizeType>, bi::constant_time_size<false> >::type type;
171 };
172
173 template<class Container>
reinsert_was_usedboost::container::dtl::block_container_traits174 static void reinsert_was_used(Container &container, typename Container::value_type &v, bool is_full)
175 {
176 if(is_full){
177 container.erase(Container::s_iterator_to(v));
178 container.push_back(v);
179 }
180 }
181
182 template<class Container>
insert_was_emptyboost::container::dtl::block_container_traits183 static void insert_was_empty(Container &container, typename Container::value_type &v, bool is_full)
184 {
185 if(is_full){
186 container.push_back(v);
187 }
188 else{
189 container.push_front(v);
190 }
191 }
192
193 template<class Container>
erase_firstboost::container::dtl::block_container_traits194 static void erase_first(Container &container)
195 {
196 container.pop_front();
197 }
198
199 template<class Container>
erase_lastboost::container::dtl::block_container_traits200 static void erase_last(Container &container)
201 {
202 container.pop_back();
203 }
204 };
205
206 /////////////////////////////
207 //
208 // adaptive_pool_types
209 //
210 /////////////////////////////
211 template<class MultiallocationChain, class VoidPointer, class SizeType, unsigned int Flags>
212 struct adaptive_pool_types
213 {
214 typedef VoidPointer void_pointer;
215 static const unsigned ordered = (Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered));
216 typedef block_container_traits<VoidPointer, SizeType, ordered> block_container_traits_t;
217 typedef typename block_container_traits_t::hook_t hook_t;
218 typedef hdr_offset_holder_t<SizeType> hdr_offset_holder;
219 static const unsigned int order_flags = Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered);
220 typedef MultiallocationChain free_nodes_t;
221
222 struct block_info_t
223 : public hdr_offset_holder,
224 public hook_t
225 {
226 //An intrusive list of free node from this block
227 free_nodes_t free_nodes;
operator <boost::container::dtl::adaptive_pool_types228 friend bool operator <(const block_info_t &l, const block_info_t &r)
229 {
230 return less_func<SizeType, order_flags>::
231 less(l.free_nodes.size(), r.free_nodes.size(), &l , &r);
232 }
233
operator ==boost::container::dtl::adaptive_pool_types234 friend bool operator ==(const block_info_t &l, const block_info_t &r)
235 { return &l == &r; }
236 };
237 typedef typename block_container_traits_t:: template container<block_info_t>::type block_container_t;
238 };
239
240
241 /////////////////////////////////////////////
242 //
243 // candidate_power_of_2_ct
244 //
245 /////////////////////////////////////////////
246 template< std::size_t alignment
247 , std::size_t real_node_size
248 , std::size_t payload_per_allocation
249 , std::size_t min_elements_per_block
250 , std::size_t hdr_size
251 , std::size_t hdr_offset_size
252 , std::size_t overhead_percent>
253 struct candidate_power_of_2_ct_helper
254 {
255 static const std::size_t hdr_subblock_elements_alone = (alignment - hdr_size - payload_per_allocation)/real_node_size;
256 static const std::size_t hdr_subblock_elements_first = (alignment - hdr_size - payload_per_allocation)/real_node_size;
257 static const std::size_t elements_per_b_subblock_mid = (alignment - hdr_offset_size)/real_node_size;
258 static const std::size_t elements_per_b_subblock_end = (alignment - hdr_offset_size - payload_per_allocation)/real_node_size;
259 static const std::size_t num_b_subblock =
260 hdr_subblock_elements_alone >= min_elements_per_block
261 ? 0
262 : ( ((hdr_subblock_elements_first + elements_per_b_subblock_end) >= min_elements_per_block)
263 ? 1
264 : 2 + (min_elements_per_block - hdr_subblock_elements_first - elements_per_b_subblock_end - 1)/elements_per_b_subblock_mid
265 )
266 ;
267
268 static const std::size_t num_b_subblock_mid = (num_b_subblock > 1) ? (num_b_subblock - 1) : 0;
269
270 static const std::size_t total_nodes = (num_b_subblock == 0)
271 ? hdr_subblock_elements_alone
272 : ( (num_b_subblock == 1)
273 ? (hdr_subblock_elements_first + elements_per_b_subblock_end)
274 : (hdr_subblock_elements_first + num_b_subblock_mid*elements_per_b_subblock_mid + elements_per_b_subblock_end)
275 )
276 ;
277 static const std::size_t total_data = total_nodes*real_node_size;
278 static const std::size_t total_size = alignment*(num_b_subblock+1);
279 static const bool overhead_satisfied = (total_size - total_data)*100/total_size < overhead_percent;
280 };
281
282 template< std::size_t initial_alignment
283 , std::size_t real_node_size
284 , std::size_t payload_per_allocation
285 , std::size_t min_elements_per_block
286 , std::size_t hdr_size
287 , std::size_t hdr_offset_size
288 , std::size_t overhead_percent
289 , bool Loop = true>
290 struct candidate_power_of_2_ct
291 {
292 typedef candidate_power_of_2_ct_helper
293 < initial_alignment
294 , real_node_size
295 , payload_per_allocation
296 , min_elements_per_block
297 , hdr_size
298 , hdr_offset_size
299 , overhead_percent> helper_t;
300
301 static const std::size_t candidate_power_of_2 = initial_alignment << std::size_t(!helper_t::overhead_satisfied);
302
303 typedef typename candidate_power_of_2_ct
304 < candidate_power_of_2
305 , real_node_size
306 , payload_per_allocation
307 , min_elements_per_block
308 , hdr_size
309 , hdr_offset_size
310 , overhead_percent
311 , !helper_t::overhead_satisfied
312 >::type type;
313
314 static const std::size_t alignment = type::alignment;
315 static const std::size_t num_subblocks = type::num_subblocks;
316 static const std::size_t real_num_node = type::real_num_node;
317 };
318
319 template< std::size_t initial_alignment
320 , std::size_t real_node_size
321 , std::size_t payload_per_allocation
322 , std::size_t min_elements_per_block
323 , std::size_t hdr_size
324 , std::size_t hdr_offset_size
325 , std::size_t overhead_percent
326 >
327 struct candidate_power_of_2_ct
328 < initial_alignment
329 , real_node_size
330 , payload_per_allocation
331 , min_elements_per_block
332 , hdr_size
333 , hdr_offset_size
334 , overhead_percent
335 , false>
336 {
337 typedef candidate_power_of_2_ct
338 < initial_alignment
339 , real_node_size
340 , payload_per_allocation
341 , min_elements_per_block
342 , hdr_size
343 , hdr_offset_size
344 , overhead_percent
345 , false> type;
346
347 typedef candidate_power_of_2_ct_helper
348 < initial_alignment
349 , real_node_size
350 , payload_per_allocation
351 , min_elements_per_block
352 , hdr_size
353 , hdr_offset_size
354 , overhead_percent> helper_t;
355
356 static const std::size_t alignment = initial_alignment;
357 static const std::size_t num_subblocks = helper_t::num_b_subblock+1;
358 static const std::size_t real_num_node = helper_t::total_nodes;
359 };
360
361 /////////////////////////////////////////////
362 //
363 // candidate_power_of_2_rt
364 //
365 /////////////////////////////////////////////
candidate_power_of_2_rt(std::size_t initial_alignment,std::size_t real_node_size,std::size_t payload_per_allocation,std::size_t min_elements_per_block,std::size_t hdr_size,std::size_t hdr_offset_size,std::size_t overhead_percent,std::size_t & alignment,std::size_t & num_subblocks,std::size_t & real_num_node)366 inline void candidate_power_of_2_rt ( std::size_t initial_alignment
367 , std::size_t real_node_size
368 , std::size_t payload_per_allocation
369 , std::size_t min_elements_per_block
370 , std::size_t hdr_size
371 , std::size_t hdr_offset_size
372 , std::size_t overhead_percent
373 , std::size_t &alignment
374 , std::size_t &num_subblocks
375 , std::size_t &real_num_node)
376 {
377 bool overhead_satisfied = false;
378 std::size_t num_b_subblock = 0;
379 std::size_t total_nodes = 0;
380
381 while(!overhead_satisfied)
382 {
383 std::size_t hdr_subblock_elements_alone = (initial_alignment - hdr_size - payload_per_allocation)/real_node_size;
384 std::size_t hdr_subblock_elements_first = (initial_alignment - hdr_size - payload_per_allocation)/real_node_size;
385 std::size_t elements_per_b_subblock_mid = (initial_alignment - hdr_offset_size)/real_node_size;
386 std::size_t elements_per_b_subblock_end = (initial_alignment - hdr_offset_size - payload_per_allocation)/real_node_size;
387
388 num_b_subblock =
389 hdr_subblock_elements_alone >= min_elements_per_block
390 ? 0
391 : ( ((hdr_subblock_elements_first + elements_per_b_subblock_end) >= min_elements_per_block)
392 ? 1
393 : 2 + (min_elements_per_block - hdr_subblock_elements_first - elements_per_b_subblock_end - 1)/elements_per_b_subblock_mid
394 )
395 ;
396
397 std::size_t num_b_subblock_mid = (num_b_subblock > 1) ? (num_b_subblock - 1) : 0;
398
399 total_nodes = (num_b_subblock == 0)
400 ? hdr_subblock_elements_alone
401 : ( (num_b_subblock == 1)
402 ? (hdr_subblock_elements_first + elements_per_b_subblock_end)
403 : (hdr_subblock_elements_first + num_b_subblock_mid*elements_per_b_subblock_mid + elements_per_b_subblock_end)
404 )
405 ;
406 std::size_t total_data = total_nodes*real_node_size;
407 std::size_t total_size = initial_alignment*(num_b_subblock+1);
408 overhead_satisfied = (total_size - total_data)*100/total_size < overhead_percent;
409 initial_alignment = initial_alignment << std::size_t(!overhead_satisfied);
410 }
411 alignment = initial_alignment;
412 num_subblocks = num_b_subblock+1;
413 real_num_node = total_nodes;
414 }
415
416 /////////////////////////////////////////////
417 //
418 // private_adaptive_node_pool_impl_common
419 //
420 /////////////////////////////////////////////
421 template< class SegmentManagerBase, unsigned int Flags>
422 class private_adaptive_node_pool_impl_common
423 {
424 public:
425 //!Segment manager typedef
426 typedef SegmentManagerBase segment_manager_base_type;
427 typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain;
428 typedef typename SegmentManagerBase::size_type size_type;
429 //Flags
430 //align_only
431 static const bool AlignOnly = (Flags & adaptive_pool_flag::align_only) != 0;
432 typedef bool_<AlignOnly> IsAlignOnly;
433 typedef true_ AlignOnlyTrue;
434 typedef false_ AlignOnlyFalse;
435
436 typedef typename SegmentManagerBase::void_pointer void_pointer;
437 static const typename SegmentManagerBase::
438 size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation;
439
440 typedef typename boost::intrusive::pointer_traits
441 <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t;
442
443 protected:
444 typedef adaptive_pool_types
445 <multiallocation_chain, void_pointer, size_type, Flags> adaptive_pool_types_t;
446 typedef typename adaptive_pool_types_t::free_nodes_t free_nodes_t;
447 typedef typename adaptive_pool_types_t::block_info_t block_info_t;
448 typedef typename adaptive_pool_types_t::block_container_t block_container_t;
449 typedef typename adaptive_pool_types_t::block_container_traits_t block_container_traits_t;
450 typedef typename block_container_t::iterator block_iterator;
451 typedef typename block_container_t::const_iterator const_block_iterator;
452 typedef typename adaptive_pool_types_t::hdr_offset_holder hdr_offset_holder;
453 typedef private_adaptive_node_pool_impl_common this_type;
454
455 static const size_type MaxAlign = alignment_of<void_pointer>::value;
456 static const size_type HdrSize = ((sizeof(block_info_t)-1)/MaxAlign+1)*MaxAlign;
457 static const size_type HdrOffsetSize = ((sizeof(hdr_offset_holder)-1)/MaxAlign+1)*MaxAlign;
458
459 segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager
460 block_container_t m_block_container; //Intrusive block list
461 size_type m_totally_free_blocks; //Free blocks
462
463 class block_destroyer;
464 friend class block_destroyer;
465
466 class block_destroyer
467 {
468 public:
block_destroyer(const this_type * impl,multiallocation_chain & chain,const size_type num_subblocks,const size_type real_block_alignment,const size_type real_num_node)469 block_destroyer(const this_type *impl, multiallocation_chain &chain, const size_type num_subblocks, const size_type real_block_alignment, const size_type real_num_node)
470 : mp_impl(impl), m_chain(chain), m_num_subblocks(num_subblocks), m_real_block_alignment(real_block_alignment), m_real_num_node(real_num_node)
471 {}
472
operator ()(typename block_container_t::pointer to_deallocate)473 void operator()(typename block_container_t::pointer to_deallocate)
474 { return this->do_destroy(to_deallocate, IsAlignOnly()); }
475
476 private:
do_destroy(typename block_container_t::pointer to_deallocate,AlignOnlyTrue)477 void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyTrue)
478 {
479 BOOST_ASSERT(to_deallocate->free_nodes.size() == m_real_num_node);
480 m_chain.push_back(to_deallocate);
481 }
482
do_destroy(typename block_container_t::pointer to_deallocate,AlignOnlyFalse)483 void do_destroy(typename block_container_t::pointer to_deallocate, AlignOnlyFalse)
484 {
485 BOOST_ASSERT(to_deallocate->free_nodes.size() == m_real_num_node);
486 BOOST_ASSERT(0 == to_deallocate->hdr_offset);
487 hdr_offset_holder *hdr_off_holder =
488 mp_impl->priv_first_subblock_from_block(boost::movelib::to_raw_pointer(to_deallocate), m_num_subblocks, m_real_block_alignment);
489 m_chain.push_back(hdr_off_holder);
490 }
491
492 const this_type *mp_impl;
493 multiallocation_chain &m_chain;
494 const size_type m_num_subblocks;
495 const size_type m_real_block_alignment;
496 const size_type m_real_num_node;
497 };
498
499 //This macro will activate invariant checking. Slow, but helpful for debugging the code.
500 //#define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
priv_invariants(const size_type real_num_node,const size_type num_subblocks,const size_type real_block_alignment) const501 void priv_invariants(const size_type real_num_node, const size_type num_subblocks, const size_type real_block_alignment) const
502 {
503 (void)real_num_node; (void)num_subblocks; (void)real_block_alignment;
504 #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
505 //Check that the total totally free blocks are correct
506 BOOST_ASSERT(m_block_container.size() >= m_totally_free_blocks);
507
508 const const_block_iterator itend(m_block_container.cend());
509 const const_block_iterator itbeg(m_block_container.cbegin());
510
511 { //Try to do checks in a single iteration
512 const_block_iterator it(itbeg);
513 size_type total_free_nodes = 0;
514 size_type total_free_blocks = 0u;
515 for(; it != itend; ++it){
516 if(it != itbeg){
517 //Check order invariant
518 const_block_iterator prev(it);
519 --prev;
520 BOOST_ASSERT(!(m_block_container.key_comp()(*it, *prev)));
521 (void)prev; (void)it;
522 }
523
524 //free_nodes invariant
525 const size_type free_nodes = it->free_nodes.size();
526 BOOST_ASSERT(free_nodes <= real_num_node);
527 BOOST_ASSERT(free_nodes != 0);
528
529 //Acummulate total_free_nodes and total_free_blocks
530 total_free_nodes += free_nodes;
531 total_free_blocks += it->free_nodes.size() == real_num_node;
532
533 if (!AlignOnly) {
534 //Check that header offsets are correct
535 hdr_offset_holder *hdr_off_holder = this->priv_first_subblock_from_block(const_cast<block_info_t *>(&*it), num_subblocks, real_block_alignment);
536 for (size_type i = 0, max = num_subblocks; i < max; ++i) {
537 const size_type offset = reinterpret_cast<char*>(const_cast<block_info_t *>(&*it)) - reinterpret_cast<char*>(hdr_off_holder);
538 (void)offset;
539 BOOST_ASSERT(hdr_off_holder->hdr_offset == offset);
540 BOOST_ASSERT(0 == (reinterpret_cast<std::size_t>(hdr_off_holder) & (real_block_alignment - 1)));
541 BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1)));
542 hdr_off_holder = reinterpret_cast<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + real_block_alignment);
543 }
544 }
545 }
546 BOOST_ASSERT(total_free_blocks == m_totally_free_blocks);
547 BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*real_num_node);
548 }
549 #endif
550 }
551
priv_deallocate_free_blocks(const size_type max_free_blocks,const size_type real_num_node,const size_type num_subblocks,const size_type real_block_alignment)552 void priv_deallocate_free_blocks( const size_type max_free_blocks, const size_type real_num_node
553 , const size_type num_subblocks, const size_type real_block_alignment)
554 { //Trampoline function to ease inlining
555 if(m_totally_free_blocks > max_free_blocks){
556 this->priv_deallocate_free_blocks_impl(max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
557 }
558 }
559
priv_first_subblock_from_block(block_info_t * block,const size_type num_subblocks,const size_type real_block_alignment) const560 hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment) const
561 { return this->priv_first_subblock_from_block(block, num_subblocks, real_block_alignment, IsAlignOnly()); }
562
priv_first_subblock_from_block(block_info_t * block,const size_type num_subblocks,const size_type real_block_alignment,AlignOnlyFalse) const563 hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment, AlignOnlyFalse) const
564 {
565 hdr_offset_holder *const hdr_off_holder = reinterpret_cast<hdr_offset_holder*>
566 (reinterpret_cast<char*>(block) - (num_subblocks-1)*real_block_alignment);
567 BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(block) - reinterpret_cast<char*>(hdr_off_holder)));
568 BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (real_block_alignment - 1)));
569 BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1)));
570 return hdr_off_holder;
571 }
572
priv_first_subblock_from_block(block_info_t * block,const size_type num_subblocks,const size_type real_block_alignment,AlignOnlyTrue) const573 hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block, const size_type num_subblocks, const size_type real_block_alignment, AlignOnlyTrue) const
574 {
575 (void)num_subblocks; (void)real_block_alignment;
576 return reinterpret_cast<hdr_offset_holder*>(block);
577 }
578
priv_deallocate_free_blocks_impl(const size_type max_free_blocks,const size_type real_num_node,const size_type num_subblocks,const size_type real_block_alignment)579 void priv_deallocate_free_blocks_impl( const size_type max_free_blocks, const size_type real_num_node
580 , const size_type num_subblocks, const size_type real_block_alignment)
581 {
582 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
583 //Now check if we've reached the free nodes limit
584 //and check if we have free blocks. If so, deallocate as much
585 //as we can to stay below the limit
586 multiallocation_chain chain;
587 {
588 if(Flags & adaptive_pool_flag::size_ordered){
589 const_block_iterator it = m_block_container.cend();
590 --it;
591 size_type totally_free_blocks = m_totally_free_blocks;
592
593 for( ; totally_free_blocks > max_free_blocks; --totally_free_blocks){
594 BOOST_ASSERT(it->free_nodes.size() == real_num_node);
595 void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it), num_subblocks, real_block_alignment);
596 --it;
597 block_container_traits_t::erase_last(m_block_container);
598 chain.push_front(void_pointer(addr));
599 }
600 }
601 else{
602 const_block_iterator it = m_block_container.cend();
603 size_type totally_free_blocks = m_totally_free_blocks;
604
605 while(totally_free_blocks > max_free_blocks){
606 --it;
607 if(it->free_nodes.size() == real_num_node){
608 void *addr = priv_first_subblock_from_block(const_cast<block_info_t*>(&*it), num_subblocks, real_block_alignment);
609 it = m_block_container.erase(it);
610 chain.push_front(void_pointer(addr));
611 --totally_free_blocks;
612 }
613 }
614 }
615 BOOST_ASSERT((m_totally_free_blocks - max_free_blocks) == chain.size());
616 m_totally_free_blocks = max_free_blocks;
617 }
618 this->mp_segment_mngr_base->deallocate_many(chain);
619 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
620 }
621
priv_fill_chain_remaining_to_block(multiallocation_chain & chain,size_type target_elem_in_chain,block_info_t & c_info,char * mem_address,size_type max_node_in_mem,const size_type real_node_size)622 void priv_fill_chain_remaining_to_block
623 ( multiallocation_chain &chain, size_type target_elem_in_chain, block_info_t &c_info
624 , char *mem_address, size_type max_node_in_mem
625 , const size_type real_node_size)
626 {
627 BOOST_ASSERT(chain.size() <= target_elem_in_chain);
628
629 //First add all possible nodes to the chain
630 const size_type left = target_elem_in_chain - chain.size();
631 const size_type add_to_chain = (max_node_in_mem < left) ? max_node_in_mem : left;
632 char *free_mem_address = static_cast<char *>(boost::movelib::to_raw_pointer
633 (chain.incorporate_after(chain.last(), void_pointer(mem_address), real_node_size, add_to_chain)));
634 //Now store remaining nodes in the free list
635 if(const size_type free = max_node_in_mem - add_to_chain){
636 free_nodes_t & free_nodes = c_info.free_nodes;
637 free_nodes.incorporate_after(free_nodes.last(), void_pointer(free_mem_address), real_node_size, free);
638 }
639 }
640
641 //!Allocates a several blocks of nodes. Can throw
priv_append_from_new_blocks(size_type min_elements,multiallocation_chain & chain,const size_type max_free_blocks,const size_type real_block_alignment,const size_type real_node_size,const size_type real_num_node,const size_type num_subblocks,AlignOnlyTrue)642 void priv_append_from_new_blocks( size_type min_elements, multiallocation_chain &chain
643 , const size_type max_free_blocks
644 , const size_type real_block_alignment, const size_type real_node_size
645 , const size_type real_num_node, const size_type num_subblocks
646 , AlignOnlyTrue)
647 {
648 (void)num_subblocks;
649 BOOST_ASSERT(m_block_container.empty());
650 BOOST_ASSERT(min_elements > 0);
651 const size_type n = (min_elements - 1)/real_num_node + 1;
652 const size_type real_block_size = real_block_alignment - PayloadPerAllocation;
653 const size_type target_elem_in_chain = chain.size() + min_elements;
654 for(size_type i = 0; i != n; ++i){
655 //We allocate a new NodeBlock and put it the last
656 //element of the tree
657 char *mem_address = static_cast<char*>
658 (mp_segment_mngr_base->allocate_aligned(real_block_size, real_block_alignment));
659 if(!mem_address){
660 //In case of error, free memory deallocating all nodes (the new ones allocated
661 //in this function plus previously stored nodes in chain).
662 this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
663 throw_bad_alloc();
664 }
665 block_info_t &c_info = *new(mem_address)block_info_t();
666 mem_address += HdrSize;
667 this->priv_fill_chain_remaining_to_block(chain, target_elem_in_chain, c_info, mem_address, real_num_node, real_node_size);
668 const size_type free_nodes = c_info.free_nodes.size();
669 if(free_nodes){
670 const bool is_full = free_nodes == real_num_node;
671 BOOST_ASSERT(free_nodes < real_num_node);
672 m_totally_free_blocks += static_cast<size_type>(is_full);
673 block_container_traits_t::insert_was_empty(m_block_container, c_info, is_full);
674 }
675 }
676 }
677
priv_append_from_new_blocks(size_type min_elements,multiallocation_chain & chain,const size_type max_free_blocks,const size_type real_block_alignment,const size_type real_node_size,const size_type real_num_node,const size_type num_subblocks,AlignOnlyFalse)678 void priv_append_from_new_blocks( size_type min_elements, multiallocation_chain &chain
679 , const size_type max_free_blocks
680 , const size_type real_block_alignment, const size_type real_node_size
681 , const size_type real_num_node, const size_type num_subblocks
682 , AlignOnlyFalse)
683 {
684 BOOST_ASSERT(m_block_container.empty());
685 BOOST_ASSERT(min_elements > 0);
686 const size_type n = (min_elements - 1)/real_num_node + 1;
687 const size_type real_block_size = real_block_alignment*num_subblocks - PayloadPerAllocation;
688 const size_type elements_per_subblock_mid = (real_block_alignment - HdrOffsetSize)/real_node_size;
689 const size_type elements_per_subblock_end = (real_block_alignment - HdrOffsetSize - PayloadPerAllocation) / real_node_size;
690 const size_type hdr_subblock_elements = (real_block_alignment - HdrSize - PayloadPerAllocation)/real_node_size;
691 const size_type target_elem_in_chain = chain.size() + min_elements;
692
693 for(size_type i = 0; i != n; ++i){
694 //We allocate a new NodeBlock and put it the last
695 //element of the tree
696 char *mem_address = static_cast<char*>
697 (mp_segment_mngr_base->allocate_aligned(real_block_size, real_block_alignment));
698 if(!mem_address){
699 //In case of error, free memory deallocating all nodes (the new ones allocated
700 //in this function plus previously stored nodes in chain).
701 this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
702 throw_bad_alloc();
703 }
704 //First initialize header information on the last subblock
705 char *hdr_addr = mem_address + real_block_alignment*(num_subblocks-1);
706 block_info_t &c_info = *new(hdr_addr)block_info_t();
707 //Some structural checks
708 BOOST_ASSERT(static_cast<void*>(&static_cast<hdr_offset_holder&>(c_info).hdr_offset) ==
709 static_cast<void*>(&c_info)); (void)c_info;
710 for( size_type subblock = 0, maxsubblock = num_subblocks - 1
711 ; subblock < maxsubblock
712 ; ++subblock, mem_address += real_block_alignment){
713 //Initialize header offset mark
714 new(mem_address) hdr_offset_holder(size_type(hdr_addr - mem_address));
715 const size_type elements_per_subblock = (subblock != (maxsubblock - 1)) ? elements_per_subblock_mid : elements_per_subblock_end;
716 this->priv_fill_chain_remaining_to_block
717 (chain, target_elem_in_chain, c_info, mem_address + HdrOffsetSize, elements_per_subblock, real_node_size);
718 }
719 this->priv_fill_chain_remaining_to_block
720 (chain, target_elem_in_chain, c_info, hdr_addr + HdrSize, hdr_subblock_elements, real_node_size);
721 m_totally_free_blocks += static_cast<size_type>(c_info.free_nodes.size() == real_num_node);
722 if (c_info.free_nodes.size())
723 m_block_container.push_front(c_info);
724 }
725 }
726
727 //!Allocates array of count elements. Can throw
priv_allocate_node(const size_type max_free_blocks,const size_type real_block_alignment,const size_type real_node_size,const size_type real_num_node,const size_type num_subblocks)728 void *priv_allocate_node( const size_type max_free_blocks, const size_type real_block_alignment, const size_type real_node_size
729 , const size_type real_num_node, const size_type num_subblocks)
730 {
731 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
732 //If there are no free nodes we allocate a new block
733 if(!m_block_container.empty()){
734 //We take the first free node the multiset can't be empty
735 free_nodes_t &free_nodes = m_block_container.begin()->free_nodes;
736 BOOST_ASSERT(!free_nodes.empty());
737 const size_type free_nodes_count = free_nodes.size();
738 void *first_node = boost::movelib::to_raw_pointer(free_nodes.pop_front());
739 if(free_nodes.empty()){
740 block_container_traits_t::erase_first(m_block_container);
741 }
742 m_totally_free_blocks -= static_cast<size_type>(free_nodes_count == real_num_node);
743 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
744 return first_node;
745 }
746 else{
747 multiallocation_chain chain;
748 this->priv_append_from_new_blocks
749 (1, chain, max_free_blocks, real_block_alignment, real_node_size, real_num_node, num_subblocks, IsAlignOnly());
750 void *node = boost::movelib::to_raw_pointer(chain.pop_front());
751 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
752 return node;
753 }
754 }
755
priv_allocate_nodes(const size_type n,multiallocation_chain & chain,const size_type max_free_blocks,const size_type real_block_alignment,const size_type real_node_size,const size_type real_num_node,const size_type num_subblocks)756 void priv_allocate_nodes( const size_type n, multiallocation_chain &chain
757 , const size_type max_free_blocks, const size_type real_block_alignment, const size_type real_node_size
758 , const size_type real_num_node, const size_type num_subblocks)
759 {
760 size_type i = 0;
761 BOOST_TRY{
762 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
763 while(i != n){
764 //If there are no free nodes we allocate all needed blocks
765 if (m_block_container.empty()){
766 this->priv_append_from_new_blocks
767 (n - i, chain, max_free_blocks, real_block_alignment, real_node_size, real_num_node, num_subblocks, IsAlignOnly());
768 BOOST_ASSERT(m_block_container.empty() || (++m_block_container.cbegin() == m_block_container.cend()));
769 BOOST_ASSERT(chain.size() == n);
770 break;
771 }
772 free_nodes_t &free_nodes = m_block_container.begin()->free_nodes;
773 const size_type free_nodes_count_before = free_nodes.size();
774 m_totally_free_blocks -= static_cast<size_type>(free_nodes_count_before == real_num_node);
775 const size_type num_left = n-i;
776 const size_type num_elems = (num_left < free_nodes_count_before) ? num_left : free_nodes_count_before;
777 typedef typename free_nodes_t::iterator free_nodes_iterator;
778
779 if(num_left < free_nodes_count_before){
780 const free_nodes_iterator it_bbeg(free_nodes.before_begin());
781 free_nodes_iterator it_bend(it_bbeg);
782 for(size_type j = 0; j != num_elems; ++j){
783 ++it_bend;
784 }
785 free_nodes_iterator it_end = it_bend; ++it_end;
786 free_nodes_iterator it_beg = it_bbeg; ++it_beg;
787 free_nodes.erase_after(it_bbeg, it_end, num_elems);
788 chain.incorporate_after(chain.last(), &*it_beg, &*it_bend, num_elems);
789 //chain.splice_after(chain.last(), free_nodes, it_bbeg, it_bend, num_elems);
790 BOOST_ASSERT(!free_nodes.empty());
791 }
792 else{
793 const free_nodes_iterator it_beg(free_nodes.begin()), it_bend(free_nodes.last());
794 free_nodes.clear();
795 chain.incorporate_after(chain.last(), &*it_beg, &*it_bend, num_elems);
796 block_container_traits_t::erase_first(m_block_container);
797 }
798 i += num_elems;
799 }
800 }
801 BOOST_CATCH(...){
802 this->priv_deallocate_nodes(chain, max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
803 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
804 BOOST_RETHROW
805 }
806 BOOST_CATCH_END
807 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
808 }
809
810 //!Deallocates an array pointed by ptr. Never throws
priv_deallocate_node(void * pElem,const size_type max_free_blocks,const size_type real_num_node,const size_type num_subblocks,const size_type real_block_alignment)811 void priv_deallocate_node( void *pElem
812 , const size_type max_free_blocks, const size_type real_num_node
813 , const size_type num_subblocks, const size_type real_block_alignment)
814 {
815 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
816 block_info_t &block_info = *this->priv_block_from_node(pElem, real_block_alignment);
817 const size_type prev_free_nodes = block_info.free_nodes.size();
818 BOOST_ASSERT(block_info.free_nodes.size() < real_num_node);
819
820 //We put the node at the beginning of the free node list
821 block_info.free_nodes.push_back(void_pointer(pElem));
822
823 //The loop reinserts all blocks except the last one
824 this->priv_reinsert_block(block_info, prev_free_nodes == 0, real_num_node);
825 this->priv_deallocate_free_blocks(max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
826 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
827 }
828
priv_deallocate_nodes(multiallocation_chain & nodes,const size_type max_free_blocks,const size_type real_num_node,const size_type num_subblocks,const size_type real_block_alignment)829 void priv_deallocate_nodes( multiallocation_chain &nodes
830 , const size_type max_free_blocks, const size_type real_num_node
831 , const size_type num_subblocks, const size_type real_block_alignment)
832 {
833 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
834 //To take advantage of node locality, wait until two
835 //nodes belong to different blocks. Only then reinsert
836 //the block of the first node in the block tree.
837 //Cache of the previous block
838 block_info_t *prev_block_info = 0;
839
840 //If block was empty before this call, it's not already
841 //inserted in the block tree.
842 bool prev_block_was_empty = false;
843 typedef typename free_nodes_t::iterator free_nodes_iterator;
844 {
845 const free_nodes_iterator itbb(nodes.before_begin()), ite(nodes.end());
846 free_nodes_iterator itf(nodes.begin()), itbf(itbb);
847 size_type splice_node_count = size_type(-1);
848 while(itf != ite){
849 void *pElem = boost::movelib::to_raw_pointer(boost::movelib::iterator_to_raw_pointer(itf));
850 block_info_t &block_info = *this->priv_block_from_node(pElem, real_block_alignment);
851 BOOST_ASSERT(block_info.free_nodes.size() < real_num_node);
852 ++splice_node_count;
853
854 //If block change is detected calculate the cached block position in the tree
855 if(&block_info != prev_block_info){
856 if(prev_block_info){ //Make sure we skip the initial "dummy" cache
857 free_nodes_iterator it(itbb); ++it;
858 nodes.erase_after(itbb, itf, splice_node_count);
859 prev_block_info->free_nodes.incorporate_after(prev_block_info->free_nodes.last(), &*it, &*itbf, splice_node_count);
860 this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node);
861 splice_node_count = 0;
862 }
863 //Update cache with new data
864 prev_block_was_empty = block_info.free_nodes.empty();
865 prev_block_info = &block_info;
866 }
867 itbf = itf;
868 ++itf;
869 }
870 }
871 if(prev_block_info){
872 //The loop reinserts all blocks except the last one
873 const free_nodes_iterator itfirst(nodes.begin()), itlast(nodes.last());
874 const size_type splice_node_count = nodes.size();
875 nodes.clear();
876 prev_block_info->free_nodes.incorporate_after(prev_block_info->free_nodes.last(), &*itfirst, &*itlast, splice_node_count);
877 this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node);
878 this->priv_deallocate_free_blocks(max_free_blocks, real_num_node, num_subblocks, real_block_alignment);
879 }
880 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
881 }
882
priv_reinsert_block(block_info_t & prev_block_info,const bool prev_block_was_empty,const size_type real_num_node)883 void priv_reinsert_block(block_info_t &prev_block_info, const bool prev_block_was_empty, const size_type real_num_node)
884 {
885 //Cache the free nodes from the block
886 const size_type this_block_free_nodes = prev_block_info.free_nodes.size();
887 const bool is_full = this_block_free_nodes == real_num_node;
888
889 //Update free block count
890 m_totally_free_blocks += static_cast<size_type>(is_full);
891 if(prev_block_was_empty){
892 block_container_traits_t::insert_was_empty(m_block_container, prev_block_info, is_full);
893 }
894 else{
895 block_container_traits_t::reinsert_was_used(m_block_container, prev_block_info, is_full);
896 }
897 }
898
priv_block_from_node(void * node,const size_type real_block_alignment,AlignOnlyFalse) const899 block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyFalse) const
900 {
901 hdr_offset_holder *hdr_off_holder =
902 reinterpret_cast<hdr_offset_holder*>((std::size_t)node & size_type(~(real_block_alignment - 1)));
903 BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (real_block_alignment - 1)));
904 BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (real_block_alignment - 1)));
905 block_info_t *block = reinterpret_cast<block_info_t *>
906 (reinterpret_cast<char*>(hdr_off_holder) + hdr_off_holder->hdr_offset);
907 BOOST_ASSERT(block->hdr_offset == 0);
908 return block;
909 }
910
priv_block_from_node(void * node,const size_type real_block_alignment,AlignOnlyTrue) const911 block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyTrue) const
912 {
913 return (block_info_t *)((std::size_t)node & std::size_t(~(real_block_alignment - 1)));
914 }
915
priv_block_from_node(void * node,const size_type real_block_alignment) const916 block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment) const
917 { return this->priv_block_from_node(node, real_block_alignment, IsAlignOnly()); }
918
919 //!Deallocates all used memory. Never throws
priv_clear(const size_type num_subblocks,const size_type real_block_alignment,const size_type real_num_node)920 void priv_clear(const size_type num_subblocks, const size_type real_block_alignment, const size_type real_num_node)
921 {
922 #ifndef NDEBUG
923 block_iterator it = m_block_container.begin();
924 block_iterator itend = m_block_container.end();
925 size_type n_free_nodes = 0;
926 for(; it != itend; ++it){
927 //Check for memory leak
928 BOOST_ASSERT(it->free_nodes.size() == real_num_node);
929 ++n_free_nodes;
930 }
931 BOOST_ASSERT(n_free_nodes == m_totally_free_blocks);
932 #endif
933 //Check for memory leaks
934 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
935 multiallocation_chain chain;
936 m_block_container.clear_and_dispose(block_destroyer(this, chain, num_subblocks, real_block_alignment, real_num_node));
937 this->mp_segment_mngr_base->deallocate_many(chain);
938 m_totally_free_blocks = 0;
939 this->priv_invariants(real_num_node, num_subblocks, real_block_alignment);
940 }
941
942 public:
private_adaptive_node_pool_impl_common(segment_manager_base_type * segment_mngr_base)943 private_adaptive_node_pool_impl_common(segment_manager_base_type *segment_mngr_base)
944 //General purpose allocator
945 : mp_segment_mngr_base(segment_mngr_base)
946 , m_block_container()
947 , m_totally_free_blocks(0)
948 {}
949
num_free_nodes()950 size_type num_free_nodes()
951 {
952 typedef typename block_container_t::const_iterator citerator;
953 size_type count = 0;
954 citerator it (m_block_container.begin()), itend(m_block_container.end());
955 for(; it != itend; ++it){
956 count += it->free_nodes.size();
957 }
958 return count;
959 }
960
swap(private_adaptive_node_pool_impl_common & other)961 void swap(private_adaptive_node_pool_impl_common &other)
962 {
963 std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base);
964 std::swap(m_totally_free_blocks, other.m_totally_free_blocks);
965 m_block_container.swap(other.m_block_container);
966 }
967
968 //!Returns the segment manager. Never throws
get_segment_manager_base() const969 segment_manager_base_type* get_segment_manager_base()const
970 { return boost::movelib::to_raw_pointer(mp_segment_mngr_base); }
971 };
972
973 template< class SizeType
974 , std::size_t HdrSize
975 , std::size_t PayloadPerAllocation
976 , std::size_t RealNodeSize
977 , std::size_t NodesPerBlock
978 , std::size_t HdrOffsetSize
979 , std::size_t OverheadPercent
980 , bool AlignOnly>
981 struct calculate_alignment_ct
982 {
983 static const std::size_t alignment = upper_power_of_2_ct<SizeType, HdrSize + RealNodeSize*NodesPerBlock>::value;
984 static const std::size_t num_subblocks = 0;
985 static const std::size_t real_num_node = (alignment - PayloadPerAllocation - HdrSize)/RealNodeSize;
986 };
987
988 template< class SizeType
989 , std::size_t HdrSize
990 , std::size_t PayloadPerAllocation
991 , std::size_t RealNodeSize
992 , std::size_t NodesPerBlock
993 , std::size_t HdrOffsetSize
994 , std::size_t OverheadPercent>
995 struct calculate_alignment_ct
996 < SizeType
997 , HdrSize
998 , PayloadPerAllocation
999 , RealNodeSize
1000 , NodesPerBlock
1001 , HdrOffsetSize
1002 , OverheadPercent
1003 , false>
1004 {
1005 typedef typename candidate_power_of_2_ct
1006 < upper_power_of_2_ct<SizeType, HdrSize + PayloadPerAllocation + RealNodeSize>::value
1007 , RealNodeSize
1008 , PayloadPerAllocation
1009 , NodesPerBlock
1010 , HdrSize
1011 , HdrOffsetSize
1012 , OverheadPercent
1013 >::type type;
1014
1015 static const std::size_t alignment = type::alignment;
1016 static const std::size_t num_subblocks = type::num_subblocks;
1017 static const std::size_t real_num_node = type::real_num_node;
1018 };
1019
1020
1021 /////////////////////////////////////////////
1022 //
1023 // private_adaptive_node_pool_impl_ct
1024 //
1025 /////////////////////////////////////////////
1026 template< class SegmentManagerBase
1027 , std::size_t MaxFreeBlocks
1028 , std::size_t NodeSize
1029 , std::size_t NodesPerBlock
1030 , std::size_t OverheadPercent
1031 , unsigned int Flags>
1032 class private_adaptive_node_pool_impl_ct
1033 : public private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags>
1034 {
1035 typedef private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> base_t;
1036
1037 //Non-copyable
1038 private_adaptive_node_pool_impl_ct();
1039 private_adaptive_node_pool_impl_ct(const private_adaptive_node_pool_impl_ct &);
1040 private_adaptive_node_pool_impl_ct &operator=(const private_adaptive_node_pool_impl_ct &);
1041
1042 public:
1043 typedef typename base_t::void_pointer void_pointer;
1044 typedef typename base_t::size_type size_type;
1045 typedef typename base_t::multiallocation_chain multiallocation_chain;
1046 typedef typename base_t::segment_manager_base_type segment_manager_base_type;
1047
1048 static const typename base_t::size_type PayloadPerAllocation = base_t::PayloadPerAllocation;
1049
1050 //align_only
1051 static const bool AlignOnly = base_t::AlignOnly;
1052
1053 private:
1054 static const size_type MaxAlign = base_t::MaxAlign;
1055 static const size_type HdrSize = base_t::HdrSize;
1056 static const size_type HdrOffsetSize = base_t::HdrOffsetSize;
1057
1058 static const size_type RealNodeSize = lcm_ct<NodeSize, alignment_of<void_pointer>::value>::value;
1059
1060 typedef calculate_alignment_ct
1061 < size_type, HdrSize, PayloadPerAllocation
1062 , RealNodeSize, NodesPerBlock, HdrOffsetSize, OverheadPercent, AlignOnly> data_t;
1063
1064 //Round the size to a power of two value.
1065 //This is the total memory size (including payload) that we want to
1066 //allocate from the general-purpose allocator
1067 static const size_type NumSubBlocks = data_t::num_subblocks;
1068 static const size_type RealNumNode = data_t::real_num_node;
1069 static const size_type RealBlockAlignment = data_t::alignment;
1070
1071 public:
1072
1073 //!Constructor from a segment manager. Never throws
private_adaptive_node_pool_impl_ct(typename base_t::segment_manager_base_type * segment_mngr_base)1074 private_adaptive_node_pool_impl_ct(typename base_t::segment_manager_base_type *segment_mngr_base)
1075 //General purpose allocator
1076 : base_t(segment_mngr_base)
1077 {}
1078
1079 //!Destructor. Deallocates all allocated blocks. Never throws
~private_adaptive_node_pool_impl_ct()1080 ~private_adaptive_node_pool_impl_ct()
1081 { this->priv_clear(NumSubBlocks, data_t::alignment, RealNumNode); }
1082
get_real_num_node() const1083 size_type get_real_num_node() const
1084 { return RealNumNode; }
1085
1086 //!Allocates array of count elements. Can throw
allocate_node()1087 void *allocate_node()
1088 {
1089 return this->priv_allocate_node
1090 (MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks);
1091 }
1092
1093 //!Allocates n nodes.
1094 //!Can throw
allocate_nodes(const size_type n,multiallocation_chain & chain)1095 void allocate_nodes(const size_type n, multiallocation_chain &chain)
1096 {
1097 this->priv_allocate_nodes
1098 (n, chain, MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks);
1099 }
1100
1101 //!Deallocates an array pointed by ptr. Never throws
deallocate_node(void * pElem)1102 void deallocate_node(void *pElem)
1103 {
1104 this->priv_deallocate_node(pElem, MaxFreeBlocks, RealNumNode, NumSubBlocks, RealBlockAlignment);
1105 }
1106
1107 //!Deallocates a linked list of nodes. Never throws
deallocate_nodes(multiallocation_chain & nodes)1108 void deallocate_nodes(multiallocation_chain &nodes)
1109 {
1110 this->priv_deallocate_nodes(nodes, MaxFreeBlocks, RealNumNode, NumSubBlocks, data_t::alignment);
1111 }
1112
deallocate_free_blocks()1113 void deallocate_free_blocks()
1114 { this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment); }
1115
1116 //Deprecated, use deallocate_free_blocks
deallocate_free_chunks()1117 void deallocate_free_chunks()
1118 { this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment); }
1119 };
1120
1121 /////////////////////////////////////////////
1122 //
1123 // private_adaptive_node_pool_impl_rt
1124 //
1125 /////////////////////////////////////////////
1126 template<class SizeType>
1127 struct private_adaptive_node_pool_impl_rt_data
1128 {
1129 typedef SizeType size_type;
1130
private_adaptive_node_pool_impl_rt_databoost::container::dtl::private_adaptive_node_pool_impl_rt_data1131 private_adaptive_node_pool_impl_rt_data(size_type max_free_blocks, size_type real_node_size)
1132 : m_max_free_blocks(max_free_blocks), m_real_node_size(real_node_size)
1133 , m_real_block_alignment(), m_num_subblocks(), m_real_num_node()
1134 {}
1135
1136 const size_type m_max_free_blocks;
1137 const size_type m_real_node_size;
1138 //Round the size to a power of two value.
1139 //This is the total memory size (including payload) that we want to
1140 //allocate from the general-purpose allocator
1141 size_type m_real_block_alignment;
1142 size_type m_num_subblocks;
1143 //This is the real number of nodes per block
1144 size_type m_real_num_node;
1145 };
1146
1147
1148 template<class SegmentManagerBase, unsigned int Flags>
1149 class private_adaptive_node_pool_impl_rt
1150 : private private_adaptive_node_pool_impl_rt_data<typename SegmentManagerBase::size_type>
1151 , public private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags>
1152 {
1153 typedef private_adaptive_node_pool_impl_common<SegmentManagerBase, Flags> impl_t;
1154 typedef private_adaptive_node_pool_impl_rt_data<typename SegmentManagerBase::size_type> data_t;
1155
1156 //Non-copyable
1157 private_adaptive_node_pool_impl_rt();
1158 private_adaptive_node_pool_impl_rt(const private_adaptive_node_pool_impl_rt &);
1159 private_adaptive_node_pool_impl_rt &operator=(const private_adaptive_node_pool_impl_rt &);
1160
1161 protected:
1162
1163 typedef typename impl_t::void_pointer void_pointer;
1164 typedef typename impl_t::size_type size_type;
1165 typedef typename impl_t::multiallocation_chain multiallocation_chain;
1166
1167 static const typename impl_t::size_type PayloadPerAllocation = impl_t::PayloadPerAllocation;
1168
1169 //Flags
1170 //align_only
1171 static const bool AlignOnly = impl_t::AlignOnly;
1172
1173 static const size_type HdrSize = impl_t::HdrSize;
1174 static const size_type HdrOffsetSize = impl_t::HdrOffsetSize;
1175
1176 public:
1177
1178 //!Segment manager typedef
1179 typedef SegmentManagerBase segment_manager_base_type;
1180
1181 //!Constructor from a segment manager. Never throws
private_adaptive_node_pool_impl_rt(segment_manager_base_type * segment_mngr_base,size_type node_size,size_type nodes_per_block,size_type max_free_blocks,unsigned char overhead_percent)1182 private_adaptive_node_pool_impl_rt
1183 ( segment_manager_base_type *segment_mngr_base
1184 , size_type node_size
1185 , size_type nodes_per_block
1186 , size_type max_free_blocks
1187 , unsigned char overhead_percent
1188 )
1189 : data_t(max_free_blocks, lcm(node_size, size_type(alignment_of<void_pointer>::value)))
1190 , impl_t(segment_mngr_base)
1191 {
1192 if(AlignOnly){
1193 this->m_real_block_alignment = upper_power_of_2(HdrSize + this->m_real_node_size*nodes_per_block);
1194 this->m_real_num_node = (this->m_real_block_alignment - PayloadPerAllocation - HdrSize)/this->m_real_node_size;
1195 }
1196 else{
1197 candidate_power_of_2_rt ( upper_power_of_2(HdrSize + PayloadPerAllocation + this->m_real_node_size)
1198 , this->m_real_node_size
1199 , PayloadPerAllocation
1200 , nodes_per_block
1201 , HdrSize
1202 , HdrOffsetSize
1203 , overhead_percent
1204 , this->m_real_block_alignment
1205 , this->m_num_subblocks
1206 , this->m_real_num_node);
1207 }
1208 }
1209
1210 //!Destructor. Deallocates all allocated blocks. Never throws
~private_adaptive_node_pool_impl_rt()1211 ~private_adaptive_node_pool_impl_rt()
1212 { this->priv_clear(this->m_num_subblocks, this->m_real_block_alignment, this->m_real_num_node); }
1213
get_real_num_node() const1214 size_type get_real_num_node() const
1215 { return this->m_real_num_node; }
1216
1217 //!Allocates array of count elements. Can throw
allocate_node()1218 void *allocate_node()
1219 {
1220 return this->priv_allocate_node
1221 (this->m_max_free_blocks, this->m_real_block_alignment, this->m_real_node_size, this->m_real_num_node, this->m_num_subblocks);
1222 }
1223
1224 //!Allocates n nodes.
1225 //!Can throw
allocate_nodes(const size_type n,multiallocation_chain & chain)1226 void allocate_nodes(const size_type n, multiallocation_chain &chain)
1227 {
1228
1229 this->priv_allocate_nodes
1230 (n, chain, this->m_max_free_blocks, this->m_real_block_alignment, this->m_real_node_size, this->m_real_num_node, this->m_num_subblocks);
1231 }
1232
1233 //!Deallocates an array pointed by ptr. Never throws
deallocate_node(void * pElem)1234 void deallocate_node(void *pElem)
1235 {
1236 this->priv_deallocate_node(pElem, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);
1237 }
1238
1239 //!Deallocates a linked list of nodes. Never throws
deallocate_nodes(multiallocation_chain & nodes)1240 void deallocate_nodes(multiallocation_chain &nodes)
1241 {
1242 this->priv_deallocate_nodes(nodes, this->m_max_free_blocks, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment);
1243 }
1244
deallocate_free_blocks()1245 void deallocate_free_blocks()
1246 { this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment); }
1247
1248 //Deprecated, use deallocate_free_blocks
deallocate_free_chunks()1249 void deallocate_free_chunks()
1250 { this->priv_deallocate_free_blocks(0, this->m_real_num_node, this->m_num_subblocks, this->m_real_block_alignment); }
1251 };
1252
1253 } //namespace dtl {
1254 } //namespace container {
1255 } //namespace boost {
1256
1257 #include <boost/container/detail/config_end.hpp>
1258
1259 #endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP
1260