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 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
98 value_type * m_pFirst;
104 void preallocate_pool()
106 m_pFirst = allocator_type().allocate( m_Queue.capacity() );
107 m_pLast = m_pFirst + m_Queue.capacity();
109 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
110 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
113 bool from_pool( value_type * p ) const
115 return m_pFirst <= p && p < m_pLast;
120 /// Preallocates the pool of object
122 \p nCapacity argument is the queue capacity. It should be passed
123 if the queue is based on dynamically-allocated buffer.
124 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
126 vyukov_queue_pool( size_t nCapacity = 0 )
127 : m_Queue( nCapacity )
132 /// Deallocates the pool.
136 allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
139 /// Allocates an object from pool
141 The pool supports allocation only single object (\p n = 1).
142 If \p n > 1 the behaviour is undefined.
144 If the queue is not empty, the popped value is returned.
145 Otherwise, a new value allocated.
147 value_type * allocate( size_t n )
151 value_type * p = m_Queue.pop();
153 assert( from_pool(p) );
157 return allocator_type().allocate( n );
160 /// Deallocated the object \p p
162 The pool supports allocation only single object (\p n = 1).
163 If \p n > 1 the behaviour is undefined.
165 If \p p is from preallocated pool, it pushes into the queue.
166 Otherwise, \p p is deallocated by allocator provided.
168 void deallocate( value_type * p, size_t n )
173 if ( from_pool( p ) )
176 allocator_type().deallocate( p, n );
182 /// Lazy free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
183 /** @ingroup cds_memory_pool
185 - \p T - the type of object maintaining by free-list
186 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
187 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
191 This free-list is very simple.
192 At construction time the pool is empty.
193 When allocating the free-list tries to pop an object from
194 internal queue. If success the popped object is returned.
195 Otherwise a new one is allocated.
196 When deallocating, the free-list tries to push the object into the pool.
197 If internal queue is full, the object is deallocated by using the allocator provided.
198 The pool can manage more than \p N items but only \p N items is placed in the free-list.
202 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
203 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
204 an accessor functor to this object and use \p pool_allocator as an allocator:
206 #include <cds/memory/vyukov_queue_pool.h>
207 #include <cds/memory/pool_allocator.h>
209 // Pool of Foo object of size 1024.
210 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
211 static pool_type thePool( 1024 );
213 struct pool_accessor {
214 typedef typename pool_type::value_type value_type;
216 pool_type& operator()() const
222 // Declare pool allocator
223 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
225 // Use pool_allocator
226 // Allocate an object
227 Foo * p = pool_allocator().allocate( 1 );
238 pool_allocator().deallocate( p , 1 );
242 template <typename T, typename Traits = vyukov_queue_pool_traits>
243 class lazy_vyukov_queue_pool
246 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
249 typedef T value_type ; ///< Value type
250 typedef Traits traits; ///< Pool traits
251 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
259 /// Constructs empty pool
260 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
261 : m_Queue( nCapacity )
264 /// Deallocates all objects from the pool
265 ~lazy_vyukov_queue_pool()
268 while ( !m_Queue.empty() ) {
269 value_type * p = m_Queue.pop();
270 a.deallocate( p, 1 );
274 /// Allocates an object from pool
276 The pool supports allocation only single object (\p n = 1).
277 If \p n > 1 the behaviour is undefined.
279 If the queue is not empty, the popped value is returned.
280 Otherwise, a new value allocated.
282 value_type * allocate( size_t n )
286 value_type * p = m_Queue.pop();
290 return allocator_type().allocate( n );
293 /// Deallocated the object \p p
295 The pool supports allocation only single object (\p n = 1).
296 If \p n > 1 the behaviour is undefined.
298 If the queue is not full, \p p is pushed into the queue.
299 Otherwise, \p p is deallocated by allocator provided.
301 void deallocate( value_type * p, size_t n )
306 if ( !m_Queue.push( *p ))
307 allocator_type().deallocate( p, n );
313 /// Bounded free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
314 /** @ingroup cds_memory_pool
316 - \p T - the type of object maintaining by free-list
317 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
318 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
322 At construction time, the free-list allocates the array of N items
323 and stores them into the queue, where N is the queue capacity.
324 When allocating the free-list tries to pop an object from
325 internal queue i.e. from preallocated pool. If success the popped object is returned.
326 Otherwise a \p std::bad_alloc exception is raised.
327 So, the pool can contain up to \p N items.
328 When deallocating, the object is pushed into the queue.
329 In debug mode \p deallocate() member function asserts
330 that the pointer is from preallocated pool.
334 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
335 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
336 an accessor functor to this object and use \p pool_allocator as an allocator:
338 #include <cds/memory/vyukov_queue_pool.h>
339 #include <cds/memory/pool_allocator.h>
341 // Pool of Foo object of size 1024.
342 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
344 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
346 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
347 static pool_type thePool;
349 struct pool_accessor {
350 typedef typename pool_type::value_type value_type;
352 pool_type& operator()() const
358 // Declare pool allocator
359 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
361 // Use pool_allocator
362 // Allocate an object
363 Foo * p = pool_allocator().allocate( 1 );
374 pool_allocator().deallocate( p , 1 );
377 template <typename T, typename Traits = vyukov_queue_pool_traits >
378 class bounded_vyukov_queue_pool
381 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
384 typedef T value_type; ///< Value type
385 typedef Traits traits; ///< Pool traits
386 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
391 value_type * m_pFirst;
392 value_type * m_pLast;
397 void preallocate_pool()
399 m_pFirst = allocator_type().allocate( m_Queue.capacity() );
400 m_pLast = m_pFirst + m_Queue.capacity();
402 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
403 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
406 bool from_pool( value_type * p ) const
408 return m_pFirst <= p && p < m_pLast;
413 /// Preallocates the pool of object
415 \p nCapacity argument is the queue capacity. It should be passed
416 if the queue is based on dynamically-allocated buffer.
417 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
419 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
420 : m_Queue( nCapacity )
425 /// Deallocates the pool.
426 ~bounded_vyukov_queue_pool()
429 allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
432 /// Allocates an object from pool
434 The pool supports allocation only single object (\p n = 1).
435 If \p n > 1 the behaviour is undefined.
437 If the queue is not empty, the popped value is returned.
438 Otherwise, a \p std::bad_alloc exception is raised.
440 value_type * allocate( size_t n )
445 value_type * p = m_Queue.pop();
447 assert( from_pool(p) );
451 throw std::bad_alloc();
454 /// Deallocated the object \p p
456 The pool supports allocation only single object (\p n = 1).
457 If \p n > 1 the behaviour is undefined.
459 \p should be from preallocated pool.
461 void deallocate( value_type * p, size_t n )
467 assert( from_pool( p ));
474 }} // namespace cds::memory
477 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H