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 typedef cds::backoff::yield back_off;
23 /// Free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
24 /** @ingroup cds_memory_pool
26 - \p T - the type of object maintaining by free-list
27 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
28 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
32 This free-list is very simple.
33 At construction time, the free-list allocates the array of N items
34 and stores them into queue, where N is the queue capacity.
35 When allocating the free-list tries to pop an object from
36 internal queue i.e. from preallocated pool. If success the popped object is returned.
37 Otherwise a new one is allocated. When deallocating, the free-list checks whether
38 the object is from preallocated pool. If so, the object is pushed into queue, otherwise
39 it is deallocated by using the allocator provided.
40 The pool can manage more than \p N items but only \p N items is contained in the free-list.
44 \p %vyukov_queue_pool should be used together with \ref pool_allocator.
45 You should declare an static object of type \p %vyukov_queue_pool, provide
46 an accessor to that object and use \p pool_allocator as an allocator:
48 #include <cds/memory/vyukov_queue_pool.h>
49 #include <cds/memory/pool_allocator.h>
51 // Pool of Foo object of size 1024.
52 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
54 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
56 typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
57 static pool_type thePool;
59 struct pool_accessor {
60 typedef typename pool_type::value_type value_type;
62 pool_type& operator()() const
68 // Declare pool allocator
69 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
73 Foo * p = pool_allocator().allocate( 1 );
84 pool_allocator().deallocate( p , 1 );
87 template <typename T, typename Traits = vyukov_queue_pool_traits >
88 class vyukov_queue_pool
91 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
94 typedef T value_type ; ///< Value type
95 typedef Traits traits; ///< Traits type
96 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
97 typedef typename traits::back_off back_off; ///< back-off strategy
101 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
104 value_type * m_pFirst;
105 value_type * m_pLast;
110 void preallocate_pool()
112 m_pFirst = cxx_allocator().NewArray( m_Queue.capacity() );
113 m_pLast = m_pFirst + m_Queue.capacity();
115 for ( value_type * p = m_pFirst; p < m_pLast; ++p ) {
116 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
120 bool from_pool( value_type * p ) const
122 return m_pFirst <= p && p < m_pLast;
127 /// Preallocates the pool of object
129 \p nCapacity argument is the queue capacity. It should be passed
130 if the queue is based on dynamically-allocated buffer.
131 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
133 vyukov_queue_pool( size_t nCapacity = 0 )
134 : m_Queue( nCapacity )
139 /// Deallocates the pool.
143 cxx_allocator().Delete( m_pFirst, m_Queue.capacity());
146 /// Allocates an object from pool
148 The pool supports allocation only single object (\p n = 1).
149 If \p n > 1 the behaviour is undefined.
151 If the queue is not empty, the popped value is returned.
152 Otherwise, a new value allocated.
154 value_type * allocate( size_t n )
159 value_type * p = m_Queue.pop();
161 assert( from_pool(p) );
165 return cxx_allocator().New();
168 /// Deallocated the object \p p
170 The pool supports allocation only single object (\p n = 1).
171 If \p n > 1 the behaviour is undefined.
173 If \p p is from preallocated pool, it pushes into the queue.
174 Otherwise, \p p is deallocated by allocator provided.
176 void deallocate( value_type * p, size_t n )
182 if ( from_pool(p) ) {
183 // The queue can notify about false fullness state
184 // so we push in loop
186 while ( !m_Queue.push( *p ))
190 cxx_allocator().Delete( p );
196 /// Lazy free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
197 /** @ingroup cds_memory_pool
199 - \p T - the type of object maintaining by free-list
200 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
201 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
205 This free-list is very simple.
206 At construction time the pool is empty.
207 When allocating the free-list tries to pop an object from
208 internal queue. If success the popped object is returned.
209 Otherwise a new one is allocated.
210 When deallocating, the free-list tries to push the object into the pool.
211 If internal queue is full, the object is deallocated by using the allocator provided.
212 The pool can manage more than \p N items but only \p N items is placed in the free-list.
216 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
217 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
218 an accessor functor to this object and use \p pool_allocator as an allocator:
220 #include <cds/memory/vyukov_queue_pool.h>
221 #include <cds/memory/pool_allocator.h>
223 // Pool of Foo object of size 1024.
224 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
225 static pool_type thePool( 1024 );
227 struct pool_accessor {
228 typedef typename pool_type::value_type value_type;
230 pool_type& operator()() const
236 // Declare pool allocator
237 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
239 // Use pool_allocator
240 // Allocate an object
241 Foo * p = pool_allocator().allocate( 1 );
252 pool_allocator().deallocate( p , 1 );
256 template <typename T, typename Traits = vyukov_queue_pool_traits>
257 class lazy_vyukov_queue_pool
260 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
263 typedef T value_type ; ///< Value type
264 typedef Traits traits; ///< Pool traits
265 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
269 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
275 /// Constructs empty pool
276 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
277 : m_Queue( nCapacity )
280 /// Deallocates all objects from the pool
281 ~lazy_vyukov_queue_pool()
284 while ( !m_Queue.empty() )
285 a.Delete( m_Queue.pop());
288 /// Allocates an object from pool
290 The pool supports allocation only single object (\p n = 1).
291 If \p n > 1 the behaviour is undefined.
293 If the queue is not empty, the popped value is returned.
294 Otherwise, a new value allocated.
296 value_type * allocate( size_t n )
301 value_type * p = m_Queue.pop();
305 return cxx_allocator().New();
308 /// Deallocated the object \p p
310 The pool supports allocation only single object (\p n = 1).
311 If \p n > 1 the behaviour is undefined.
313 If the queue is not full, \p p is pushed into the queue.
314 Otherwise, \p p is deallocated by allocator provided.
316 void deallocate( value_type * p, size_t n )
322 // Here we ignore false fullness state of the queue
323 if ( !m_Queue.push( *p ))
324 cxx_allocator().Delete( p );
330 /// Bounded free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
331 /** @ingroup cds_memory_pool
333 - \p T - the type of object maintaining by free-list
334 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
335 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
339 At construction time, the free-list allocates the array of N items
340 and stores them into the queue, where N is the queue capacity.
341 When allocating the free-list tries to pop an object from
342 internal queue i.e. from preallocated pool. If success the popped object is returned.
343 Otherwise a \p std::bad_alloc exception is raised.
344 So, the pool can contain up to \p N items.
345 When deallocating, the object is pushed into the queue.
346 In debug mode \p deallocate() member function asserts
347 that the pointer is from preallocated pool.
351 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
352 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
353 an accessor functor to this object and use \p pool_allocator as an allocator:
355 #include <cds/memory/vyukov_queue_pool.h>
356 #include <cds/memory/pool_allocator.h>
358 // Pool of Foo object of size 1024.
359 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
361 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
363 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
364 static pool_type thePool;
366 struct pool_accessor {
367 typedef typename pool_type::value_type value_type;
369 pool_type& operator()() const
375 // Declare pool allocator
376 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
378 // Use pool_allocator
379 // Allocate an object
380 Foo * p = pool_allocator().allocate( 1 );
391 pool_allocator().deallocate( p , 1 );
394 template <typename T, typename Traits = vyukov_queue_pool_traits >
395 class bounded_vyukov_queue_pool
398 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
401 typedef T value_type; ///< Value type
402 typedef Traits traits; ///< Pool traits
403 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
404 typedef typename traits::back_off back_off; ///< back-off strategy
408 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
411 value_type * m_pFirst;
412 value_type * m_pLast;
417 void preallocate_pool()
419 size_t const nCount = m_Queue.capacity();
420 m_pFirst = cxx_allocator().NewArray( nCount );
421 m_pLast = m_pFirst + nCount;
423 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
424 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
427 bool from_pool( value_type * p ) const
429 return m_pFirst <= p && p < m_pLast;
434 /// Preallocates the pool of object
436 \p nCapacity argument is the queue capacity. It should be passed
437 if the queue is based on dynamically-allocated buffer.
438 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
440 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
441 : m_Queue( nCapacity )
446 /// Deallocates the pool.
447 ~bounded_vyukov_queue_pool()
450 cxx_allocator().Delete( m_pFirst, m_Queue.capacity() );
453 /// Allocates an object from pool
455 The pool supports allocation only single object (\p n = 1).
456 If \p n > 1 the behaviour is undefined.
458 If the queue is not empty, the popped value is returned.
459 Otherwise, a \p std::bad_alloc exception is raised.
461 value_type * allocate( size_t n )
466 value_type * p = m_Queue.pop();
468 assert( from_pool(p) );
472 throw std::bad_alloc();
475 /// Deallocated the object \p p
477 The pool supports allocation only single object (\p n = 1).
478 If \p n > 1 the behaviour is undefined.
480 \p should be from preallocated pool.
482 void deallocate( value_type * p, size_t n )
488 assert( from_pool( p ));
490 // The queue can notify it is full but that is false fullness state
491 // So, we push in loop
492 while ( !m_Queue.push(*p) )
499 }} // namespace cds::memory
502 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H