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
97 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
100 value_type * m_pFirst;
101 value_type * m_pLast;
106 void preallocate_pool()
108 m_pFirst = cxx_allocator().NewArray( m_Queue.capacity() );
109 m_pLast = m_pFirst + m_Queue.capacity();
111 for ( value_type * p = m_pFirst; p < m_pLast; ++p ) {
112 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
116 bool from_pool( value_type * p ) const
118 return m_pFirst <= p && p < m_pLast;
123 /// Preallocates the pool of object
125 \p nCapacity argument is the queue capacity. It should be passed
126 if the queue is based on dynamically-allocated buffer.
127 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
129 vyukov_queue_pool( size_t nCapacity = 0 )
130 : m_Queue( nCapacity )
135 /// Deallocates the pool.
139 cxx_allocator().Delete( m_pFirst, m_Queue.capacity());
142 /// Allocates an object from pool
144 The pool supports allocation only single object (\p n = 1).
145 If \p n > 1 the behaviour is undefined.
147 If the queue is not empty, the popped value is returned.
148 Otherwise, a new value allocated.
150 value_type * allocate( size_t n )
155 value_type * p = m_Queue.pop();
157 assert( from_pool(p) );
161 return cxx_allocator().New();
164 /// Deallocated the object \p p
166 The pool supports allocation only single object (\p n = 1).
167 If \p n > 1 the behaviour is undefined.
169 If \p p is from preallocated pool, it pushes into the queue.
170 Otherwise, \p p is deallocated by allocator provided.
172 void deallocate( value_type * p, size_t n )
178 if ( from_pool( p ) )
181 cxx_allocator().Delete( p );
187 /// Lazy free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
188 /** @ingroup cds_memory_pool
190 - \p T - the type of object maintaining by free-list
191 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
192 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
196 This free-list is very simple.
197 At construction time the pool is empty.
198 When allocating the free-list tries to pop an object from
199 internal queue. If success the popped object is returned.
200 Otherwise a new one is allocated.
201 When deallocating, the free-list tries to push the object into the pool.
202 If internal queue is full, the object is deallocated by using the allocator provided.
203 The pool can manage more than \p N items but only \p N items is placed in the free-list.
207 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
208 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
209 an accessor functor to this object and use \p pool_allocator as an allocator:
211 #include <cds/memory/vyukov_queue_pool.h>
212 #include <cds/memory/pool_allocator.h>
214 // Pool of Foo object of size 1024.
215 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
216 static pool_type thePool( 1024 );
218 struct pool_accessor {
219 typedef typename pool_type::value_type value_type;
221 pool_type& operator()() const
227 // Declare pool allocator
228 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
230 // Use pool_allocator
231 // Allocate an object
232 Foo * p = pool_allocator().allocate( 1 );
243 pool_allocator().deallocate( p , 1 );
247 template <typename T, typename Traits = vyukov_queue_pool_traits>
248 class lazy_vyukov_queue_pool
251 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
254 typedef T value_type ; ///< Value type
255 typedef Traits traits; ///< Pool traits
256 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
260 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
266 /// Constructs empty pool
267 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
268 : m_Queue( nCapacity )
271 /// Deallocates all objects from the pool
272 ~lazy_vyukov_queue_pool()
275 while ( !m_Queue.empty() )
276 a.Delete( m_Queue.pop());
279 /// Allocates an object from pool
281 The pool supports allocation only single object (\p n = 1).
282 If \p n > 1 the behaviour is undefined.
284 If the queue is not empty, the popped value is returned.
285 Otherwise, a new value allocated.
287 value_type * allocate( size_t n )
292 value_type * p = m_Queue.pop();
296 return cxx_allocator().New();
299 /// Deallocated the object \p p
301 The pool supports allocation only single object (\p n = 1).
302 If \p n > 1 the behaviour is undefined.
304 If the queue is not full, \p p is pushed into the queue.
305 Otherwise, \p p is deallocated by allocator provided.
307 void deallocate( value_type * p, size_t n )
313 if ( !m_Queue.push( *p ))
314 cxx_allocator().Delete( p );
320 /// Bounded free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
321 /** @ingroup cds_memory_pool
323 - \p T - the type of object maintaining by free-list
324 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
325 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
329 At construction time, the free-list allocates the array of N items
330 and stores them into the queue, where N is the queue capacity.
331 When allocating the free-list tries to pop an object from
332 internal queue i.e. from preallocated pool. If success the popped object is returned.
333 Otherwise a \p std::bad_alloc exception is raised.
334 So, the pool can contain up to \p N items.
335 When deallocating, the object is pushed into the queue.
336 In debug mode \p deallocate() member function asserts
337 that the pointer is from preallocated pool.
341 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
342 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
343 an accessor functor to this object and use \p pool_allocator as an allocator:
345 #include <cds/memory/vyukov_queue_pool.h>
346 #include <cds/memory/pool_allocator.h>
348 // Pool of Foo object of size 1024.
349 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
351 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
353 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
354 static pool_type thePool;
356 struct pool_accessor {
357 typedef typename pool_type::value_type value_type;
359 pool_type& operator()() const
365 // Declare pool allocator
366 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
368 // Use pool_allocator
369 // Allocate an object
370 Foo * p = pool_allocator().allocate( 1 );
381 pool_allocator().deallocate( p , 1 );
384 template <typename T, typename Traits = vyukov_queue_pool_traits >
385 class bounded_vyukov_queue_pool
388 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
391 typedef T value_type; ///< Value type
392 typedef Traits traits; ///< Pool traits
393 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
397 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
400 value_type * m_pFirst;
401 value_type * m_pLast;
406 void preallocate_pool()
408 m_pFirst = cxx_allocator().NewArray( m_Queue.capacity() );
409 m_pLast = m_pFirst + m_Queue.capacity();
411 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
412 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
415 bool from_pool( value_type * p ) const
417 return m_pFirst <= p && p < m_pLast;
422 /// Preallocates the pool of object
424 \p nCapacity argument is the queue capacity. It should be passed
425 if the queue is based on dynamically-allocated buffer.
426 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
428 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
429 : m_Queue( nCapacity )
434 /// Deallocates the pool.
435 ~bounded_vyukov_queue_pool()
438 cxx_allocator().Delete( m_pFirst, m_Queue.capacity() );
441 /// Allocates an object from pool
443 The pool supports allocation only single object (\p n = 1).
444 If \p n > 1 the behaviour is undefined.
446 If the queue is not empty, the popped value is returned.
447 Otherwise, a \p std::bad_alloc exception is raised.
449 value_type * allocate( size_t n )
454 value_type * p = m_Queue.pop();
456 assert( from_pool(p) );
460 throw std::bad_alloc();
463 /// Deallocated the object \p p
465 The pool supports allocation only single object (\p n = 1).
466 If \p n > 1 the behaviour is undefined.
468 \p should be from preallocated pool.
470 void deallocate( value_type * p, size_t n )
476 assert( from_pool( p ));
483 }} // namespace cds::memory
486 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H