3 #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
4 #define CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
6 #include <cds/details/allocator.h>
7 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
9 namespace cds { namespace memory {
11 /// \p vyukov_queue_pool traits
12 /** @ingroup cds_memory_pool
14 struct vyukov_queue_pool_traits : public cds::intrusive::vyukov_queue::traits
17 typedef CDS_DEFAULT_ALLOCATOR allocator;
20 /// Free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
21 /** @ingroup cds_memory_pool
23 - \p T - the type of object maintaining by free-list
24 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
25 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
29 This free-list is very simple.
30 At construction time, the free-list allocates the array of N items
31 and stores them into queue, where N is the queue capacity.
32 When allocating the free-list tries to pop an object from
33 internal queue i.e. from preallocated pool. If success the popped object is returned.
34 Otherwise a new one is allocated. When deallocating, the free-list checks whether
35 the object is from preallocated pool. If so, the object is pushed into queue, otherwise
36 it is deallocated by using the allocator provided.
37 The pool can manage more than \p N items but only \p N items is contained in the free-list.
41 \p %vyukov_queue_pool should be used together with \ref pool_allocator.
42 You should declare an static object of type \p %vyukov_queue_pool, provide
43 an accessor to that object and use \p pool_allocator as an allocator:
45 #include <cds/memory/vyukov_queue_pool.h>
46 #include <cds/memory/pool_allocator.h>
48 // Pool of Foo object of size 1024.
49 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
51 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
53 typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
54 static pool_type thePool;
56 struct pool_accessor {
57 typedef typename pool_type::value_type value_type;
59 pool_type& operator()() const
65 // Declare pool allocator
66 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
70 Foo * p = pool_allocator().allocate( 1 );
81 pool_allocator().deallocate( p , 1 );
84 template <typename T, typename Traits = vyukov_queue_pool_traits >
85 class vyukov_queue_pool
88 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
91 typedef T value_type ; ///< Value type
92 typedef Traits traits; ///< Traits type
93 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
94 typedef typename traits::back_off back_off; ///< back-off strategy
98 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
101 value_type * m_pFirst;
102 value_type * m_pLast;
107 void preallocate_pool()
109 m_pFirst = cxx_allocator().NewArray( m_Queue.capacity() );
110 m_pLast = m_pFirst + m_Queue.capacity();
112 for ( value_type * p = m_pFirst; p < m_pLast; ++p ) {
113 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
117 bool from_pool( value_type * p ) const
119 return m_pFirst <= p && p < m_pLast;
124 /// Preallocates the pool of object
126 \p nCapacity argument is the queue capacity. It should be passed
127 if the queue is based on dynamically-allocated buffer.
128 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
130 vyukov_queue_pool( size_t nCapacity = 0 )
131 : m_Queue( nCapacity )
136 /// Deallocates the pool.
140 cxx_allocator().Delete( m_pFirst, m_Queue.capacity());
143 /// Allocates an object from pool
145 The pool supports allocation only single object (\p n = 1).
146 If \p n > 1 the behaviour is undefined.
148 If the queue is not empty, the popped value is returned.
149 Otherwise, a new value allocated.
151 value_type * allocate( size_t n )
156 value_type * p = m_Queue.pop();
158 assert( from_pool(p) );
161 // The pool is empty - allocate new from the heap
162 return cxx_allocator().New();
165 /// Deallocated the object \p p
167 The pool supports allocation only single object (\p n = 1).
168 If \p n > 1 the behaviour is undefined.
170 If \p p is from preallocated pool, it pushes into the queue.
171 Otherwise, \p p is deallocated by allocator provided.
173 void deallocate( value_type * p, size_t n )
179 if ( from_pool(p) ) {
180 // The queue can notify about false fullness state
181 // so we push in loop
183 while ( !m_Queue.push( *p ))
187 cxx_allocator().Delete( p );
193 /// Lazy free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
194 /** @ingroup cds_memory_pool
196 - \p T - the type of object maintaining by free-list
197 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
198 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
202 This free-list is very simple.
203 At construction time the pool is empty.
204 When allocating the free-list tries to pop an object from
205 internal queue. If success the popped object is returned.
206 Otherwise a new one is allocated.
207 When deallocating, the free-list tries to push the object into the pool.
208 If internal queue is full, the object is deallocated by using the allocator provided.
209 The pool can manage more than \p N items but only \p N items is placed in the free-list.
213 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
214 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
215 an accessor functor to this object and use \p pool_allocator as an allocator:
217 #include <cds/memory/vyukov_queue_pool.h>
218 #include <cds/memory/pool_allocator.h>
220 // Pool of Foo object of size 1024.
221 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
222 static pool_type thePool( 1024 );
224 struct pool_accessor {
225 typedef typename pool_type::value_type value_type;
227 pool_type& operator()() const
233 // Declare pool allocator
234 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
236 // Use pool_allocator
237 // Allocate an object
238 Foo * p = pool_allocator().allocate( 1 );
249 pool_allocator().deallocate( p , 1 );
253 template <typename T, typename Traits = vyukov_queue_pool_traits>
254 class lazy_vyukov_queue_pool
257 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
260 typedef T value_type ; ///< Value type
261 typedef Traits traits; ///< Pool traits
262 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
266 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
272 /// Constructs empty pool
273 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
274 : m_Queue( nCapacity )
277 /// Deallocates all objects from the pool
278 ~lazy_vyukov_queue_pool()
281 while ( !m_Queue.empty() )
282 a.Delete( m_Queue.pop());
285 /// Allocates an object from pool
287 The pool supports allocation only single object (\p n = 1).
288 If \p n > 1 the behaviour is undefined.
290 If the queue is not empty, the popped value is returned.
291 Otherwise, a new value allocated.
293 value_type * allocate( size_t n )
298 value_type * p = m_Queue.pop();
302 return cxx_allocator().New();
305 /// Deallocates the object \p p
307 The pool supports allocation only single object (\p n = 1).
308 If \p n > 1 the behaviour is undefined.
310 If the queue is not full, \p p is pushed into the queue.
311 Otherwise, \p p is deallocated by allocator provided.
313 void deallocate( value_type * p, size_t n )
319 // Here we ignore false fullness state of the queue
320 if ( !m_Queue.push( *p ))
321 cxx_allocator().Delete( p );
327 /// Bounded free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
328 /** @ingroup cds_memory_pool
330 - \p T - the type of object maintaining by free-list
331 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
332 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
336 At construction time, the free-list allocates the array of N items
337 and stores them into the queue, where N is the queue capacity.
338 When allocating the free-list tries to pop an object from
339 internal queue i.e. from preallocated pool. If success the popped object is returned.
340 Otherwise a \p std::bad_alloc exception is raised.
341 So, the pool can contain up to \p N items.
342 When deallocating, the object is pushed into the queue.
343 In debug mode \p deallocate() member function asserts
344 that the pointer is from preallocated pool.
348 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
349 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
350 an accessor functor to this object and use \p pool_allocator as an allocator:
352 #include <cds/memory/vyukov_queue_pool.h>
353 #include <cds/memory/pool_allocator.h>
355 // Pool of Foo object of size 1024.
356 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
358 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
360 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
361 static pool_type thePool;
363 struct pool_accessor {
364 typedef typename pool_type::value_type value_type;
366 pool_type& operator()() const
372 // Declare pool allocator
373 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
375 // Use pool_allocator
376 // Allocate an object
377 Foo * p = pool_allocator().allocate( 1 );
388 pool_allocator().deallocate( p , 1 );
391 template <typename T, typename Traits = vyukov_queue_pool_traits >
392 class bounded_vyukov_queue_pool
395 struct internal_traits : public Traits {
396 typedef cds::atomicity::item_counter item_counter;
400 typedef cds::intrusive::VyukovMPMCCycleQueue< T, internal_traits > queue_type ; ///< Queue type
403 typedef T value_type; ///< Value type
404 typedef Traits traits; ///< Pool traits
405 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
406 typedef typename traits::back_off back_off; ///< back-off strategy
410 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
413 value_type * m_pFirst;
414 value_type * m_pLast;
419 void preallocate_pool()
421 size_t const nCount = m_Queue.capacity();
422 m_pFirst = cxx_allocator().NewArray( nCount );
423 m_pLast = m_pFirst + nCount;
425 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
426 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
429 bool from_pool( value_type * p ) const
431 return m_pFirst <= p && p < m_pLast;
436 /// Preallocates the pool of object
438 \p nCapacity argument is the queue capacity. It should be passed
439 if the queue is based on dynamically-allocated buffer.
440 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
442 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
443 : m_Queue( nCapacity )
448 /// Deallocates the pool.
449 ~bounded_vyukov_queue_pool()
452 cxx_allocator().Delete( m_pFirst, m_Queue.capacity() );
455 /// Allocates an object from pool
457 The pool supports allocation only single object (\p n = 1).
458 If \p n > 1 the behaviour is undefined.
460 If the queue is not empty, the popped value is returned.
461 Otherwise, a \p std::bad_alloc exception is raised.
463 value_type * allocate( size_t n )
468 value_type * p = m_Queue.pop();
472 while ( m_Queue.size() ) {
480 throw std::bad_alloc();
484 assert( from_pool(p) );
488 /// Deallocates the object \p p
490 The pool supports allocation only single object (\p n = 1).
491 If \p n > 1 the behaviour is undefined.
493 \p p should be from preallocated pool.
495 void deallocate( value_type * p, size_t n )
501 assert( from_pool( p ));
503 // The queue can notify it is full but that is false fullness state
504 // So, we push in loop
505 while ( !m_Queue.push(*p) )
512 }} // namespace cds::memory
515 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H