1 //////////////////////////////////////////////////////////////////////////////
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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
10 #ifndef BOOST_CONTAINER_DETAIL_NODE_POOL_IMPL_HPP
11 #define BOOST_CONTAINER_DETAIL_NODE_POOL_IMPL_HPP
13 #ifndef BOOST_CONFIG_HPP
14 # include <boost/config.hpp>
17 #if defined(BOOST_HAS_PRAGMA_ONCE)
21 #include <boost/container/detail/config_begin.hpp>
22 #include <boost/container/detail/workaround.hpp>
23 #include <boost/container/container_fwd.hpp>
25 #include <boost/container/detail/math_functions.hpp>
26 #include <boost/container/detail/mpl.hpp>
27 #include <boost/container/detail/pool_common.hpp>
28 #include <boost/container/detail/to_raw_pointer.hpp>
29 #include <boost/container/detail/type_traits.hpp>
31 #include <boost/intrusive/pointer_traits.hpp>
32 #include <boost/intrusive/set.hpp>
33 #include <boost/intrusive/slist.hpp>
35 #include <boost/core/no_exceptions_support.hpp>
36 #include <boost/assert.hpp>
41 namespace container_detail {
43 template<class SegmentManagerBase>
44 class private_node_pool_impl
47 private_node_pool_impl();
48 private_node_pool_impl(const private_node_pool_impl &);
49 private_node_pool_impl &operator=(const private_node_pool_impl &);
51 //A node object will hold node_t when it's not allocated
53 typedef typename SegmentManagerBase::void_pointer void_pointer;
54 typedef typename node_slist<void_pointer>::slist_hook_t slist_hook_t;
55 typedef typename node_slist<void_pointer>::node_t node_t;
56 typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t;
57 typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain;
58 typedef typename SegmentManagerBase::size_type size_type;
61 typedef typename bi::make_slist
62 < node_t, bi::base_hook<slist_hook_t>
64 , bi::constant_time_size<false> >::type blockslist_t;
66 static size_type get_rounded_size(size_type orig_size, size_type round_to)
67 { return ((orig_size-1)/round_to+1)*round_to; }
71 //!Segment manager typedef
72 typedef SegmentManagerBase segment_manager_base_type;
74 //!Constructor from a segment manager. Never throws
75 private_node_pool_impl(segment_manager_base_type *segment_mngr_base, size_type node_size, size_type nodes_per_block)
76 : m_nodes_per_block(nodes_per_block)
77 , m_real_node_size(lcm(node_size, size_type(alignment_of<node_t>::value)))
78 //General purpose allocator
79 , mp_segment_mngr_base(segment_mngr_base)
86 //!Destructor. Deallocates all allocated blocks. Never throws
87 ~private_node_pool_impl()
88 { this->purge_blocks(); }
90 size_type get_real_num_node() const
91 { return m_nodes_per_block; }
93 //!Returns the segment manager. Never throws
94 segment_manager_base_type* get_segment_manager_base()const
95 { return container_detail::to_raw_pointer(mp_segment_mngr_base); }
98 { return this->priv_alloc_node(); }
100 //!Deallocates an array pointed by ptr. Never throws
101 void deallocate_node(void *ptr)
102 { this->priv_dealloc_node(ptr); }
104 //!Allocates a singly linked list of n nodes ending in null pointer.
105 void allocate_nodes(const size_type n, multiallocation_chain &chain)
107 //Preallocate all needed blocks to fulfill the request
108 size_type cur_nodes = m_freelist.size();
110 this->priv_alloc_block(((n - cur_nodes) - 1)/m_nodes_per_block + 1);
113 //We just iterate the needed nodes to get the last we'll erase
114 typedef typename free_nodes_t::iterator free_iterator;
115 free_iterator before_last_new_it = m_freelist.before_begin();
116 for(size_type j = 0; j != n; ++j){
117 ++before_last_new_it;
120 //Cache the first node of the allocated range before erasing
121 free_iterator first_node(m_freelist.begin());
122 free_iterator last_node (before_last_new_it);
124 //Erase the range. Since we already have the distance, this is O(1)
125 m_freelist.erase_after( m_freelist.before_begin()
126 , ++free_iterator(before_last_new_it)
129 //Now take the last erased node and just splice it in the end
130 //of the intrusive list that will be traversed by the multialloc iterator.
131 chain.incorporate_after(chain.before_begin(), &*first_node, &*last_node, n);
135 void deallocate_nodes(multiallocation_chain &chain)
137 typedef typename multiallocation_chain::iterator iterator;
138 iterator it(chain.begin()), itend(chain.end());
142 this->priv_dealloc_node(pElem);
146 //!Deallocates all the free blocks of memory. Never throws
147 void deallocate_free_blocks()
149 typedef typename free_nodes_t::iterator nodelist_iterator;
150 typename blockslist_t::iterator bit(m_blocklist.before_begin()),
151 it(m_blocklist.begin()),
152 itend(m_blocklist.end());
153 free_nodes_t backup_list;
154 nodelist_iterator backup_list_last = backup_list.before_begin();
156 //Execute the algorithm and get an iterator to the last value
157 size_type blocksize = (get_rounded_size)
158 (m_real_node_size*m_nodes_per_block, (size_type) alignment_of<node_t>::value);
161 //Collect all the nodes from the block pointed by it
162 //and push them in the list
163 free_nodes_t free_nodes;
164 nodelist_iterator last_it = free_nodes.before_begin();
165 const void *addr = get_block_from_hook(&*it, blocksize);
167 m_freelist.remove_and_dispose_if
168 (is_between(addr, blocksize), push_in_list(free_nodes, last_it));
170 //If the number of nodes is equal to m_nodes_per_block
171 //this means that the block can be deallocated
172 if(free_nodes.size() == m_nodes_per_block){
175 it = m_blocklist.erase_after(bit);
176 mp_segment_mngr_base->deallocate((void*)addr);
178 //Otherwise, insert them in the backup list, since the
179 //next "remove_if" does not need to check them again.
181 //Assign the iterator to the last value if necessary
182 if(backup_list.empty() && !m_freelist.empty()){
183 backup_list_last = last_it;
185 //Transfer nodes. This is constant time.
186 backup_list.splice_after
187 ( backup_list.before_begin()
189 , free_nodes.before_begin()
191 , free_nodes.size());
196 //We should have removed all the nodes from the free list
197 BOOST_ASSERT(m_freelist.empty());
199 //Now pass all the node to the free list again
200 m_freelist.splice_after
201 ( m_freelist.before_begin()
203 , backup_list.before_begin()
205 , backup_list.size());
208 size_type num_free_nodes()
209 { return m_freelist.size(); }
211 //!Deallocates all used memory. Precondition: all nodes allocated from this pool should
212 //!already be deallocated. Otherwise, undefined behaviour. Never throws
215 //check for memory leaks
216 BOOST_ASSERT(m_allocated==0);
217 size_type blocksize = (get_rounded_size)
218 (m_real_node_size*m_nodes_per_block, (size_type)alignment_of<node_t>::value);
220 //We iterate though the NodeBlock list to free the memory
221 while(!m_blocklist.empty()){
222 void *addr = get_block_from_hook(&m_blocklist.front(), blocksize);
223 m_blocklist.pop_front();
224 mp_segment_mngr_base->deallocate((void*)addr);
226 //Just clear free node list
230 void swap(private_node_pool_impl &other)
232 BOOST_ASSERT(m_nodes_per_block == other.m_nodes_per_block);
233 BOOST_ASSERT(m_real_node_size == other.m_real_node_size);
234 std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base);
235 m_blocklist.swap(other.m_blocklist);
236 m_freelist.swap(other.m_freelist);
237 std::swap(m_allocated, other.m_allocated);
244 push_in_list(free_nodes_t &l, typename free_nodes_t::iterator &it)
245 : slist_(l), last_it_(it)
248 void operator()(typename free_nodes_t::pointer p) const
250 slist_.push_front(*p);
251 if(slist_.size() == 1){ //Cache last element
252 ++last_it_ = slist_.begin();
257 free_nodes_t &slist_;
258 typename free_nodes_t::iterator &last_it_;
263 typedef typename free_nodes_t::value_type argument_type;
264 typedef bool result_type;
266 is_between(const void *addr, std::size_t size)
267 : beg_(static_cast<const char *>(addr)), end_(beg_+size)
270 bool operator()(typename free_nodes_t::const_reference v) const
272 return (beg_ <= reinterpret_cast<const char *>(&v) &&
273 end_ > reinterpret_cast<const char *>(&v));
280 //!Allocates one node, using single segregated storage algorithm.
282 node_t *priv_alloc_node()
284 //If there are no free nodes we allocate a new block
285 if (m_freelist.empty())
286 this->priv_alloc_block(1);
287 //We take the first free node
288 node_t *n = (node_t*)&m_freelist.front();
289 m_freelist.pop_front();
294 //!Deallocates one node, using single segregated storage algorithm.
296 void priv_dealloc_node(void *pElem)
298 //We put the node at the beginning of the free node list
299 node_t * to_deallocate = static_cast<node_t*>(pElem);
300 m_freelist.push_front(*to_deallocate);
301 BOOST_ASSERT(m_allocated>0);
305 //!Allocates several blocks of nodes. Can throw
306 void priv_alloc_block(size_type num_blocks)
308 BOOST_ASSERT(num_blocks > 0);
309 size_type blocksize =
310 (get_rounded_size)(m_real_node_size*m_nodes_per_block, (size_type)alignment_of<node_t>::value);
313 for(size_type i = 0; i != num_blocks; ++i){
314 //We allocate a new NodeBlock and put it as first
315 //element in the free Node list
316 char *pNode = reinterpret_cast<char*>
317 (mp_segment_mngr_base->allocate(blocksize + sizeof(node_t)));
318 char *pBlock = pNode;
319 m_blocklist.push_front(get_block_hook(pBlock, blocksize));
321 //We initialize all Nodes in Node Block to insert
322 //them in the free Node list
323 for(size_type j = 0; j < m_nodes_per_block; ++j, pNode += m_real_node_size){
324 m_freelist.push_front(*new (pNode) node_t);
329 //to-do: if possible, an efficient way to deallocate allocated blocks
335 //!Deprecated, use deallocate_free_blocks
336 void deallocate_free_chunks()
337 { this->deallocate_free_blocks(); }
339 //!Deprecated, use purge_blocks
341 { this->purge_blocks(); }
344 //!Returns a reference to the block hook placed in the end of the block
345 static node_t & get_block_hook (void *block, size_type blocksize)
347 return *reinterpret_cast<node_t*>(reinterpret_cast<char*>(block) + blocksize);
350 //!Returns the starting address of the block reference to the block hook placed in the end of the block
351 void *get_block_from_hook (node_t *hook, size_type blocksize)
353 return (reinterpret_cast<char*>(hook) - blocksize);
357 typedef typename boost::intrusive::pointer_traits
358 <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t;
360 const size_type m_nodes_per_block;
361 const size_type m_real_node_size;
362 segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager
363 blockslist_t m_blocklist; //Intrusive container of blocks
364 free_nodes_t m_freelist; //Intrusive container of free nods
365 size_type m_allocated; //Used nodes for debugging
369 } //namespace container_detail {
370 } //namespace container {
371 } //namespace boost {
373 #include <boost/container/detail/config_end.hpp>
375 #endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP