]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
b32b8144 | 31 | #include <boost/move/detail/iterator_to_raw_pointer.hpp> |
7c673cae FG |
32 | #include <boost/container/detail/math_functions.hpp> |
33 | #include <boost/container/detail/mpl.hpp> | |
b32b8144 | 34 | #include <boost/move/detail/to_raw_pointer.hpp> |
7c673cae FG |
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 | ||
11fdf7f2 | 58 | namespace dtl { |
7c673cae FG |
59 | |
60 | template<class size_type> | |
61 | struct hdr_offset_holder_t | |
62 | { | |
63 | 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 | { | |
75 | 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 | { | |
82 | 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 | { | |
89 | static bool less(SizeType, SizeType, const void *la, const void *ra) | |
92f5a8d4 | 90 | { return la < ra; } |
7c673cae FG |
91 | }; |
92 | ||
93 | template<class SizeType> | |
94 | struct less_func<SizeType, adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered> | |
95 | { | |
96 | static bool less(SizeType ls, SizeType rs, const void *la, const void *ra) | |
97 | { return (ls < rs) || ((ls == rs) && (la < ra)); } | |
98 | }; | |
99 | ||
92f5a8d4 | 100 | template<class VoidPointer, class SizeType, unsigned OrderFlags> |
7c673cae FG |
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> | |
116 | static void reinsert_was_used(Container &container, typename Container::reference v, bool) | |
117 | { | |
118 | typedef typename Container::const_iterator const_block_iterator; | |
92f5a8d4 TL |
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{ | |
7c673cae FG |
134 | container.erase(this_block); |
135 | container.insert(v); | |
136 | } | |
137 | } | |
138 | } | |
139 | ||
140 | template<class Container> | |
141 | static void insert_was_empty(Container &container, typename Container::value_type &v, bool) | |
142 | { | |
143 | container.insert(v); | |
144 | } | |
145 | ||
146 | template<class Container> | |
147 | static void erase_first(Container &container) | |
148 | { | |
149 | container.erase(container.cbegin()); | |
150 | } | |
151 | ||
152 | template<class Container> | |
153 | static void erase_last(Container &container) | |
154 | { | |
155 | container.erase(--container.cend()); | |
156 | } | |
157 | }; | |
158 | ||
159 | template<class VoidPointer, class SizeType> | |
92f5a8d4 | 160 | struct block_container_traits<VoidPointer, SizeType, 0u> |
7c673cae FG |
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> | |
174 | 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> | |
183 | 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> | |
194 | static void erase_first(Container &container) | |
195 | { | |
196 | container.pop_front(); | |
197 | } | |
198 | ||
199 | template<class Container> | |
200 | static void erase_last(Container &container) | |
201 | { | |
202 | container.pop_back(); | |
203 | } | |
204 | }; | |
205 | ||
92f5a8d4 TL |
206 | ///////////////////////////// |
207 | // | |
208 | // adaptive_pool_types | |
209 | // | |
210 | ///////////////////////////// | |
7c673cae FG |
211 | template<class MultiallocationChain, class VoidPointer, class SizeType, unsigned int Flags> |
212 | struct adaptive_pool_types | |
213 | { | |
214 | typedef VoidPointer void_pointer; | |
92f5a8d4 | 215 | static const unsigned ordered = (Flags & (adaptive_pool_flag::size_ordered | adaptive_pool_flag::address_ordered)); |
7c673cae FG |
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; | |
228 | 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 | ||
234 | 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 | ||
92f5a8d4 TL |
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 | |
7c673cae | 254 | { |
92f5a8d4 TL |
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 | }; | |
7c673cae | 281 | |
92f5a8d4 TL |
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 | ///////////////////////////////////////////// | |
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) | |
7c673cae | 376 | { |
7c673cae | 377 | bool overhead_satisfied = false; |
92f5a8d4 TL |
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); | |
7c673cae | 410 | } |
92f5a8d4 TL |
411 | alignment = initial_alignment; |
412 | num_subblocks = num_b_subblock+1; | |
413 | real_num_node = total_nodes; | |
7c673cae FG |
414 | } |
415 | ||
92f5a8d4 TL |
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 | |
7c673cae | 423 | { |
92f5a8d4 TL |
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; | |
7c673cae FG |
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; | |
7c673cae | 435 | |
92f5a8d4 TL |
436 | typedef typename SegmentManagerBase::void_pointer void_pointer; |
437 | static const typename SegmentManagerBase:: | |
438 | size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation; | |
7c673cae | 439 | |
92f5a8d4 TL |
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: | |
7c673cae FG |
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; | |
92f5a8d4 | 453 | typedef private_adaptive_node_pool_impl_common this_type; |
7c673cae FG |
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 | ||
92f5a8d4 TL |
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 | |
7c673cae | 462 | |
92f5a8d4 TL |
463 | class block_destroyer; |
464 | friend class block_destroyer; | |
465 | ||
466 | class block_destroyer | |
467 | { | |
468 | public: | |
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 | ||
473 | void operator()(typename block_container_t::pointer to_deallocate) | |
474 | { return this->do_destroy(to_deallocate, IsAlignOnly()); } | |
475 | ||
476 | private: | |
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 | ||
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 | |
501 | void priv_invariants(const size_type real_num_node, const size_type num_subblocks, const size_type real_block_alignment) const | |
7c673cae | 502 | { |
92f5a8d4 TL |
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); | |
7c673cae | 548 | } |
92f5a8d4 | 549 | #endif |
7c673cae FG |
550 | } |
551 | ||
92f5a8d4 TL |
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 | } | |
7c673cae | 559 | |
92f5a8d4 TL |
560 | 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()); } | |
7c673cae | 562 | |
92f5a8d4 TL |
563 | 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 | ||
573 | 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 | ||
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 | ||
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 | |
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 | ||
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 | } | |
7c673cae FG |
726 | |
727 | //!Allocates array of count elements. Can throw | |
92f5a8d4 TL |
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) | |
7c673cae | 730 | { |
92f5a8d4 | 731 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae FG |
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(); | |
b32b8144 | 738 | void *first_node = boost::movelib::to_raw_pointer(free_nodes.pop_front()); |
7c673cae FG |
739 | if(free_nodes.empty()){ |
740 | block_container_traits_t::erase_first(m_block_container); | |
741 | } | |
92f5a8d4 TL |
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); | |
7c673cae FG |
744 | return first_node; |
745 | } | |
746 | else{ | |
747 | multiallocation_chain chain; | |
92f5a8d4 TL |
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; | |
7c673cae FG |
753 | } |
754 | } | |
755 | ||
92f5a8d4 TL |
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) | |
7c673cae FG |
759 | { |
760 | size_type i = 0; | |
761 | BOOST_TRY{ | |
92f5a8d4 | 762 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae FG |
763 | while(i != n){ |
764 | //If there are no free nodes we allocate all needed blocks | |
765 | if (m_block_container.empty()){ | |
92f5a8d4 TL |
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()); | |
7c673cae FG |
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(); | |
92f5a8d4 | 774 | m_totally_free_blocks -= static_cast<size_type>(free_nodes_count_before == real_num_node); |
7c673cae FG |
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(...){ | |
92f5a8d4 TL |
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); | |
7c673cae FG |
804 | BOOST_RETHROW |
805 | } | |
806 | BOOST_CATCH_END | |
92f5a8d4 | 807 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae FG |
808 | } |
809 | ||
92f5a8d4 TL |
810 | //!Deallocates an array pointed by ptr. Never throws |
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 | ||
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) | |
7c673cae | 832 | { |
92f5a8d4 | 833 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae FG |
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){ | |
b32b8144 | 849 | void *pElem = boost::movelib::to_raw_pointer(boost::movelib::iterator_to_raw_pointer(itf)); |
92f5a8d4 TL |
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); | |
7c673cae FG |
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); | |
92f5a8d4 | 860 | this->priv_reinsert_block(*prev_block_info, prev_block_was_empty, real_num_node); |
7c673cae FG |
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); | |
92f5a8d4 TL |
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); | |
7c673cae | 879 | } |
92f5a8d4 | 880 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae FG |
881 | } |
882 | ||
92f5a8d4 | 883 | void priv_reinsert_block(block_info_t &prev_block_info, const bool prev_block_was_empty, const size_type real_num_node) |
7c673cae | 884 | { |
92f5a8d4 TL |
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); | |
7c673cae | 896 | } |
7c673cae FG |
897 | } |
898 | ||
92f5a8d4 | 899 | block_info_t *priv_block_from_node(void *node, const size_type real_block_alignment, AlignOnlyFalse) const |
7c673cae | 900 | { |
92f5a8d4 TL |
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; | |
7c673cae FG |
909 | } |
910 | ||
92f5a8d4 TL |
911 | 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 | } | |
7c673cae | 915 | |
92f5a8d4 TL |
916 | 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()); } | |
7c673cae FG |
918 | |
919 | //!Deallocates all used memory. Never throws | |
92f5a8d4 | 920 | void priv_clear(const size_type num_subblocks, const size_type real_block_alignment, const size_type real_num_node) |
7c673cae FG |
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 | |
92f5a8d4 | 928 | BOOST_ASSERT(it->free_nodes.size() == real_num_node); |
7c673cae FG |
929 | ++n_free_nodes; |
930 | } | |
931 | BOOST_ASSERT(n_free_nodes == m_totally_free_blocks); | |
932 | #endif | |
933 | //Check for memory leaks | |
92f5a8d4 | 934 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae | 935 | multiallocation_chain chain; |
92f5a8d4 | 936 | m_block_container.clear_and_dispose(block_destroyer(this, chain, num_subblocks, real_block_alignment, real_num_node)); |
7c673cae FG |
937 | this->mp_segment_mngr_base->deallocate_many(chain); |
938 | m_totally_free_blocks = 0; | |
92f5a8d4 | 939 | this->priv_invariants(real_num_node, num_subblocks, real_block_alignment); |
7c673cae FG |
940 | } |
941 | ||
92f5a8d4 TL |
942 | public: |
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 | ||
950 | size_type num_free_nodes() | |
7c673cae | 951 | { |
92f5a8d4 TL |
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; | |
7c673cae FG |
959 | } |
960 | ||
92f5a8d4 | 961 | void swap(private_adaptive_node_pool_impl_common &other) |
7c673cae | 962 | { |
92f5a8d4 TL |
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); | |
7c673cae FG |
966 | } |
967 | ||
92f5a8d4 TL |
968 | //!Returns the segment manager. Never throws |
969 | 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; | |
7c673cae | 1070 | |
92f5a8d4 | 1071 | public: |
7c673cae | 1072 | |
92f5a8d4 TL |
1073 | //!Constructor from a segment manager. Never throws |
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 | |
1080 | ~private_adaptive_node_pool_impl_ct() | |
1081 | { this->priv_clear(NumSubBlocks, data_t::alignment, RealNumNode); } | |
1082 | ||
1083 | size_type get_real_num_node() const | |
1084 | { return RealNumNode; } | |
1085 | ||
1086 | //!Allocates array of count elements. Can throw | |
1087 | void *allocate_node() | |
7c673cae | 1088 | { |
92f5a8d4 TL |
1089 | return this->priv_allocate_node |
1090 | (MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks); | |
7c673cae FG |
1091 | } |
1092 | ||
92f5a8d4 TL |
1093 | //!Allocates n nodes. |
1094 | //!Can throw | |
1095 | void allocate_nodes(const size_type n, multiallocation_chain &chain) | |
7c673cae | 1096 | { |
92f5a8d4 TL |
1097 | this->priv_allocate_nodes |
1098 | (n, chain, MaxFreeBlocks, data_t::alignment, RealNodeSize, RealNumNode, NumSubBlocks); | |
7c673cae FG |
1099 | } |
1100 | ||
92f5a8d4 TL |
1101 | //!Deallocates an array pointed by ptr. Never throws |
1102 | void deallocate_node(void *pElem) | |
7c673cae | 1103 | { |
92f5a8d4 | 1104 | this->priv_deallocate_node(pElem, MaxFreeBlocks, RealNumNode, NumSubBlocks, RealBlockAlignment); |
7c673cae FG |
1105 | } |
1106 | ||
92f5a8d4 TL |
1107 | //!Deallocates a linked list of nodes. Never throws |
1108 | void deallocate_nodes(multiallocation_chain &nodes) | |
7c673cae | 1109 | { |
92f5a8d4 | 1110 | this->priv_deallocate_nodes(nodes, MaxFreeBlocks, RealNumNode, NumSubBlocks, data_t::alignment); |
7c673cae FG |
1111 | } |
1112 | ||
92f5a8d4 TL |
1113 | void deallocate_free_blocks() |
1114 | { this->priv_deallocate_free_blocks(0, RealNumNode, NumSubBlocks, data_t::alignment); } | |
7c673cae | 1115 | |
92f5a8d4 TL |
1116 | //Deprecated, use deallocate_free_blocks |
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 | ||
1131 | 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 | {} | |
7c673cae | 1135 | |
7c673cae FG |
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 | |
92f5a8d4 | 1141 | size_type m_real_block_alignment; |
7c673cae FG |
1142 | size_type m_num_subblocks; |
1143 | //This is the real number of nodes per block | |
7c673cae | 1144 | size_type m_real_num_node; |
92f5a8d4 TL |
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 | |
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 | |
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 | ||
1214 | size_type get_real_num_node() const | |
1215 | { return this->m_real_num_node; } | |
1216 | ||
1217 | //!Allocates array of count elements. Can throw | |
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 | |
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 | |
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 | |
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 | ||
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 | |
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); } | |
7c673cae FG |
1251 | }; |
1252 | ||
11fdf7f2 | 1253 | } //namespace dtl { |
7c673cae FG |
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 |